When Splitting Makes Stronger: A Theoretical and Empirical Analysis of Divide-and-Conquer Prompting in LLMs
Authors: Yizhou Zhang
Defu Cao
Lun Du
Qiang Fu
Yan Liu
Venue: COLM 2025 (2025)
Keywords: Program-guided Prompt
Divide-and-Conquer
Foundation Model
Large Language Models
Deceptive content
TL;DR: This paper examines when divide-and-conquer (DaC) prompting is beneficial for LLMs. Through theoretical and empirical analysis, we identify specific task types where breaking inputs into sub-parts improves performance.

Abstract: Foundation models, particularly Large Language Models (LLMs), have garnered significant interest due to their wide range of applications.  Yet these models demonstrate notable weaknesses when confronted with tasks involving iterative sub-problems or deliberately misleading content—exemplified by complex arithmetic operations and comprehensive fake news evaluation. 
Conventional instructional prompting frequently produces flawed outputs in these scenarios. While research has established that advanced techniques such as Chain-of-Thoughts and Least-to-Most methodologies can dramatically enhance LLM performance, emerging investigation indicates that a more streamlined divide-and-conquer (DaC) approach—which systematically partitions input sequences into discrete components—can yield remarkable improvements for particular problem classes like misinformation assessment. Our investigation rigorously examines the efficacy of DaC prompting strategies and precisely delineates the task characteristics that benefit most from this methodology. Through comprehensive theoretical analysis, we establish formal guarantees for performance enhancement in specifically identified task categories. We validate our theoretical framework through focused empirical studies on large integer multiplication and factual verification tasks, where experimental outcomes robustly confirm our analytical predictions, demonstrating DaC's practical superiority in these challenging domains.

Published as a conference paper at COLM 2025
When Splitting Makes Stronger: A Theoretical and Empirical Analysis of Divide-and-Conque Prompting in LLMs
Yizhou Zhang 1.t
Defu Cao², Lun Du Qiang Fut, Yan Liu?
Variational Al
University of Southern California
3 Ant Research
*Microsoft Research {zyizhou96, dulun28344 @mgai com, gifulmicrosoft.com {de yanliu.... os @usc. edu
Abstract
Foundation models, particularly Large Language Models (LLMs), have garnered significant interest due to their wide range of applications. Yet these models demonstrate notable weaknesses when confronted with tasks involving iterative sub-problems or deliberately misleading contett-eeemllifee by complex arith- metic operations and comprehensive fake news evaluation. Conventional instruc- tional prompting frequently produces flawed outputs in these scenarios. While research has established that advanced techniques such as Chain-of-Thoughts and Least-to-Most methodologies can dramatically enhance LLM performance, emerging investigation indicates that more streamlined divide-and-conquer (DaC) approach- which systematically partitions input sequences into discrete compo- nents-can can yield remarkable improvements for particular problem classes like misinformation assessment. Our investigation rigorously examines the efficacy of DaC prompting strategies and precisely delineates the task characteristics that ben- efit most from this methodology. Through comprehensive theoretical analysis, we establish formal guarantees for performance enhancement in specifically identified task categories. We validate our theoretical framework through focused empirical studies on large integer multiplication and factual verification tasks, where experi- mental outcomes robustly confirm our analytical predictions, demonstrating DaC's practical superiority in these challenging domains.
Introduction
Large language models (LLM) based on the Transformer architecture have led to major breakthroughs in natural language processing and other related fields in artificial intelligence (Jiang et al., 2025; Brown et al., 2020; Radford et al.: Touvron et al., 2023; Cao et al., 2024b). State-of-the-arr general- purpose language models have demonstrated remarkable advancements in various domains, including question answering, graph learning, reading comprehension, text generation, and machine translation (Darm et al., 2025; Cao al., 2024a; Chen et al., 2024; Tan al., 2023; Hendy et al., 2023; Mao et al., 2023; Zong & Krishnamachari, 2023; Jia et al., 2024; Zhang et al., 2023a). Their remarkable adaptability stems not only from architectural innovations but also from increasingly effective prompting strategies that unlock their reasoning capabilities. These developments paves the way towards general general-purpose -purpose problem solvers (Li et al., 2024; Bubeck et al., 2023).
However, as pointed out in (Wei et al., 2022), significant challenges emerge when applying even the most advanced LLMs to tasks involving extended solution paths, particularly those requiring sophisti- cated mathematical reasoning or complex knowledge integration. A series theoretic works attribute this challenge to Parallelism Tradeoff (Merrill Sabharwal, 2023), a fundamental limitation of Transformers. Specifically, unlike Recurrent Neural Network, whose computational depth is linear to the input sequence length (i.c., the depth is O(n), where n is the input sequence length). Transformer does not contain any recurrent structure. Such design, while achieving superior parallelizability than
Yizhou Zhang's 's work was done during his PhD program University of Southern California and internship in Microsoft. Lun Du's work done when he previously worked in Microsoft.

---

Published as a conference paper at COLM 2025
Task: Verify the truthfulness of summary.
Example Divide-and-Cone Conquer Problem Solving
#Muerial:: Mansille, Franse (CNN)The Ereech prosecator leading invesigation ana crshh Genmawwagg Flight 9525 isssied... poteearee
so vićeos
Sub-tack I:
wete used... aoded. penson invesigatos" Marc Mosiclin.... the report were "corspleely wrong" ...
video
aive to the
claim contradict with the material? #Clain video shawing final memeets Germanving Flight 9525 inrestigators from the wreelaage site. Yos, the contrd
by
Example of Entangled Problem Solving
meterill The moterial stores that Marseille ofany video foorago thom
#Sunnarsh: video showing fiaal moments Gee Geemannigg Flggn u525
drom the who delbbuustl
by
Masscill
Briez
prosecutor fiicc Rohin insited that was
ontrond
and that stilens were seal the involigation Hoseever clém stmoe cidko shoncing final momente Cermanse
inmeddatte.. Andress Lubizz, plant had
severe depressou
9525 has been Nabbrack 3:
investgattons comm
saicidal testencies
@: You are the materfal and sommary. Please
Ai contain cluiss contendicted with material?
Does
Broe the claim 2 contratict with the materialt of Tallm 240
leeaa the provited dinement the
tendercies the cogglln, Andreas Lubrzz
Grnennaaiigg Flight 9525,
cuteriaal coutines listory depression and suiedaa
the
showing the fixal
claics costrndicedd
Nabbcask
Illssdd the provited docemenn the -....om.........................
Bres the claim 3 contradict with the materiall
Figure I: An illustrative example of hallucination detection with entangled problem solving (i.e.. directly forward all inputs into the LLM) and divide-and-congee problem solving (i.e., divide the problem inputs into parallel sub-tasks and tackle them in parallel). The sentence marked with red font in the material is the evidence that contradicts the first claim in the summary, which is marked with red font.
RNN, makes Transformers suffer from limited expressive power Merrill & Sabharwal proved that the expressive power of fixed-depth log-precision Transformer, which is very close to the most com- monly applied Transformer architecture for LLMs, is bounded by constant-depth logspace-unife uniform threshold circuits. This theoretical ceiling explains why these models struggle with tasks requiring extended sequential reasoning or precise tracking of long dependency chains, despite their impressive performance on many natural language tasks.
To address this challenge, carefully designed prompting strategies have been developed to tackle tasks that require stronger expressive power (Wang et al., 2025; Feng et al., 2023). A series of works focus on prompting the LLM with instructions or context samples to output the intermediate steps that derive the final answer in an autoregressive manner, such Chain-of-Thoughh (CoT) (Wei et al., 2022; Wang et al., 2022; Zhou et al.; Chen et al., 2023). Some works further apply programs to guide LLM to strictly follow designated reasoning steps (Yao et al., 2023). Theoretically, these prompting strategies convert the role of the Transformer from complete problem solver to sub-proble problem solver in dynamic programming or tree searching algorithm (Peng et al., 2024; Merrill & Sahharwal, 2024). In this way, these prompting strategies expand the expressive power of the LLMs and successfully improve the reasoning and searching of LLMs (Feng et al., 2023; Ye et al., 2024).
In contrast to methods that employ instructions, contextual examples, programs to decompose reasoning processes into sequential intermediate steps, researchers have discovered that for certain tasks, LLM performance can be significantly enhanced through fundamentally different approach: dividing input sequences into multiple sub-inputs and then merging the responses generated for cach sub-input, as illustrated in Fig. 1. For example, Cui al. proposes that in automated evaluation, LLM's performance can be further boosted by first dividing the input text into sentences and then evaluating them one by one. Intuitively, this paradigm benefits the tasks in way similar human brains, especially when the tasks are too hard or too complex. For example, when reviewing a long academic paper, some reviewers produce low-quality reviews (Garcia et al., 2021; Tennant & Ross-Hellauer, 2020; Cortes& & Lawrence, 2021) containing hallucination-lin like intermediate errors, such as pointing out some 'missing baselines' that have already been sufficiently discussed by authors. To avoid such mistakes, experienced reviewers usually think slowly (Kahneman, 2011 1) to follow Divide-and-Conquer paradigm to handle this task. Specifically, they decompose the paper review as examinations of multiple central opinions and then retrieve corpus to verify them respectively.
However, unlike Chain-of- Thhoughtss, whose advance in expressive power is supported by theoretical analysis (Feng et al., 2023), the performance boost from the Divide-and-Congee paradigm lacks rigorous theoretical support. This theoretical gap leaves practitioners without clear guidance regarding the specific conditions under which DaC prompting provides demonstrable advantages over alternative approaches. To tackle this challenge, in this paper, we aim to understand the utility of DaC prompting. More specifically, we attempt answer the following two research questions:
2

---

Published as a conference paper at COLM 2025
1. RQ1: Compared to straightforward instructional prompting, does DaC have theoreti- cally guaranteed advantages similar as CoT and its variants?
2. RQ2: Compared CoT and its variants, what utility and limitations does DaC have?
To answer these questions, we first provide theoretical paradigm that can help us analyze how the divide-and-conquer strategy expands the expressive power of fixed-depth peg-precision Transformer on a given task. In this way, we provide a framework that can provide a theoretical guarantee to the DaC paradigm in various tasks. In this way, we present some conditions under which DaC have advantages compared to other prompting strategies. We then empirically evaluate DaC prompting and representative baselines on tasks that satisfy the proposed conditions and are challenging to existing prompting strategies even on state-of-the-arr LLMss Large Integer Multiplication, Hallucination Detection, Article-level Fact Verification (Cheng & Zhang, 2023; Li et al., 2023a; Wadden al., 2020; Hu et al., 2024; Wu al., 2023). These tasks either require very long reasoning paths (e.g.. large integer multiplication) or contain deceptive contents (e.g., hallucination detection and fact verification), making existing methods like Chain-of-Thouge prompting prone to intermediate errors. Importantly, these empirical findings align precisely with our theoretical predictions, confirming that DaC's s advantages manifest most strongly in tasks featuring independent subtasks prone to intermediate errors e
exactly as our theoretical framework anticipates.
Substask
Sub- Sub-Solution
Sabtack Solution
Intemnedinc
Imput
Input
Inpur
Input
Vate
Outpul
Ouipul
Ourput
Octput
Output
(A). COT
(B). Least Most
(C), COT-SC
(D). Tree of thought
(E). Divide and Conquer (Ours)
Figure The comparison between DaC and the existing methods for prompting. The ellipse marks represent sub-tasks, the right-angled rectangles represent sub-task solutions, and the rounded rectangles represent intermediate steps that entangle sub-task and sub-solutions. The different shades in Tree of Thoughts (subfigure D) indicate the rates of different search directions. In CoT (Chain- of-Thuughts), CoT-SC, and ToT, the Large Language Models must simultaneously generate and resolve sub-tasks. Least-to-Mor to-Most (also Decomposed Prompting) disentangles sub-task generation and resolution. However, its sub-task resolution and resolution assembly process are intertwined as sequentially attaches new sub-tasks onto the previous resolution. Different from them, DaC totally disentangles the sub-task generation, sub-task resolution, and resolution assembly process.
2 Related Work
2.1 Expressive Power of Transformer
As discussed in previous works (Merrill & Sabharwal, 2023; Young, 2025; Feng et al., 2023; Yang et al., 2024), the expressive power of fixed-length log-precision transformers, which are widely applied in modern Pre-trained Large Language Models, is actually much more limited than people's expectations. Merrill & Sabharwal gives a theoretical proof that the expressive power of fixed-length log-precising transformers upper-bounded with TC", Feng al. further extends their analysis to explain that lot of common problems exceed the expressive power of fixed-length log-precision transformers. Such results explain why the powerful LLM may make some ridiculous mistakes and how CoT improves the performance.
2.2 Prompting Strategies of LLM
In this sub-section, we introduce the existing prompting and discuss their limitations and drawbacks. Following the notations in (Yao et al., 2023), denote the Large Language Models with parameter
3

---

Published as a conference paper at COLM 2025
0 pa and use lower case letters x, y, to denote input sequence. result, and intermediate steps, respectively.
Input-Output (IO) Prompting is the standard prompting strategy that attach input x with instructions and/or few-shot in-context-lcarning examples to aqcuaire a prompt, denoted as prompt(2) (Yao et al., 2023). The LLM takes prompt(x)) as input and predict result, i.e. y po py)yprrop)(()))
Shain-of-Thoughee (CoT) Prompting (Wei et al., 2022) aims at simulating humans' thinking process that handles complicated tasks (e.g., combinational reasoning and mathematical calculation) in step-by-step manner. More specifically, the LLM is guided to output a series of intermediate steps 21, 22, nn (also known as thoughts) autoregressively, i.e. 2;
(x), =1, -.., Z;-1). Then the LLM output the prediction of result y based on the thoughts, i.c. y ~ pe (zi (r),
Zn). Exploration-of-Thoughh (EoTT) Prompting and Program-guided Prompting are two variants of COT. EoT includes series of CoT's variants, such as Self-consistency with CoT (CoT-SC), prompting (Wang et al., 2022) and Tree-of- Theeuhhss (ToT), prompting (Yao al., 2023), which aim at addressing the limitation of CoT in exploration. Their common central idea is to generate multiple chains of thought through sampling or proposing prompting, and then ensembling them to acquire a final prediction. Program-guided Prompting aims at controlling the LLM'' generation process with symbolic programs or pre-defined procedures (Zhu al., 2023; Jung et al., 2022; Zhou et al.; Khot et al., 2023; Creswell & Shanahan, 2022: Gao et al., 2023). Among them, the Least-to-Man Most (LIM) Prompting (Zhou et al.) and Decomposed Prompting (Khot et al., 2023) are close to this work. They the earliest attempts that explicitly prompt the LLM to decompose the task as series of sub-tasks and sequentially tackle them. LIM prompts an L.M to iteratively raise sub-tasks and sequentially solve them acquire the final resolution. Decomposed Prompting can be regarded as an upgraded version of LTM. It introduces special notations into the prompt to represent program states and thus can call itself (i.e., recursion) or other modules (i.e.. hierarchical decomposition), endowing it with stronger expressive power. Such a design increased the compositional generalization ability of LLMs in different areas, such as symbolic manipulation and multi-hop QA (Khot et al., 2023).
The aforementioned CoT and EoT families incorporate LLM with stronger expressive power than IO prompting. However, a critical issue of them is that, they could miss or ignore some important intermediate steps or contents (Paeng & Kwon, 2024; Liu et al., 2023). This problem is even worse when we are handling tasks involving long input (e.g.. long documents and large numbers). Typical examples include large number arithmetic calculations and fact verification in long documents. Compared to them, Least-to-Most prompting and Decomposed Prompting introduce explicit task decomposition to enumerate sub-tasks. However, their task decomposers are based multi-round conversation or question-answering which navigate the L.LM through the deceptive content's 's flow sequentially, and propagate the hallucinatioondecceptooo in the contexts (Dziri et al., 2024; Yang & Ettinger, 2023), leading to decreased performance.
3 Preliminary of Divide-and-Conquer Prompting
In this section, we summarize and formalize Bivide-and-Conquee prompting strategy. Unlike Tree of Thoughts (ToT), which interweaves reasoning with exploratory search, Sriiide-and-ooqquee prompting strategy consists of three distinct stages: task decomposition stage, sub-task resolution stage, solution merge stage. In task decomposition stage, the L.M is prompted to explicitly decom- pose the task as a series of parallel homogeneous sub-tasks with smaller problem sizes (e.g. divide a long paragraph to sentences). Such design avoids the multi-round conversation or question-answent in LLM and Decomposed Prompting, making the model less prone to deception. After that, in sub-task resolution stage, the LLM is prompted to provide the solutions for every sub-task. Finally, in the solution merge stage, the LLM is prompted to assembly the solutions of subtasks and acquire the final answer. To tackle tasks of different sizes, Divide-and-Conquu be divided to two variants: Single-Level DaC Solver and Multi-I DaC Solver. Note that DaC requires additional tokens for sub-task decomposition and solution merging, but it reduces the average decoding context window size during sub-task resolution.
prompting strategy can
Single-level Divide-and-Conque the original task as a tree of one level. The algorithm is presented in the Alg. 1. The advantage of this variant is its simplicity and efficiency. However, when the original input too long, lenele- Dnd Bovidu-and-Conquer Solver may acquire sub-tasks with large problem sizes that will still trigger intermediate errors. In such case, following (Khot et al., 2023), can recursively expand the
Solver decomposes the task in one call to the LLM, which expands
4

---

Published as a conference paper at COLM 2025
Algorithm Single-Level Divide-and-Conque Solver a,,,
Require: Input Sequence S, Prompt m (for solution merge), Prompt (for sub-task task tackling), Prompt d (for task decomposition), LLM L
Ensure: Results of the task on input sequence S
1: {S1, 52,, 5x} <- L(d,s)
2: Result f- ?
3: for = 1,2, ..., do
4: Result < Result +[SEP] + S(),
5: end for
6: Return L(m, Result)
task as multi-level tree. More specifically, we repeat the aforementioned steps to further divide the sub-tasks hierarchically until they are easy enough to be handled by the LLM. This can be done through recursive program presented in Alg. 2. More discussions the proposed method's application scope, including its comparison with other prompting strategies and limitations, can be found in A.I.
Algorithm 2 Multi-Level Divide-and-Conquer Solver Recursion T(S, m, f, f, f,
Require: Input Sequence Problem Size Metric Function f(-) function that measure the problem size), hyper-parameter w, Prompt m (for merge), Prompt (for sub-task tackling), Prompt d (for task decomposition), Large Language Model
Ensure: Results of the task on input sequence
1: S2, ..., Sg f- Sd)
2: Result f- Ø
3: for == 1,2, ..., do
4: if f(,) w then
5: Result + Result + +SEEP| + T(S m, m,t,
6: else
7: Result < Result [SEP]] + Ltt,
8:
end if
9:
end for
Return L(m, Result)
4 Theoretic Analysis
In this section, we provide theoretic analysis to the utility and limitations of the Divide-and-Comque prompting. In the first subsection, we provide comparison of IO prompting (common fixed-length instructional prompting) and DaC prompting in expressive power perspective. This part answers the first research question: the expressive power of IO prompting is subset of DaC prompting. In the second subsection, we provide a comparison between Chain-of-Thoughhe and DaC prompting in expressive power. Our comparison suggests that, although the expressive power of DaC prompting subset of Chain-of-Thougee
for tasks satisfying specific conditions, DaC prompting the problem with lower average context window length when decoding the tokens. Such property is empirically proved to be helpful for reducing the intermediate error and thus boost the performance.
solve
4.1 Divide-and-Come Connuuer I0 Prompting
We show that the expressive power of Divide-and-Comee is stronger than IO Prompting: We denote the set of problems that a fixed-precision transformer with fixed-length IO prompting can tackle S(IO). Similarly, we denote the set of problems that fixed -eed-precision transformer with DaC prompting can tackle S(DaC). Then we have the following results:
S(10) c TC c NC C S(DaC)
The function f(-) and the hyper- parameter to are task dependent and are often determined empirically based on the capabilities of the specific I.IM being used (c.g.. the number of digits where an L.M'' multiplication accuracy drops, the length of text segment beyond which verification quality degrades).
5

---

Published as a conference paper at COLM 2025
Proof Sketch: The conclusion that S(OO) C TC is corollary of the main results in (Chiang al., 2023). In this paper, mainly focus proving NC¹ C S(DaC). This is significant because it establishes a rigorous computational complexity boundary between these prompting paradigms. Specifically, we exploit 2-color Binary Subtree Isomorphism (2-BSI) problem for the proof. In (Jenner et al., 2003). 2-BSI problem is proved to be an -Cmmpeeee problem. Its definition is: 2-color Binary Subtree Isomorphism problem is that, given a pattern 2-colorbinary tree tp and a base 2-color binary tree fj. solver is required judge whether the pattern tree is isomorphic to a sub-tree of lb In (Jenner et al., 2003), the authors pointed out that the encoding of the problem will influence the hardness of the problem. In this paper, focus pointer list encoding of 2-BSI. Detailed information about the pointer list encoding of 2-BSI can be found in Appendix. For pointer list encoding of 2-BSI, we have the following theorem:
There exists a log-pre log-precision transformer with fixed depth L and hidden dimension d that can solve the 2-BSI of any size with fixed-length prompt mI (for merge), / (for sub-task tackling) and d (for task decomposition). Proof Sketch: The detailed proof is provided in the Appendix A.2. Here we give a brief flow of the proof. To prove this theorem, we first show an algorithm that can solve the problem with divide-and-conquu strategy. Then we prove that there exists a log-precision transformer with fixed depth and hidden dimension that can express the modules in the algorithms with different but fixed-length prompts. In this way, can prove the theorem.
With the above theorem, we can prove that NC S S((DC), which finishes the proof. With this theoretic results, we can answer the RQ 1:
Compared to 10 prompting, DaC have theoretically guaranteed advantages in expressive power.
4.2 DaC vs. CoT
In this section, we compare Soride-and-Conquee with Chain-of- Chain-of-Thoughss in order to understand the utility and limitation of DaC prompting. The limitation of DaC prompting is that its expressive power is a subset of CoT prompting: We denote the set of problems that a fixed-precision transformer with DaC prompting can tackle S(DaC). Similarly, we denote the set of problems that a exed-precision transformer with CoT prompting can tackle as S(Co'T)) Then we have the following results:
S(DaC) S S(CoT)
(2)
The proof of this proposition is very straightforward. For any problem that DaC can solve, we can concatenate all outputs of LLM in dividing, tackling and merging as a sequence. Then we can prompt LLM with CoT to output this sequence. Thus, the problem set that DaC can resolve is a subset of COT.
The limitation revealed by the above theorem shows that compared to CoT, the appliance scope of Swvide-and-Conuue is limited. However, by analyzing the average decoding context window size, we show that on specific tasks, divide and conquer can reduce the problem complexity: Decoding Context Window Size: In auto-regressive decoding, each token is decoded from a window that covers all previous tokens. We denote the length of the window the Decoding Context Window Size of the token. Suppose that a task contains k sub-tasks, each of which does not rely on the answers of other sub-tasks. We define such sub-tasks as parallel sub-tasks. If an LLM tackle these sub-tasks sequentially with CoT, then the average decoding context window size of the sub-tasks'
-- where r; is the length of the response to the i-th sub-task and C is the length of input context. if we tackle them parallely with DaC, then the average decoding context
Σ 2
resolution will be C C+
window size of the sub-tasks" resolution will be C 5 (r: 1)? < C+ Ei n=
2
The above proposition shows that when task contains a large amount of parallel sub-tasks, DaC is more helpful for reducing the average decoding context window size than COT. Existing works have empirically showed that long decoding context window will propagate intermediate errors and thus increase the probability of generating hallucination (Yang & Ettinger, 2023). Thus, we can acquire a
TC represents problems solvable by constant- depth threshold circuits and is often associated with tasks like multiplication. NC1 represents problems solvable by logarithmic-dege depth circuits, indicating high parallelizability. The known inclusion TCº C NC1 is crucial as it formally places the expressive power of DaC, prompting in higher complexity class than standard I/O prompting.

---

Published as a conference paper at COLM 2025
conclusion that DaC is competetive on tasks that contain large amount of parallel sub-tasks and are bothered by intermediate errors and hallucination. With these theoretic results, we can answer the RQ 2:
Compared to CoT and its variants, DaC prompting's 's expressive power is weaker. However, on tasks containing large amount of parallel sub-tasks, DaC is more helpful.
4.3
Advantages of DaC
The above analysis answer the research questions that proposed. By summarizing these two answers, we can acquire the two conditions such that when a task simultaneously satisfied both conditions, DaC bring performance boost:
Condition the task harder than S(1O), such as TC -complete problems and NC². complete problems.
Condition 2: the lask contains large amount of parallel sub-tasks and is bothered by hallucinations or intermediate errors.
In Tab. 1, we present some sample tasks that satisfied the conditions. Also, we list some tasks that typically do not satisfy the conditions. This is helpful for guiding prompt engineering. Details are provided in Appendix A.7.
Experiments
Our experiments are specifically designed to test the boundaries identified in our theoret- ical analysis. We selected tasks that directly correspond to the conditions outlined in Sec- tion 4.3. For integer multiplication (a TC²_ complete problem), we strategically chose operand sizes that push beyond the reliable capacity of standard prompting to verify the theoretical complexity boundaries. For fact verification, we constructed test cases that re- quire parallel verification of multiple claims, directly testing DaC's advantage in handling independent subtasks. Our evaluation metrics edit distance for arithmetic and F Fl/precision/recall for verification tasks were chosen to directly measure the impact reduced intermediate errors, which our theory predicts should be DaC's primary advantage.
Applicable Tasks
Non-Applicable Tasks Integer Addition Multi-round QA Planning
Integer Multiplication Fact Verification Consistency Evaluation
Table 1: We list some example tasks that satisfy the conditions and some tasks that do not satisfy the conditions.
5.1 Case Long Integer Arithmetic
In this case, consider two tasks in long integer arithmetic: Multiplication, which satisfy the conditions we proposed, and Addition, which does not satisfy the first condition Our experiment results will show that DaC prompting brings a performance boost multiplication and does bring a boost on integer addition.
Task Setup: For this task, randomly generated 200 pairs of 5-digit integers. We choose for the digit length because according to previous works, ChatGPT-3.5 gets 0% accuracy on 4- digit multiplications (Cheng & Zhang, 2023), and ChatGPT-4 gets close to 0% accuracy 5-digit multiplications (Yang et al., 2023). We evaluate the performance with Edit Distance (Marzal & Vidal, 1993; Schaeffer al., 2023).
Setup of baselines and DaC: In this task, our baselines include IO prompting, Chain of Thought (CoT), CoT-SC, Least-to-Most (LtM), and Decomposed Prompting (DeP). Tree-of-Thnne Tree-of-Thoughts is not applicable. This is because that multiplication is deterministic calculation without requiring search in a tree. For DaC, we apply Multi-Level Divide-and- antn--u mrogram-guided solver.
Multiplication is TCC-complett problem and can be divided to multiple parallel sub-tasks, while Addition in ((TO) al. (2023)

---

Published as a conference paper at COLM 2025
GPT-3.5-Turbo GPT-4
GPT-3.5-Turbo
GPT-4
Edit Distance
Edit Distance
La5
4-
Lo0-
0.5-
0.58
025
020
10 CoTCoT-SCLLM DeP DaC
CoTCOT-SCLLM
DeP DaC
(a) Edit distance DaC and baseline prompting strategies on GPT-3.5 and GPT-4 for Multiplication.
(b) Edit distance of DaC baseline prompting strategies on GPT-3.5 and GPT-4 for Addition.
Figure 3: Performance of different prompting strategies on long integer multiplication.
Strategies
GPT-3.5- -urbo
GPT-4
F1
Acc
Prec
Recall
F1
Acc
Prec
Recall
10-rrompting
61.69
61.27
62.11
61.28
64.07
72.66
93.41
48.76
Chain-of-Thouggh
46.85
64.26
91.36
31.50
71.05
76.10
90.08
58.66
CoT-SC
47.70
64.25
88.83
32.60
71.39
76.36
90.41
58.98
-hoouhf-T
70.40
59.91
55.83
95.34
69.41
71.73
75.53
64.28
Least-to-Man Most
56.43
64.91
74.42
45.44
72.51
77.11
90.74
60.38
Dividc-and-Conque
74.84
75.55
77.41
72.03
76.92
78.99
85.36
70.01
Table 2: Performance of different prompting methods on HaluEval dataset.
Results: Experimental results are shown in Fig. 3(a) and 3(b). As we can see, for integer addition which does not satisfy our proposed conditions, the performance of DaC. CoT and its variants does not significantly outperform IO prompting for both ChatGPT-3.5 and However, for integer multiplication which satisfy our proposed conditions, under all settings, our proposed prompting strategy outperform all the baselines. This phenomenon indicate that our proposed conditions are useful for recognizing the tasks where DaC is more powerful.
5.2 Case 2: Fact Verification of Long Text
In the previous section, we show that for arithmetic tasks, our proposed conditions are discerning the tasks where divide-and-conquer has advantages. In this section, we further present how our conditions can be applied to natural language tasks. Specifically, we present the performance of baselines and Srride-and-Congeee to whether long corpus is aligned with base knowledge. This task satisfied the proposed two conditions. For the first condition, we can reduce 2-BTI problem to fact verification by describing the two trees with natural language. In this way, we can convert the trees to two paragraphs, and what we need to do is to ask the LLM to judge whether the two paragraphs are aligned or not. For the second condition, since are tackling long text, each sentence can be regarded as a parallel sub-task. We select two benchmarks of fact verification: Fact- Verification for Hallucination Detection and Fact-Vert Verification for Misinformation Detection
on fact verification of long text. In this task. the LLM is required
5.2.1 Hallucination Detection
Although Large Language Models have achieved impressive performance on various NLP tasks, they are bothered by hallucination problem (Manakul al., 2023), especially when the generated content the input context is too long for the user to have thoroughly review (Zhang et al., 2023b). In this paper, we focus on evaluating the performance different strategies in guiding LLM to recognize inconsistency between given context and model response with hallucination.
Task Setup: We use the Suuunvaa--ummrr dataset. It is one of the three datasets in HaluEval benchmark for hallucination detection, which contains the hallucination generated by ChatGPT-3.5. HaluEval-Summan have the longest context and generated contents among all three tasks this benchmark (Li al., 2023a). Thus, detecting hallucination this dataset requires repeatedly verify
8

---

Published as a conference paper at COLM 2025
Strategies
GPT-3.5- Turbo
GPT-4
F1
G-M
Prec
Recall
G-M
Prec
Recall
lo Pr-Proppiing
72.12
72.77
83.22
63,64
69.15
71.77
94.44
54.55
Chain-of-Thougee
56,09
60.64
90.48
40.64
74.03
75.79
94.21
60.96
CoT-SC
56.83
61.44
91.67
41.18
70.09
73.45
100.0
53.95
Sirc--ofThhoughee
69.91
73.30
53.74
100.0
77.34
78.00
88.89
68.45
Lccasttt- -ost
54.08
54.15
51.46
56,99
73.56
74.25
85.21
64.71
Swvide-andCooquue
76.88
77.13
83.65
71.12
81.11
81.24
76.67
86.10
Table 3: Performance of different prompting methods on SciFact dataset.
each sentence in the response, making standard prompting strategies acquire the worst accuracy across all three tasks. We report the Accuracy, Fl score (the hallucination pairs are positive samples), Precision and Recall.
Setup of baselines, ablation variants and DaC: In this task, our baselines include IO prompting, Chain of Thought, CoT-SC, tree-of-Thoughte Least-to-Most, and Decomposed Prompting. this task, the sub-tasks are verifying fragments of the summary, which are homogeneous and do not require recurssion. In such a setting, Decomposed Prompting is equivalent to LIM. For this task, we apply single level Divide-and-Congeee handle them separately and then merge the conclusions of all sentences. The details are in Appendix.
solver to decompose the summary to multiple sentences,
Results: Experimental results are shown in Tab. For both GPT-3.5 and GPT-4, our proposed prompting strategy outperforms the baselines, presenting the advantage of DaC. More specifically, compared 10-prompting, DaC achieved better performance in general, indicating the advantage brought by stronger expressive power. Meanwhile, compared to CoT and CoT-SC results, DaC clearly achieved much better recall. Tree-of- Tree-of-Thoughts, benefited by its searching ability, acquired a significantly better recall score compared to other baselines. However, its significantly lower precision substantially harms its overall performance and leads to accuracy that is even worse than standard 10 prommptiing. On the contrary, DaC carefully checked all sentences, located the one containing factual error, and merged the answers. We hypothesize that this systematic and exhaustive approach contributes to DaC achieving a better balance between recall and precision, it addresses each component without making overly broad or speculative inferences.
5.2.2 Misinformation Detection
The increasing abuse of misinformation toward manipulating public opinions on social media has been observed in different areas, such as healthcare (e.g. the recent COVID-19 pandemic) (Sharma et al., 2020; 2022). This threat is increasingly serious due to LLM's capacity in content generation (Li et al., 2023b; Weidinger et al., 2021; Zhang et al., 2022). This challenge raise the importance of fact-verification, which aims at judging the authenticity of an article based on a collection of evidence from verified source (Whitehouse et al., 2022; Zhang& & Gao, 2023). In this experiment, present that DaC can outperform other baselines in fact-verification involved with news article.
Task Setup:
In this experiment, we mainly adopt SciFact dataset (Wadden et al., 2020). In SeiFact dataset, each sample pair of news and evidence, where the evidence is the abstract of peer- reviewed paper and the news is sentence of claim. To better simulate the real-world scenario where news on social media usually appears as an paragraph of post, following Chen & Shu, we generate a dataset of paragraph-level misinformation based on SeiFact dataset. Specifically, for given claim, we apply ChatGPT-4 to extend the claim as an article based on the evidence. For this task, similar as hallucination detection, we apply single level Divide-and -nnidd-un-- solver to decompose the news article to multiple sentences, handle them separately and then merge the conclusions of all sentences. Also, the baselines in this experiments are the same as Hallucination Detection. The evaluation metrics includes Fl score, G-Mean score (geometric mean of precision and recall), Precision and Recall. We do not apply accuracy as the positive and negative classes are not balanced.
Results: Experimental results are shown in Tab. 3. Notably, GPT-3.5 incorporated with our proposed prompting strategy even outperform the performance of GPT-4 incorporated with IO-prompting. Least-to-Most, CoT and CoT-SC, which have significantly lower recall scores, indicating their proneness to deception. Only Tree-of- Tfoougghsss which is benefited by its advantage in exploring various options, acquired the best results among all baselines, but is still defeated by DaC. Moreover,

---

Published as a conference paper at COLM 2025
see, for GPT-4 the performance of CoT-SC is than CoT, which is supposed to be a specific case CoT-SC without exploration. These results suggests that, when facing deceptive contents generated on purpose, existing works' improvement may not be robust.
Practical Guidelines for Practitioners
Based on our theoretical and empirical analyses, we offer practical guidelines for practitioners considering DaC prompting:
Task Assessment: DaC is most effective for tasks where: (a) subtasks can be processed inde- pendently, (b) the original task is prone to error accumulation, and (c) the task exceeds the reliable capacity of standard prompting-
2. Implementation Strategy:
When implementing DaC, focus on clear subtask boundaries and explicit instructions for merging results. Our experiments show that template prompts that explicitly guide the model through decomposition, resolution, and merging phases yield the most reliable results.
While DaC provides benefits across different model capacities, the magnitude of improvement may vary. For critical applications requiring high precision, combining DaC with more capable models (e.g., GPT-4) provides the most reliable results, particularly for complex tasks.
Model Selection:
4. Efficiency Considerations: For tasks with stringent latency requirements, DaC offers potential advantages through reduced context window size and opportunities for parallel processing, though this benefit must be weighed against the overhead of multiple model calls.
These guidelines provide starting point for practitioners to effectively leverage DaC prompting in real-world applications.
Conclusions
In this paper, we analyze the utility and limitations of the divide-and -nnnnqu prompting strategy. We prompting and compare it with representa-
first provide theoretical analysis of Divide-and-Conpen tive prompting strategies. Based on these theoretical results, we summarize two conditions under which task is suitable for Divide-and-Conge ann-Conquer prompting. After that, we conducted experiments on several tasks. The empirical results validated our theoretical analysis and show that the two conditions we proposed are helpful for recognizing the applicable scope of Divide-and-Conque prompting.
Acknowledgement
This work was supported in part by the Department of Defense under Cooperative Agreement Number W91 1991NNF-442-011 contained in this document are those of the authors and should not interpreted as representing the official policies, either expressed or implied, of the Army Research Office or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein. D. Cao also acknowledges support from the USC Endowed Fellowship.
and NSF Research Grant IIS-2226087. The views and conclusions
References
Pablo Barcelo, Alexander Kozachinskiy, Anthony Widjaja Lin, and Vladimir Podolskii. Logical languages accepted by transformer encoders with hard attention, 2023.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint arXiv: /27 12, 2023.
10

---

Published as a conference paper at COLM 2025
Defu Cao, Furong Jia, Sercan O Arik, Tomas Pfister, Yixiang Zheng, Wen Ye, and Yan Liu. TEMPO: Prompt-based generative pre-trained transformer for time series forecasting, In The Twelfth International Conference Learning Representations, 2024a. URL httttts:/pppeeeeeeeee d=YH5w1 200uU.
Defu Cao, Wen Ye, Yizhou Zhang, and Yan Liu. Timedit: General-purpose diffusion transformers for time series foundation model. arXiv preprint S2XX::2409.02322,, 2024b.
Canyu Chen and Kai Shu. Can llm-generated misinformation be detected? In NeurlPS 2023 Workshop Regulatable MI, 2023.
Yuyan Chen, Qiang Fu, Yichen Yuan, Zhihao Wen, Ge Fan, Dayiheng Liu, Dongmei Zhang, Zhixu Li, and Yanghua Xiao. Hallucination detection: Robustly discerning reliable answers in large language models. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pp. 245 255, 2023.
Zhikai Chen, Haitao Mao, Hang Li, Wei Jin, Hongzhi Wen, Xiaochi Wei, Shuaiqiang Wang, Dawei Yin, Wenqi Fan, Hui Liu, et al. Exploring the potential of large language models (Ilms) in learning on graphs. ACM SIGKDD Explorations Newsletter, 25(2):42-61, 2024.
Vincent Cheng and Yu Zhang. Analyzing ChatGPT's mathematical deficiencies: Insights and contributions. In Jheng-Long Wu and Ming-Hsiang Su (eds.), Proceedings of the 35th Conference on Computational Linguistics and Speech Processing (ROCLING 2023), pp. 188-193, Taipei City, Taiwan, October 2023. The Association for Computational Linguistics and Chinese Language Processing (ACLCLP). URL https: /aclanttolooyyyyo org/ 2203 rocling-l..... 222.
David Chiang, Peter Cholak, and Anand Pillay. Tighter bounds on the expressivity of transformer encoders. In International Conference on Machine Learning, pp. 5544-5562 PMLR, 2023.
Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. 2022.
Corinna Cortes and Neil D Lawrence. Inconsistency in conference peer review: revisiting the 2014 neurips experiment. arXiv preprint arXiv:2109.09774, 2021.
Antonia Creswell and Murray Shanahan. Faithful reasoning using large language models. arXiv preprint arXiv:2208. 0ttt22228..427777 14271, 2022.
Wendi Cui, Jiaxin Zhang, Zhuohang Li, Damien Lopez, Kamalika Das, Bradley Malin, and Sricharan Kumar. A divide-conqqer--easnnin approach to consistency evaluation and improvement in blackbox large language models. Socially Responsible Language Modelling Research, 2023.
Paul Darm, James Xic, and Annalisa Riccardi. Inference- time intervention in large language models for reliable requirement verification. arXiv preprint arXiv:2503.14130 2025.
Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, et al. Faith and fate: Limits of transformers on compositionality. Advances Neural Information Processing Systems, 36, 2024.
Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: theoretical perspective. Advances in Neural Information Processing Systems, 36.70757-70798, 2023.
Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang. Jamie Callan, and Graham Neubig. Pal: Program-aidee language models. International Conference on Machine Learning, pp. 10764-10799, PMLR, 2023.
Jose A Garcia, Rosa Söncrgu and Valdiva. Quality censoring in peer review. Scientometrics, 126:825-830, 2021.
Amr Hendy, Mohamed Abdelrehim, Amr Sharaf, Vikas Raunak, Mohamed Gabr, Hitokazu Mat- sushita. Young Jin Kim, Mohamed Afify, and Hany Hassan Awadalla. How good are gpt models at machine translation? comprehensive evaluation. arXiv preprint arXiv:2302.09211 10, 2023.
11

---

Published as a conference paper at COLM 2025
Beizhe Hu, Qiang Sheng, Juan Cao. Yuhui Shi, Yang Li. Danding Wang, and Peng Qi. Bad actor, good advisor: Exploring the role of large language models in fake news detection. Proceedings of the AAAI conference artificial intelligence, volume 38, pp. 22105-221111 22113,1111111112 2024.
Birgit Jenner, Johannes Köbler, Pierre McKenzie, and Jacobo Torán. Completeness results for graph isomorphism. Journal of Computer and System Sciences, 66(3):549-666, 2003.
Furong Jia, Kevin Wang, Yixiang Zheng, Defu Cao, and Yan Liu. Gpt4mts: Prompt-based large language model for multimodal time-series forecasting. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 23343-23351. 2024.
Xue Jiang, Weiren Wang, Shaohan Tian, Hao Wang, Turab Lookman, and Yanjing Su. Applications of natural language processing and large language models in materials discovery. npj Computational Materials, 11(1):79, 2025.
Jaehun Jung, Lianhui Qin, Sean Welleck, Faeze Brahman, Chandra Bhagavatula, Ronan Le Bras, and Yejin Choi. Maieutic prompting: Logically consistent reasoning with recursive explanations. In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang (eds.), Proceedings of the 2022 Conference on Empirical Methods in Natural Lunguage Processing, pp. 1266-1279 Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics. doi: 10. 10.18633/1/2022. emnlp- m2...82. URL https: : /aaaaaaaaasii www.aaannnoooo.o.aaaoaaoaooollla org 2022. commmp-mminn 82/.
Daniel Kahneman. Thinking, fast and slow. macmillan, 2011.
Tushar Khot, Harsh Trivedi, Matthew Finlayson, Yao Fu, Kyle Richardson, Peter Clark, and Ashish Sabharwal. Decomposed prompting: A modular approach for solving complex tasks. In The Eleventh International Conference on Learning Representations, 2023. URL https: //openreview. wet.iiiwwweeeeeeee............ fest/forummt forum?ide peniidd=______ee_ee
Bingxuan Li, Yiwei Wang, Tao Meng, Kai-Wei Chang, and Nanyun Peng. Control large language models via divide and conquer. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Proceedings of the 2024 Conference on Empirical Methods Natural Language Processing, pp. 19240-15256, Miami, Florida, USA, November 2024. Association for Computational Linguis- tics. doi: 10.1865.330 1//8//////2224....o// 2ew.0224.mmmi-mmiin555555 URL /tL.tttsss//accaathhoooooo org/2024. emrlp-pe ma in. 850/.
Junyi Li, Xiaoxue Cheng, Wayne Xin Zhao, Jian- Nie, and Ji-Rong Wen. Halueval: A large- scale hallucination evaluation benchmark for large language models. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 6449 1464, 2023a.
Siyu Li, Jin Yang, and Kui Zhao. Are you in a masquerade? exploring the behavior and impact of large language model driven social bots in online social networks. arXiv preprint 2303 2023b.
Yang Liu, Yuanshun Yao, Jean-Francois Ton, Xiaoying Zhang, Ruocheng Guo Hao Cheng, Yegor Klochkov, Muhammad Faaiz Taufiq. and Hang Li. Trustworthy llms: survey and guideline for evaluating large language models' alignment. arXiv preprint arXiv:2308.05331 05377, 2023.
Potsawee Manakul, Adian Liusie, and Mark Gales. Selfcheckgpt: Zero-resource black-box hallucina- tion detection for generative large language models. Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 9004-9001, 2023.
Rui Mao, Guanyi Chen, Xulang Zhang, Frank Guerin, and Erik Cambria. Gpteval: A survey on assessments of chatgpt and gpt-4. arXiv preprint arXiv:2308.1244 12488, 2023.
Andres Marzal and Enrique Vidal. Computation of normalized edit distance and applications. IEEE Iransactions on pattern analysis and machine intelligence, 15(9):92--932 1993.
William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log precision transformers. Transactions of the Association for Computational Linguistics, 11:531-545, 2023. doi: 10.1 16./tacl 00562. URL https: //cl
tacl 11.1.
12

---

Published as a conference paper at COLM 2025
William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. In The Tweifth International Conference on Learning Representations, 2024. URL https: /pppneeeeeewww.. net/ a
Won-Gi Paeng and Daesuk Kwon. Folded context condensation in path integral formalism for infinite context transformers. arXiv preprint orXiv:2405.04620, 2024.
Binghui Peng, Srini Narayanan, and Christos Papadimitriou. On limitations of the transformer architecture. In First Conference on Language Modeling, 2024. URL httthtt//opeeeeeiieeet hott/foouuniddkkdyyyte
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners.
Rylan Schaeffer, Brando Miranda, and Sanmi Koyejo. Are emergent abilities of large language models a mirage? arXiv preprint arXiv:2304. 15004, 2023.
Karishma Sharma, Sungyong Seo, Chuizheng Meng. Sirisha Rambhatla, and Yan Liu. Coronavirus on social media: Analyzing misinformation twitter conversations. arXiv preprint arXiv:2003.123099 2020.
Karishma Sharma, Yizhou Zhang, and Yan Liu. Covid- 19 vaccine misinformation campaigns and social media narratives. Proceedings of the International AAAI Conference on Web and Social Media, volume 16, pp. 920-931, 2022.
Yiming Tan, Dehai Min, Yu Li, Wenbo Li, Nan Hu, Yongrui Chen, and Guilin Qi. Evaluation of chatgpt as a question answering system for answering complex questions. arXiv preprint arXiv:2303.07992, 2023.
Jonathan P Tennant and Tony
The limitations to our understanding of peer review. Research integrity and peer review, 5(1):6, 2020.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anm Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro. Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. 13971, 2023.
David Wadden, Shanchuan Lin, Kyle Lo, Lucy Lu Wang, Madeleine van Zuylen, Arman Co- han, and Hannanch Hajishirzi. Fact fiction: Verifying scientific claims. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.), Proceedings of the 2020 Conference on Empir- ical Methods in Natural Language Processing (EMNLP), pp. 7534-7550, Online, November main.609, URL
2020. Association for Computational Linguistics. doi: https: http:///aaaaaathhhaecoeo org/2020. emnlp- ma mainn 609.
Jincheng Wang. Penny Karanasou, Pengyuan Wei, Elia Gatti, Diego Martinez Plasencia, and Dimitrios Kanoulas. Long-short decision transformer: Bridging global and local dependencies for generalized Decision-making. In The Thirteenth International Conference on Learning Representations, 2025.
URL wwt.t:tt//// //ttpp:://ppnee /twpnr/eeeeeeeeeeeeeeeeeeeeeeeee iew..eeweee......... net./ forum? i d=NHMuM8 RT.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang. Aakanksha Chowdh- cry, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203. /711, 2022.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of thought prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35:24824-24837 2022.
Laura Weidinger. John Mellor, Maribeth Rauh, Conor Griffin, Jonathan Uesato, Po-Sen Huang, Myra Cheng, Mia Glaese, Borja Balle, Atoosa Kasirzadeh, et Ethical and social risks of harm from language models. arXiv preprint arXiv: /2.04359 2021.
Chenxi Whitehouse, Tillman Weyde, Pranava Madhyastha, and Nikos Komninos. Evaluation of fake news detection with nowledde-enhaneed language models. In Proceedings of the International AAAI Conference Web and Social Media, volume 16, pp. 1425-1429, 2022.
13

---

Published as a conference paper at COLM 2025
Yuanhao Wu, Juno Zhu, Siliang Xu, Kashun Shum, Cheng Niu, Randy Zhong. Juntong Song, and Tong Zhang. Ragtruth: A hallucination corpus for developing trustworthy retrieval- -uggenttdd language models. arXiv preprint arXiv:2401.00330 2023.
Chenghao Yang and Allyson Etinger. Can you follow me? testing situational understanding for chatgpt. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 6385 6398, 2023.
Yaming Yang. Defu Cao, Ming Zeng. Jing Yu, Xiang Ren, Yunhai Tong, and Yujing Wang. Collab- orative multi-task representation for natural language understanding. In IJNN, pp. 1-8, 2024. URL https: /ooi wrg/10.../....oo..oooooo........ 11111111111100111 1109/ IJNNN6 899. 2024. 10650257.
Zhen Yang. Ming Ding, Qingsong Lv, Zhihuan Jiang, Zehai He, Yuyi Guo, Jinfeng Bai, and Jie Tang. Gpt can solve mathematical problems without calculator. arXiv preprint (rXiv2339.032211 2023.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. arXiv preprint arXiv:2305. 10601, 2023.
Wen Ye, Wei Yang, Defu Cao, Yizhou Zhang, Lumingyuan Tang. Jie Cai, and Yan Liu. Domain- oriented time series inference agents for reasoning and automated analysis. arXiv preprint arXiv:2410.04044 2024.
Robin Young. Token democracy: The architectural limits of alignment in transformer-based language models. arXiv preprint arXiv:2501.15444 2025.
Xuan Zhang and Wei Gao. Towards lIm-basee based fact verification on news claims with hierarchical step-by-step prompting method. In Proceedings of the 13th International Joint Conference on Natural Language Processing and the 3rd Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 996-1011, 2023.
Yizhou Zhang. Defu Cao, and Yan Liu. Counterfactual neural temporal point process for estimating causal inffuence of misinformation on social media. Advances in Neural Information Processing Systems, 35: 15643-1010555 2022.
Yizhou Zhang, Loc Trinh, Defu Cao, Zijun Cui, and Yan Liu. Interpretable detection of out-of- context misinformation with wwwsssyyoooobeeeeeeeeeeeee large multimodal model. arXiv preprint arXiv:2304.07633, 2023a.
Yue Zhang, Yafu Li, Leyang Cui, Deng Cai, Lemao Liu, Tingchen Fu, Xinting Huang, Enbo Zhao, Yu Zhang, Yulong Chen, et al. Siren's s song in the ai ocean: A survey on hallucination in large language models. arXiv preprint 2rXivv2309.01219 2023b.
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc V Le, et al. Least-to-most prompting enables complex reasoning in large language models. In The Eleventh International Conference on Learning Representations.
Xinyu Zhu, Junjie Wang. Lin Zhang, Yuxiang Zhang, Yongfeng Huang, Ruyi Gan, Jiaxing Zhang, and Yujiu Yang. Solving math word problems via cooperative reasoning induced language models. In ACL (1), 2023.
Mingyu Zong and Bhaskar Krishnamachari. Solving math word problems concerning systems of equations with 3pt-3. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 15972-15979, 2023.
14

---

Published as a conference paper at COLM 2025
A Appendix
A.1 Discussions and Limitations
In summary, the proposed method has the following advantages:
Comparison with 10-Prompting: Superiority in Expressive Power As proved in Sec. 4, compared to 10-prompting, DaC has stronger expressive power and thus can solve harder problems.
Comparison with CoT and EoT: Disentangling the task decomposition and task resolution Compared to the prompting family of CoT and EoT, DaC explicitly separates the task decomposition stage and task resolution stage. Therefore, we can acquire explicit decomposed sub-tasks rather than intermediate thoughts proposed during decoding. Consequently, we can explicitly enumerate all sub-tasks output by the decomposition module and avoid the model from missing important sub-taske
Comparison with CoT and ToT: Separates task decomposition from resolution: Unlike Tree of Thoughts (ToT), which interweaves reasoning with exploratory search, DaC explicitly separates task decomposition from resolution, treating them as distinct phases. While ToT generates and evaluates reasoning paths simultaneously, DaC first identifies all relevant subtasks before solving any of them. Furthermore, DaC can handle heterogeneous decomposition patterns where subtasks vary in complexity through recursive application of the decomposition process, as shown in Algorithm In cases where certain subtasks require deeper analysis, DaC recursively applies the decomposition until reaching manageable units, creating a multi-level tree structure with varying depths across branches.
Comparison with LtM and Decomposed Prompting: Parallel Sub-task Handler and Sequential Sub-task Handler Similar as DaC, some program -egradd- prompting like LiM and Decomposed Prompting also explicitly separate the task decomposition stage and task resolution stage. However, they are mainly designed for multi-step reasoning for complex tasks. Thus, they sequentially tackle the sub-tasks and assembly the resolutions. As result, they tend to follow the flow of the deceptive contents, leading to proneness to deceptive content.
Although DaC surpasses the baselines on the proposed tasks, it still has some limitations. The first issue is that the appliance scope of DaC is still limited. More specifically, CoT, FOT, LiM and DaC are based on different algorithmic paradigms, learning to different Appliance Scopes. As pointed out by Feng et al., CoT and LIM can be considered as a neural dynamic programming algorithm. Thus, CoT is more suitable for tasks that can be bridged to dynamic programming, such as multi-step question answering. Differently, EoT is based on exploration and search, which is more suitable for planning and search, such as Game of 24 (Yao et al., 2023). DaC is based on Siride-and-Conquee algorithm. Thus, it is more suitable for tasks that can be decomposed to a series sub-tasks that are disjoint or only slightly overlapped. Our future work will focus on further expand the appliance scope of DaC to more areas like question answering.
A.2 Proof to Theorem 4.2
Before providing the proof, we first formally define how to organize the inputs (i.e., two 2-color trees) as a sequence. We assume that we acquire two trees tp of size n and fg of size m. They are organized as two sequences of nodes with random order. Each node has three variables: color, left child index, and right child index. If any child is null, then the index is filled with O. Then we can organize them as as two sequences Xp E R and X3 E IR'xs x3 where each item in the sequence is a vector of 3 dimensions. The first dimension is the index of the left child, the second dimension is the index of the right child, the third dimension is the color indicator (0 or 1). In addition, we have a root vector r with three dimensions. The first dimension is the index of the root node of Ip (i.e., pointing to the root node of fp) and the second is the index of the root node of to (i.e., pointing to the root node of t.). The third dimension of r is filled with 0 to make it have same dimension as the items in X, and X5. This expression of trees is also called as pointer list encoding according to (Jenner et al., 2003). Note that in the following proof, we assume that all indices start from 1. Thus 0 is regarded as a NULL pointer.
Following the proof flow we provided in Sec. 4.2, we first provide the following divide-and -ndde--nddcoquer algorithm that can solve the above problem:
15

---

Published as a conference paper at COLM 2025
Algorithm 3 Recursion Divide-and-Conquee Algorithm for 2-BSI BST Xp, Xp, m, f,
Require: Inputs r, Xp, Xg. problem size metric function f()), hyper-parameter w, merge function sub-task tackling function f, task decomposition function d
Ensure: A 0-1 indicator vector z: if there exists subtree with node as root that is isomorphic with pattern tree P defined with inputs r, Xp, Xb, then the z[i] is 1. Otherwise, v[i] is O.
1: T, < Xp, Xb)
2: for i E [1,r] do
3:
if' fri, Xp, Xp) > w then
4: Dj f BSI Xp, Xbr m, t, f,w)
5: else
6: Vi - trri, Xb)
7: end if
8: end for
9:
Return m(r, Xp, Xbr 2/, Dr)
Algorithm 4 Implementation of d(r, Xp, Xx) when the depth of the tree indicated by r is not longer
than
Require: Inputs IR, Xp R"x3 X2 R"'x3
Ensure: A 0-1 indicator vector v: if there exists subtree with node i as root that is isomorphic with pattern tree 1p defined with inputs r, Xp, X3, then the z[[] is Otherwise, v[i] is O.
fj << 2),
2: r, < Xp 3
3: Return Fr
Algorithm 5 Implementation of f(r, Xp, Xb) when the depth of the tree indicated by is not longer
than 2
Require: Inputs r IR3, Xp E R#x3 X₁ R3'x3
Ensure: A 0-1 indicator vector if there exists subtree with node i as root that is isomorphic with pattern tree tp defined with inputs r, Xp, Xy, then the vli] is Otherwise, o(i] is O.
1: Initialize v as all q vector with length of n'
2: if r[] = then
3: Return
4: end if
5: for i 21, } do
6: if 1g
3|
[,p][[],,3] then
7: v 0
8: end if
9: end for
10: Return
The algorithm described above is typical divide-andd-onquer algorithm for solving rooted tree isomorphism. Its justification can be found in many textbooks introducing algorithms, such as Introduction to Algorithms (Cormen al., 2022). Here we provide the detailed definition and implementation of problem size metric f(.), hyper-parameter w, merge function m(), sub-task tackling function f(-), task decomposition function d(-):
1, and f(r, X(, X²) is defined the depth of the pattern tree fp indicated with root vector Although precisely calculating f(r, Xp, X₂) is of O(n), judging whether fr, Xp, X₂) > 1 only require check whether the root node has child. If not, then return False.
d(r, Xp, X₂) rL r, returns two new root vectors r,, Fr. Both Y2 ry have the same second and third dimension the root node that r points to. The r, first dimension is updated to be the index of the right child of the root node that points The updating function can be written
The 's first dimension is updated be the index of the left child
16

---

Published as a conference paper at COLM 2025
Algorithm 6 Implementation of m(r, Xp, Xp, vr,
Require: Inputs E IR² Xp E R XB R"'xs Uy E R", E R"
Ensure: A 0-I indicator vector v: if there exists a subtree with node i as root that is isomorphic with pattern tree tp defined with inputs r, Xp, Xz, then the v|i] is 1. Otherwise, v[i] is O.
1: Initialize v as all O vector with length of n'
2: if r == then
3: Return
4: end if'
5: for i E 21, m do
6: if [i] == Xp 3 then
7:
if oj 11 [ 1]] == and By [X, 2]]] == 1 then
8:
v i
9:
else if by x 2]]] == and o, [ 1]]] == 1ten
11: end if
12: end if
13:
end for
14:
Return v
= a returns a 0-1 indicator vector v E IR" with the same length of the base tree size. If there exists subtree with node i as root that is isomorphic with pattern tree fp defined with inputs r, Xp, Xp, then the v[1] is 1. Otherwise, v[i] is O. When the pattern tree's depth is not higher than (i.e., 1-node tree), (r, Xp, Xb) is equivalent to output a 0-1 vector indicating the nodes in the base tree that have the same color of the root node of pattern tree. The implementation is provided in Alg. 5.
(r, Xp, X1) Xp)
m(r, Xp, Xb, D2, v1) with the same length of the base tree size. If there exists a subtree with node i as root that is isomorphic with pattern tree tp defined with inputs Xp, X5. then the zli] is 1. Otherwise, vii] is O. This function can be implemented by checking whether the pattern root's children have perfect match with each node's children. Since each node has at most two children, checking the perfect match can be done in constant time. The implementation is provided in Alg.
merge the results Vi, Uj to acquire a 0-1 indicator vector u E R"
After providing the detailed implementation of the functions d(:), ((),, that there exists one unified transformer that can handle all these tasks with different prompts d, t, m. First, we will provide the following Lemma:
m(-). we are going to prove
Any fixed-size logic circuit that only contains multi-fan-in AND gates, multi-fan-in OR gates, NOT gates and has no recurrent structure can be precisely simulated by a multi-layer perceptron (MLP)
with ReLU activation function and width of O[ + |Circuit)) ) and a depth of O([Circuit]) )), where [npuf] denotes the size of input and |Circuit] denotes the number of gates in the circuit. Assume that we are given series of input pins with logic variable of 0 or 1, organized as 0-1 vector x E R² We first prove that all gates can be simulated by a two-layer perceptron. Then we can serialize all gates in the circuits and stack their corresponding 2-layer simulators accordingly to acquire MLP simulator. An AND gate that take input can be simulated as:
AND(x) = ( h +1
where 0 is the ReLU activation function, and W is a weight vector with all dimensions equal to 1. If some dimensions of x are not the input of the gate, we can set the corresponding dimensions in the weight vector as 0 and adjust the /t as the input pin number. Similarly, an OR gate that take x as input can be simulated as:
OR(x) = 1 - ( + h 1)
(4)
where o is the ReLU activation function, and wo is a weight vector with all dimensions equal to -1. NOT gate is different, since it only takes one input pin. In such case, denote the index of the input pin as i, then we can simulate NOT gate as:
NOT(x) o +1)
(5)
17

---

Published as a conference paper at COLM 2025
where WN is a weight is weight vector whose i-th dimension equals to -1 and all other dimensions equal to 0. Also, since the x is a 0-1 vector, the activation function is equivalent to a identical function to x:
x (x)
(6)
To construct a MLP that can simulate a fixed-size logic circuit without recurrent structure, we apply the circuit serialization in (Merrill & Sabharwal, 2024) which order the gates based on topologiaal order. In this way. we can represent the circuit as a sequence GATE[U], GATE[2], GATTE3]...,GATTEL.. where each GATE(i]'s input only contains the output of the previous gates and the original input x. Therefore, we can construct a 2L-layer MLP base on the above serialization. Specifically, the 2i-th and 2i + 1-th layers of the MLP will simulate the GAT'E[i] E[i] as well as copy all previous inputs with activation function and concatenate them together. This can be done by concatenate an identical matrix on the GATE's s weight vector A, wo or WN). In this way, we can construct a MLP that precisely simulate the circuit. Since every time we concatenate the output of gate with the input of it, the input dimension number of the final layer can be bounded by O[1x] + L). In the worst case, for a circuit of size I., we needs 21. layers to precisely simulate it. However, in many cases, a lot of gates in the circuits can be run parallelly. In such cases, the MLP could be much more shallow.
Now, we can start prove our main theorem:
There exists a log-precision transformer with fixed depth and hidden dimension that can solve the 2-BSI of any size with fixed-length prompt m (for merge), / (for sub-task tackling) and d (for task decomposition). We prove this theorem by constructing a Transformer that can tackle this problem. First we define how to organize the input given r, Xp, Xp and the prompt. Specifically, we construct
a feature sequence X E R(+++++')x7 Each item in this sequence is a feature of 7 dimensions, indicating a token. The first two dimensions indicate whether the token is prompt ( ('00'), root vector ('01"), a pattern tree node ('10', or a base tree node ('11"). The third to fifth dimensions carries the information about the token. For a prompt token, '100' indicates merge prompt m, '010' indicates sub-task tackling prompt f. and '001' indicates task decomposition prompt d. For other cases, these three dimensions are with the same formula as the three dimensions in r, Xp, Xg. The rest two dimensions are allocated specifically for the merge function mn(-) to store D. and v,. More specifically, for the feature of token indicating the i-th base tree node, its sixth dimension is Dj [i] and its seventh dimension is vy [i] For other tokens, these two dimensions are filled with O. In [[] we store the prompt token. In X [2] and [[3] store the input root vector duplicately. We store the same token twice so that we can tackle rj and r, separately. To separate this two token, we use the last dimension, which was padded 0 in r, distinguish them. X is set as 0 and X 5) is set as 1. From X(4] to 3 + z1]. we store Xp. From X + xI] to X(3 + π + n²'.. we store X₁. For all node indices of pattern tree, we add them by 3. For all node indices of base tree, we add them by 3+n, so that the indices can be applied to directly retrieve the positional embeddings. After preparing the inputs, we start to construct our Transformer. The transformer first attach the position index for each token (positional embedding). After that, the inputs are forwarded into transformer with depth of 2. Each transformer layer contains multi-head attention layer followed by a MLP. As proved by (Merrill & Sabharwal, 2024; Feng et al., 2023), the attention layer of Transformer can retrieve the feature of tokens whose positional embeddings satisfy specific conditions. For multi-head attention, different heads can retrieve tokens with different conditions. In the following construction, we will use this conclusion to construct attention heads with different functions.
In the first Transformer layer, the function of each attention head is defined as:
Head only attends to the token itself to store X[i] for token i.
Head 2 attends the token with positional embedding matches the X[i,3] and copy this token's 5-dimension feature. For tree node tokens, this head's job is to retrieve the feature of [[]]'s left child. For root vector tokens, this head's job is retrieve the feature of pattern tree root node. For the first token (prompt token), this head's retrieved feature will not be applied in the afterwards layers and thus does not influence the correctness of the model.
Similar as Head 2, Head 3 attends to the token with a positional embedding matches the X 4] and copy this token's 's 5-dimension feature. This head's job is to retrieve the feature of X 's right child. For root vector tokens, this head's job is to retrieve the feature of base tree root node.
18

---

Published as a conference paper at COLM 2025
Algorithm 7 Logic circuit for MLP of the second Transformer layer
Require: Input feature x" E R
Ensure: Output feature y E IR?
1: y <- x=[1= (Initialize y}
2: [xx"[1:2 = 00 or x" [1 == Prompt Token or Pattern Tree Node} then
3: Return
4: else if x - 01 { /Root Vector Token} then
5:
if [24 26 001 (Prompt d) then
6:
if xxx5 = 0 then
7:
y[3] x" [10]
{get rı. similar as line in Alg. 4)
8:
else if x
then
9:
y/3) [] x" [11] {get ry. similar as line Alg. 4}
10:
end if
end if
12:
else if x1(1 [1: 2] = 11 { (Base Tree Node Token) then
13:
if' x [24 26
010 Prompt f} then
14:
if x [40]
=
x x5 [Line 6 in Alg. 5} then
15:
y [5]
16:
else
17:
[5] +- 0
18:
end if
19:
else if x x²[24: 26] = 100 (rrmpr is m) then
x [1x"(13 [13]
and [21] = (Line in Alg. 6} then
21:
y [5] + 1
else if [14]
and x=[20] ([Line in Alg. 6) then
23:
[5] +
24:
else
25:
5| <- 0
26:
end if
27:
end if
28:
end if
Head 4 attends to the first token (prompt token) and copy this token's 7-dimension feature.
This head's ' job to retrieve the prompt indicator.
Head attends to the second token (root token) and copy this token's 7-dimension feature. This head's job retrieve the root information.
With the above 5 heads, the attention layer will output a 35-dimension feature for each token. We denote these features X' (R(++++')xx3 x33, After that, these features are forwarded into a MLP fitting identical mapping to acquire the input features for the second Transformer layer.
In the second Transformer layer, the function of each attention head defined as:
Head only attends to the token itself to store X' for token i.
Head attends to the token with a positional embedding matches the ('i,, 31] and copy this token's 's 1-7 dimension features (X' ['(X'i,, [1,, : 7). This head's job is to broadcast the feature of the pattern tree root node every token.
With the above 2 heads, the attention layer will output a 42-dimension feature for each token. We denote these features as X (3 In') For root vector token, only the features from head and head 4 are useful. For base tree node tokens, all 42 dimensions are useful. Then each token's s feature are parallely forwarded into MLP. We will use this MLP to the logical circuit described in Alg. 7. The function of Alg. is to aggregate the functions of m(-), ())) together and assign the correct value based on the prompt indicator. In Alg. 7, all operations are AND, OR, NOT. SELECTOR, and ASSIGN and there is not loop. Thus, it is static logical circuit and can be implemented with multi-fan-in AND, OR, NOT gates. Thus, can be precisely simulated by a MLP according to Lemma A.2.
19

---

Published as a conference paper at COLM 2025
After acquiring the y E R for each token,
organize them feature sequence Y e
IR (( When the prompt is d, we return 3|2,3 : 5] as ry and Y|3,3: : 5] as ry. If the prompt t or then we can output Y + π + 1 3 + n', 5] the expected v.
A.2.1 Token Efficiency and Practical Trade-off's
While DaC requires additional tokens for sub-task decomposition and solution merging, it significantly reduces the average decoding context window size during sub-task resolution. The following illustrative tables demonstrate this trade-off.
Table 4: Illustrative Token Usage Comparison for 1234 x 5678
Method
Stage
Prompt
Inpat Tokens
Est. Output
Stage Tokens
DaC (Single-Lovel)
1. Decomposition
50
(implicit)
25
77
Sub-Task Resolution
~30 (each)
~3 (each)
~12 (each)
~138
3. Solution Merge
-00
(implicit)
22
~52
DaC' Total
~26
CoT LIM
Full Task Full (Sequential)
25
(implicit) (implicit)
~-0
~175
90
~310
Table 5: Illustrative Token Usage Comparison for Hallucination Detection (5-sentence summary)
Method
Stuge
Est. Prompt Tokens
Est. Input Data Tokens
Est. Output Tokems
Sluge Total Tokens
DaC
Decomposition
(instructions)
40 (summary)
~70
~50
2. Suh: Task Resolution
~ 100 (base prompt)
165 (dnetstalement)
~0 (each)
~~375
3. Solution Merge
25 (instructios)
75 (analysis resulis)
~1
~~10
DaC Total
~1663
CoT
Foll Task Combined Stages
~0 (instructions)
230 (doc+summary)
350
6600
ToT (Illust.)
-0 (main prompt)
230 (doc+-summry)
950 (all pathsecval)
~223
Reflecting on these illustrative comparisons, when considering the DaC prompting strategy, practi- tioners should weigh the potential increase in total token usage and the number of LLM calls against the significant benefits DaC can offer for specific task types. The tables suggest DaC might involve higher token counts, particularly if context is repeated across sub-tasks. However, this is trade-off' for key advantages, such as achieving superior performance and reliability for complex problems that align with its core principles. erucial benefit of DaC is the reduction in the average decoding context window size for each sub-task, which can improve performance and manage complexity.
A.3 Justification to Proposition 4.2
Suppose that the LLM is auto-regressively decoding n tokens from an input context window with length of C. Then the decoding window of the i-th token is C+i- 1. Thus, the average window size will be:
[h C+ __
π Thus, when we sequentially decode all the sub-task resolutions, the total length of the decoded sequence will be D/=1"; rj. Thus the average window size will be:
2
E 2
C+
(8)
Meanwhile, when we apply Sivide-and-Conquee we parallely decode each sub-task's 's resolution. Thus, for each sub-task. total window size will be 1 Σ (n=!"". Thus the average window size will be C E (1-1in Mcanwhile, with Jensen inequility, we have:
2
k ( 0.5))
Σ 1)r Σ ( <
Σ - 0.5kk
(9)
1
Thus, when & 2 2, we have:
k Σ
Σ
(ri 1)r <
ri - 1)2
(10)
1=1
20

---

Published as a conference paper at COLM 2025
Thus, have:
1)2 <C
Σ - ri-1
C+
(II)
2 2 -
A.4 Refining Condition 2
To better illustrate Condition 2, we refine it into two distinct sub-conditions:
Condition 2.1 (Parallel Subtasks): The task must involve subtasks that can be processed independently and in parallel, without requiring intermediate results from other subtasks to proceed. Specifically, task satisfies this condition if: (a) each subtask can be solved without relying the outputs or reasoning paths of other subtasks, and (b) subtasks share a common structure or computational requirements, enabling consistent treatment by the model.
Condition 2.2 (Susceptibility to Intermediate Errors): The task must be prone to intermediate
errors that arise during sequential reasoning. These errors typically originate from subtask solution emtors-mistakes made during individual sub-task resolution-whic then propagate through the reasoning chain and affect the final solution, creating a cascading effect that significantly impacts accuracy.
A.4.1 Task Selection Rationale
Our task selection is driven primarily by scenario characteristics rather than granularity considerations. We deliberately selected tasks representing distinet types of dependencies between subtasks: Multi- round QA and Planning represent highly sequential reasoning where subtasks depend heavily on previous outputs, making them less suitable for DaC; while Verification and Consistency Evaluation involve naturally independent subtasks that align well with DaC's parallel processing capabilities. The difference granularity between tasks secondary to their structural characteristics peteerrtttsssssssppiiilllllll whether they exhibit the parallel subtask property (Condition 2.1) and susceptibility to intermediate errors (Condition 2.2) that our theoretical analysis identifies as crucial for DaC's effectiveness.
A.4.2 Handling Heterogeneous Subtasks
In real-world applications, subtasks often vary significantly in complexity. For instance, in document analysis, some sections may contain dense technical content requiring further decomposition, while others might be straightforward. DaC's recursive nature naturally accommodates these variations by dynamically adjusting decomposition depth. When f(Si) > in Algorithm 2, the system recursively decomposes complex subtasks until reaching manageable units, creating branches of varying depths. This adaptive approach is particularly valuable for tasks like hierarchical summarization technical document analysis where content complexity varies substantially throughout the input.
A.5 Prompting Details of DaC
Multiplication of Long Integers: Suppose we have two 2n-di numbers AB and CD, where
A, B, D are all n-digit numbers. Then we can break AB x CD as (A x C x 102h) ) + (A x D x 10") + (B x C x 10") + (B x D), where the calculation in each bracket pair is disjoint with others bracket pairs. We only need to compute the results of multiplication in each bracket pair parallelly and then merge all them with addition:
Decomposer Prompt d: Please split the string from the middle as two separated strings. The lengths of the two separated strings should be as close as possible. Please only return the two strings separated by comma and do not return anything else.
Sub-task Tackling Prompt (1)Please compute a b. (2) Please only return the final results and do not return anything else (ensure disentangled-sub-proeess principle).
Merge Prompt m: Please compute x = a* 102" + b 10" and = c 10" + d. Based on the above calculation, please compute x y carefully step by step.
Long Integer Addition: Similar to multiplication, we applied a divide-and andiide-and-ooqueer approach to integer addition empirically demonstrate its unsuitability. The prompts used were designed to
21

---

Published as a conference paper at COLM 2025
follow the same DaC structure for fair comparison, though the task itself does not benefit from this paradigm. The prompts used were:
Decomposer Prompt d: "Please split the string from the middle two separated strings. The lengths of the two separated strings should be as close as possible. Please only return the two strings separated by comma and do not return anything else."
Sub-task Tackling Prompt 1: "Please compute the sum of the two numbers a and Please only return the final results and do not return anything else."
Merge Prompt m. "Please compute the final sum of the numbers a, b, c, and d. Please add them carefully step by step, ensuring you carry the values correctly from the rightmost digits. Show your work and return the final number."
We divide the summary sentences. After that, parallelly verify the sentences. Finally, we merge the verification to each sentence:
Hallucination Detection in Long Context:
Decomposer Prompt d: Please help me segment the following paragraph sentences. The separated sentence should be output as: #Statement ##: ...#Statement 2#: ...Do not say anything else. Just return the statements in the given format.
Paragraph
Sub-task Tackling Prompt t: I want you act as a factual contradiction checker. You are given set of statements and document. Among the statements, there might be one more statements that contain contradictions with the document. Please find the problematic statement if exist by analyzing the statements one by one. For each statement, please make a choice:
* A: The statement is totally aligned with the document for sure.
B: The statement contradicts with the document.
Merge Prompt m: Based the above analysis, please tell me, does any statement above contain contradiction with the document?.
Fact- Verif-eeiiiintion for Misinformation Defection: Similar as hallucination detection, we divide the summary to sentences. After that, we paralelly verify the sentences. Finally, we merge the verification each sentence. Thus, our decomposer prompt and sub-task tackling prompt are the same as hallucination detection. The only difference is the merge prompt.
Merge Prompt m: If we connect the above statements be news article, based on the above analyzation, please answer me: Is there any contradiction between the document and the article?
Sub-tusk
Sol-Sioution
A.6 Decomposed Prompting and Least to Most
Input
Input
Least-to-Most (LtM) Prompting (Zhou al.) and Decomposed Prompting (Khot et al., 2023) two similar works to our work. They both propose to explicitly prompt the LLM decompose the task as series of sub-tasks and sequentially tackle them. In Fig we merge these two methods. Here, we will provide more detailed comparison of them, which is shown Fig. Decomposed Prompting can regarded as upgraded ver- sion of LAM. It introduces special notations into the prompt represent program states so that when sequentially tackling the sub-tasks, it call heterogeneous modules to tackle them. Such design enable the LLM to call external programs (e.g., retrieval documents
...
DeP
Output
Output
(A). Least Most
(B). Decomposed Prompting (DeP)
Figure 4: Comparison of Least-to-Most (LIM) Prompting and Decomposed Prompting (DeP).
22

---

Published as a conference paper at COLM 2025
on WikiPedia and program based calculator)
and/or itself (i.e., recursion). Such design
endows it stronger expressive power and increases the compositional generalization ability of LLMs in different areas, such as symbolic manipulation and multi-hop QA (Khot et al., 2023). Also, endows LLM the ability do open-domain QA by retrieving from external knowledge base.
A.7 Typical Tasks that Satisfy and Dissatisfy the Proposed Conditions
To better assist the prompt engineering on different tasks, we list the typical tasks that satisfy and dissatisfy the proposed conditions. common tasks, the following tasks satisfy the proposed conditions. For such tasks, searching good decomposition prompt for DaC is likely to be helpful for the performance:
1. Multiplication
2. Fact Verification Long Text
3. Auto Evaluation on Long Text
4. Article-level Summary
The following tasks typically do not satisfy the proposed conditions. For such tasks, searching good decomposition prompt for DaC is not very likely to be helpful for the performance:
1. Addition: It is too simple and violate the condition
2. Division: It does not contain parallel sub-tasks, thus violate condition
3. Multi-Round Oreestion-Anseeriig
a typical sequential task, thus violate condition
4. Planning: It is typical sequential task, thus violate condition 2
A.8 More Discussions on Sequential Sub-task Tackling and Parallel Sub-task Tackling
Example Sequential Sub-task Tackling
Example Parallel Sub-task Tackling
Complete Task Compuie 12345767800
Complete Task. Compute 12345667800
Compute
tack Compute 3-45190:
Ar...
Ar...
Sub 3: Based on the above result, compute 11:---191111-----"9
Sub- tnok 2: Compute 90112:11'0""
the above result, compute 2m85" 678 10-96688111---11100 28-125-90110----85 At
Compute 2745"678
A: A
Sub-tnak 4: Compute 1=123"678-1004:
task Based the above result,
==122"678"11
Resolution Assembly: above computation, compute stytzen
A: A....
Figure 5: Toy example of Sequential Sub-task Tackling and Parallel Sub-task Tackling in long integer multiplication
Sequential Sub-task Tackling and Parallel Sub-task Tackling are two different paradigm in decom- posing complex tasks sub-task to tackle. The first one decompose a complex tasks as a series of sub-tasks. In this series, each sub-task relies on the previous one', 's output as input or context. The second one decompose a complex tasks as a set of sub-tasks, each of which does not rely on others. Two examples for multiplication and hallucination detection are provided in Fig 5 and 6
23

---

Published as a conference paper at COLM 2025
Example Sequeatial Complet Vority sammary
Example Paralld Sub-task
Complei
in
receaigronn snddage Masuill linos Behen irgad via night mare lus kove innoddaakly. Andrea Lukete, the co-pike occsodioo xessddof detieeneelyy criding plans. had heevey of peseem depeossess and uneutal londensio.
rensard insuuignon fiom smodagy Mireelle Brios Rihie wlar rigin lave fooage las Lowe inmociiadds Aadica Lubtie lae cogiitt secaued of deliemerty cradiig the plane hod herry sevens ceprosion ant maccib lendencis.
ASuerarryh sidee
Genrensinng Flight
(Sanmoryy video
C'Cenaniings Flight
recovered inventuzion woddage At
recovered invertgutton then soockage
A
Sab-tads Blased abore anatydt, werty fullendeg ctatemett MBannnayhh sidiesliiing uesuero Gentating Figlt unged incentgroes wradage
Verily the fellenteg statement: :
Sanmmayy Marseill presecstar Rubin uged ateone vho night lave footage staly.
Sab-tak Verit the following statenent
Sab-task to Blaed on the abone analyst, veriby fellendag statament: Mtnerrrrph sidre show ng morsons Comrrrsing riing Flight
Cammmayyl Andrea Lotto, the cospict socaed delivrracly crabiia the plass, lad hicory of saum deprestion wlosbi iendencio
inveatianaes woddageiis Mascille procouue Brize ansd onpone deficcatele mncinncee.
immodassly.
co-piie
Roslation Asscubdy alove mmbbiis verily cansist above
Figure 6: Toy example of Sequential Sub-task Tackling and Parallel Sub-task Tackling in hallucination detection
24


Reviews:
[{"review_id": "ocPXkHotmE", "reviewer": "Reviewer_N6F9", "summary": "The paper presents a prompting method for LLMs called Divide-and-Conquer (DaC). It splits the input sequence into several independent parts and then merges the outputs. Through theoretical analysis and experiments, the authors test the effectiveness of DaC and identify the task types for which DaC is suitable.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The paper builds a thorough theoretical framework for DaC prompting, compares it with previous methods such as IO prompting and CoT, and reveals the task categories where DaC is applicable. I must admit that fully understanding the theoretical analysis is beyond my expertise, so I cannot offer a complete assessment of their strengths and weaknesses. However, the analytical approach itself appears valuable and worth referencing.", "reasons_to_reject": "- The paper does not provide detailed prompt templates for concrete problems. In the DaC process, is the task decomposition done by directly prompting the LLM to split the task itself, or is there human intervention?\n    - If the task is split by humans, the decomposition strategies can vary widely and may be impractical in real applications, are there proposed solutions?\n    - If the LLM itself decomposes the problem before answering each sub-question, this path may be more interesting. How are the prompts designed? Since there are many possible decomposition strategies, will there be incorrect splits? Can the LLM determine whether it is worth using the DaC strategy and decide to split the task on its own?\n- How exactly is long integer addition handled with DaC, such that its performance becomes even worse than the previous baselines? Many details seem to be missing.", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zvV0DtFTFB", "reviewer": "Reviewer_1hW4", "summary": "This paper explores the DaC (Divide and Conquer) strategy for enhancing language model performance, particularly in solving tasks that can be decomposed into parallel subtasks. The approach is grounded in rigorous theoretical analysis, demonstrating DaC's ability to efficiently solve NC1-complete problems, while outperforming conventional methods like CoT (Chain of Thought) in tasks like multi-digit multiplication and hallucination detection. Practical templates and criteria for applying DaC further enhance its usability. However, the study is constrained by its focus on parallelizable tasks, lacking complexity analysis for multi-level DaC and offering a limited evaluation restricted to synthetic or curated datasets. A more comprehensive theoretical analysis and diverse empirical validation would strengthen the work's generalizability.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1.\tRigorous theoretic support for DaC strategy. The paper provides a solid theoretical foundation for the DaC (Divide and Conquer) strategy, offering a clear computational complexity boundary that highlights DaC's advantages for specific problem classes. This foundational contribution is significant because previous studies lacked formal guarantees for DaC. Specifically, the paper rigorously proves that DaC can solve NC1-complete problems, such as the 2-color Binary Subtree Isomorphism, whereas IO prompting is limited to TC0 (as discussed in Section 4.1, Equation 1). This theoretical insight establishes DaC's superiority in addressing these computational challenges.\n2.\tReduction of intermediate errors in parallelizable tasks. The DaC strategy demonstrates a clear advantage in minimizing intermediate errors during parallelizable tasks. The experimental results validate this advantage by showing that DaC effectively reduces error propagation in tasks with parallel subtasks (Condition 2), which significantly outperforms sequential methods like CoT (Chain of Thought). For instance, in the 5-digit multiplication task, DaC achieves a lower edit distance compared to CoT and IO prompting. Additionally, in hallucination detection, DaC shows a remarkable improvement, increasing the F1 score by approximately 10% over CoT on GPT-4. These empirical results are well-aligned with the theoretical predictions, reinforcing the practical utility of the DaC approach.\n3.\tDaC strategy is of good practical utility. The paper effectively bridges theory and practice by providing actionable guidelines for employing the DaC strategy. It introduces practical prompting templates, such as decomposition prompts for multiplication, and outlines clear criteria for identifying tasks that are well-suited to DaC. By explicitly separating task decomposition from resolution, DaC avoids the pitfalls of entangled reasoning, thereby enhancing clarity and efficiency. This practical guidance greatly contributes to the adoption of DaC in real-world applications.", "reasons_to_reject": "1.\tLimited task scope The DaC strategy is inherently restricted to tasks that can be effectively decomposed into parallel subtasks. As a result, it is unsuitable for sequential or interdependent problems, which violate the core assumption of parallelizable subtasks (Condition 2.1). This limitation is explicitly acknowledged in the paper, as evidenced by the exclusion of multi-round QA and planning tasks from Table 1. However, this narrow applicability reduces the generalizability of DaC. Furthermore, the paper does not explore potential hybrid approaches, such as combining DaC with CoT (Chain of Thought) for tasks that involve a mix of parallel and sequential reasoning, which could have broadened its applicability.\n2.\tInsufficient theoretic analysis. Although the paper provides a strong theoretical foundation for DaC’s performance on specific problem classes (e.g., Theorem 4.2 for 2-BSI), the theoretical analysis is incomplete. Specifically, the complexity of recursive DaC is not fully explored. While it is mentioned that a multi-level DaC solver may encounter subtasks with large problem sizes, the associated overhead is neither quantified nor analyzed. This omission is critical, as the absence of complexity analysis for multi-level decomposition (e.g., token overhead and computational cost) raises concerns about the scalability of DaC in real-world scenarios. A more comprehensive analysis would have greatly enhanced the theoretical depth of the work.\n3.\tEvaluation scope is limited. The empirical evaluation of DaC is primarily confined to controlled conditions, such as synthetic tasks (e.g., 5-digit multiplication) and curated datasets. While these experiments demonstrate DaC’s advantages under ideal settings, they fail to capture its performance in more diverse or challenging scenarios. Specifically, the paper does not test DaC on noisy inputs, multi-modal tasks (e.g., text combined with images), or adversarial examples, which are common in real-world applications. This limited evaluation reduces confidence in DaC’s generalizability and robustness. A broader range of experiments, including cross-domain generalization and stress-testing, would significantly strengthen the practical relevance of the proposed approach.", "questions_to_authors": "None", "extra_scores": {}}, {"review_id": "A5eBEulUH4", "reviewer": "Reviewer_kq9V", "summary": "The paper proposes the divide-and-conquer (DaC) prompting strategy and identifies two conditions under which it leads to performance gains. It provides a theoretical framework to determine the types of tasks where DaC prompting is advantageous and offers a theoretical guarantee of its effectiveness. The authors empirically validate their analysis on tasks like Large Integer Multiplication and Hallucination Detection, tasks that involve long reasoning paths.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- The theoretical analysis on the Divide-and-Conquer prompting method is solid and well-motivated\n- The performance gains obtained on the 2 tasks presented are encouraging", "reasons_to_reject": "- Unless a token usage comparison is available between DaC, CoT, ToT, the adoption of DaC may not be as broad as it involve overheads in decomposition and merging steps", "questions_to_authors": "Can you include a token usage comparison between the 3 methods?", "extra_scores": {}}, {"review_id": "jribxo3J2o", "reviewer": "Reviewer_uHuS", "summary": "This paper is about a way of prompting language models (I use the word prompting with a large meaning) called Divide and Conquer. The paper first compares the approach with other methods like Chain of Thoughts. It then theoretically classifies the proposed approach according to equivalent computation models. This leads to a characterisation of two conditions on the task to solve, under which the proposed prompting method will be efficient. Finally the paper presents a list of experiment results on three types of tasks that confirm the the predicted behaviour.\n\n**Clarity:** The logical flow of the paper is easy to understand.\n\n**Originality:** I think that the paper is original in its way of handling and presenting the work. It presents an original way at analysing work on prompting. I was not aware of this kind of approach.\n\n**Reliability:** I am not able to judge the well-foundedness and the exactness of the theoretical analysis, a field that I do not know. After documenting myself on the topic, I do not think that there is any reason to suspect any error.\n\n**Significance:** Although the idea of the study is interesting, the results might not be so influencial. The characterisation in two conditions is interesting and somehow might sound paradoxical: some simple problems (large additions) will not be so well handled by the proposed prompting approach, while other simlarly simple ones (long multiplications) will profit from it.", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- Logical flow of the paper.\n- Research questions are clearly identified.\n- Theoretical analysis leading to clear conditions to delimit the efficiency of a proposed approach.\n- Experimental results that confirm the predictions.\n- For me, new way of considering how we should analyse prompting.", "reasons_to_reject": "- Maybe too simple results.\n- The theoretical results need some further explanation. and it might be questionable whether such a formalisation is really needed to extract the conditions.\n- The algorithms are a little bit simplistic and might not be necessary.\n\nThe theoretical analysis is out of my competency. So, although I doumented myself and tried to understand, I cannot really judge. The opinion of the other reviewers is needed.", "questions_to_authors": "**Style:** I had problems with the syntax in many places. In particular subject-verb agreement is flawed in many different places. Because I am not a native speaker of English myself, I hate to say it, but correction using some automatic grammar-checker and spell-checker is really needed.\n\n**Figure 1:** it takes time to identify the relevant parts #Material#, etc. in the figure and how they interact. A better layout might be welcome.\n\n**Notations:** There are notations to explain IO prompting and CoT, but then no notation for the other prompting startegies. This is deceiving as the easy to understand formulae for the first two ones apear a lttle bit superfluous.\n\n**Line 180:** finally, what are the criteria to decide when a sub-task \"is easy enough to be handled by the LLM\"?\n\n**Theoretical Analysis:** A simple note on what TC^0 and NC^1 are would be welcome. Also the fact that it is known that TC^0 is included in NC^1 should be mentioned, and succintly explained, as this is missing frm the text.\n\n**5.1. Longer Integer Arithmetic** I understand that the paper is following teh method in previosu wosk, but is edit distance the right way of measuring the success in the task. Shouldn't accuracy be preferred in the first place. Wouldn't the difference between the solution output by the LLM and the exact solution be a better metric?\n\n**Table 2.** Some further analysis on the balance between recall and precision would be welcome. In particular it could be observed that the proposed approach is better balanced, wheras almost all other approaches are unbalanced and seem to favour either recall or precision. Is this due to some intrinnsic features of DaC?\n\n**Location of tables** Tables 2 and 3 could be placed in the respective paragraphs they illustrate.\n\n**Bibliography:** too many cited papers form ArXiv. Check whether these papers have been reviewed and published in reliable venues (I mean venues with a reviewing committee).", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes a new method of prompting: divide-and-conquer, and provides theoretical understandings on under what conditions can this prompting help improve performance.

Pros:
- The paper is well-written.
- The theoretical analysis is insightful and provides groundings of whether the proposed prompting works vs not, and on what type of tasks.
- Experiments on a few real tasks showed the effectiveness (and ineffectiveness) of the DaC prompting.

Cons:
- As some reviewers point out, the study is relatively narrow in scope, and the proposed method only works (as the authors point out) on a very restricted set of tasks. How to reliably determine whether a task is applicable in practice also remains to be a question.
Decision: Accept