🤖 machine learning

DecompRL: Solving Harder Problems by Learning Modular Code Generation

The paper introduces DecompRL, a reinforcement learning algorithm that enables Large Language Models to solve previously intractable coding problems by learning to decompose tasks into modular sub-functions, which are then recombined to exponentially expand the search space and significantly reduce GPU inference costs.

Original authors: Juliette Decugis, Fabian Gloeckle, Francis Bach, Taco Cohen, Gabriel Synnaeve

Published 2026-07-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Juliette Decugis, Fabian Gloeckle, Francis Bach, Taco Cohen, Gabriel Synnaeve

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "One-Shot" Bottleneck

Imagine you are trying to solve a very difficult puzzle. You have a super-smart robot (a Large Language Model) that can try to solve it for you.

Currently, the standard way to get the robot to solve hard puzzles is to ask it to try over and over again.

The Old Way: You ask the robot, "Write me a whole solution." If it fails, you ask again. If it fails again, you ask again.
The Problem: Every time you ask the robot to write a whole new solution from scratch, it costs a lot of money and time (GPU power). If the puzzle is really hard, the robot might need to try millions of times to get one right. This is like hiring a master chef to cook a full 10-course meal from scratch every single time you want to see if they can make a decent omelet. It's too expensive.

The New Idea: The "Lego" Approach (DecompRL)

The authors of this paper realized that instead of asking the robot to build the whole castle at once, we should teach it to build the castle piece by piece.

Think of a complex coding problem like building a massive Lego castle.

Standard Method: The robot tries to build the entire castle in one go. If it gets the roof wrong, the whole thing fails.
DecompRL Method: The robot is taught to break the castle down into small, independent parts: "Here is a wall," "Here is a door," "Here is a window."

Once the robot has learned to make these small parts, something magical happens: Recombination.

Imagine the robot makes 5 different versions of a "wall," 5 different versions of a "door," and 5 different versions of a "window."
Instead of building 5 full castles (which is expensive), you can mix and match them. You can take Wall #1, Door #3, and Window #5 to make a new castle. Then Wall #2, Door #1, Window #4.
With just 15 small parts, you can create 125 different castles (5 x 5 x 5).

How It Works: The Two-Step Dance

The paper introduces a new training method called DecompRL that teaches the robot to do this "Lego" approach. It uses two specialized roles (policies):

The Architect (Decomposition Policy): This part of the robot looks at the hard problem and says, "Okay, to solve this, we need a sorting function, a math function, and a printing function." It breaks the big problem into small, manageable tasks.
The Builder (Implementation Policy): This part of the robot writes the code for each of those small tasks.

The Magic Trick:
The system generates many different versions of the "Architect's plan" and many different versions of the "Builder's code." Then, it uses a cheap computer (CPU) to mix and match all the combinations.

The Cost Shift: Writing the code is expensive (like hiring a high-paid architect). Checking if the code works is cheap (like a simple quality check).
The Result: By generating fewer "whole" solutions but mixing and matching many "parts," the system can test thousands of potential solutions for the price of generating just a few. It shifts the bottleneck from expensive "brain power" (GPU) to cheap "checking power" (CPU).

Why This Matters

The paper shows that for very hard problems where the robot usually fails 99.9% of the time:

Standard methods hit a wall. No matter how many times you ask the robot to try a whole solution, it just keeps failing.
DecompRL keeps getting better. Because it can test thousands of combinations by mixing and matching small parts, it finds solutions that the "whole solution" method never could.

The Catch (Limitations)

The paper is honest about the downsides:

The "Format Tax": For easy problems, breaking things down is actually slower and less efficient. It's like taking apart a sandwich to eat the bread and meat separately when you could have just eaten the sandwich. The robot needs to be trained specifically to know when to break things down.
Training Difficulty: The robot doesn't naturally know how to do this. It has to be retrained from scratch using a special reinforcement learning process to learn the "Architect" and "Builder" roles.

Summary

DecompRL is a new way to teach AI to solve hard problems by stopping it from trying to write the whole answer at once. Instead, it teaches the AI to build a toolbox of small, reusable parts. By mixing and matching these parts, the AI can test millions of possibilities without paying the high cost of generating millions of full answers. It turns an expensive "guess and check" game into a cheap "mix and match" game.

Technical Summary: DecompRL

Problem Statement

Large Language Models (LLMs) currently struggle to solve complex problems where the base policy has a near-zero probability of generating a correct solution. Existing strategies face significant bottlenecks:

Repeated Sampling (pass@k): While effective for scaling test-time compute, the GPU cost grows linearly with the number of attempts. Performance gains often grow logarithmically relative to these linear costs.
Standard Reinforcement Learning (RL): Methods like Proximal Policy Optimization (PPO) or Group Relative Policy Optimization (GRPO) improve single-attempt accuracy (pass@1) but often reduce sample diversity. This undermines their effectiveness when scaling inference for high $k$ values ( $k \gg 100$ ).
The Core Limitation: When the search space is too large, neither increased sampling nor gradient signals can overcome the low probability of the base policy producing a correct solution.

Methodology: DecompRL

The authors propose DecompRL, a reinforcement learning framework that shifts the scaling bottleneck from expensive GPU inference to cheap CPU evaluation by leveraging hierarchical modular generation.

1. Hierarchical Inference

Instead of generating a monolithic code solution, DecompRL trains models to decompose a problem into a hierarchy of independently solvable sub-functions.

Decomposition Policy ( $\pi(D)$ ): Breaks a problem $x$ into a set of $n$ functions specified by signatures and natural language docstrings ( $D$ ).
Implementation Policy ( $\pi(I|D)$ ): Generates $k$ independent implementations for each function in $D$ .
Recombination: By generating $k$ implementations for each of $n$ functions, the system creates $k^n$ candidate solutions through recombination. This allows for a combinatorial explosion of potential programs ( $k^n$ ) with only a linear inference cost ( $k \times n$ tokens).

2. Reinforcement Learning Objectives

DecompRL treats hierarchical inference as a cooperative multi-agent RL problem involving two policies. To handle the sparse rewards and high variance inherent in recombination, the authors introduce specific algorithmic adaptations:

LogMeanExp Objective: To balance exploration and exploitation, the authors use a soft objective function defined as $\text{logmeanexp}_\beta(r_1, \dots, r_n) = \beta \log(\frac{1}{n} \sum e^{r_i/\beta})$ . This interpolates between the average ( $\beta \to \infty$ ) and the maximum ( $\beta \to 0$ ), approximating a log-uniform mixture of pass@k objectives.
Leave-One-Out Baseline: To compute policy gradients, the authors use a leave-one-out baseline. For a specific action (decomposition or implementation), the advantage is calculated by comparing the multi-sample objective of the full set of rewards against the objective computed from the set excluding that action. This reduces gradient variance and prevents bias.
Sequential Training: The decomposition and implementation policies are trained sequentially (alternating steps) rather than jointly. This addresses the "moving target" problem in multi-agent RL, preventing the implementation policy from overfitting to a specific decomposition and vice versa.

3. Computational Shift

The method fundamentally shifts the computational bottleneck:

Standard RL: Dominated by GPU inference costs for generating full solutions.
DecompRL: Dominated by CPU execution costs for evaluating recombined solutions. GPU token generation is reduced by approximately 50× for equivalent evaluation budgets (e.g., 512 evaluations).

Key Results

Experiments were conducted on LiveCodeBench and CodeContests using Qwen 2.5 7B, Llama 3.1 8B Instruct, and Code World Model 32B.

Performance on Hard Problems: DecompRL outperforms standard RL baselines (GRPO, pass@k training, SPO) when token budgets exceed $10^5$ . It solves problems that standard generation cannot reach, achieving up to 35% solve rates on the "hard" subset of LiveCodeBench.
Scaling Behavior: While standard methods saturate as token budgets increase, DecompRL's success rate continues to scale. With up to 3 million tokens per problem, it significantly outperforms existing methods.
Diversity and Recombination: The method generates diverse solutions. Analysis shows that models trained with DecompRL learn to create larger decompositions (more functions) as training progresses, which correlates with higher success rates at large inference budgets.
Efficiency: At 512 evaluations per problem, DecompRL reduces GPU token generation from ~198k (standard) to ~4k, shifting the wall-clock time dominance to CPU execution (99.6% CPU time vs. 0.4% GPU time).

Significance and Claims

The paper claims that DecompRL offers a novel pathway for solving "harder" problems where the base policy has near-zero success rates:

Overcoming the Cold Start: It acts as an exploration tool to discover correct solutions for tasks unreachable by standard high-pass@k sampling, making it a natural complement for policy distillation pipelines.
Efficient Scaling: By decoupling generation cost from evaluation cost, it allows scaling search on cheap CPU clusters without proportionally increasing GPU footprints.
Modularity as a Control Axis: The resulting generation pipeline offers interpretability and control axes not available in repeated sampling or scaled chain-of-thought methods.
Limitations: The authors note a "format tax" where hierarchical inference underperforms on easy problems or low token budgets compared to monolithic generation. They also observe a tendency for "size collapse" (reducing decomposition size) during training, which they mitigate via the logmeanexp objective and sequential training.

The authors position DecompRL not as a replacement for standard RL post-training (which remains more sample-efficient for strong starting policies) but as a specialized exploration strategy for discovering high-quality data and solving previously unsolvable tasks.