\section{Task Prompts}
\label{app:prompts}
We have provided the task prompts for all the datasets for COT and our Decomposed Prompting\ approach.

\paragraph{CoT} Since CoT methods also perform 2-step reasoning: first generate the chain-of-thought and second extract the answer from the CoT, we use the same decomposition-based framework for COT baselines too. For example, consider the following example in our COT prompt:
\textbox{\linewidth}{%
QC: Take the letters at position 1 of the words in ”Alan Mathison Turing” and concatenate them
using a space.\\
QS: [extract] The letter at position 1 of ”Alan” is ”A”. The letter at position 1 of ”Mathison” is ”M”. The
letter at position 1 of ”Turing” is ”T”. Concatenating ”A”, ”M”, ”T” using a space leads to ”A
M T”. So, ”Alan Mathison Turing” outputs ”A M T”.\\
A: ”A M T”\\
QS: [EOQ]\\
}
GPT3 generates the chain-of-thought during the "decomposition" step and a regex-based answer extractor \texttt{extract} (\texttt{'.* outputs "(.*)"\textbackslash.'}) then takes this CoT and generates the answer. In some cases, the module name is skipped in the prompt (the CoT is sent to the extractor by default).

\paragraph{Operators} In this work, we use the same operators as defined by \citeauthor{Khot2022HeyAC}. Their \texttt{select} operator is just the basic operator that replaces references to an answer index with its answer. When not specified, \texttt{select} is assumed to be the default operator. In addition, we consider two operators in our experiments: \texttt{project\_values} and \texttt{project\_values\_flat\_unique}.
\begin{itemize}
    \item \texttt{project\_values}: This operator takes a list answer $\#i = X$ and iterates over it to generate new questions by replacing mentions of $\#i$ i.e. Q = [q.replace(\#i, x) for x $\in$ X]. The answer to each question is simply concatenated to get the final answer i.e. A = [model(q) for q $\in$ Q]. We refer to this as \texttt{foreach} for simplicity in the main text.

    \item \texttt{project\_values\_flat\_unique}: This operator performs the same steps as \texttt{project\_values} but then additionally flattens the list and only returns the unique entities in the flattened list. We refer to this as \texttt{foreach\_merge} in the main text for simplicity.
\end{itemize}
\subsection{Letter Concatentation}
We show one of the prompts used for experiments here. The entire set of prompts is provided as supplemetary material.
\colorlet{shadecolor}{gray!10}
\lstset{breaklines=true, columns=fullflexible, backgroundcolor=\color{shadecolor}}

\subsubsection{Decomposed Prompting}
\lstinputlisting[title=\texttt{decomp}]{prompts/letter_cat/letter_cat_n3_ex3_decomp.txt}
\lstinputlisting[title=\texttt{split}]{prompts/letter_cat/split.txt}
\lstinputlisting[title=\texttt{str\_position}]{prompts/letter_cat/str_position.txt}
\lstinputlisting[title=\texttt{merge}]{prompts/letter_cat/merge.txt}
\lstinputlisting[title=\texttt{arr\_position}]{prompts/letter_cat/arr_position.txt}
\subsubsection{COT with rollout}
\lstinputlisting[title=\texttt{COT w/ rollout}]{prompts/letter_cat/cot_rollout_letter_cat_n3_ex3_decomp.txt}
\subsubsection{COT}
\lstinputlisting[title=\texttt{COT}]{prompts/letter_cat/cot_letter_cat_n3_ex3_decomp.txt}

\subsection{Sequence Reversal}

\subsubsection{Split Reverseal}
The prompts in this section implement Algorithm~\ref{alg:split}.

\begin{algorithm}
  \caption{A recursive reversal strategy that splits the sequence in half, reverses each half, and concatenates them. Runs in $O(\log n)$ calls to the LM where $n$ is the number of items in the sequence.}\label{alg:split}
  \input{alg/split.tex}
\end{algorithm}

\lstinputlisting[title=\texttt{reverse}]{prompts/reverse/decomp.txt}
\lstinputlisting[title=\texttt{remove\_numbers}]{prompts/reverse/rm_num.txt}
\lstinputlisting[title=\texttt{join}]{prompts/reverse/join.txt}
\lstinputlisting[title=\texttt{cot}]{prompts/reverse/cot.txt}
\lstinputlisting[title=\texttt{unrolled\_decomp}]{prompts/reverse/unrolled.txt}

\subsection{Long-Document QA}
We show one of the prompts used for CommaQA experiments here. The entire set of prompts is provided as supplemetary material.
\subsubsection{Decomposed Prompting (coarse)}
\lstset{literate={è}{{\`e}}1}
\lstinputlisting[title=\texttt{decomp}]{prompts/commaqa/decomp_coarse.txt}
\lstinputlisting[title=\texttt{qa}]{prompts/commaqa/qa.txt}

\subsubsection{Decomposed Prompting (fine)}
\lstinputlisting[title=\texttt{decomp}]{prompts/commaqa/decomp_fine.txt}
\lstinputlisting[title=\texttt{aw\_qa}]{prompts/commaqa/aw_qa.txt}
\lstinputlisting[title=\texttt{pos\_qa}]{prompts/commaqa/pos_qa.txt}
\lstinputlisting[title=\texttt{simp\_qa}]{prompts/commaqa/simp_qa.txt}

\subsubsection{COT}
\lstinputlisting[title=\texttt{COT}]{prompts/commaqa/cot.txt}

\subsection{HotpotQA}

The prompts in this section implement Decomposed Prompting approach to open-domain multihop QA. For brevity we've included prompts for 5 of 25 randomly sampled questions. The full prompts are attached with the submission and will also be released with the code. Note that we selected a set of 100 questions from the development set to tune the hyperparameter (number of paragraphs to retrieve for all of the retrieval-based approaches).

\lstinputlisting[title=\texttt{decomp}]{prompts/hotpotqa/v2__decomp.txt}
\lstinputlisting[title=\texttt{retrieve\_odqa}]{prompts/hotpotqa/v2__retrieve_odqa.txt}
\lstinputlisting[title=\texttt{singlehop\_titleqa}]{prompts/hotpotqa/v2__singlehop_titleqa.txt}
\lstinputlisting[title=\texttt{multihop\_titleqa (direct)}]{prompts/hotpotqa/v2__multihop_titleqa_direct.txt}
\lstinputlisting[title=\texttt{multihop\_titleqa (cot)}]{prompts/hotpotqa/v2__multihop_titleqa_cot.txt}

\section{Introduction}
Large Language Models (LLMs) such as GPT-3 \citep{gpt3} have been shown to solve various tasks given only a few examples as prompts, also referred to as in-context learning. These models can even perform more complex reasoning tasks when shown the sequence of simple reasoning steps needed to perform the complex task as a prompt~\cite{Wei2022ChainOT,Nye2021ShowYW}. In essence, the sequence of reasoning steps, such as in Chains-of-Thought (CoT\xspace) prompting \citep{Wei2022ChainOT}, demonstrates how to decompose the complex task as well as how each reasoning step should be performed. However, as tasks become more complex, few demonstrations of the complex task aren't sufficient for current models to learn to perform all necessary reasoning steps. E.g., few-shot demonstrations of concatenating the $k^{\mathrm{th}}$ letter of words in a string is insufficient for GPT-3 to learn to extract the $k^{\mathrm{th}}$ letter, or learn to answer hard single-hop questions when only provided a few demonstrations of multi-hop questions. Additionally, it is unclear whether tasks such as document retrieval and integration, for knowledge-intensive tasks, can even be done by few-shot prompts.

\begin{figure}[htbp]
    \centering
    \includegraphics[width=\linewidth]{images/decomp_intro_modified.pdf}
    \caption{While standard approaches only provide labeled examples (shown as a grey input box with green label box), Chain-of-Thought prompting also describes the reasoning steps to arrive at the answer for every example in the prompt. Decomposed Prompting, on the other hand, uses the decomposer prompt to only describe the procedure to solve the complex tasks using certain sub-tasks. Each sub-task, indicated here with A, B and C is handled by sub-task specific handlers which can vary from a standard prompt (sub-task A), a further decomposed prompt (sub-task B) or a symbolic function such as retrieval (sub-task C)
    }
    \label{fig:intro}
\end{figure}

To address these limitations, we propose \textbf{Decomposed Prompting} (\textsc{DecomP}\xspace), a new approach to solve complex tasks by instead decomposing them into simpler sub-tasks and delegating these to sub-task specific LLMs, with both the decomposer and the sub-task LLMs (henceforth, \emph{sub-task handlers}) having their own few-shot prompts. Fig~\ref{fig:intro} illustrates our approach. The decomposer prompt only describes a sequence of sub-tasks (A, B, and C) needed to solve the complex tasks, indicated with the dashed lines. Each sub-task is then delegated to the corresponding sub-task handler shown on the right.

Using a software engineering analogy, the decomposer defines the top-level \emph{program} for the complex task using interfaces to simpler, sub-task functions. The sub-task handlers serve as modular, debuggable, and upgradable \emph{implementations} of these simpler functions, akin to a software library. If a particular sub-task handler, say the one for identifying the $k^{\mathrm{th}}$ letter or retrieving a document, is not performing well enough, we can debug this handler in isolation, explore alternative prompts or implementations, and seamlessly plug the improved module back into the overall system, as a systematic way to try to improve performance on the complex end-task.

This approach has several advantages over prior work (as also shown in the figure). The sub-task handlers can be shown a broader and richer set of examples (of the simpler task) than the specific ones needed for the complex task prompt (task A). If a sub-task is too complex, it can be further decomposed into simpler sub-tasks (task B). Similar to software libraries, these sub-task handlers can be shared across multiple tasks; e.g., here tasks A and C are reused in the model for task B. As noted above, a sub-task handler can be easily swapped with an improved implementation without any change to the rest of the system. Finally, few-shot prompt based LLMs can be even replaced with a symbolic system for tasks more suited for non-neural methods; e.g., task C uses a symbolic retrieval system such as Elasticsearch that can handle very large-scale corpora.

To illustrate these advantages of \textsc{DecomP}\xspace, we empirically evaluate it against prior work on four challenging datasets using GPT3 models: 1) On a task of concatenating the $k^{\mathrm{th}}$ letter, we show that our approach of factoring out each sub-task allows us to more effectively teach the sub-problem of extracting the $k^{\mathrm{th}}$ letter(specifically, by decomposing it into even easier sub-tasks). 2) On a task of reversing a list, we show that \textsc{DecomP}\xspace\ allows us to extend the capabilities of a weaker model and build a scale-invariant system by recursively decomposing the task into reversal of smaller and smaller lists. 3) On a task of long-context QA~\citep{Khot2022HeyAC}, our approach allows each sub-task handler to accommodate more examples than feasible with CoT\xspace prompting leading to better QA performance. 4) On multi-hop open-domain QA dataset~\cite{hotpotqa}, we can incorporate a symbolic retrieval (ElasticSearch) API as the handler for the retrieval sub-task leading to better results than CoT\xspace systems.

\section{Related Work}
\paragraph{Few-shot Prompts for Multi-Step Reasoning}
Large-scale Language models (LLMs) have been shown to learn various NLP tasks given just few examples as prompts~\citep{gpt3}. Recently, they have also been successfully applied to various multi-step reasoning tasks by providing the intermediate reasoning steps, i.e. Chain-of-Thought~\citep{Wei2022ChainOT,chowdhery2022palm}, needed to arrive at the answer.
Building of the successes of Chain-of-thought (CoT\xspace) style prompting on LLMs, many subsequent studies have focused on improvements of this basic model. This includes, for example, diverse decoding and ensembling to improve self-consistency  \citep{wang2022self}, more complex and contrasting rationales \citep{marasovic2021few,wang2022rationale}, generating sub-questions and answering them sequentially in least-to-most complexity order~\citep{Zhou2022LeasttoMostPE}, integration with symbolic modules \citep{jung2022maieutic}, selection inference \citep{creswell2022selection}, coupling in-context learning with sparse fine-tuning \citep{zelikman2022star}, and even presented many of them under a single probabilistic programming framework~\citep{dohan2022language}.

We view these prior works as specialized systems with a pre-defined decomposition structure. For example, the closest work to our approach is the idea of least-to-most prompting~\citep{Zhou2022LeasttoMostPE} where one prompt is used to generate the sub-questions needed to answer a complex question and a second prompt sequentially answers these sub-questions. In contrast, our approach allows for diverse decomposition structures and can use different prompts to answer each sub-question, even including symbolic systems. Moreover,
rather than generating the entire set of sub-questions (i.e., the decomposition) at once, we can
iteratively generate new questions based on the answers to previous steps (e.g., our prompt for HotpotQA\xspace\ in Sec.~\ref{subsec:hotpot} is one such use case.)

\paragraph{Modular Approaches for Multi-Step Reasoning}

Our work follows a long literature in NLP on neural modular modeling architectures \citep{andreas2016neural,talmor2018web,jiang2019self,gupta2020neural,perez2020unsupervised,khot-etal-2021-text,levine2022standing} for question-answering and other tasks. We take particular inspiration from the \emph{Text Modular Networks} approach of \cite{khot-etal-2021-text}, whereby problem decomposition consists of a learned \emph{next question} generator trained to generate questions in the language of a collection of textual and symbolic agents. Best-first search strategy was used to explore the space of possible decompositions during inference. In contrast to this work, which largely centered around supervised training of the next-question generator \emph{given existing agents}, we leverage the power and recent successes of few-shot LLMs to build both the decomposer and the sub-task agents that best fit the ideal decomposition. This has the advantage of obviating the need for specialized supervised training data that may not always be available for all sub-tasks -- a key bottleneck of this prior work.

\paragraph{Neural Programming}
Our work also relates to work on neural programming architectures \citep{reed2015neural,neelakantan2015neural,cai2017making}, which aims at building neural models that can represent and execute compositional programs, often focusing on algorithmic tasks of the type we investigate here. Specifically, our top-level decomposer prompts with their corresponding \emph{sub-task handlers} (see  Figure~\ref{fig:intro}), which get constructed incrementally and interpreted by the underlying LLM, can be interpreted as structured programs where the the underlying program construction and interpretation process is performed using LLMs.

\section{Decomposed Prompting}

As with conventional \emph{few-shot} prompting, the goal is to teach an LLM to find an answer $A$ to a query $Q$ using a small set of \emph{in-context} examples $D = \{E_{1},...,E_{|D|}\}$. The answer $A$ is obtained from the underlying distribution $p(A \mid Q,D,\theta)$ \citep{dohan2022language}. In the most basic few-shot setup, examples take the form $E_j = (Q_j, A_j)$. In the case of CoT\xspace-style prompting, the goal is to obtain answers by first generating a sequence or chain of intermediate reasoning steps or ``thoughts'' $T$, and then deriving the final answer based on $T$. To teach this ability, one uses more sophisticated in-context examples that take the form $E_{j} = (Q_{j},(T_{j,1},\ldots,T_{j,k}),A_{j})$.

In \textsc{DecomP}\xspace, the core is a \emph{decomposer} LLM that tries to solve a complex task by generating a \textbf{prompting program} $P$ for it. Each step of $P$ directs a simpler sub-query to a function in an auxiliary set of \textbf{sub-task functions} $\mathcal{F}$ available to the system. Given a query $Q$ whose answer is $A$, the program $P$ is a sequence of the form $\big((f_1,Q_1,A_1),...,(f_k,Q_k,A_k)\big)$ where $A_k$ is the final answer predicted by the program and $Q_i$ is a sub-query directed to the sub-task function $f_i \in \mathcal{F}$. The prompting program $P$ is executed by a high-level imperative \textbf{controller}, which passes the inputs and outputs between the decomposer and sub-task handler until a stopping condition is met in $P$ and a final output is obtained.

To teach the decomposer LLM in a few-shot prompting manner, we use in-context examples that take the form $E_j = \big( (Q_j, \big(f_{j,1},Q_{j,1},A_{j,1}),...,(f_{j,k_j},Q_{j,k_j},A_{j,k_j})\big) \big)$ where $A_{j,k_j} = A_j$ is the final answer for $Q_j$ and $(Q_{j,1}, \ldots, Q_{j,k_j})$ is a decomposition of $Q_j$. Each sub-task function $f$, in turn, is operationalized via a sub-task handler as an in-context prompting LLM (e.g., a separate CoT\xspace-style prompt or a additional prompting program dedicated to that sub-task), or any other symbolic or learned function (e.g., a calculator or specialized supervised trained model).

\subsection{Decomposed Prompts}

\begin{figure}[t]
    \centering
    \includegraphics[width=0.8\linewidth]{images/letter_cat_prompts.pdf}
    \caption{Prompts for the decomposer and the \texttt{split} and \texttt{merge} sub-tasks used by the decomposer. The decomposer specifies the sequence of questions and corresponding sub-tasks (within square braces). The sub-task prompts can be written independent of the complex task examples and can even capture generalizations, e.g., letters in word (\texttt{split}) and no delimiter (\texttt{merge}).}
    \label{fig:letter_cat_prompts}
\end{figure}

To illustrate this with an example, consider a multi-step task such as ``Concatenate the first letter of every word in $str$ using a space''. We can solve this task by decomposing it into a sequence of three simple sub-tasks: 1) Collect the list of words in the $str$; 2) For each word, extract the third letter; 3) Concatenate the extracted letters using space as the separator. Figure~\ref{fig:letter_cat_prompts} shows an example decomposition prompt for this task. Much like a conventional structured program, the top-level \texttt{decomp} prompt provides an example program $E_j$ using three sub-task functions: $f_1:$\texttt{split} that \emph{splits words in an input string}, $f_2:$\texttt{str\_pos} that \emph{finds character positions in strings} and $f_3:$\texttt{merge} that \emph{concatenates characters}. In this case, we operationalize each sub-task function as a separate in-context prompt (e.g., using a standard prompting approach for \texttt{split} and \texttt{merge} on the right side), each containing a set of in-context examples that are independent of the original complex task.

In addition to the three functions described above, additional control structure is included, such as the symbolic function \texttt{foreach}, which iterates over arrays and references to previous answers such as \#1. We note that such a helper function is not strictly necessary (e.g., we could directly generate ``Q2': What is the first letter of Jack?'' and ``Q3': What is the first letter of Ryan?'' instead of Q2 in the figure) and is added to reduce the manual effort needed to specify the decomposition and also reduce potential errors during decomposition. In our experiments we use two of the compositional operators defined by \citet{Khot2022HeyAC} (see appendix for details), although it is capable of using all their operators (which also capture the QDMR operators from \cite{Wolfson2020Break}).

\begin{figure}[htbp]
    \centering
    \includegraphics[width=0.9\linewidth]{images/letter_cat_exec.pdf}
    \caption{The inference procedure in \textsc{DecomP}\xspace\ iteratively calls the decomposer prompt to generate the next question and sub-task at each step, given the current history of question and answers. The generated question is then routed to the assigned sub-task handler (with some handling of special operators, when needed). When the special end-of-questions \texttt{[EOQ]} marker is generated, the previous answer is returned as the final prediction.}
    \label{fig:letter_exec}
\end{figure}
\subsection{Prompt Execution and Inference}

Given a new question and a set of background in-context examples $D$, the inference (i.e., the program construction and execution) process is illustrated in Fig.~\ref{fig:letter_exec}. The new complex question is fed to the decomposer prompt to get the first sub-question to be asked to the \texttt{split} prompt. With the help of our symbolic controller, the answer generated from this prompt is then appended to the decomposer prompt to get the second sub-question, $Q2$. Due to the \texttt{foreach} operator in the generated question, $Q2$ results in two questions (one for each word in the answer $\#1$) to be fed to the \texttt{str\_pos} prompt. The answers are combined into an array to get the answer $\#2$. The entire decomposition history is used to generate $Q3$  and passed to the \texttt{merge} prompt to get the final answer. Since the task has been solved, the decomposition prompt produces the special end-of-sequence marker([EOQ]) and the last answer is returned as the final answer. Formally, performing inference involves finding the best answer $A$ to a new query $Q$, which in the simplest form of prompting involves computing the MAP answer using the LLMs predictive distribution for $A$, i.e., $\hat{A} = \argmax_{A} p(A \mid D,Q,\theta)$ \citep{dohan2022language}. For practicality, such computations are approximated using greedy search, which we pursue in our experiments.

\subsection{\textsc{DecomP}\xspace\ Capabilities}
Next we describe three types of few-shot prompting solutions that our approach enables.

\textbf{Hierarchical Decomposition}
Certain sub-tasks, even when given many examples, are not solvable with few-shot prompting. E.g., we found identifying the $k^{\mathrm{th}}$ letter of a string to be challenging for the GPT3 \texttt{text-davinci-002} model. In such a scenario, we can decompose the sub-task prompt further, to first identify the letters and their position and then select the $k^{\mathrm{th}}$ element of this array (see Fig.~\ref{fig:str_pos_prompts}). We can also re-use existing sub-task prompts in our framework. E.g., the \texttt{split} prompt can be reused since it was developed for the general task of splitting strings.\footnote{Appendix~\ref{app:prompts} contains the complete \texttt{split} prompt which has examples for questions such as ``Q: What are the letters and their positions in ``Mathison"?''.}
\begin{figure}[htbp]
    \centering
    \includegraphics[width=\linewidth]{images/str_pos_prompts.pdf}
    \caption{Since identifying the $k^{th}$ character is challenging for GPT3 \texttt{davinci-002} model, we further decompose it into two simpler sub-tasks: split the word into its letters (using the shared sub-task \texttt{split}) and then return the $k^{th}$ item of this list using the \texttt{arr\_pos} prompt.}
    \label{fig:str_pos_prompts}
\end{figure}

\textbf{Recursive Decomposition}
Some problems can be naturally broken down into one or more smaller problems of the same form.
Recursive algorithms such as merge sort use this idea to solve large problems efficiently, using a succinctly described method.
We apply this same principle in \textsc{DecomP}\xspace by allowing the decomposer prompt to recursively call itself, as shown in Fig.~\ref{fig:reverse_prompts} for the task of list reversal. By using recursion, we are able to generalize any base prompting approach (CoT in this figure) to much longer lists by breaking the input into smaller and smaller lists till we reach a list length where the model is highly accurate. Such recursive approaches can not be described by current methods such as CoT\xspace and standard prompting. Least-to-most prompting~\citep{Zhou2022LeasttoMostPE} also proposes a similar solution but differs in two key aspects (a) it has to identify all the sub-problems in one-shot instead of our iterative top-down decomposition (b) it has to learn to identify the relevant answers from the previous solutions which we get for free from our decomposition.
\begin{figure}[htbp]
    \centering
    \includegraphics[width=\linewidth]{images/reverse_decompv2.pdf}
    \caption{Sample prompt for recursive decomposition for reversing lists. Each list is split into two halves and each half is reversed and concatenated in the reverse order. We can recursively split a list till we hit the base case (lists of length 3 here) where existing approaches such as CoT are accurate.}
    \label{fig:reverse_prompts}
\end{figure}

\paragraph{External API Calls}

In certain cases, the sub-tasks may not be feasible to solve using only a LLM. E.g., retrieving knowledge from a KB or large corpus. Such sub-tasks, however, can be easily solved using existing systems such as retrieving documents using an Elasticsearch index or webpages using Google search~\cite{Lazaridou2022InternetaugmentedLM}.  Fig.~\ref{fig:hotpotqa_prompt_intro}  shows how \textsc{DecomP}\xspace\ can easily use such a system to retrieve the relevant documents and answer a single-hop open-domain question.

\begin{figure}[htbp]
    \centering
    \includegraphics[width=\linewidth]{images/hotpotqa_prompt_intro.pdf}
    \caption{A Decomposed Prompt to answer open-domain questions using Elasticsearch-based retrieval. Full usage of this prompt for open-domain multihop questions is given in Figure ~\ref{fig:hotpotqa_prompt_detailed}.}
    \label{fig:hotpotqa_prompt_intro}
\end{figure}

\section{Case Studies}
We showcase \textsc{DecomP}\xspace's strengths through four tasks; two symbolic manipulation tasks similar to those investigated in \cite{Wei2022ChainOT} and two existing textual multi-hop reasoning tasks. Unless specified, we use \texttt{text-davinci-002} InstructGPT3 model~\cite{Ouyang2022TrainingLM} as the LLM and report the Exact Match (EM) numbers, following prior work. For order-independent list answers, we evaluate set equality as EM. To show the value of decomposed prompting, we compare our approach to CoT\xspace rather than each specific decomposition structure used in prior work. The complete prompts for all our tasks are provided in App.~\ref{app:prompts}

\subsection[k-th letter concatenation (Hierarchical Decomposition)]{$k^{\mathrm{th}}$ letter concatenation (Hierarchical Decomposition)}
We compare \textsc{DecomP}\xspace to CoT\xspace prompting for concatenating letters at the $k^{\mathrm{th}}$ position. All prompts contain examples of concatenating letters in position 1, 4, and last position of strings with 3 words. We create three different prompts for all our baselines and present the average to account for variance due to the choice of examples following \cite{Perez2021TrueFL}. We use the \texttt{decomp}, \texttt{split}, \texttt{str\_pos} (further decomposed as shown in Fig.~\ref{fig:str_pos_prompts}), and \texttt{merge} prompts for decomposition prompting. We adapt the CoT\xspace for last letter concatenation from prior work~\citep{Wei2022ChainOT} for this task as shown below. In addition, we consider a \emph{rolled out} version of our decomposition prompts in terms of a CoT\xspace, i.e., we describe the entire decomposition process (identify words, split each word into letters, take $k^{\mathrm{th}}$ letter and concatenate) as a single CoT\xspace. e.g, for the question ``Take the letters at position 4 of the words in "Herbert Alexander Simon" and concatenate them using a space.'', we use the CoT\xspace:

\noindent \begin{minipage}{0.5\textwidth}
\textbox{19em}{\textbf{Chain-Of-Thought}\\
\small
The letter at position 4 of "Herbert" is "b". The letter at position 4 of "Alexander" is "x". The letter at position 4 of "Simon" is "o". Concatenating "b", "x", "o" using a space leads to "b x o". So, "Herbert Alexander Simon" outputs "b x o".
...}
\end{minipage}
\begin{minipage}{0.5\textwidth}
\textbox{19em}{\textbf{Chain-Of-Thought (rolled out)}\\
\small
The words in "Herbert Alexander Simon" are "Herbert", "Alexander", and "Simon". The letters and their positions in "Herbert" are "[(H, 1), (e, 2), (r, 3), (b, 4), (e, 5), (r, 6), (t, 7)]". The letter at position 4 in this sequence is "b". $\cdots$ outputs "b x o".
...}
\end{minipage}

We compare these three prompting techniques on 4 datasets to evaluate generalization along 3 axes: (1) unobserved letter position $k=3$\footnote{Note that none of the sub-task prompts contain examples for this position} (2) longer inputs, \#words=4 and 5 (3) new delimeter "semicolon". The words in the test examples come from a list of most popular first and last names.\footnote{\url{forebears.io/earth/forenames} and \url{forebears.io/earth/surnames}} All evaluation datasets have 100 examples. See Fig.~\ref{fig:letter_cat_results} for results.

\begin{figure}
    \begin{subfigure}{.5\textwidth}
    \includegraphics[width=\linewidth]{images/letter_cat_results_space.pdf}
    \caption{Space}
    \label{fig:letter_cat_results_space}
    \end{subfigure}
    \hfill
    \begin{subfigure}{.5\textwidth}
    \includegraphics[width=\linewidth]{images/letter_cat_results_semic.pdf}
    \caption{Semi-Colon}
    \label{fig:letter_cat_results_semic}
    \end{subfigure}
    \caption{EM Results on the $k^{th}$ letter concatenation task (k=3) with different values for N, the number of words in the input. \textsc{DecomP}\xspace\ always outperforms and generalizes better than CoT\xspace.
    }
    \label{fig:letter_cat_results}
\end{figure}

\textbf{\textsc{DecomP}\xspace outperforms chain-of-thought reasoning}, even when the chain-of-thought uses the same reasoning procedure as the rolled out decomposition. This shows that the separate prompts are more effective at teaching hard sub-tasks than a single CoT\xspace prompt.

\textbf{\textsc{DecomP}\xspace generalizes perfectly to longer sequences.} As the length of the input sequence increases, our approach continues to achieve close to 100\% accuracy on this task.
The CoT\xspace-based approaches drop noticeably in their scores with longer input lengths, widening the performance gap.

\subsection{List Reversal (Recursive Decomposition)}

We use the task of reversing lists of words\footnotemark
to show how recursive \textsc{DecomP}\xspace
enables length generalization.
We adapt the relevant CoT\xspace prompt from \citet{Wei2022ChainOT},
and integrate it in a decomposed prompt.
As a control, we also compare to a CoT\xspace version w/ rollout of our decomposed prompt.
All prompts contain the same 3 examples of reversing word sequences
with 3-5 items.
We evaluate all prompts for generalization
to 4, 6, 8, and 10-item sequences.
Here we use \texttt{davinci-001} to show that \textsc{DecomP}\xspace enables a weaker model approach \texttt{davinci-002}'s performance (which does solve this task). \footnotetext{We use the vocabulary from \citet{Wei2022ChainOT}: \url{https://www.vocabulary.com/lists/189583}} We use the strategy from Fig.~\ref{fig:reverse_prompts} and provide our prompts in App.~\ref{app:prompts}.
Figure~\ref{fig:reverse} shows the results of the prompting strategies on different input lengths.

\textbf{\textsc{DecomP}\xspace improves the length generalization of few-shot prompting.} While our base CoT prompt does not generalize at all to longer sequences, our approach can recursively decompose the problem and achieve better length generalization.

\textbf{CoT\xspace w/ rollout fails.}
The CoT\xspace version of our decomposition strategy fails
because the unrolled prompt becomes too long and convoluted
without the ability to abstract away sub-modules.

\begin{figure}[htbp]
    \begin{minipage}{.475\textwidth}
    \includegraphics[width=\linewidth]{images/reverse_barv2.pdf}
    \caption{EM results on reversing sequences. Incorporating CoT\xspace in \textsc{DecomP}\xspace greatly increases the ability of the model to generalize to new sequence lengths.}\label{fig:reverse}
    \end{minipage}
    \hfill
    \begin{minipage}{.475\textwidth}
    \includegraphics[width=\linewidth]{images/commaqa_results.pdf}
    \caption{EM results on the CommaQA-E datasets. \textsc{DecomP}\xspace\ always outperforms CoT\xspace, with fine-grained marginally out-performing coarse-grained decomposition.}\label{fig:commaqa_results}
    \end{minipage}
\end{figure}

\subsection{Long-Context Question Answering}
We next evaluate on the CommaQA-E dataset \citep{Khot2022HeyAC} under the reading comprehension setting. The dataset consists of synthetically generated entities (e.g. Erowid award), facts (``Wetherality was an actor in the movie Dewbar.'') and multi-hop questions (e.g., ``What awards have the actors of the Erowid winning movies received?''). Due to the presence of many distractors and, as a result, longer context, this dataset has been shown to be hard for standard LMs even when fine-tuned.

To fit these questions within GPT3's context limit (2049 tokens), we generate a smaller version of the CommaQA-E dataset and of the compositional generalization split such that we can fit at least four examples in the context for CoT\xspace prompts. For the question ``What awards have movies produced by people born in 1910 won?'', the CoT\xspace is:
\textit{The people born in 1910 were Muntaril and Teeplemole. Teeplemole produced the movies Featsaw and Zalate. Muntaril produced the movie Premercy. Featsaw was awarded the Zorgion award. Premercy was awarded the Chowwurst award. Zalate was awarded the Hallowcock award. So the answer is ["Zorgion", "Chowwurst", "Hallowcock"].}

\begin{figure}[htbp]
    \centering
    \includegraphics[width=\linewidth]{images/commaqa_decomp_only.pdf}
    \caption{Sample prompts used for the CommaQA dataset. On the left, the coarse-grained decomposition defines a single QA sub-task with all single-hop questions being delegated to a single sub-task handler. On the right, the fine-grained decomposition assigns questions to three different sub-tasks (see App.~\ref{app:prompts} for their prompts) depending on the question type. This allows us to provide more examples for each question type allowing the model to learn the sub-task more effectively.}
    \label{fig:commaqa_prompts}
\end{figure}

For \textsc{DecomP}\xspace, we can separate the task of decomposition (independent of the context) from the sub-tasks of single-hop question answering. As shown in Fig.~\ref{fig:commaqa_prompts}, we provide examples of the context-independent decomposition in the decomposer prompt and use the separate sub-task prompts to teach the QA skill over the given context. Additionally, we can choose the granularity of decomposition to trade off human effort for increased accuracy. For example, we could have single QA prompt to handle all the questions or create QA prompts for different classes of questions. In our experiments, each sub-task prompt contains 8 QA examples (2 questions/para) (see App.~\ref{app:prompts} for the prompts). We evaluate three different prompts and report the average results in Fig.~\ref{fig:commaqa_results}.

\textbf{\textsc{DecomP}\xspace is more accurate than CoT\xspace on CommaQA.} Irrespective of the granularity of decomposition or the evaluate split, our approach outperforms CoT\xspace on this task.

\textbf{Finer grained decomposition can help improve performance}. Our fine-grained decomposition can provide more examples for each class of questions resulting in increased single-hop QA performance and as a result increased performance on CommaQA.

\textbf{\textsc{DecomP}\xspace also generalizes to new compositions.} Compositional generalization split of CommaQA uses the same relations as the training set but with new compositions. While CoT has a drop in score, both decomposition-based approaches even have slightly better scores (the subset of relations used in Comp. Gen split are easier for our specialized QA models).

\begin{figure}[htbp]
    \centering
    \includegraphics[width=\linewidth]{images/hotpotqa_prompt_detailed.pdf}
    \caption{The prompt used to answer open-domain multihop questions using Elasticsearch-based retrieval. The \texttt{retrieve\_odqa} prompt is given in Figure~\ref{fig:hotpotqa_prompt_intro}.}
    \label{fig:hotpotqa_prompt_detailed}
\end{figure}

\subsection{Open-Domain Question Answering}
\label{subsec:hotpot}

Next, we demonstrate the ability of our approach to integrate external API calls on the task of open-domain multihop question answering. We evaluate our approach on the HotpotQA\xspace dataset
under the \texttt{fullwiki}  setting that requires relevant paragraphs to be retrieved from a Wikipedia corpus. We use the code-davinci-002 model here since it can fit the much longer contexts needed here.

Fig. ~\ref{fig:hotpotqa_prompt_detailed} shows the decomposition prompt we use.
The decomposer generates (singlehop) sub-questions and delegates them to \texttt{retrieve\_odqa} (described in Fig.~\ref{fig:hotpotqa_prompt_intro}).
As we showed earlier, this module retrieves relevant documents
then uses an RC model to answer.
\texttt{retrieve\_odqa} returns both the answer and the documents, allowing subsequent sub-questions to use the answers (e.g. ``Mack Rides'') and the \texttt{multihop\_rcqa} model to use the documents

We implement the final \texttt{multihop\_rcqa} model in two ways: (i) prompting the model to generate the answer directly (\textbf{Decomp-Ctxt QA}) as shown in Fig.~\ref{fig:hotpotqa_prompt_detailed} and (ii) prompting the model to generate the Chain-of-Thought (\textbf{Decomp-Ctxt CoT QA}) (e.g. ``The Lost Gravity was manufactured by Mack Rides. Mack Rides is a German company. So the answer is: Germany."). We compare our approach against two baselines: \textbf{A. No Context (No-Ctxt),} A closed-book setting baseline where the model must rely only on its parametric knowledge. \textbf{B. NoDecomp Context (\textbf{NoDecomp-Ctxt}),} A simple retrieval baseline where we retrieve K (set to 8) paragraphs using the multi-hop question as the input and use that as context. In both these baselines, we consider the QA and CoT\xspace QA variants.

We manually annotate CoTs and decompositions for 25 training set questions, and sample 3 prompts of 15 questions each for all approaches. The detailed prompts are given in the Appendix \ref{app:prompts}.  We evaluate on the subset of bridge questions from our held-out dev questions (248/300) i.e. questions where answer for the first sub-question is needed for the second sub-question (as in our example). On the comparison questions in HotpotQA (e.g. ``Who is older Jeremy Horn or Renato Sobral ?''), the relevant entities are clearly mentioned in the question and do not necessitate multi-step retrieval.\footnote{We did evaluate our approach on `comparison' questions and, as expected, our performance is comparable to the NoDecomp-Ctxt baselines.}

\begin{figure}[htbp]
    \centering
    \includegraphics[width=\linewidth]{images/hotpotqa_results.pdf}
    \caption{Answer F1\protect\footnotemark for comparison questions on open-domain setting of HotpotQA for three randomly sampled sets of prompt examples. (Left) Standard (non-CoT) variants (Right) CoT variants. Decomp-Ctxt models (ours) significantly outperform the corresponding No-Ctxt models, and also our strong baselines of NoDecomp-Ctxt models.}
    \label{fig:hotpotqa-results}
\end{figure}
\footnotetext{Answer F1 is computed by treating prediction and ground truth answer as bags of tokens and computing their precision and recall~\cite{rajpurkar-etal-2016-squad}. See HotpotQA~\cite{hotpotqa} for details.}

\textbf{Results} are presented in Fig.~\ref{fig:hotpotqa-results}. The NoDecomp-Ctxt models perform significantly better than No-Ctxt models in both QA (i.e. standard prompting) and CoT variants showing that external knowledge can be leveraged to improve standard and CoT based open-domain mulithop QA. Furthermore, our Decomp-Ctxt models are yet better at leveraging external knowledge than a strong retrieval baseline (NoDecomp-Ctxt), regardless of whether we leverage CoT jointly with our approach or not.

\section{Conclusion}
We proposed a new approach, Decomposed Prompting, to solve complex tasks using few-shot prompts, by decomposing them into a prompting program built out of simpler sub-tasks. Drawing inspiration from software libraries, our decomposer and shared sub-tasks are designed in a modular fashion: they use their own few-shot prompts, allowing one to independently optimize each prompt, decompose a sub-task further if necessary, or even seamlessly replace it with a symbolic system. We show that Decomposed Prompting\ outperforms prior work on four different tasks and generalization settings, establishing it as an effective few-shot paradigm for solving complex tasks.