When Splitting Makes Stronger: A Theoretical and Empirical Analysis of Divide-and-Conquer Prompting in LLMs

Dear Reviewer uHuS,

Thank you for your insightful and positive review. We are particularly encouraged by your appreciation for the paper's logical flow, the originality of the analytical approach to prompting, the clear identification of research questions, and the experimental confirmation of our theoretical predictions. We provide the following responses to your comments and questions:

• Results and Algorithms: We believe the clarity and interpretability of the conditions derived from our analysis are a strength. Divide-and-Conquer (DaC) itself is a fundamental algorithmic paradigm, and our work demonstrates how its core principles, when applied to LLM prompting, lead to clear and significant improvements under well-defined circumstances. The algorithms (Alg. 1 & 2) are presented to formally specify the single-level and multi-level DaC processes, including recursion, which is crucial for the method's operationalization and understanding.

• Theoretical explanation: We acknowledge that the theoretical analysis can be dense. The formalization was undertaken precisely to move beyond intuition and establish formal guarantees for DaC's performance enhancement—a point you noted as significant in your "Reasons To Accept." This formal approach also allowed us to rigorously define the boundaries (Conditions 1 & 2) where DaC is provably beneficial compared to standard prompting. We are happy to clarify any specific aspects further and, as detailed below, will add more explanatory notes for terms like $TC^0$ and $NC^1$.

Dear Reviewer 1hW4,

We are very grateful to the reviewer for their thorough assessment, positive evaluation, and insightful comments. We are particularly encouraged that the reviewer recognized the rigorous theoretical support for our Divide-and-Conquer (DaC) strategy, its effectiveness in reducing intermediate errors in parallelizable tasks, and its practical utility with actionable guidelines.

We appreciate the suggestions for strengthening the work's generalizability and offer the following responses:

1. Task scope: The current paper's primary goal was to first establish the theoretical guarantees and empirical validation for "pure" DaC within its identified applicable domain. We acknowledge that the DaC strategy, as presented in this paper, is primarily designed for tasks that can be effectively decomposed into parallel subtasks (Condition 2.1). This focus was intentional to clearly establish its foundational principles and benefits for this specific class of problems. As the reviewer notes, Table 1 explicitly lists tasks like multi-round QA and planning as non-applicable due to their sequential nature, thereby defining the current scope. The suggestion to explore hybrid approaches, such as combining DaC with CoT for tasks involving mixed reasoning, is an excellent one. Indeed, our future work aims to "expand the appliance scope of DaC to more areas like question answering", which would naturally involve investigating such hybrid models.

2. Further theoretical analysis (for multi-level DaC complexity): Our primary theoretical focus was on establishing the expressive power bounds of DaC relative to other prompting strategies (Section 4.1, 4.2) and identifying the conditions under which DaC is beneficial. We do, however, qualitatively address efficiency considerations. The paper notes 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" in #line 152. Furthermore, Appendix A.2, Practical Guidelines for Practitioners, states, "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". To further illustrate how overheads might accrue in a multi-level scenario, we've worked through an illustrative token usage and call count estimation for a 5-digit multiplication, like 12345×67890, which is a task that would utilize the Multi-Level DaC Solver (Algorithm 2).

Here’s a table summarizing the illustrative breakdown:

Tabel 1: Illustrative Multi-Level DaC for $12345 \times 67890$

Dear Reviewer kq9V,

We sincerely thank you for your positive assessment of our paper, particularly for recognizing the solid and well-motivated theoretical analysis and the encouraging performance gains from the Divide-and-Conquer (DaC) prompting strategy. While our paper notes that "DaC requires additional tokens for sub-task decomposition and solution merging, but reduces the average decoding context window size during sub-task resolution" and discusses efficiency trade-offs in Appendix A.2, we agree that concrete comparisons would strengthen our analysis. To further address your valuable suggestion and illustrate these trade-offs more concretely, we've prepared some illustrative token usage comparisons for tasks discussed in our paper:

Table 1. Illustrative Token Usage Comparison for $1234 \times 5678

Table 2. Illustrative Token Usage Comparison for Hallucination Detection (5-sentence summary)

Reflecting on these illustrative comparisons, when considering the DaC prompting strategy, practitioners 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, as identified in our paper. The tables suggest DaC might involve higher token counts, particularly if context like a source document is repeated across sub-tasks. However, this is a trade-off for key advantages. As discussed in our paper (e.g., Section 4.3), DaC is beneficial for tasks harder than $S(IO)$, contain many parallelizable sub-tasks, and are prone to intermediate errors or hallucination. Our paper's Appendix A.2 provides practical guidelines, emphasizing task assessment for suitability—DaC excels with independent subtasks where standard prompting might lead to error accumulation. A crucial benefit of DaC is the reduction in the average decoding context window size for each sub-task (as highlighted in your provided summary table and discussed in lines 212-220 of our paper), which can improve performance and manage complexity, especially for models with context limitations. Furthermore, the parallel nature of DaC sub-tasks offers potential for reduced latency. While CoT might appear more token-efficient for simpler tasks, DaC's structured approach can unlock superior performance and reliability for complex problems that align with its core principles, like isolating and preventing "deceptive content flow" in verification tasks (as mentioned in lines 137-139 of our paper regarding sequential methods). Thus, the potentially higher token cost can be a justified investment for these gains in reliability.

We thank the reviewer for highlighting this practical aspect, and we will incorporate such discussion in our revised version.

Thank you authors for providing these details! Including this in the final paper if accepted would be beneficial to the community. I will retain my positive score.

Dear Reviewer N6F9,

We sincerely thank you for your positive assessment of our theoretical framework and for your insightful questions regarding the practical implementation and nuances of the Divide-and-Conquer (DaC) prompting strategy. We appreciate the opportunity to clarify these aspects.

Detailed Prompt Templates and Task Decomposition

We would like to clarify that detailed prompt templates for the specific tasks used in our experiments (Large Integer Multiplication, Hallucination Detection, and Misinformation Detection) are provided in Appendix A.6 of the submitted manuscript. These include the exact prompts used for the task decomposition ($d$), sub-task tackling ($t$), and solution merging ($m$) stages. For instance, for Large Integer Multiplication, the decomposition prompt $d$ is: "Please split the string a 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...". Similarly, for text-based tasks like Hallucination Detection, the decomposer prompt $d$ guides the LLM to segment paragraphs into sentences.

In our DaC framework, the LLM executes the task decomposition based on specific prompts ($L(d,S)$ as shown in Algorithms 1 and 2). The strategy for decomposition, however, is determined by the task type and the desired level of controllability. Our paper presents comprehensive experiments of decomposition that incorporate both human-guided and LLM-based approaches.

• For numerical tasks like multiplication, the decomposition strategy is typically human-defined, following established algorithms (e.g., splitting numbers, as described for AB×CD). These strategies are then translated into prompts for the LLM to execute, ensuring precision and adherence to the algorithm. By carefully crafting the decomposition prompt $d$, we can direct the LLM to split tasks in a way that is most beneficial for the subsequent sub-task processing and merging stages.
• For text-based tasks such as fact verification or consistency evaluation (examples of generation/analysis tasks), the decomposition is guided by prompts that instruct the LLM to segment the input into meaningful, parallelizable units, like sentences.
  • Prompt Design for LLM Decomposition: Prompts are designed to guide the LLM toward a specific, useful decomposition suitable for parallel processing, as detailed in Appendix A.6.
  • Handling Incorrect Splits: While incorrect splits by the LLM are possible, the Multi-Level DaC Solver (Algorithm 2) can recursively further decompose sub-tasks that remain too complex. We recognize that developing more sophisticated methods for detecting and correcting decomposition errors represents an important avenue for future research.
  • LLM Autonomy in Choosing DaC: Currently, the decision to apply DaC is based on our theoretical analysis of task characteristics (Section 4.3). Extending the framework to enable autonomous LLM decision-making regarding DaC application presents a promising direction for future work, potentially enhancing both the flexibility and effectiveness of our approach.

Long Integer Addition with DaC

We thank the reviewer for this question, as it allows us to clarify an important aspect of our experimental design. As shown in Table 1, the Long Integer Addition task was intentionally chosen as a case where DaC is not expected to provide benefits, thereby helping to validate the boundaries of our proposed conditions for DaC's effectiveness. The following is the detailed explanation:

• Theoretical Unsuitability: As stated in Section 5.1, integer addition "does not satisfy the first condition", which is that "the task is harder than S(IO)". Applying DaC to such tasks introduces overhead (multiple LLM calls for decomposition, sub-task solving, and merging) without a corresponding benefit in expressive power or error reduction for that specific task type.
• Demonstrating Boundary Conditions: The purpose of including the addition was to empirically demonstrate that DaC does not universally improve performance and that its advantages are specific to tasks meeting the identified criteria. The results in Figure 3b (showing DaC performing worse than or comparable to IO prompting for addition) confirm our theoretical prediction that DaC is not advantageous for this type of problem. While the DaC mechanism (splitting numbers, processing parts, then summing) can be mechanically applied to addition, the inherent simplicity of addition relative to the LLM's capabilities means the decomposition and merging steps add unnecessary complexity and potential for minor errors or inefficiencies, leading to slightly worse performance.

We believe these clarifications address the reviewer's concerns. We are confident in the contributions of our work, particularly the theoretical formalization and the identification of its applicable scope. We will incorporate these clarifications into the manuscript.