Reinforcement Learning for Code Optimization

Analysis

Why This Paper Matters

Code optimization is a critical yet underexplored area for reinforcement learning (RL) applied to large language models (LLMs). While RL has succeeded in code correctness (e.g., generating programs that pass tests), extending it to optimization—where execution time is the reward—has proven difficult due to measurement noise, reward sparsity, and training instability. This paper systematically identifies these failure modes and proposes a three-stage solution that makes optimization learnable. The significance lies in bridging the gap between correctness-focused RL and real-world performance tuning, which is essential for deploying efficient code in latency-sensitive applications.

Technical Contributions

• DMC-Optim Benchmark: A new benchmark with large optimization tests and a calibrated sandbox that reduces timing noise, providing a reliable evaluation environment.
• Reward Composition: Combines correctness and speed into a single reward signal, using an offline simulator to predict the most promising configurations before full RL training.
• Adapted GRPO: Modifies the Group Relative Policy Optimization algorithm to handle sparser and noisier rewards in timed-execution settings, improving training stability.
• Robustness Analysis: Demonstrates that the approach maintains gains even when the timing sandbox is degraded, achieving 100% to 200% improvement over standard RLVR.

Results

• On DMC-Optim, top-50% pass@1 improved from 18.0% to 31.3% on Qwen 2.5 7B and from 30.7% to 50.4% on CWM 32B.
• At stricter top-30% percentile, CWM 32B showed 125% relative improvement.
• Pure-correctness scores were preserved, indicating no trade-off between speed and correctness.
• On the LCB benchmark, CWM 32B won up to 83% of median-sample speed comparisons against standard RLVR.
• Relative to the fastest correct human submissions, the model achieved about half the human rate of complexity-class improvements (14% vs. 28%).

Significance

This paper provides a blueprint for applying RL to code optimization, addressing key practical challenges. The three-stage pipeline (benchmark, reward design, algorithm adaptation) is generalizable and could be applied to other domains where timing or efficiency is the objective. The results show that with careful engineering, RL can yield substantial speedups without sacrificing correctness, opening the door to automated code tuning in production. However, the gap to human-level optimization (28% vs. 14%) suggests that further advances in model architecture or training methodology are needed. Overall, this work advances the state of the art in RL for code and offers a solid foundation for future research.