Reasoning Strategies › Decomposition Strategies
Language AI HandbookAll chapters Reasoning Strategies › Decomposition StrategiesOne section · Sections in this chapter5 / 10 ↓
Reading tools Definitions & inline links
Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.
Article links
Make inline references clickable
Least-to-most prompting is one instance of a broader family of decomposition strategies. The unifying theme is that complex reasoning tasks benefit from being broken into simpler components, but there are multiple ways to decompose a problem depending on its structure. Different problem types call for different decomposition styles.
The family includes approaches that decompose by logical dependency (least-to-most), by task type and tool availability (DECOMP), by shifting computation to an interpreter (Program-of-Thought), and by problem scale through recursive application. Each strategy addresses a specific structure in the problems it targets.
Decomposed Prompting (DECOMP)
DECOMP, introduced by Khot et al. (2022), generalizes decomposition by allowing each sub-problem to be handled by a specialized sub-solver. The top-level model decomposes the problem and routes each piece to the appropriate handler.
In DECOMP, the language model is given a set of sub-task "tools" it can invoke:
- A search tool for retrieving facts from a knowledge source
- A QA tool for answering simple factual questions
- An arithmetic tool for numerical computation
- A sort tool for ordering items
The model decomposes the original problem into a sequence of sub-tasks, calling the appropriate tool for each. The results are chained together to produce the final answer.
This approach separates decomposition, which the language model is good at, from execution, which specialized tools are better at. Arithmetic tools make no rounding errors. Search tools retrieve accurate facts from authoritative sources. The language model provides the reasoning glue: understanding the problem, identifying what is needed, calling the right tools, and synthesizing the results. Each component does what it does best.
The DECOMP architecture foreshadows tool-use in modern language model systems, where models call web search APIs, execute code, query databases, and invoke domain-specific functions. The core insight is the same: language models are excellent at understanding, planning, and synthesizing, but unreliable at precise computation and factual recall. Routing those sub-tasks to tools that are reliable by construction allows the overall system to exceed the model's standalone capabilities.
Program-of-Thought and PAL
A particularly effective decomposition strategy offloads computation to an interpreter. Program-of-Thought prompting (PoT) and Program-Aided Language models (PAL), both from 2022, share the same insight: generate a program instead of a prose answer, then execute the program to get the answer.
The language model's role shifts from computation to specification. Rather than computing "How many weeks does a 24-hour task take at 7 hours/day?", the model generates Python code:
# How many weeks does a task requiring 24 hours take at 7 hours/day?
hours_per_week = 7 * 5 # 5-day work week
hours_needed = 24
weeks = hours_needed / hours_per_week
print(f"{weeks:.1f} weeks")0.7 weeks
The interpreter handles arithmetic exactly. The model handles the harder problem of setting up the right calculation: what quantities are needed, how they relate to each other, and how to express those relationships in code.
This decomposition is especially powerful for tasks that mix language understanding with computation, such as math word problems and data analysis. On the MathBench dataset, PAL outperformed standard chain of thought by 15 to 20 percentage points, with the gap widening for problems requiring more computation steps. The more computation a problem requires, the more arithmetic errors accumulate in prose reasoning, and the more the interpreter's exact arithmetic helps.
The generated code also serves a different purpose beyond correctness: it is more interpretable than prose reasoning. A chain of thought answer contains natural language steps that can be ambiguous or hard to verify. A program is precise, executable, and checkable. You can run it, inspect intermediate values, and verify that each step computes the right quantity. This interpretability has practical value in high-stakes applications.
The key architectural distinction is where computation happens. Chain of thought performs all computation inside the language model's forward pass, using token probabilities to simulate arithmetic. Program-of-Thought generates code that is then executed by a Python interpreter, which performs arithmetic exactly. The language model handles natural language understanding and program structure; the interpreter handles the numbers.
Recursive Decomposition
Some problems have recursive structure: solving a complex instance requires solving simpler instances of the same problem type. Recursive decomposition, also called Recursive Reprompting and Revision (Re3) in the literature, applies the same decomposition prompt repeatedly until each piece is simple enough to solve directly.
For long document summarization, for example:
- Split the document into sections
- Summarize each section independently (simple sub-problem)
- Combine section summaries into a document summary (simpler than summarizing the full document directly)
The key advantage is that each sub-problem fits comfortably within the model's effective reasoning window, even when the original problem does not. A model with a 4,000-token context can summarize a 40,000-token document by summarizing 10 sections of 4,000 tokens each, then combining the 10 short summaries into a final summary. Each step is within the model's capability even though the original task exceeds it.
The recursive structure also generalizes naturally. If 4,000-token sections are still too long, split them further. The recursion terminates when each piece is small enough to process directly. This hierarchical approach applies beyond summarization: hierarchical question answering, multi-document analysis, long-form reasoning chains, and systematic review all benefit from the same structure.
# Demonstrate recursive decomposition for document summarization
# Compare accuracy of direct vs decomposed summarization as document length grows
def simulate_summarization_quality(n_sections, direct=False, seed=42):
"""
Simulate summarization quality as a function of document length.
Direct: single pass over full document (quality degrades with length)
Decomposed: summarize each section, then combine (quality stays higher)
"""
rng = np.random.default_rng(seed)
if direct:
# Quality degrades as document gets longer (context overload)
base_quality = 0.90
decay_per_section = 0.07
quality = max(0.2, base_quality - n_sections * decay_per_section)
noise = rng.normal(0, 0.02)
return min(1.0, max(0.0, quality + noise))
else:
# Each section is summarized at full quality, combination is easy
section_quality = 0.88
combination_penalty = 0.03
quality = section_quality - combination_penalty
noise = rng.normal(0, 0.02)
return min(1.0, max(0.0, quality + noise))
section_counts = list(range(1, 11))
n_trials = 500
direct_quality = {
n: np.mean(
[
simulate_summarization_quality(n, direct=True, seed=i)
for i in range(n_trials)
]
)
for n in section_counts
}
decomposed_quality = {
n: np.mean(
[
simulate_summarization_quality(n, direct=False, seed=i)
for i in range(n_trials)
]
)
for n in section_counts
}
Interleaving Reasoning and Retrieval
A related decomposition strategy interleaves reasoning with information retrieval. Standard chain of thought requires the model to rely entirely on parametric knowledge: what it learned during training. When problems require specific facts the model may not know reliably, or facts that change over time, this reliance on parametric knowledge creates errors. The model hallucinates specific details with confident-sounding prose, and without retrieval there is no mechanism to catch these errors.
Interleaved retrieval-augmented generation, referred to as IRCoT and related systems in the literature, decomposes the solving process into alternating steps:
- Generate the next reasoning step based on what is currently known
- Identify what fact is needed to continue
- Retrieve that fact from an external source (a search engine, a knowledge base, or a document collection)
- Continue reasoning with the retrieved fact appended to the context
Each retrieval is a sub-problem with a precisely defined form: what piece of information is needed at this step? This decomposition prevents the model from hallucinating facts while still using its language understanding for the non-factual reasoning steps. The language model handles the reasoning structure; the retrieval system handles the factual content. The combination outperforms either component alone on knowledge-intensive multi-hop reasoning tasks.
The interleaving structure also makes the system's reasoning process more auditable. You can see exactly which facts were retrieved, when they were retrieved, and how they influenced subsequent reasoning steps. This transparency is valuable in applications where users need to verify that reasoning is grounded in reliable sources.