Decomposed Prompting: How Modular Sub-Task Handlers Solve What Chain-of-Thought Cannot

Chain-of-thought prompting transformed how language models handle multi-step problems. By generating explicit reasoning steps before an answer, models gained the ability to work through arithmetic, commonsense inference, and symbolic manipulation that stumped direct prompting. But chain-of-thought has a ceiling that researchers at the Allen Institute for AI, Stony Brook University, and the University of Edinburgh identified and quantified: when a reasoning step is itself too complex for the model to learn from a handful of demonstrations, the entire chain fails. The model is asked to learn both how to decompose the task and how to execute each step, all from the same few examples. When either piece is hard, the whole prompt struggles. Tushar Khot, Harsh Trivedi, Matthew Finlayson, Yao Fu, Kyle Richardson, Peter Clark, and Ashish Sabharwal published 'Decomposed Prompting: A Modular Approach for Solving Complex Tasks' in October 2022 (arXiv:2210.02406) and presented it at ICLR 2023. The paper introduces DecomP, a framework that separates the problem of decomposing a task from the problem of executing each sub-task, delegating each piece to a dedicated prompt or function optimized for exactly that piece.

The ceiling chain-of-thought hits on hard reasoning steps

Chain-of-thought prompting bundles decomposition and execution into a single prompt. A few labeled examples show the model both how to break the task into steps and how to perform each step. This works well when both pieces are learnable from a small set of demonstrations. The failure mode appears when one step is inherently hard for the model at the scale of examples the prompt can contain. The paper's clearest illustration is concatenating the kth letter from each word in a list, such as finding the third letter of each word in 'school' 'bus' 'airport' and concatenating them. Chain-of-thought prompts that demonstrate the full multi-step task do not give the model enough focused practice on the sub-task of extracting the kth letter from a word. The sub-task is embedded inside the larger task demonstration, so the model receives only indirect, sparse signal about how to execute it. A different failure mode appears when the input is very long. Multi-hop question answering over a large document requires reasoning that chain-of-thought cannot compress into a fixed-length prompt without losing the relevant context. These are structural problems, not scale problems. Bigger models help but do not resolve the underlying issue that a single-prompt approach must teach every sub-skill from the same limited set of examples.

The DecomP architecture: a decomposer and a handler library

DecomP splits the work into two distinct components. The first is a decomposer: a prompt that takes a complex task and outputs a sequence of sub-task calls, using named handlers as building blocks. The decomposer does not execute any sub-task itself. It only specifies the procedure: call handler A with this input, pass its output to handler B, and so on. The decomposer is analogous to a top-level function in software that calls into a library of utilities without implementing them. The second component is the handler library: a collection of prompts, each dedicated to one sub-task. Each handler receives only the inputs relevant to its specific job and is shown focused demonstrations of that sub-task alone. A handler for extracting the kth letter from a word is shown many examples of exactly that operation; it does not see the full concatenation task. This separation means each handler can be shown a richer, broader, and more targeted set of demonstrations than it could receive if it were embedded inside a single complex prompt. Handlers are not limited to prompts. The framework explicitly supports symbolic functions: a retrieval handler backed by Elasticsearch or a similar index, a sorting function implemented in Python, or any other deterministic module. When a sub-task is better handled by a symbolic system than by an LLM, DecomP allows the developer to plug in that system without modifying the decomposer or any other handler.

Three handler types and the recursive fallback

The paper distinguishes three kinds of handlers that cover the full range of sub-task complexity. The first is a standard few-shot prompt handler, identical in structure to a conventional few-shot prompt but focused on one sub-task. This handles steps that are individually learnable with enough targeted demonstrations. The second is a recursively decomposed handler: a sub-task that is still too complex for direct prompting gets its own decomposer and its own handler library. The kth letter extraction task is handled this way in the paper. Rather than teaching the model to extract the kth letter in one prompt, a recursive decomposer breaks that into even simpler steps, such as enumerating letter positions and selecting by index. The third is a symbolic handler: a non-neural function that executes the sub-task exactly. The open-domain multi-hop QA evaluation uses a retrieval handler backed by a large-scale document index rather than asking the LLM to retrieve information from memory. The handler interface is uniform regardless of what implements it: the decomposer sends a typed input and receives a typed output. This means a prompt-based handler can be upgraded to a fine-tuned model, a fine-tuned model upgraded to a symbolic system, or a symbolic system replaced with a retrieval-augmented prompt, with no change to the decomposer or any sibling handler in the library.

Results across eight datasets using GPT-3

The paper evaluates DecomP against chain-of-thought prompting and direct few-shot baselines on eight datasets using GPT-3. The symbolic reasoning evaluations cover kth letter concatenation and list reversal, two tasks the paper uses to illustrate cases where chain-of-thought demonstrations are insufficient. On kth letter concatenation, DecomP with recursive sub-task decomposition substantially outperforms chain-of-thought, because the focused handler learns the letter-extraction sub-task from a richer set of targeted examples rather than the sparse implicit signal in full-task demonstrations. On list reversal, DecomP uses recursive decomposition to handle arbitrarily long lists by breaking them into smaller chunks handled by the same handler. The long-context multi-hop QA evaluation uses the MuSiQue dataset, where questions require evidence from multiple paragraphs of a long document. DecomP handlers are each shown focused single-hop demonstrations, making the sub-task of answering a single-hop question easier to learn than the full multi-hop task would be from the same number of examples. On the open-domain multi-hop QA evaluation using the HotpotQA and 2WikiMultiHopQA datasets, the retrieval handler backed by a symbolic search index replaces the expectation that the LLM retrieves from parametric memory, directly addressing the knowledge-intensive bottleneck. Across all eight evaluations, DecomP outperforms the prior few-shot prompting baselines using the same underlying GPT-3 model.

• DecomP separates task decomposition (the decomposer prompt) from sub-task execution (a library of handler prompts or symbolic functions), so each piece can be optimized independently.
• Handlers can be standard few-shot prompts, recursively decomposed sub-tasks, or symbolic functions such as Elasticsearch retrieval or Python sorting utilities.
• The handler interface is uniform: typed input in, typed output out; swapping a prompt handler for a fine-tuned model or symbolic function requires no change to the decomposer.
• On symbolic reasoning tasks such as kth letter concatenation and list reversal, recursive decomposition teaches hard sub-tasks that chain-of-thought demonstrations cannot cover adequately.
• On open-domain multi-hop QA (HotpotQA, 2WikiMultiHopQA), a symbolic retrieval handler replaces LLM memory retrieval, directly addressing the knowledge-intensive bottleneck.
• arXiv:2210.02406, submitted October 5, 2022; ICLR 2023; authors from Allen Institute for AI, Stony Brook University, and University of Edinburgh; code at github.com/allenai/DecomP.

Why DecomP matters for building AI systems today

DecomP arrived before tool-use and function-calling became standard features of production LLM APIs, but the framework anticipates both. Modern agent systems that route LLM calls through tool-use schemas are implementing the same separation: a planner that emits structured sub-task calls, and a set of handlers (tools, APIs, retrieval systems) that execute each call independently. The key insight DecomP surfaces is that this separation is not just an engineering convenience but a prompting technique with measurable accuracy benefits. Focused demonstrations of a sub-task teach the model more reliably than sparse implicit demonstrations embedded in a complex task. Symbolic handlers outperform LLM handlers on tasks where deterministic execution is appropriate. Recursive decomposition extends the technique to sub-tasks that are themselves too complex. PromptingIndex covers DecomP alongside least-to-most prompting, ReAct, and PAL in its series on prompting techniques that treat language model calls as composable building blocks rather than monolithic single-prompt systems.