An Examination on the Effectiveness of Divide-and-Conquer Prompting in Large Language Models

Dear Reviewer,

We appreciate your detailed feedback on our paper, "An Examination on the Effectiveness of Divide-and-Conquer Prompting in Large Language Models." Below, we address your concerns and provide clarifications:

Generalizability of Findings

Reviewer Concern: "The paper does not explore DaC's applicability to a broader range of tasks or domains, limiting the generalizability of findings."

Response: We acknowledge the importance of exploring broader applicability. However, our study intentionally focuses on two representative and challenging domains (arithmetic and fact verification) to ensure the theoretical and empirical analysis is both rigorous and interpretable. While expanding the scope is valuable, the current scope aligns with our research questions and highlights tasks where DaC excels. We explicitly outline the conditions under which DaC is beneficial in Section 4.3, laying a foundation for future studies to expand this work.

Novelty of DaC Prompting

Reviewer Concern: "It is difficult to claim that the idea of divide-and-conquer prompting is novel, as many prompting strategies exist. The paper does not compare with recent studies, such as Graph of Thoughts and Program of Thoughts."

Response: Our contribution is not limited to proposing DaC as a strategy but rather providing a theoretical framework that formalizes its utility and limitations. This framework, to the best of our knowledge, is the first to rigorously characterize DaC's expressive power relative to other strategies like Chain-of-Thought and Least-to-Most. Additionally, we emphasize the efficiency and robustness of DaC in tasks with parallel sub-tasks and intermediate errors. We note that comparisons with Graph of Thoughts and Program of Thoughts are indeed valuable and will be added to the discussion in future iterations.

Accessibility of Theoretical Analysis

Reviewer Concern: "The theoretical analysis may be challenging for readers without a strong background in computational complexity theory."

Response: We strive to balance technical depth and accessibility. To assist readers with less background, we provide intuitive explanations alongside formal proofs (e.g., in Sections 4.1 and 4.2). Furthermore, we include a summary table (Table 1) and diagrams (Figure 2) to visually clarify key insights. In future revisions, we are committed to enhancing accessibility by adding simplified summaries in an appendix.

Comparison with Latest Prompting Techniques

Reviewer Question: "How does DaC compare with the latest prompting techniques or methods in terms of performance and computational efficiency?"

Response: Thank you for raising this important question. As detailed in Tables 2 and 3, DaC outperforms other prompting strategies like Chain-of-Thought (CoT) and Least-to-Most (LtM) in specific scenarios, particularly for tasks with parallel sub-tasks and susceptibility to intermediate errors.

We acknowledge that recent methods such as Graph of Thoughts (GoT) are promising in other contexts. However, GoT is not applicable to the tasks discussed in our paper. GoT is designed for tasks requiring exploratory or search-based reasoning (e.g., planning or optimization), where multiple reasoning paths are evaluated and combined. In contrast, the tasks we address—such as large integer arithmetic and fact verification—are deterministic and involve decomposable sub-tasks that do not require such search-based exploration.

Robustness and Failure Sources

Reviewer Question: "Could the authors provide further insights into the robustness of DaC prompting and discuss potential sources of error or failure in the context of their case studies?"

Response: Robustness is a key advantage of DaC prompting, as demonstrated by our experimental results. In the fact verification task, DaC achieves significantly higher recall than other strategies such as CoT and LtM (Table 3), ensuring it effectively identifies factual inconsistencies. Similarly, in the hallucination detection task (Table 2), DaC consistently outperforms baselines by reducing intermediate errors, which are more prevalent in strategies relying on sequential reasoning.

The robustness of DaC stems from its explicit decomposition of tasks into independent sub-tasks, which mitigates error propagation—a key challenge for sequential approaches like CoT. Additionally, DaC’s reduced decoding context window size (Proposition 4.4) helps limit the accumulation of intermediate hallucinations or inaccuracies.

Our results further highlight that DaC excels in tasks involving parallel sub-tasks (e.g., large integer multiplication), while it is less impactful for tasks without such characteristics (e.g., integer addition). This aligns with our theoretical analysis and confirms the robustness of DaC within its applicable scope.

Dear Reviewer,

We appreciate your thoughtful feedback on our paper and the constructive suggestions. Below, we address your comments and provide clarifications to demonstrate the robustness and contributions of our work.

Clarification on Condition 2

Reviewer Concern: "The concept in condition 2 is too general. What does it mean to be subject to hallucinations or intermediate errors, and I think most tasks suffer from this problem. Can this definition be more specific?"

Response: Thank you for pointing this out. Condition 2 specifically refers to tasks where intermediate errors accumulate during sequential reasoning processes, as commonly observed in Chain-of-Thought prompting. While hallucinations or intermediate errors are general issues, their impact is significantly amplified in tasks involving long reasoning chains or compositional sub-tasks. We will update the manuscript to clearly define the characteristics of tasks prone to these issues and provide further examples.

Granularity of Applicable and Inapplicable Tasks

Reviewer Concern: "The granularity of the 6 tasks is completely different. Integer Multiplication and Integer Addition belong to large integer arithmetic, but the remaining four tasks are not at the same granularity. The reasons for selecting these six tasks should be described in detail."

Response: Thank you for pointing out the differences in task granularity. This variation is intentional and designed to illustrate the breadth and applicability of our theoretical framework. Specifically:

Granularity Differences: Tasks like Integer Multiplication and Integer Addition are subcategories of arithmetic operations, chosen to demonstrate the theoretical distinctions between tasks that satisfy the proposed conditions and those that do not. In contrast, broader tasks like Fact Verification or Multi-round QA represent different problem domains to clarify the boundaries of DaC's effectiveness.

Purpose of Granularity Variation: By including tasks of varying granularity, we aim to:

1. Showcase how the theoretical framework generalizes across domains.
2. Provide actionable guidance for practitioners on the types of tasks where DaC is expected to excel (e.g., those with parallel sub-tasks or error-prone intermediate steps).

Task Selection Rationale: The six tasks were chosen to validate both the applicability and limitations of DaC:

1. Applicable Tasks: Integer Multiplication, Fact Verification, and Hallucination Detection represent tasks that align well with DaC's properties and satisfy both proposed conditions.
2. Inapplicable Tasks: Integer Addition, Multi-round QA, and Planning highlight cases where DaC is less effective due to the absence of parallel sub-tasks or limited task complexity.

Answer Extraction and Metrics Analysis

Reviewer Concern: "In this paper, how is the answer extraction of the LLMs to make experimental statistics? Can the 100% on some metrics in Table 3 be analyzed in detail?"

Response: Thank you for this question. The answer extraction process in our experiments involves a two-step approach:

1. Answer Generation: LLMs first generate outputs for sub-tasks, which are then merged to form the final output (e.g., a factual consistency decision or arithmetic result).
2. Binary Decision Extraction: To simplify evaluation, we prompt the LLM to provide a binary decision (Yes or No) based on the final output, ensuring consistent and comparable results across all methods.

Regarding the 100% precision and recall observed in Table 3: This phenomenon reflects the tendency of certain baseline methods (e.g., CoT-SC and LtM) to overwhelmingly favor one class (e.g., Yes or No) in their outputs, irrespective of the actual content. While this leads to perfect scores for one metric (e.g., precision or recall), it also results in poor overall performance due to imbalanced predictions.

In contrast, DaC explicitly verifies sub-tasks independently, producing balanced outputs and consistently high performance across metrics. This characteristic is particularly evident in its superior F1 scores, as shown in Table 3, which better capture the overall effectiveness of the method.

Dear Reviewer,

We sincerely thank you for your thoughtful and constructive feedback on our work. We deeply appreciate your positive remarks about our theoretical focus and alignment of experiments with theoretical results. Below, we address your comments and aim to clarify the aspects you found confusing.

Difference Between ToT and DaC

Reviewer Concern: "From the description of the paper, it looks like DaC prompts LLMs to perform subtask decomposition first and then solve each subtask, while ToT does not distinguish between subtasks and general intermediate reasoning steps, just performing a tree-based reasoning process. From Figure 2, DaC seems to solve tasks with homogeneous decomposition. Is there any situation in which the depth of each subtask is not the same?"

Response: Thank you for highlighting this important distinction. Your understanding is correct: DaC explicitly separates task decomposition, subtask resolution, and solution merging, while ToT interweaves intermediate reasoning with search-based exploration. The key differences are:

1. Task Characteristics: DaC excels in problems with homogeneous parallel subtasks (e.g., large integer arithmetic or fact verification), where subtasks are well-defined and largely independent.
2. Heterogeneous Subtasks: DaC is also applicable when subtasks vary in complexity or "depth." For example, in hierarchical document summarization, some paragraphs may require deeper reasoning or multiple decomposition levels. In such cases, DaC can recursively decompose tasks until the subtasks are manageable.

Theorem 4.1 and Its Implications

Reviewer Concern: "Theorem 4.1 seems trivial to me as all IO prompts can be seen as special cases of DaC prompts, so there must be $S(IO) \subseteq S(DaC)$."

Response: Thank you for raising this point. We agree that the conclusion that IO prompting is a subset of DaC prompting (i.e., $S(IO) \subseteq S(DaC)$) is indeed trivial and intuitive. However, the primary contribution of Theorem 4.1 lies not in this subset relationship but in proving the existence of a gap between IO and DaC in terms of expressive power (i.e. $S(IO) \subset S(DaC)$), which is far from trivial.

1. Non-Trivial Contribution: By leveraging computational complexity theory, we demonstrate that DaC can solve problems in NC1 (e.g., 2-BSI) that are provably outside the scope of IO prompting. This result establishes a clear and rigorously defined gap between the two paradigms, providing a theoretical guarantee of DaC's superiority in handling certain tasks.

2. Significance of the Gap: This gap is critical for identifying tasks where DaC can outperform IO such as our discussion about multiplication and addition

Dear Reviewer,

Thank you very much for your thoughtful and constructive feedback. We greatly appreciate your recognition of the theoretical contributions of our work and its practical value in understanding and applying Divide-and-Conquer (DaC) prompting. Below, we address the specific weaknesses and questions you raised.

Error Analysis in CoT and DaC

Reviewer Concern: "In the task decomposition stage of Algorithm 1 and Algorithm 2, hallucinations or intermediate errors also seem to occur. It is not clear whether the errors in CoT stem from the subtask solutions rather than the subtask decomposition. I suggest conducting further statistical analysis on the types of errors in CoT and DaC."

Response: Thank you for this insightful suggestion. While our current analysis primarily focuses on overall performance metrics, we agree that a deeper statistical breakdown of errors would provide more clarity. Specifically:

In CoT, errors predominantly arise from the propagation of inaccuracies across intermediate steps, which is compounded by the sequential nature of reasoning. This often leads to hallucinated intermediate results impacting the final outcome. In DaC, errors in task decomposition are possible, but they are generally confined to the boundaries of sub-tasks and do not propagate across the entire reasoning process. This containment reduces the overall impact of individual errors.

Applicability and Token Usage

Reviewer Concern: "Considering that the applicability of DaC may not be as broad as CoT and that the reasoning process may require more tokens, the potential impact of this paper might not be as significant as Feng et al. 2023."

Response: We appreciate your perspective and agree that DaC has a narrower scope compared to CoT, as it is particularly suited to tasks with parallel sub-tasks or those prone to intermediate errors. However, we believe this narrower applicability is balanced by DaC’s robustness and efficiency in handling these specific tasks:

1. Task Suitability: DaC is designed for scenarios where sub-tasks are well-defined and largely independent. For such tasks (e.g., large integer multiplication, fact verification), DaC reduces error propagation and achieves significant performance gains, as shown in Tables 2 and 3.
2. Token Usage: While DaC may require additional tokens for task decomposition and merging, the overall token usage is comparable to CoT due to shorter context lengths during sub-task resolution. We will include a detailed comparison of token usage and inference time between DaC and CoT in our revisions to provide clarity on this point.

Token Usage and Inference Time

Reviewer Question: "How do the token usage and inference time of DaC compare to those of CoT?"

Response: In terms of token usage:

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 terms of inference time:

DaC’s inference time is influenced by the parallelism of sub-task processing. When parallel execution is supported, DaC can achieve faster inference compared to CoT for tasks with large numbers of independent sub-tasks. However, for tasks requiring sequential reasoning, CoT remains more efficient.