Source-linked AI summary
Training LLMs for Divide-and-Conquer Reasoning Elevates Test-Time Scalability
Xiao Liang, Zhong-Zhi Li, Zhenghao Lin, Eric Hancheng Jiang, Hengyuan Zhang, Yelong Shen, Kai-Wei Chang, Ying Nian Wu, Yeyun Gong, Weizhu Chen
TL;DR
The paper addresses the gap between general or CoT-centric post-training and DAC inference, which limits DAC reasoning on challenging tasks. It introduces end-to-end DAC-RL that trains decomposition and solution generation together, and reports higher reasoning ceilings and stronger scalability than CoT on competition-level benchmarks.
Problem
General or CoT-centric post-training is misaligned with DAC inference, limiting models’ ability to use DAC reasoning effectively on challenging problems.
Method
DAC-RL uses end-to-end reinforcement learning to train a policy to decompose problems, solve subproblems, and answer the original problem conditioned on those solutions.
Results
8.6% in Pass@1 and 6.3% in Pass@32 are the reported DAC-style margins over CoT on competition-level benchmarks.
Takeaways & Limitations
DAC-style reasoning achieves a higher performance ceiling and stronger test-time scalability than traditional step-by-step CoT on the evaluated benchmarks.
Takeaways & Limitations
The division policy must generate more than Ns subproblems; without this constraint, it can collapse to producing no useful subproblems and revert to CoT-like solving.
Abstract
from arXiv · showhide
Large language models (LLMs) have demonstrated strong reasoning capabilities through step-by-step chain-of-thought (CoT) reasoning. Nevertheless, at the limits of model capability, CoT often proves insufficient, and its strictly sequential nature constrains test-time scalability. A potential alternative is divide-and-conquer (DAC) reasoning, which decomposes a complex problem into subproblems to facilitate more effective exploration of the solution. Although promising, our analysis reveals a fundamental misalignment between general-purpose post-training and DAC-style inference, which limits the model's capacity to fully leverage this potential. To bridge this gap and fully unlock LLMs' reasoning capabilities on the most challenging tasks, we propose an end-to-end reinforcement learning (RL) framework to enhance their DAC-style reasoning capacity. At each step, the policy decomposes a problem into a group of subproblems, solves them sequentially, and addresses the original one conditioned on the subproblem solutions, with both decomposition and solution integrated into RL training. Under comparable training, our DAC-style framework endows the model with a higher performance ceiling and stronger test-time scalability, surpassing CoT by 8.6% in Pass@1 and 6.3% in Pass@32 on competition-level benchmarks.
1. Introduction
Standard CoT reasoning becomes limited on the hardest tasks, while DAC inference offers a promising alternative but is misaligned with general post-training. The paper proposes dedicated DAC-RL training and evaluates its effects on competition-level reasoning benchmarks.
- Standard CoT prompting often has limited effectiveness on highly challenging reasoning tasks, including olympiad mathematics and advanced theorem proving.
- DAC reasoning decomposes complex problems into subproblems and uses structured reasoning to facilitate final solutions and test-time scalability.
- General or CoT-centric post-training is misaligned with DAC inference, constraining DAC reasoning even on problems that CoT can solve.
- Direct DAC inference generally underperforms CoT in evaluated models, indicating that dedicated DAC training is needed to unlock DAC-style problem solving.
- DAC-RL trains decomposition and solution generation jointly through end-to-end reinforcement learning, targeting higher performance ceilings and stronger test-time scalability.
- 8.6% in Pass@1 and 6.3% in Pass@32 are the reported DAC-style improvements over CoT on competition-level benchmarks.
2. Method
The method trains an LLM to divide each problem into subproblems, solve them sequentially, and then solve the original problem using those solutions. Reinforcement learning jointly optimizes division and conquering, using final-answer correctness and division-validity signals.
- DAC-style reasoning: DAC-style inference first generates a set of subproblems, then sequentially solves them before answering the original problem conditioned on those solutions.The division and conquering responses are generated by the same policy.
- RL training: Each RL step optimizes both division and conquering responses through their expected rewards.Division creates subproblems; conquering solves the subproblems and the original problem.
- RL training: The policy must generate more than Ns subproblems, preventing collapse to empty decomposition and standard CoT-like direct solving.Without this constraint, the conquering stage degrades to directly solving the original problem.
- Reward design: Division rewards combine format validity, quantity validity, and subproblem helpfulness for solving the original problem.Helpfulness rewards groups that enable at least one correct original-problem solution.
- Reward design: Because subproblem ground truths are unavailable, final-answer correctness from the conquering response serves as a surrogate reward for subproblem solving and the original answer.The scalar reward is presented as a consistent surrogate signal under the stated causal-direction assumption.
- Training procedure: Algorithm 1 samples division groups and conquering candidates, computes correctness and division rewards, stores both tuple types, and updates the policy from the experience buffer.The procedure repeats this process for T training steps.
3. Experiments
Experiments evaluate DAC-RL across competition-level mathematical benchmarks and compare its training trajectory and scalability with CoT-RL. DAC training ultimately surpasses CoT performance and remains beneficial under deeper training.
- 3.1. Settings: Experiments use Qwen2.5-7B-Instruct and Qwen3-4B-Instruct-2507 on four competition-level mathematical benchmarks with integer answers.Training uses DAPO-Math-17k and evaluates Pass@1 and Pass@32.
- 3.2. Main Results: 6.3% overall Pass@32 improvement is achieved by DAC-style training for Qwen3-4B-Instruct-2507, compared with standard CoT RL.The corresponding improvement for Qwen2.5-7B-Instruct is 3.4%.
- 3.2. Main Results: DAC performance begins below CoT but grows faster during training, eventually exceeding CoT on the evaluated benchmarks.CoT-RL provides no further gains for Qwen3-4B-Instruct-2507, suggesting saturation after post-training.
- 3.2. Main Results: Figure 4 tracks intermediate evaluations across four benchmarks and includes a difficult-subset update and a 32-rollout CoT comparison in its respective panels.The middle panel updates Qwen3-4B-Instruct-2507’s training set after the 400th iteration.
4. Analysis
Analysis examines mixed CoT/DAC training, test-time allocation, reasoning compactness and diversity, cold-start initialization, and strict subproblem-format constraints. DAC training improves both DAC-style scalability and, in some settings, CoT reasoning, while strict formatting can reduce evaluation performance.
- 4.1. Integrating CoT- and DAC-RL Training: Over 10% improvement in CoT performance across all benchmarks occurs when Mix-RL adds DAC training on challenging problems.Further CoT-style RL training alone yields no additional gains in the comparison.
- 4.1. Integrating CoT- and DAC-RL Training: Mix-RL consistently surpasses its CoT counterpart under DAC inference, while full DAC-RL outperforms Mix-RL, suggesting broader DAC training is beneficial.Mix-RL applies DAC-style solutions to problems whose CoT accuracy is below 25%.
- 4.2. Test-time Scalability and Configurations: With a fixed budget of k = 1024, allocating more subproblem groups improves Pass@k over 1024 independent CoT generations.Larger group counts increase subproblem diversity and expand the test-time exploration space.
- 4.3. Concise and Diverse Reasoning with DAC: DAC training produces shorter reasoning, fewer clipped rollouts, and higher policy entropy than CoT-style RL.The combination indicates compact training responses alongside broader solution-space exploration.
- 4.4. Cold-Start DAC Training: Cold-start distillation improves both DAC and CoT, while subsequent RL fine-tuning yields a larger gain for DAC than for the CoT baseline.Under an equal budget of 3k samples, the distilled model has stronger DAC-style reasoning than CoT.
- 4.5. The Effects of a Subproblem-Solving Format Constraint: Strict subproblem-answer formatting increases format adherence but worsens evaluation performance, indicating an alignment tax.The constraint requires explicitly answering every generated subproblem before the final answer.
5. Related Work
Related work frames DAC as a decomposition-and-combination strategy used in prompting and structured LLM reasoning. Existing methods mainly apply DAC during inference, motivating unified RL training to align training with DAC reasoning.
- 5.1. Divide-and-Conquer in LLM Reasoning: DAC decomposes complex problems into smaller subproblems, solves them, and combines their solutions into a final answer.LLM approaches implement this through prompting, expansion, search, reflection, or staged reasoning.
- 5.1. Divide-and-Conquer in LLM Reasoning: Existing DAC studies primarily apply the strategy during inference, creating misalignment with general post-training that emphasizes direct problem answering.The paper positions unified RL training as its response to this gap.
- 5.2. Reinforcement Learning for LLM Reasoning: Prior RL research has improved complex reasoning and explored optimization methods that strengthen generalization and exploration.The paper builds on algorithms including PPO, GRPO, and DAPO.
6. Conclusion
The paper identifies a gap between general or CoT-centric post-training and DAC inference, then uses RL training to enhance DAC reasoning. Experiments report a higher performance ceiling and stronger test-time scalability than traditional CoT on competition-level benchmarks.
- 6. Conclusion: DAC-RL addresses the gap between general post-training and DAC inference by training LLMs for DAC reasoning.The study evaluates DAC beyond standard CoT for complex reasoning problems.
- 6. Conclusion: DAC-style reasoning achieves a higher performance upper bound and stronger test-time scalability than traditional step-by-step CoT.The reported improvements occur on competition-level benchmarks.
A. Preliminaries on GRPO for LLMs
GRPO performs group-relative reinforcement learning for LLMs without requiring a separate critic, using normalized rollout rewards and constrained policy updates.
- GRPO mechanism: GRPO computes token advantages from rewards normalized within a group of generated responses.The advantage is based on each response's reward relative to the group mean.
- GRPO mechanism: The method avoids an additional critic model for estimating token values.
- GRPO mechanism: GRPO clips the policy probability ratio within a trust region to stabilize optimization.A KL term also limits deviation from the reference model.
- Implementation: The training incorporates Clip-Higher and Token-Level Loss to improve training efficiency.
B. Proof for Lemma 2.1
The proof models subproblem correctness as influencing final-answer correctness and shows that rewarding correct final answers can favor trajectories with more correct subproblems under stated assumptions.
- Setup: The conquering procedure solves subproblems sequentially before solving the original problem, inducing a causal structure from subproblem outcomes to final correctness.
- Assumptions: Assumption 1 requires final-answer correctness probability to be nondecreasing in every subproblem's correctness.It must be strictly increasing in at least one coordinate.
- Assumptions: Assumption 2 states that the policy parameters determine the distribution of subproblem correctness.
- Proof: The proof expands final-answer correctness using the law of total probability over subproblem-correctness configurations.It represents the result as an expectation of the conditional final-answer correctness function.
- Proof: Under monotonicity, improving final-answer probability shifts probability toward configurations with more correct subproblems.The argument applies Bayes' rule to relate final-answer conditioning to subproblem correctness.
- Conclusion: The correctness indicators for a subproblem and the final answer have nonnegative covariance, with strictness when that subproblem influences the final answer.Rewarding correct final answers therefore preferentially upweights trajectories containing more correct subproblem solutions.
C. Discussion on Conquering Accuracy as Feedback for Division Reward
Using conquering accuracy directly to reward division can make the policy solve problems prematurely instead of decomposing them, motivating a relaxed helpfulness reward.
- Initial reward: The initial strategy rewards division responses with the average accuracy of conquer solutions conditioned on the generated subproblem group.
- Failure mode: Conquering-accuracy rewards cause the model to solve the original problem during division rather than generate subproblems.The behavior reflects conflict between prompt instructions and the reward objective.
- Revised reward: The proposed relaxed division reward guarantees only a lower bound on subproblem helpfulness, reducing early greedy behavior and premature optimization of the original problem.
D. A Case Study on How DAC Reduces Reasoning Redundancy
A case study contrasts DAC and CoT on the same algebraic system: both linearize the problem, but DAC follows a predefined decomposition while CoT repeatedly verifies and re-derives results.
- Case study: The case study uses a DAPO-Math-17k problem and presents partial DAC and CoT solutions targeting the same linear system.
- DAC reasoning: DAC's predefined subproblem decomposition maps each subproblem to a necessary transformation or computation.
- Comparison: DAC avoids redundant restatements and self-corrections, producing a more compressed reasoning trace than CoT.
- DAC reasoning: DAC introduces auxiliary variables and transforms the original equations into a simpler linear system.The displayed substitutions yield equations x + z = 5, x + y = 10, and y + z = 13.
E. Prompts
The framework uses separate division and conquering prompts: problems are decomposed into subproblems, whose instantiated solutions condition the solution of the original problem. The illustrated algebraic example uses pairwise-product substitutions to obtain a unique positive triple and the final answer m+n=55.
- Prompt design: The division and conquering prompts operationalize DAC reasoning by decomposing the original problem and then solving the subproblems and original problem.During training and inference, conquering-prompt placeholders are replaced with the actual decomposed subproblems.
- Algebraic transformation: The original equations are rewritten as a linear system in pairwise products x=ab, y=bc, and z=ac.The transformed equations are x+z=5, x+y=10, and y+z=13.
- Interpretation: The passages characterize the system as algebraic and structurally solvable through pairwise-product substitutions rather than requiring geometric insight.They also describe the positive solution as uniquely determined by the constraints.
- Final result: The resulting sum is 49/6 in lowest terms, so m=49, n=6, and m+n=55.The fraction is reduced because gcd(49,6)=1.