Juliette Decugis, Fabian Gloeckle, Francis Bach, Taco Cohen, Gabriel Synnaeve
This paper proposes DecompRL, a reinforcement learning method that learns to decompose hard coding problems into modules, implement them, and recombine the implementations to solve problems that standard LLMs cannot.
Large Language Models (LLMs) struggle with extremely difficult problems where the base policy has near-zero probability of generating a correct solution, rendering repeated sampling or standard RL ineffective due to an excessively large search space.
DecompRL introduces an RL algorithm that explicitly learns to decompose problems into smaller, independently solvable sub-functions and implement them. The recombination of these modular implementations yields up to k^n candidate solutions, shifting the computational bottleneck from GPU inference to cheap CPU evaluation.
On benchmarks like LiveCodeBench and CodeContests, DecompRL significantly outperforms standard and diversity-optimized RL baselines, solving problems unreachable by standard generation. It also reduces GPU token costs by approximately 50x, demonstrating a more efficient approach to scaling test-time compute for hard problems.