Decomposed prompting (DECOMP): a complete guide

Big prompts fail in a frustrating way: the model can do every individual step, but stitching them together in one pass falls apart. Decomposed Prompting (DECOMP) fixes that by treating prompting like programming. A decomposer LLM breaks the task into a "prompting program"—a sequence of typed calls to a library of small, specialized sub-task handlers. In the original paper (Khot et al., 2022, ICLR 2023, arXiv:2210.02406, from AI2 and the University of Washington), this beat Chain-of-Thought by 14-17 percentage points on math reasoning and held near-100% accuracy on symbolic tasks where CoT degraded with length.

See it work

Here's a math word problem solved two ways. Watch where the monolithic version slips.

Task: A bakery makes 12 batches of cookies with 24 per batch.
They sell 3/4 of them. How many cookies remain?

# Monolithic CoT (one call, does its own arithmetic)
"12 x 24 = 288. 3/4 of 288 = 215. So 73 remain."     <- arithmetic slip

# DECOMP (decomposer emits a program; handlers run each step)
total     = multiply(12, 24)              # symbolic -> 288
fraction  = simplify_fraction("3/4")      # LLM      -> 0.75
sold      = multiply_fraction(288, 0.75)  # symbolic -> 216
remaining = subtract(288, 216)            # symbolic -> 72
answer    = remaining                      # -> 72 cookies remain

Same logic, same steps. The difference is that DECOMP hands the arithmetic to a Python function instead of trusting the model to multiply in its head. That single move removes an entire class of errors. The decomposer never has to be right about 288 x 0.75—it just has to know that step belongs to multiply_fraction.

The mental model

Think of a senior engineer who doesn't write the whole feature themselves. They split the work into tickets, hand each to the right specialist, and wire the results together. Some tickets go to a teammate (an LLM handler), some to a script (a symbolic function), some to a service (a trained model). The manager's only job is a good breakdown.

DECOMP optimizes how you structure a program of prompts, not what you cram into one prompt.

Standard prompting asks one model to be a generalist. DECOMP lets it be a planner that delegates to specialists—and specialists, it turns out, are easier to teach than a generalist juggling five things at once.

How it works

1. Decompose. The decomposer gets the task plus the signatures of available functions, then emits a prompting program—a directed acyclic graph where nodes are sub-tasks and edges are data flow. Few-shot examples (3-7 work best) teach it the decomposition style.
2. Parse and validate. Convert the program into an executable structure. Check that every referenced function exists and dependencies resolve. Build the DAG so independent steps can run in parallel.
3. Execute in topological order. For each step, gather inputs from prerequisite steps, invoke the handler—an LLM call, a symbolic Python function, or a model inference—and store the result. Retry or fall back on failure.
4. Aggregate. Collect the final outputs, format the answer, and (optionally) run a validation handler that sanity-checks consistency before returning.

It's multi-stage by design: decompose, then execute, with an optional verification pass. Within a stage, steps run sequentially, in parallel, or recursively, and a step can spawn further decomposition.

The canonical loop is small. The decomposer plans; the controller runs the plan.

# 1) Decomposer: complex task -> prompting program (a list of typed calls)
program = decompose(task, function_library)    # few-shot LLM call

# 2) Controller: run the program in dependency order
context = {"input": task}
for step in topological_sort(program):
    handler = handlers[step.function]           # LLM, symbolic, or trained
    args    = resolve(step.inputs, context)     # pull in prior outputs
    context[step.output_var] = handler(args)    # retry / fallback on failure

answer = context["answer"]

Why it works

The gains come from a few interacting mechanisms—cognitive load theory (Sweller, 1988) is the backbone. Ranked by how much they contribute (approximate, and task-dependent):

The error math explains the payoff. In a 5-step problem where each step is 90% accurate, a monolithic chain lands at 0.9^5 = 59%. Push each step to 95% and you get 0.95^5 = 77%. Make the critical steps symbolic (100%) and overall accuracy can clear 90%. Recursion adds a qualitative win: by shrinking the problem at each level (reverse a string by reversing halves), sub-problems stay inside the model's comfortable range, so accuracy holds as input length grows instead of degrading.

Where it shines

DECOMP earns its overhead on tasks that are genuinely composite:

• Mathematical reasoning. +14 points on GSM8K and +17 points on MultiArith over CoT, largely by routing arithmetic to symbolic functions.
• Symbolic manipulation. On letter concatenation with 12 words, Least-to-Most hit 74% and CoT 34%; DECOMP beat both using the same logic, because separate prompts teach a hard sub-task better than one embedded prompt. On sequence reversal it stayed near 100% as length grew while CoT-style approaches degraded.
• Multi-hop QA. On CommaQA it beat CoT across every decomposition granularity and evaluation split. On open-domain QA, Decomp-Ctxt models significantly outperformed no-retrieval and strong retrieval baselines (the exception: comparable to baseline with Codex on HotpotQA).
• Multilingual NLP. A 2024 extension (arXiv:2402.18397) applied DECOMP to part-of-speech tagging across 38 languages with 3 English-centric and 2 multilingual LLMs, beating iterative prompting in both zero-shot and few-shot settings on accuracy and efficiency.
• Long-document and multi-source work. Hierarchical decomposition processes inputs beyond the context window; parallel retrieval plus per-source extraction plus synthesis handles multi-source questions.

Domain teams reach for it whenever some steps are deterministic. Financial analysis runs ratios through symbolic code; clinical pipelines validate ICD-10/CPT codes with a function for 100% format compliance; code generation runs the test suite as a symbolic handler so generated code is actually checked.

When to use it (and when not)

Reach for DECOMP when: the task needs at least 3 distinct reasoning steps, baseline prompting sits below about 80% accuracy with errors that localize to specific steps, sub-task boundaries are clear, or some operations are deterministic and beg to be symbolic. It also wins when inputs approach the context limit or when auditability matters—the modular trace shows exactly how the answer was derived.

Skip it when: the task is single-step, the baseline already clears 95%, you need a response in under 2 seconds, your token budget can't absorb multiple calls (cost must stay under $0.10 per task), or the work is genuinely holistic—"is this design beautiful?" loses its essence when you cut it apart. For exploratory tasks where you can't predetermine the breakdown, ReAct-style agents fit better.

Model fit. The decomposer is the highest-leverage component, so give it your best model: GPT-4, Claude 3.5 Sonnet, or stronger (minimum GPT-3.5-turbo / Claude 3 Haiku with careful prompting). Critical handlers want GPT-4-level reasoning; simple extraction and classification handlers can ride cheaper, faster models (GPT-3.5-turbo at $0.002/1K input is about 15x cheaper than GPT-4); deterministic steps need no model at all. Models below 7B parameters generally can't decompose reliably, and you want at least an 8K-token context to hold the function library plus examples plus task.

Escalation thresholds. Move to fine-tuning above 50,000 requests or when latency must drop under 1 second. Move to ReAct/agents when a fixed decomposition keeps producing poor plans. Add human-in-the-loop when DECOMP stays below 90% on high-stakes work. De-escalate to plain prompting when DECOMP beats the baseline by less than 5%—the complexity isn't worth it.

DECOMP itself comes in flavors: Sequential (linear dependencies), Parallel (independent sub-tasks, lower latency), Recursive (self-similar problems, length generalization), Conditional (strategy depends on input type), Iterative refinement (quality loops with evaluable output), and Hybrid symbolic-neural (mix deterministic code with LLM steps).

Structure and components

Four components are required, two are optional:

1. Decomposer prompt — task description, available function signatures, 3-7 decomposition examples, strategy instructions, and a strict output format (pseudocode or JSON).
2. Function library — typically 5-20 handlers, each with an unambiguous signature, description, and I/O spec. Each is tagged llm, symbolic, or trained_model.
3. Sub-task handlers — LLM prompts (3-5 examples each), pure Python functions, or fine-tuned models. They're interchangeable behind the same call interface.
4. Execution controller — parses the program, builds the dependency DAG, runs steps in topological order (parallel where possible), handles retries, and aggregates results.

Optional but recommended: a validation handler (sanity-checks answers, mandatory for high-stakes domains) and a meta-learner/optimizer (tunes decomposition strategy from execution traces, worth it for long-lived production systems).

Design principles keep it healthy: decompose to the simplest meaningful sub-tasks (Miller's 7±2 suggests 3-7 per level), define clear typed interfaces, keep each handler single-purpose, substitute symbolic code for anything deterministic, and start coarse—only split a sub-task further when it shows a high error rate.

The signature wins: hybrid and recursive handlers

Two handler patterns carry most of DECOMP's advantage. Replacing error-prone steps with deterministic code gives perfect accuracy at near-zero cost, and recursive shrinking gives length generalization.

# Hybrid: deterministic steps become code -> 100% accurate, negligible cost
def multiply(a, b):                 # replaces an LLM "calculation" that slips
    return a * b

# Recursive: shrink the input so each call stays easy -> length generalization
def reverse_string(s):
    if len(s) <= 2:
        return s[::-1]              # base case
    mid = len(s) // 2
    return reverse_string(s[mid:]) + reverse_string(s[:mid])

Implementation

A moderately complex system (multi-hop QA, say) takes roughly 20-32 hours end to end; budget 15-65 hours for richer ones. The workflow:

1. Analyze the task (1-2h). Collect 10-20 examples, solve a few by hand, note the common sub-tasks and which ones are deterministic.
2. Design the function library (2-3h). Name functions descriptively, specify typed I/O, mark symbolic candidates.
3. Implement symbolic functions first (2-3h). They're the fastest, cheapest, most reliable parts—unit-test them.
4. Build the decomposer (2-3h). Include the library, 5-7 diverse examples, and a strict output format. Spend 30-40% of total effort here; it has the highest leverage.
5. Build handlers (~20-30 min each). Specialized instructions plus 3-5 examples, tested in isolation on 20+ cases.
6. Build the controller, integrate, test (several hours). Then optimize: parallelize independent steps, swap cheap models into simple handlers, add caching.
7. Validate and deploy. Compare against the CoT/few-shot baseline on a 50-100 example holdout, then roll out to 10-20% of traffic before going wide.

Use a single platform example rather than wiring up every SDK. Here's the decomposer call with Claude, which handles XML structure reliably:

import anthropic
client = anthropic.Anthropic(api_key="...")

def decompose_with_claude(task, library_desc):
    prompt = f"""Break this task into sub-tasks using the available functions.
Functions:
{library_desc}
Task: {task}
Return XML: <decomposition><step id="1"><function>name</function>
<inputs><input key="p">value or $var</input></inputs>
<output_var>v1</output_var></step> ...</decomposition>"""
    msg = client.messages.create(
        model="claude-sonnet-4-6",
        max_tokens=2000,
        temperature=0.3,            # low for consistent decompositions
        messages=[{"role": "user", "content": prompt}],
    )
    return parse_xml(msg.content[0].text)

The same shape works on OpenAI (JSON mode plus gpt-4-turbo for the decomposer, gpt-3.5-turbo for cheap handlers), LangChain (LCEL chains), and DSPy (signatures it can auto-optimize). LlamaIndex even ships a SubQuestionQueryEngine that decomposes out of the box.

Configuration that matters:

Token budget runs ~2,000-4,000 for the decomposer call and 500-2,000 per handler, totaling roughly 5,000-20,000 per task. Latency is decomposer plus the sum of handler latencies when sequential, or decomposer plus the slowest handler when parallel; symbolic functions add under 100ms.

Do: use symbolic functions liberally, invest in the decomposer, test handlers independently, design typed interfaces, start with a 5-7 function library and grow only as needed.

Don't: use an LLM for arithmetic, sorting, or exact matching; over-decompose into 15 steps when 6 suffice (that alone can cut latency 40% and cost 30%); ship generic handler prompts (specific ones improve accuracy 20-30%); skip the baseline comparison; or treat every handler as equally critical.

Debugging by symptom

• Inconsistent outputs → lower temperature, or move the step to a symbolic function if it should be deterministic.
• Misinterpretation → add 2-3 decomposer examples like the failing case; clarify ambiguous function descriptions.
• Format violations → enforce structured output (JSON mode, XML tags), add a symbolic format validator, or upgrade a too-weak handler.
• Poor quality despite tuning → measure each handler in isolation to find the weak link; pass more context between steps; if DECOMP beats the baseline by less than 5%, the task may resist decomposition.
• Hallucinations → add a retrieval handler before reasoning, lower temperature, and let handlers answer "Unknown" instead of guessing.
• Slow or expensive → parallelize independent steps, push cheap models into simple handlers, coarsen the decomposition, and cache.

Testing

Validate on a 20-30% holdout never used in development (use 5-fold cross-validation under 100 examples), and stress it with adversarial cases: empty inputs, very long inputs, ambiguous wording. A healthy suite is roughly 50-60% happy path, 20-30% edge cases, and 10-15% adversarial. Track task-specific metrics (exact match, F1, BLEU, ROUGE) plus consistency (target above 95% on factual tasks, above 80% on creative), robustness (under 10% accuracy drop on paraphrases), and the P50/P95/P99 latency distribution. Aim for above 99% availability and under 1% error rate in production.

To prove it's worth the cost, run DECOMP and the baseline on the same set and check the gain clears the 3-5x cost.

# Prove it beats the baseline on the same held-out set
gain_base = gain_deco = 0
for ex in heldout:                       # 100+ diverse examples
    gain_base += exact_match(run_cot(ex.task),    ex.gold)
    gain_deco += exact_match(run_decomp(ex.task), ex.gold)
# accept DECOMP only if the gain is significant (paired t-test, alpha = 0.05)
# and large enough to justify its extra cost

For randomness, test 100+ cases with 3-5 runs each and use paired tests or bootstrap confidence intervals (1000 resamples). Cohen's d frames practical significance (small 0.2, medium 0.5, large 0.8)—a statistically significant but tiny effect may not be worth shipping. Self-consistency (vote across 3-5 decompositions) buys 5-15% on reasoning tasks at 3-5x the cost; reserve it for critical handlers.

Limitations

Some limits are fundamental. Not every task decomposes—holistic aesthetic judgments lose their essence when split. The decomposer is a hard ceiling: nothing downstream can exceed its plan quality. Multiple calls carry an unavoidable latency and cost floor (3-5x a single prompt). Splitting at boundaries loses holistic context, so document tone is harder to read in chunks. And errors still compound: five 95%-accurate steps multiply to 77.4%, so early-step accuracy is precious (DECOMP mitigates this with isolation and symbolic substitution, but the math doesn't disappear).

DECOMP is also a poor fit for simple tasks (overhead exceeds benefit), real-time work under 2 seconds, high-frequency low-value tasks at massive scale (fine-tune instead), and exploratory problems with unknown structure (use agents). Under stress, watch for an out-of-domain decomposer that produces plausible-but-useless plans, handlers fed unexpected formats failing silently, context overruns, and API rate limits causing partial execution—mitigate with input validation, format checks, hierarchical decomposition, and backoff. When things break, degrade gracefully: try DECOMP, then a simpler decomposition, then a monolithic prompt, then an honest error; return partial results when some handlers succeed.

Advanced techniques

Keep handler instructions explicit and imperative ("Extract all numbers" beats "you might consider extracting numbers"), define key terms, specify edge-case handling, and let examples do the disambiguating—3-5 diverse, correct examples outperform long prose, with diminishing returns past 7. For long inputs, chunk with overlap and process hierarchically (map-reduce), or pass references and metadata instead of full content; tools like LLMLingua can compress static context 50%+. Build self-correction into critical handlers (generate, critique, revise) and ask for explicit confidence so low-confidence outputs route to a stronger model or a human. Match the model to the model's quirks: Claude is excellent with XML tags, GPT with function calling; pin model versions (gpt-4-turbo-2024-04-09) and regression-test before upgrading.

Risk and ethics

DECOMP also adds an opacity layer—users don't see how their task was split—so offer an explanation mode that surfaces the decomposition and sub-task results, and log decompositions for auditing. On the security side, the structure invites prompt injection (a benign-looking input that exploits a downstream handler) and adversarial chaining; defend with input sanitization, a strict system-over-user instruction hierarchy, output validation for leaked prompts, anomaly detection on unusual decomposition patterns, and red-teaming.

Ecosystem and combinations

DECOMP composes well with neighbors. DECOMP + RAG lets decomposition target retrieval (you know exactly what to fetch). DECOMP + fine-tuning fine-tunes only the high-value handlers while keeping the decomposer as a prompt. DECOMP + self-consistency votes across multiple decompositions for reliability. DECOMP + tool use turns calculators, databases, and APIs into handlers. It generalizes Least-to-Most (Zhou et al., 2022, which is just linear sequential DECOMP) and shares PAL's hybrid symbolic-neural spirit (Gao et al., 2022), while differing from ReAct (Yao et al., 2022), which interleaves reasoning and acting dynamically rather than planning upfront. Self-Ask (Press et al., 2022) decomposes via self-generated follow-up questions in a similar spirit.

Frameworks that support it: LangChain (LCEL chains), DSPy (auto-optimizes prompt chains), Haystack (pipeline-native), LlamaIndex (SubQuestionQueryEngine), and Microsoft's Semantic Kernel (planner plus plugins). The original research code lives at allenai/decomp, with an open-domain QA variant at HarshTrivedi/DecomP-ODQA. To migrate from a monolithic prompt: find the natural step boundaries ("first... then... finally..."), extract one step into a dedicated handler, test it, then expand and finally add the decomposer.

Future directions

The active frontiers: learned decomposition (training models to decompose rather than few-shotting it, projected 10-20% accuracy gains), universal handler libraries (npm-style reuse, ~10x faster deployment for new tasks), dynamic adaptive decomposition (adjusting the plan from intermediate results, ~15-25% on ambiguous tasks), hierarchical multi-level decomposition, and tighter neurosymbolic integration with formal verification for provably correct systems.

Summary

• DECOMP turns a hard task into a prompting program: a decomposer LLM plans typed sub-task calls, and a controller runs them in dependency order across LLM, symbolic, and trained-model handlers.
• The headline result: +14 (GSM8K) and +17 (MultiArith) points over CoT, near-100% on symbolic length generalization, and consistent multi-hop QA gains (CommaQA, open-domain), plus a 38-language POS extension.
• The biggest lever is the decomposer (35-40% of the effect), followed by cognitive-load reduction; the signature trick is routing deterministic steps to symbolic code for 100% accuracy.
• Reach for it on tasks with 3+ steps, clear boundaries, and a sub-95% baseline; skip it for simple, real-time, or holistic tasks—it costs 3-5x a single prompt for a 15-25% accuracy gain.
• Build it in ~20-32 hours, spend 30-40% of that on the decomposer, test handlers in isolation, and always compare against the baseline before shipping.