Decomposed Prompting: A Modular Approach for Solving Complex Tasks

In plain words

Few-shot prompting shows a language model a handful of solved examples and hopes it copies the pattern. That works for simple tasks, but it gets shaky when a task has many steps or when one step is hard to learn from examples.

The idea here is to split the job the way a program is split. A "decomposer" prompt writes a short script: it names the sub-tasks needed and the question to ask for each. Each sub-task is then handled by its own piece, which can be another prompt with its own examples, a smaller script, an ordinary function, or a search tool. A controller runs the script step by step and feeds each answer back to the decomposer. Because every piece has its own examples, one part can be fixed or replaced without touching the others.

The same structure can also call itself on smaller inputs, which lets a model handle inputs longer than its examples. The method uses only prompts, with no supervised training data.

TL;DR

Decomposed Prompting (DecomP) replaces one long few-shot prompt with a decomposer prompt that writes a program of sub-questions. Each sub-question goes to its own few-shot prompt, a symbolic function, or a recursive call of the same procedure §3 §3.3. A controller runs the program and returns the answer of the last step §3.2 fig. 3. The authors report gains over chain-of-thought (CoT) on their case studies, and on GSM8K and MultiArith a CoT answer-extraction sub-task raises the reported scores from 36 to 50.6 and from 78 to 95 §4.5 app. B; the metric is not stated. The official code is Apache-2.0 and holds the prompts and controller; the retrieval code for open-domain QA is not in that repository.

Problem

Few-shot prompting is a strong way to use LLMs, but it struggles as task complexity grows, or when the individual reasoning steps are hard to learn, especially when they sit inside a more complex task [abstract] §1. Chain-of-thought prompts show every step, but a few demonstrations of a complex task are not enough for current models to learn all the steps. For example, a few demonstrations are not enough for GPT-3 to learn to extract the k-th letter of a word §1.

Retrieval for knowledge-intensive tasks is also unclear: the paper asks whether it can be done with few-shot prompts at all §1. Earlier decomposition methods such as least-to-most prompting and successive prompting produce a linear sequence of sub-questions, and least-to-most requires the LLM to answer the complete question at the end §2.

The method assumes LLMs that can follow few-shot prompts and produce structured outputs. The paper's case studies use GPT-3 models §4 §4.4.

Method

Formulation §3. A standard few-shot example is a query and its answer. A CoT example adds intermediate reasoning steps §3. DecomP instead writes a prompting program, a sequence of steps, each naming a sub-task function and a sub-query. The last answer in the program is the final answer §3.

P = \big((f_1, Q_1, A_1), \dots, (f_k, Q_k, A_k)\big) \qquad A_k = \text{final answer} §3

Each sub-task function f \in \mathcal{F} is implemented as an in-context prompt (CoT-style, or another decomposed prompt), or as any symbolic or learned function such as a calculator or a supervised model §3.

Decomposer and sub-task prompts §3.1 fig. 2. The paper's example task is to concatenate the first letter of each word in a string. The decomposer example uses three functions: split (split a string into words), str_pos (find character positions) and merge (concatenate characters) §3.1 fig. 2. Each sub-task prompt is written independently of the complex task and can carry its own examples §3.1.

The decomposer prompt may refer to earlier answers as #1, #2, and so on. It also uses a control operator foreach, which runs one sub-query per item of a list. The paper notes that foreach is not strictly needed, since each query could be written out, but it reduces manual effort and decomposition errors §3.1. Two operators from prior work are used: select (the default) and project_values (called foreach in the text), plus project_values_flat_unique (called foreach_merge in the text) app. G.

Execution §3.2 fig. 3. A controller runs the decomposer as follows.

1. The decomposer receives the query and all earlier sub-questions and answers, and writes the next sub-question together with its sub-task name.
2. The controller routes the sub-question to that sub-task's handler. The answer is added to the history, and the history goes back to the decomposer for the next call.
3. When the decomposer writes the end marker [EOQ], the previous answer is returned as the final prediction.

For foreach, one sub-question becomes several calls, and the answers are combined into an array §3.2 fig. 3. The intended prediction is the most likely answer, \hat{A} = \arg\max_A p(A \mid D, Q, \theta), approximated with greedy search §3.2.

# Controller loop for Decomposed Prompting  [§3.2] [fig. 3]
# Input:  query; decomposer prompt; handlers, keyed by sub-task name
# Output: final answer

def decomposed_answer(query, decomposer_prompt, handlers):
    # Earlier (sub-question, answer) pairs; empty at the start  [§3.2]
    history = []
    # Decomposer writes the next sub-task name and sub-question  [§3.2]
    step = decomposer(decomposer_prompt, query, history)
    while step.name != "[EOQ]":
        # Route to the handler; #1, #2 refer to earlier answers  [§3.1]
        answer = handlers[step.name](step.sub_query, history)
        # The next decomposer call sees this pair  [§3.2]
        history.append((step.sub_query, answer))
        step = decomposer(decomposer_prompt, query, history)
    # The last answer is the prediction  [§3.2]
    return history[-1][1]

The names and signatures above are illustrative, not the paper's. The paper's text gives no step cap; see Pitfalls.

Hierarchical decomposition §3.3 fig. 4. A sub-task that fails even with many examples can be split again. The paper's k-th letter example splits the word into letters with positions, reusing the split prompt, and then selects the k-th item with an arr_pos prompt §3.3 fig. 4.

Recursive decomposition §3.3 fig. 5 alg. 1. The decomposer can call itself on smaller inputs of the same kind. For list reversal, a list is split into halves, each half is reversed by the same procedure, and the reversed halves are joined in reverse order. Recursion stops at a base case where CoT is accurate, which the figure shows as lists of length 3 §3.3 fig. 5. Algorithm 1 gives the procedure; its base case is fewer than 4 items alg. 1 app. G.2.

# Recursive list reversal by halving  [alg. 1] [app. G.2]
# Input:  sequence (a list of items)
# Output: the same items in reverse order

def split_reverse(sequence):
    # Base case: fewer than 4 items; a CoT prompt reverses them  [alg. 1]
    if len(sequence) < 4:
        return reverse_directly(sequence)
    # Half the length, rounded down; alg. 1 writes |x| / 2 without rounding
    # [code: configs/prompts/reverse/decomp.txt#L2]
    half = len(sequence) // 2
    first_half = sequence[:half]
    second_half = sequence[half:]
    # Reverse each half with the same procedure  [alg. 1]
    first_reversed = split_reverse(first_half)
    second_reversed = split_reverse(second_half)
    # The reversed second half comes first  [alg. 1]
    # [code: configs/prompts/reverse/decomp.txt#L14-L15]
    return second_reversed + first_reversed

External API calls §3.3 fig. 6. A sub-task can be a retrieval system instead of an LLM. The paper uses an Elasticsearch index: the retrieval handler returns both an answer and the documents, so later sub-questions can use the answer and a reading model can use the documents §3.3 §4.4 fig. 6 fig. 11.

Training. No LLM is trained. Every component is a few-shot prompt or a fixed function §2 §3.

Hyperparameters

Values are for the paper's experiments. Anything not listed is "not stated".

Results

Author-reported. The paper has no tables; results are in figures and in text. Numbers are given only where the text states them. For the others, see the figure.

The GSM8K and MultiArith rows use a decomposition in which CoT is generated first and a GPT-3 sub-module extracts the answer §4.5 app. B. The text does not name the LLM used for this result.

Paper vs code

Code paths are relative to the repository root at code_commit.

• Half length in reversal. Algorithm 1 writes the split point as n = |x|/2, with no rounding alg. 1. The released prompt floors it: "Half of 5 is 5 / 2 = 2.5. Dropping the decimal" decomp.txt. The card's pseudocode follows the code.
• Base case. Both agree: Algorithm 1 uses fewer than 4 items as the base case alg. 1, and the released prompt splits only lists of 4 or more ("the minimum length of 4") decomp.txt.
• Recombination. Algorithm 1's return line indexes r^R_1..r^R_n and ℓ^R_{n+1}..ℓ^R_{|x|} alg. 1. The released example joins the reversed second half first, then the reversed first half decomp.txt.
• Decoding. The paper says greedy search §3.2. The code sets temperature 0 by default gpt3generator.py and caches temperature-0 OpenAI calls on disk gpt3generator.py gpt3generator.py.
• Decomposition cap. The paper gives no step cap. The code's question generator defaults to 10 steps and forces the end marker at the cap participant_qgen.py participant_qgen.py.
• CoT answer extraction. The appendix shows the letter-concatenation CoT extractor as .* outputs "(.*)"\. app. G. The released config is .* outputs (.*)\. with no quotes cot_letter_cat_greedy_search.jsonnet. The extractor returns the capture group unchanged participant_util.py. So the captured answer keeps its quote marks unless something later removes them; I did not check the scorer.
• Single-step CoT. The released CoT configs set max_steps: 1 cot.jsonnet, so they run as one decomposition step followed by extraction.
• Not in this repository. The open-domain QA code (retrieval handler, Elasticsearch corpora and prompts for that setting) and the math QA configuration are not in this repository. The README points open-domain QA to a separate repository, HarshTrivedi/DecomP-ODQA README.md. I did not read it, so the open-domain QA details above rest on the paper alone.

I checked the letter-concatenation and reversal configs against the paper's controller, end marker and default engine gpt3generator.py and found no further discrepancy. I did not check every prompt file.

Pitfalls

• Inconsistent example. The §3.1 example says to concatenate the first letter of each word, then in its second step says "extract the third letter" §3.1. The experiments use a position k=3 §4.1. Implement from the prompts, not the example.
• Algorithm 1 is not directly runnable. It needs a rounding rule (the code floors) and a corrected return line (see Paper vs code). Its base case is fewer than 4 items, so a 3-item list is reversed by the base prompt alg. 1 fig. 5.
• Greedy and deterministic. The paper's decomposition is greedy §3.2. Sampling would change the program, which the paper does not evaluate.
• Cost grows per step. Each decomposition step sends the full decomposer prompt plus the whole history again §3.2 participant_qgen.py. The paper notes that unrolling a decomposition into one long CoT "becomes too long and convoluted" §4.2.
• Context limits. GPT-3's 2049-token context forced a smaller CommaQA dataset and shorter prompts for smaller models §4.3 app. C.
• Model choice matters. Only GPT-3-sized models were reliably able to produce the required structured output, so the decomposer cannot simply be a small model §4.4.
• Retrieval corpus leaks test paragraphs. The 2WikiMultihopQA and MuSiQue open-domain corpora combine paragraphs from train, dev and test questions app. A.1. The paper's open-domain numbers therefore reflect that setup, not a corpus built from the evaluation questions alone.
• Small samples. Math results use 300 and 200 examples app. B. The 14 and 17 point gains come from a single extraction change on those samples app. B.
• Significance is not reported. Figure 12 uses the word "significantly". The text reports no significance test.
• Figures only. Most results appear only in figures. The card gives the numbers the text states and otherwise describes the figure. Figure numbers were counted from the LaTeX source, not the PDF; check them against the PDF before citing.
• No numbered equations. The paper has no numbered equations, so equations are cited by section.
• Error analysis. On letter concatenation the paper found errors only in sub-task execution, such as a wrong letter pulled from a position list, and not in the decomposition app. F.

Lineage

• Builds on: chain-of-thought prompting (Wei et al. 2022, cited in the paper as Wei2022ChainOT), which the paper uses both as baseline and inside its sub-tasks §1 §4.
• Related: least-to-most prompting (Zhou et al. 2022) and successive prompting, both with fixed sequences §2; Text Modular Networks (Khot et al. 2021), which trained a next-question generator and so needed supervised data §2.
• Operators from Khot et al. 2022 (CommaQA) are reused app. G.
• Compared against: CoT and least-to-most on symbolic tasks §4.1 §4.2; No-Ctxt and NoDecomp-Ctxt on open-domain QA §4.4.
• Superseded by: none known from this wiki.