PaperlayerView exact revision on arXiv

Source-linked AI summary

Decomposed Prompting: A Modular Approach for Solving Complex Tasks

Tushar Khot, Harsh Trivedi, Matthew Finlayson, Yao Fu, Kyle Richardson, Peter Clark, Ashish Sabharwal

arXiv:2210.02406v2cs.CL

TL;DR

Few-shot prompting struggles when complex tasks require many or difficult reasoning steps. Decomposed Prompting delegates simpler sub-tasks to separately prompted handlers, and outperforms prior work across four tasks and generalization settings.

  • Problem

    Few-shot demonstrations become insufficient as tasks require more numerous or difficult reasoning steps.

  • Method

    Decomposed Prompting builds a prompting program that delegates simpler sub-tasks to separately prompted LLMs or symbolic and learned functions.

  • Results

    Decomposed Prompting outperforms prior work across four tasks and generalization settings, with separate prompts improving performance on difficult sub-tasks.

  • Takeaways & Limitations

    Decomposed Prompting is an effective few-shot paradigm for solving complex tasks through modular, independently optimized sub-tasks.

  • Takeaways & Limitations

    The decomposer uses GPT3-sized models because smaller models do not reliably produce the required structured outputs.

Abstract

from arXiv · show

Few-shot prompting is a surprisingly powerful way to use Large Language Models (LLMs) to solve various tasks. However, this approach struggles as the task complexity increases or when the individual reasoning steps of the task themselves are hard to learn, especially when embedded in more complex tasks. To address this, we propose Decomposed Prompting, a new approach to solve complex tasks by decomposing them (via prompting) into simpler sub-tasks that can be delegated to a library of prompting-based LLMs dedicated to these sub-tasks. This modular structure allows each prompt to be optimized for its specific sub-task, further decomposed if necessary, and even easily replaced with more effective prompts, trained models, or symbolic functions if desired. We show that the flexibility and modularity of Decomposed Prompting allows it to outperform prior work on few-shot prompting using GPT3. On symbolic reasoning tasks, we can further decompose sub-tasks that are hard for LLMs into even simpler solvable sub-tasks. When the complexity comes from the input length, we can recursively decompose the task into the same task but with smaller inputs. We also evaluate our approach on textual multi-step reasoning tasks: on long-context multi-hop QA task, we can more effectively teach the sub-tasks via our separate sub-tasks prompts; and on open-domain multi-hop QA, we can incorporate a symbolic information retrieval within our decomposition framework, leading to improved performance on both tasks. Datasets, Code and Prompts available at https://github.com/allenai/DecomP.

1 INTRODUCTION

Decomposed Prompting (DECOMP) addresses the difficulty of solving complex tasks by delegating simpler sub-tasks to separately prompted, task-specific handlers. Its modular design supports richer sub-task supervision, recursive decomposition, reuse across tasks, and isolated debugging or replacement.

  • 1 INTRODUCTION: DECOMP decomposes complex tasks into simpler sub-tasks handled by sub-task-specific LLMs, while separately prompting the decomposer and each handler.The decomposer specifies a sequence of sub-tasks, and each sub-task is delegated to its corresponding handler.
  • 1 INTRODUCTION: Unlike few-shot and Chain-of-Thought prompting, DECOMP describes a procedure using sub-tasks rather than directly providing complete reasoning steps for the complex task.Few-shot prompting supplies examples, while Chain-of-Thought prompting describes reasoning steps leading to each answer.
  • 1 INTRODUCTION: DECOMP treats the decomposer as a top-level program and handlers as modular, debuggable, upgradable implementations of simpler functions.A poorly performing handler can be debugged independently or replaced with an alternative prompt, trained model, or symbolic function.
  • 1 INTRODUCTION: Handlers can receive richer examples than the complex-task prompt, be recursively decomposed when necessary, and be shared across multiple tasks.These properties allow simpler sub-tasks to be taught independently and reused as components of other task solutions.
  • 1 INTRODUCTION: The authors evaluate DECOMP against prior work on eight challenging datasets using GPT3 models to test whether factoring out sub-tasks improves complex-task solving.The introduction highlights tasks involving kth-letter extraction and list reversal as examples of the evaluation.

2 RELATED WORK

Prior work applies few-shot prompting, chain-of-thought reasoning, and modular compositions of language models or symbolic functions to multi-step tasks. Decomposed Prompting differs by supporting diverse, recursive, and non-linear decomposition structures rather than fixed designs.

  • Few-shot Prompts for Multi-Step Reasoning: Few-shot prompting has been extended to multi-step reasoning by providing intermediate reasoning steps through Chain-of-Thought prompting (Wei et al., 2022; Chowdhery et al., 2022).LLMs can learn various NLP tasks from only a few prompted examples (Brown et al., 2020).
  • Few-shot Prompts for Multi-Step Reasoning: Other approaches compose multiple LLMs or combine LLMs with symbolic functions, forming specialized systems with pre-defined decomposition structures (Press et al., 2022; Parisi et al., 2022; Gao et al., 2022; Schick et al., 2023).
  • Few-shot Prompts for Multi-Step Reasoning: Least-to-most prompting (Zhou et al., 2023) and successive prompting (Dua et al., 2022) generate sub-questions with one prompt or model and answer them sequentially with another.
  • Few-shot Prompts for Multi-Step Reasoning: Unlike least-to-most and successive prompting, Decomposed Prompting supports diverse decomposition structures, including recursion and other non-linear forms.
  • Modular Approaches for Multi-Step Reasoning: The approach builds on neural modular modeling for question answering and related tasks, particularly Text Modular Networks, where decomposition includes learned next-question generation (Khot et al., 2021).

3 DECOMPOSED PROMPTING

DECOMP uses a decomposer LLM to construct and execute prompting programs that delegate complex queries to specialized sub-task functions. Its modular framework supports independent prompt design, symbolic or learned handlers, hierarchical and recursive decomposition, and external API calls.

  • 3 DECOMPOSED PROMPTING: DECOMP’s decomposer LLM generates a prompting program whose steps send simpler sub-queries to auxiliary sub-task functions, while a controller passes inputs and outputs until termination.The program consists of tuples pairing each sub-task function and query with its answer, ending in the final prediction.
  • 3 DECOMPOSED PROMPTING: Each sub-task handler can be an independent in-context prompt, another prompting program, or a symbolic or learned function such as a calculator or specialized supervised model.The decomposer is taught with examples containing both the final answer and the sequence of sub-task calls used to obtain it.
  • 3.1 DECOMPOSED PROMPTS: In the illustrative string task, DECOMP splits processing into word collection, character extraction, and concatenation, using separate prompts that remain independent of the original complex-task examples.Figure 2 shows the decomposer specifying questions and sub-tasks, while prompts can encode broader operations such as extracting letters or merging without delimiters.
  • 3.1 DECOMPOSED PROMPTS: Symbolic control structures such as foreach iterate over arrays and reference earlier answers, reducing the manual effort required to specify decompositions.The helper is optional because equivalent sub-questions can be generated directly.
  • 3.2 PROMPT EXECUTION AND INFERENCE: During inference, DECOMP repeatedly generates the next question and sub-task, routes the question to its handler, and returns the preceding answer when the [EOQ] marker appears.Inference approximates the MAP answer with greedy search in the experiments.
  • 3.3 DECOMP CAPABILITIES: Hierarchical decomposition further breaks difficult sub-tasks into simpler operations, such as splitting a string into letters and selecting the kth item when direct kth-letter identification is challenging.DECOMP can reuse existing sub-task prompts, including the shared split prompt.
  • 3.3 DECOMP CAPABILITIES: Recursive decomposition handles same-form subproblems by recursively calling the decomposer, while external API calls let handlers use systems such as Elasticsearch or Google search for retrieval.The framework applies recursion to list reversal and integrates retrieval for single-hop open-domain questions.

4 CASE STUDIES

Across four symbolic and textual multi-hop reasoning tasks, DECOMP consistently improves few-shot prompting by assigning difficult sub-tasks to separate handlers and recursively decomposing long or complex inputs. It outperforms CoT and related baselines, generalizes better to longer or unseen compositions, and supports targeted error correction and external knowledge.

  • Letter concatenation: DECOMP outperforms CoT and least-to-most prompting on letter concatenation, with separate sub-task prompts teaching difficult operations more effectively than a single prompt.The comparison evaluates generalization to unseen letter positions, longer inputs, and a new delimiter across four 100-example datasets.
  • Letter concatenation: DECOMP maintains nearly 100% accuracy as sequence length increases, while CoT-based approaches decline noticeably and the performance gap widens.Figure 7 reports EM for k=3 letter concatenation with different input lengths.
  • CommaQA-E: On CommaQA-E, DECOMP is more accurate than CoT across decomposition granularities and evaluation splits, generalizes to unseen relation compositions, and benefits from finer-grained question-specific prompts.Finer decomposition provides more examples for each question type, improving single-hop question-answering accuracy.
  • Open-domain multi-hop QA: On open-domain multi-hop QA, Decomp-Ctxt models outperform No-Ctxt models in every setting and beat the strong NoDecomp-Ctxt retrieval baseline except one Codex-with-HotpotQA condition.The results use direct QA prompts across three datasets, with additional results reported in the appendix.
  • Post-processing CoT for error correction: Targeted DECOMP post-processing improves answer extraction by 17 points on MultiArith, from 78 to 95, while gains remain consistent across prompt choices and decomposition schemes.A dedicated GPT3 answer-extraction handler addresses formatting errors in CoT outputs.

5 CONCLUSION … A.2 HYPERPARAMETER TUNING FOR OPEN DOMAIN QA

Decomposed Prompting solves complex tasks by composing modular few-shot prompts for simpler sub-tasks, which can be optimized, recursively decomposed, or replaced with symbolic systems. The appendix describes how open-domain QA corpora are constructed and how retrieval depth is tuned for different model families.

  • 5 CONCLUSION: Decomposed Prompting builds complex-task solutions from simpler sub-tasks assembled into a modular prompting program.Each sub-task uses its own few-shot prompt, supporting independent optimization and further decomposition.
  • 5 CONCLUSION: The modular design allows individual prompts to be independently optimized, decomposed further, or replaced with symbolic systems.
  • 5 CONCLUSION: Answer F1 treats predictions and ground-truth answers as token bags and computes precision and recall.
  • A.1 RETRIEVAL CORPUSES FOR OPEN DOMAIN QA: For open-domain QA, HotpotQA uses its associated Wikipedia corpus, while 2WikiMultihopQA and MuSiQue are converted from reading-comprehension datasets.The latter datasets’ corpora combine paragraphs from their train, development, and test questions.
  • A.2 HYPERPARAMETER TUNING FOR OPEN DOMAIN QA: Retrieval depth K is selected by grid search on 100 held-out questions per dataset to maximize performance.NoDecomp-Ctxt and Decomp-Ctxt use separate candidate ranges, with different ranges for GPT3 and Flan-T5-* models.
  • A.2 HYPERPARAMETER TUNING FOR OPEN DOMAIN QA: GPT3 and Flan-T5-* receive different retrieval-depth search ranges because GPT3 can fit more retrieved text.

A.3 ADDITIONAL RESULTS

Additional results are reported for MuSiQue, HotpotQA, and 2WikiMultihopQA.

  • Results on the MuSiQue dataset are presented in Figure 13.
  • Results on the HotpotQA dataset are presented in Figure 14.
  • Results on the 2WikiMultihopQA dataset are presented in Figure 15.

A.3.1 MUSIQUE

On MuSiQue, retrieval substantially improves performance over No-Ctxt QA, with DecomP-based Decomp-Ctxt QA providing further gains across all settings.

  • A.3.1 MUSIQUE: Retrieval yields substantial gains over No-Ctxt QA across all MuSiQue settings, while DecomP-based Decomp-Ctxt QA improves further (Fig. 13).

A.3.2 HOTPOTQA

On HotpotQA, incorporating retrieval yields large gains, while DecomP’s improvements are concentrated mostly in smaller models.

  • A.3.2 HOTPOTQA: Retrieval produces large gains on the HotpotQA results.The complete results are presented in Fig. 14.
  • A.3.2 HOTPOTQA: DecomP’s gains on HotpotQA are mostly observed in smaller models.

A.3.3 2WIKIMULTIHOPQA

On 2WikiMultihopQA, incorporating retrieval produces large gains, while adding DecomP yields substantial gains over NoDecomp-Ctxt.

  • A.3.3 2WIKIMULTIHOPQA: Large gains arise from incorporating retrieval on 2WikiMultihopQA, as shown in Fig. 15.
  • A.3.3 2WIKIMULTIHOPQA: DecomP further provides substantial gains compared with NoDecomp-Ctxt on this dataset.

B MATH QA · C EFFECT OF SCALE ON COMMAQA · D RESULTS ON ALL PROMPTS

Decomposed Prompting improves math QA by separating chain-of-thought identification from answer extraction, outperforming Chain-of-Thought on GSM8K and MultiArith. On CommAQA, performance declines with weaker and smaller models, while DECOMP remains ahead of CoT until performance approaches zero.

  • B MATH QA: DECOMP separates math QA into identifying the chain-of-thought reasoning and extracting its answer with a second GPT3-based sub-module.This avoids relying on limited-generalization patterns such as finding the number following “answer is”.
  • B MATH QA: DECOMP improves over CoT by 14 points on GSM8K and 17 points on MultiArith, demonstrating gains from simple decomposition on math QA.The result also suggests applicability to nonextractive answer generation from chain-of-thoughts.
  • C EFFECT OF SCALE ON COMMAQA: As model size and strength decrease, both CoT and DECOMP lose performance on CommAQA.The comparison includes text-curie-001, text-davinci-001, and text-davinci-002.
  • C EFFECT OF SCALE ON COMMAQA: DECOMP continues to outperform CoT across weaker models until performance approaches zero with curie-001.This scale trend is summarized in Fig. 17.
  • C EFFECT OF SCALE ON COMMAQA: On CommAQA, the evaluation compares text-curie-001, text-davinci-001, and text-davinci-002, with shorter prompts for models limited to 2048-token context windows.The reduced prompts accommodate the smaller context windows of curie-001 and davinci-001.

D.1 PER-PROMPT RESULT ON LETTER CONCATENATION

For letter concatenation with a space delimiter, DECOMP consistently outperforms chain-of-thought and Least-to-Most prompting across all tested N values and prompts P1–P3. Results remain stable across the different prompts.

  • D.1 PER-PROMPT RESULT ON LETTER CONCATENATION: Results are stable across prompts P1, P2, and P3.
  • D.1 PER-PROMPT RESULT ON LETTER CONCATENATION: The evaluation varies N while using a space delimiter for letter concatenation.
  • D.1 PER-PROMPT RESULT ON LETTER CONCATENATION: DECOMP outperforms chain-of-thought and Least-to-Most prompting across all tested N values and prompts P1, P2, and P3.The comparison is reported for the letter concatenation task with a space delimiter.

D.2 PER-PROMPT RESULTS ON COMMAQA

On CommAQA, DECOMP outperforms CoT across every evaluated prompt set.

  • D.2 PER-PROMPT RESULTS ON COMMAQA: DECOMP outperforms CoT on each prompt set evaluated on CommAQA.The comparison covers all prompts reported in Figure 19.

E EFFECT OF DECOMPOSITION SCHEME

Alternative decomposition schemes preserved or improved performance on letter concatenation and list reversal, while trading different robustness and GPT3-call costs. Both alternatives remained better than CoT.

  • E EFFECT OF DECOMPOSITION SCHEME: The alternate letter-concatenation scheme used GPT3 to generate sub-questions rather than looping over answers.Its prompt decomposes the task into splitting the words, extracting each final letter, and merging the resulting letters.
  • E EFFECT OF DECOMPOSITION SCHEME: Generating sub-questions improves robustness to malformed answer formatting but may reorder, omit, or repeat list elements.The decomposer can still produce appropriate sub-questions when an initial answer is not a valid array.
  • E EFFECT OF DECOMPOSITION SCHEME: The alternate reversal scheme reverses the tail recursively before appending the head, requiring O(n) calls instead of O(log(n)) binary splitting.The reported comparison also describes the binary-split cost as O(ln(n)) versus O(n) one element at a time.
  • E EFFECT OF DECOMPOSITION SCHEME: Both alternative decomposition schemes preserved performance, with identical letter-concatenation results and stronger reversal performance on longer inputs; both remained better than CoT.Figure 20 reports identical scores for the two letter-concatenation schemes; reversal improved on longer inputs.

F ERROR ANALYSIS · F.1 LETTER CONCATENATION · F.1.1 DECOMP

DECOMP’s letter-concatenation errors arise exclusively during sub-task execution, while DECOMP outperforms and generalizes better than CoT across input sizes. Recursive tail reversal improves stability for longer lists but requires more GPT3 calls.

  • F.1.1 DECOMP: Recursively reversing a list’s tail is more stable for longer lengths, but it requires more GPT3 calls.The stability improvement therefore trades off against increased model-call cost.
  • F ERROR ANALYSIS: All observed DECOMP errors on letter concatenation occur during sub-task execution rather than in the overall decomposition.The error analysis identifies sub-task execution as the sole error source.
  • F.1.1 DECOMP: The DECOMP analysis therefore localizes failures to the execution of modular sub-tasks, including letter extraction and concatenation.These examples illustrate distinct failure modes within the letter-concatenation decomposition.
  • F.1.1 DECOMP: DECOMP always outperforms and generalizes better than CoT on kth-letter concatenation across different numbers of input words.The comparison uses exact-match results for k=3 with semicolon delimiters and varying N.
  • F.1 LETTER CONCATENATION: One sub-task error comes from extracting the wrong letter position from a word.For the example query, the system predicts c instead of the correct third letter, n.
  • F.1 LETTER CONCATENATION: A second sub-task error comes from concatenating the extracted letters incorrectly.The predicted output omits the required spaces, producing leoie instead of the requested spaced concatenation.

F.1.2 COT W/ ROLLOUT

Chain-of-thought with rollout produced more frequent errors than DECOMP on letter concatenation because it could not effectively teach each sub-task. The errors included incorrect letter extraction during intermediate reasoning.

  • F.1.2 COT W/ ROLLOUT: CoT with rollout produced more frequent errors than DECOMP because its prompting could not effectively teach each sub-task.Error analysis found that CoT made similar generation errors, but at a higher frequency than DECOMP.
  • F.1.2 COT W/ ROLLOUT: One error involved extracting the wrong third letter from “Sheila,” predicting “i” instead of the answer’s “e.”The intermediate reasoning incorrectly indexed the letters in “Sheila.”
  • F.1.2 COT W/ ROLLOUT: Another error extracted incorrect letters in the “Shobha Kailash Nakamura Peter Benitez” example, predicting “o l k t i” instead of “o i k t n.”The reasoning selected the fourth letter of “Benitez” rather than its third letter.

F.2 COMMAQA

On CommaQA, errors mainly arise from incorrect single-hop sub-task answers. These errors are more frequent for CoT because it cannot delegate this sub-task to a specialized prompt.

  • F.2 COMMAQA: CommaQA errors are mostly caused by incorrect answers to single-hop sub-tasks.Because all observed errors were of this type, the section presents only one example.
  • F.2 COMMAQA: CoT makes the same type of error more frequently because its single-hop QA sub-task cannot be delegated to a specialized prompt.
  • F.2 COMMAQA: In the example, an incorrect sub-question answer omitted “Polytetrafluoromethane” from the predicted movies, causing the final answer to omit “Hydrallium.”

G TASK PROMPTS

This appendix specifies the prompts, decomposition operators, and worked examples used across Chain-of-Thought and Decomposed Prompting experiments, including recursive reversal and open-domain QA applications.

  • G TASK PROMPTS: CoT baselines use the same two-step decomposition framework: GPT3 generates a chain of thought, then a regex-based extractor converts it into the answer.The module name may be omitted because the chain of thought is sent to the extractor by default.
  • G TASK PROMPTS: The appendix defines project values (foreach) as replacing an answer index with each list value, answering every resulting question, and concatenating the answers.Project values flat unique (foreach merge) additionally flattens the results and keeps only unique entities.
  • G.1.1 DECOMPOSED PROMPTING: Decomposed Prompting examples split letter-concatenation tasks into word extraction, indexed-letter selection, and final merging, producing outputs such as “a a g,” “A M T,” and “b x o.”The prompts use split, project values, str position, and merge steps.
  • G.1.1 DECOMPOSED PROMPTING: The appendix provides separate prompts for elementary operators, including selecting indexed elements, concatenating lists, and extracting positions from words or ordered sequences.Examples include retrieving “sleep” at position 4 and “n” as the last letter of “Mathison.”
  • G.1.2 COT WITH ROLLOUT: CoT with rollout explicitly verbalizes the same intermediate word, letter-position, and concatenation steps before returning answers such as “a a g” and “A M T.”The rollout examples show each word’s ordered letters and the selected position before final concatenation.
  • G.2.1 SPLIT REVERSAL: The recursive reversal strategy splits a sequence in half, reverses each half, and concatenates them using O(log n) language-model calls.Here, n denotes the number of items in the sequence.
  • G.6 OPEN DOMAIN QA: Open-domain QA prompt examples demonstrate decomposed answers of “Afghanistan,” “one,” and “Jeremy Horn” for multi-step questions about detention, awards, and relative age.These examples show the prompt format returning a final answer after intermediate retrieval.
Loading 2210.02406v2…