Training LLMs for Divide-and-Conquer Reasoning Elevates Test-Time Scalability

Over recent years, large language models (LLMs) such as GPT-3, PaLM, and Codex have demonstrated remarkable capabilities in language understanding and reasoning. Techniques like chain-of-thought prompting have significantly improved their performance on complex tasks by enabling step-by-step reasoning. Despite these advances, models still struggle with highly intricate problems like advanced mathematics and theorem proving, where simple sequential reasoning reaches its limits. Prior efforts, including Tree-of-Thought and DeAR, introduced problem decomposition strategies to enhance reasoning, but these were primarily used during inference, not during training. This disconnect limited the models' ability to fully leverage divide-and-conquer (DAC) strategies, resulting in performance ceilings. Recent research indicates that embedding DAC into training could unlock higher reasoning potential, but systematic frameworks for doing so remain underexplored. This paper addresses this gap by proposing a unified RL-based training paradigm that explicitly incorporates problem decomposition, aiming to elevate the reasoning capacity of LLMs.

Existing reasoning methods like CoT are effective but inherently sequential, which constrains their scalability and depth. When faced with complex, multi-step problems, models often plateau in performance, unable to explore more effective reasoning paths. The core challenge is that models trained primarily on step-by-step answers lack the ability to decompose problems into manageable subproblems during inference, especially in unseen scenarios. This mismatch between training and inference paradigms limits the models’ capacity to handle the most challenging tasks. Additionally, current approaches do not systematically optimize the problem decomposition process, leading to suboptimal exploration and solution quality. Addressing this requires a training framework that explicitly teaches models how to decompose, solve, and recombine subproblems effectively, thus overcoming the inherent limitations of traditional methods.

The key innovation is integrating divide-and-conquer reasoning directly into the training process via reinforcement learning. This involves:

• �� Designing a policy network that decomposes problems into subproblems, guided by a reward scheme evaluating subproblem usefulness and correctness.
• �� Using PPO to optimize the decomposition and solving strategies jointly, ensuring the model learns effective problem partitioning.
• �� Introducing a reward function that encourages diversity, validity, and contribution of subproblems towards the final solution.
• �� Embedding the entire process into a unified training loop, enabling the model to learn how to systematically break down and conquer complex problems.

This approach differs from prior work by systematically training the model to perform DAC, rather than relying solely on inference-time heuristics, thus elevating the model’s reasoning ceiling and scalability.

• �� The framework employs a policy network trained via PPO to generate subproblem groups from complex inputs.
• �� During each training iteration, the model decomposes each problem into multiple subproblems, guided by prompts and reward signals.
• �� Rewards are computed based on the correctness of subproblem solutions and their contribution to the final answer, encouraging meaningful decomposition.
• �� The model then sequentially solves subproblems, aggregates solutions, and evaluates the overall correctness.
• �� The training optimizes the policy parameters to maximize expected rewards, balancing exploration and exploitation.
• �� The approach incorporates techniques like mini-batch training, reward clipping, and diversity promotion to ensure stable and effective learning.

• �� The experiments utilize datasets such as AIME 2024/2025, Beyond-AIME, and HMMT-25, focusing on mathematical reasoning benchmarks.
• �� Baselines include standard CoT prompting and fine-tuned models, evaluated via Pass@1 and Pass@32 metrics.
• �� Training involves setting subproblem group sizes, minimum subproblem counts, with 400 training steps, batch size 256.
• �� Additional ablation studies examine the effects of subproblem diversity, reward schemes, and training strategies like cold-start initialization.
• �� Evaluation metrics include accuracy, solution diversity, and scalability, with multiple runs to ensure robustness.

• �� DAC-trained models outperform baseline CoT models, with an average Pass@1 gain of 8.6% across benchmarks.
• �� The models demonstrate higher reasoning depth, broader exploration, and better generalization to unseen complex problems.
• �� Experiments show that increasing the number of subproblem groups enhances exploration and solution quality.
• �� The training framework effectively pushes the model’s reasoning ceiling beyond traditional limits, enabling it to solve more challenging problems with fewer steps.

• �� The approach is suitable for scientific research, mathematical problem solving, automated theorem proving, and complex decision-making tasks.
• �� It can be integrated into AI systems requiring deep reasoning, especially where problem decomposition is natural, such as in scientific discovery or engineering design.
• �� The method supports scalable, flexible reasoning pipelines that adapt to task complexity, improving AI’s utility in real-world applications.

• �� High computational cost due to RL training, especially for large models and complex tasks.
• �� Reward design sensitivity may lead to suboptimal subproblem generation if not carefully calibrated.
• �� The approach may still face challenges with extremely novel or poorly structured problems where decomposition is non-trivial, requiring further research to improve generalization.