PaperlayerView exact revision on arXiv

Source-linked AI summary

Reinforcement Learning for Code Optimization

Pierre Chambon, Kunhao Zheng, Juliette Decugis, Benoit Sagot, Gabriel Synnaeve

arXiv:2607.25970v1cs.LGcs.AI

TL;DR

Code models can produce correct programs without reliably optimizing their efficiency. This paper makes optimization RL trainable by composing larger tests, calibrated timing, tailored rewards, and stable GRPO, raising strict optimization pass@1 while preserving pure-correctness scores.

  • Problem

    Correctness-focused code training has not made models reliably fast, leaving code-optimization performance below human speed references.

  • Method

    The paper composes larger optimization tests, calibrated execution, optimization-aware rewards and environments, and stable GRPO updates to propagate timing feedback.

  • Results

    Top-50% pass@1 rises from 18.0% to 31.3% on Qwen 2.5 7B and from 30.7% to 50.4% on CWM 32B, while preserving p100 pure-correctness.

  • Takeaways & Limitations

    The work develops competitive-programming methods that may provide a basis for later adaptation to real-world software optimization.

  • Takeaways & Limitations

    The experiments use roughly 1,000 training prompts, so they are controlled small-scale comparisons rather than a saturated training recipe.

Abstract

from arXiv · show

RL for code correctness is now established: have the model generate a program, run it against hidden test cases, and reward solutions that pass. Extending this to code optimization seems straightforward: just add execution time to the reward. But in practice, once timing drives the reward, small problems in measurement noise, reward sparsity, or GRPO instability overwhelm the signal and make RL fail: generated solutions are barely faster, and more of them can fail. We make execution time learnable through three stages: (1) how code is tested, by building DMC-Optim with large optimization tests and a calibrated sandbox; (2) how speed is turned into reward, by composing correctness and speed in the RL environment and using an offline simulator to predict the most promising configurations; and (3) how the model learns from that reward, by adapting GRPO and evaluation to the sparser, noisier timed-execution setting. On DMC-Optim, the strongest optimization-aware configurations improve strict top-50% pass@1 from 18.0% to 31.3% on Qwen 2.5 7B and from 30.7% to 50.4% on CWM 32B. These gains further increase at stricter percentiles such as top-30%, with 125% relative improvement for CWM 32B, while preserving pure-correctness scores. When the timing sandbox is degraded, robust optimization RL reaches 100% to 200% improvement over standard RLVR, depending on the evaluation criterion. On LCB, CWM 32B wins up to 83% of median-sample speed comparisons against standard RLVR. Relative to the fastest correct human submissions per problem, it reaches about half the human rate of complexity-class improvements (14% vs. 28%).

1 Introduction

Optimization RL must make execution time learnable while preserving correctness, because noisy timing, weak tests, and unstable rewards can otherwise produce little speedup and more failures. The paper addresses this with DMC-Optim, structured optimization environments, offline configuration screening, and GRPO adaptations that yield substantial gains across evaluations.

  • Motivation: Correctness-trained models remain unreliable at code optimization, motivating reinforcement learning that rewards execution speed alongside test-passing correctness.Claude 4.5 Sonnet reaches 81% patch correctness on SWE-fficiency but captures only 4.1% of expert speedup; o4-mini reaches 89.1% pass@1 but 56.9% on Beyond-T.
  • Challenges: Optimization RL fails when timing noise, weak tests, or fast-but-wrong solutions corrupt the reward signal, making execution measurement and reward design central challenges.The training chain also requires stable optimization under rewards that are sparser and noisier than binary pass/fail rewards.
  • Benchmark and method: DMC-Optim contains 2,723 cleaned problems, including 1,302 with sufficient duration spread for timing-based rewards, and separates correctness tests from larger optimization tests.The benchmark adds 430,215 correctness tests and 352,740 optimization tests specifically designed to take longer to execute.
  • Benchmark and method: The study evaluates test filtering, execution-time constraints, post-execution human-reference ranking, and multiple correctness-speed reward formulations, using an offline simulator to screen configurations before online GRPO.The tested reward families include optimization-only or additive blends, multitask, collapsed, and hard-gated variants.
  • Results: 31.3/39.6/50.4% p50 pass@1 replaces 18.0/21.1/30.7% for Qwen 2.5 7B/32B and CWM 32B, while pure-correctness scores remain stable.At p30, CWM 32B rises from 13.7% to 30.9%, a 125% relative gain.
  • Results: 83.0% LCB median-sample speed wins and roughly 100%–200% improvement over RLVR under degraded sandbox conditions demonstrate gains beyond DMC-Optim.The degraded-sandbox improvement depends on the evaluation criterion.

2 Related Work

Prior execution-feedback RL largely targets correctness, whereas efficient-code learning adds runtime ranking, test construction, noise, and reward aggregation challenges. Afterburner improves efficiency through iterative refinement but differs from this work’s harder one-shot generation setting and increases slower-than-human solutions.

  • Execution feedback and efficiency measurement: Correctness-focused RL uses unit tests and binary execution rewards, while efficiency optimization must rank already-correct programs under measurement and aggregation challenges.CodeRL introduced unit-test-based training, and later GRPO work showed binary rewards can scale to reasoning and code generation.
  • Learning efficient code: Prior efficient-code methods include performance-feedback fine-tuning, online RL, efficiency-aware supervised fine-tuning, offline slow-fast edit learning, and inference-time search.These approaches span policy-updating and policy-fixed methods for producing faster programs.
  • Closest RL setting: 7.33% of Afterburner solutions became slower than all human references, compared with 0.33% before training.Afterburner uses GRPO with iterative refinement and additively combines format, correctness, and efficiency rewards.
  • Closest RL setting: This work studies one-shot optimization, requiring the model to generate a solution from scratch rather than iteratively refine an existing solution.The contrast is with Afterburner’s setting, which provides an existing solution plus runtime metrics.

3 How to get a reliable timing measure

Reliable timing-based optimization RL requires more than adding runtime to the reward: tests must reject incorrect code, separate correct solutions by duration, and preserve timing differences. DMC-Optim improves measurability through large-input optimization tests, duration filtering, and isolated remote execution.

  • Motivation: At most 5% gains arise from adding runtime to RLVR on base DMC problems under p50 optimization-constrained evaluation, while pure-correctness scores move only −1% to +3%.This motivates improving the tests and timing measurement rather than using the same base data.
  • DMC-Optim test design: DMC-Optim re-executes human solutions from 12,275 DMC problems, uses verified controls, adds correctness tests, and generates large-input optimization tests.The corpus construction separates correctness targets from optimization in the evaluation tests.
  • Duration filterability: 48.2% of optimization tests meet the robust CV ≥ 0.3 duration-filterability gate, versus at most 3.8% for original tests.On training data, p95/p99 durations are 1.296/3.710 s for optimization tests versus 0.145/0.463 s for original tests.
  • Execution backend: Remote CES executes code on a dedicated CPU cluster with isolated runs, minimizing contention that affects local sandbox timing during inference and rollout orchestration.The comparison distinguishes local execution on training workers from isolated remote execution on I/O tests.

4 How to turn it into a learnable reward

This section turns calibrated execution timing into a learnable optimization-RL reward by organizing environments around when timing constraints enter and how outcomes are exposed after execution. It combines correctness gating with continuous or ranked efficiency signals and uses offline screening to prioritize candidates before costly online GRPO runs.

  • Motivation: Reliable timing is necessary but insufficient for optimization RL because naively rewarding aggregate duration does not produce significant gains.The calibrated setup improves I/O tests, rejects wrong code, and compares correct solutions by duration, but direct aggregate-duration rewards remain inadequate.
  • Environment design: Optimization constraints enter at three intervention points: pre-execution filtering, intra-execution time constraints, or post-execution ranking.The taxonomy organizes prior benchmarks and new formulations by when the optimization constraint is applied.
  • Reward interface: After execution, environments expose correctness c, optimization g, and optional graded efficiency q as reward-facing quantities.c and g are binary gates, while q ∈[0, 1] is a continuous ungated signal; g can incorporate timeout tolerance and percentile thresholds.
  • Reward composition: Correctness can remain an outer gate, assigning r(x, y) = −1 to incorrect solutions and rewarding only correct solutions with an efficiency score such as 1 −q(x, y).The efficiency score may remain continuous, be bucketed, or be binarized, and the conditioning is intended to balance correctness with optimization while avoiding reward hacking.
  • Candidate selection: Offline simulation screens the large candidate environment space before online GRPO, reducing the need for costly runs that use 8–32 GPU nodes for hours or days.The simulator fixes the environment and reward computation while replacing model generations, aiming to select promising candidates rather than predict exact learning curves.

5 How to train stable RL with it, and getting the results

Stable optimization RL requires optimization-aware tests, reward environments that tolerate sparse and noisy timing signals, and evaluation criteria that transfer across training setups. The resulting configurations preserve pure correctness while substantially improving strict speed-percentile performance, with leaderboard-percentile post-execution ranking emerging as the cleanest evaluator.

  • Reward and training stability: 18.9% and 18.0% pass@1 at p50 barely exceed 18.0% for standard RLVR when timing rewards use base tests.Solutions receive proportional runtime rewards only when correct, but base tests provide a poorly refined and weak optimization signal.
  • Reward and training stability: 21% at p50 and 44% at p30 are the largest direct-timing gains over standard RLVR on base tests when optimization tests provide the signal.Against an RLVR reference already using generated correctness and optimization tests, the best p50 gain is 5%, alongside an 8% relative p100 degradation.
  • Stable optimization environments: 31 at p50, 19 at p30, and 6 at p10 are achieved while best p100 values remain around 47, preserving pure correctness.Optimization-aware environments improve strict scores over standard RLVR on base tests without reproducing naive duration rewards’ correctness tradeoff.
  • Stable optimization environments: 56.1 and 18.6 are top-30% post-execution pass@10 scores at p50 and p10, versus 41.1 and 7.4 for standard RLVR on base tests.The pass@10 gains indicate that RL changes the sampled solution distribution rather than only making the first sample resemble the best of ten.
  • Cross-evaluation: 58/60, 52/60, 52/60, and 54/60 evaluation columns keep QP p50, QP p30, Abs 2s, and TL abs 0.5s within one pass@1 point of the best row.Leaderboard-percentile post-execution ranking has a 13.5-point family-average spread and spans about 40 points from p100 to p10.

6 What Does the Model Learn?

Optimization RL improves performance across DMC-Optim difficulty levels, especially at stricter evaluation thresholds, while preserving most correctness capacity. The learned gains are dominated by I/O and constant-factor improvements, whereas humans remain stronger at algorithmic and complexity improvements, and the analysis is limited by noisy, judge-dependent labels and benchmark scope.

  • Difficulty-dependent learning: Optimization RL improves DMC-Optim performance across Easy, Medium, and Hard problems without trading off one difficulty level against another.At p50, pass@1 rises from 31.9 to 51.3 on Easy, 32.4 to 52.8 on Medium, and 21.9 to 30.6 on Hard.
  • Difficulty-dependent learning: 125% gains at p30 occur on Easy and Medium, while Hard problems improve by 70%, showing larger benefits at stricter thresholds.At 10k steps, p100 pass@1 increases only slightly across all three splits, whereas stricter thresholds move substantially more.
  • Transfer and correctness: On Easy and Medium LCB problems, optimization RL shows no large correctness difference from standard RLVR, while Hard problems lose about 13% pass@1 at top-50% and top-30%.Hard-problem pass@10 after 10k steps remains 44.7 for top-50% and decreases by only about 3% for top-30%.
  • What the model learns: 200 of 224 non-tied optimization-RL versus RLVR pairs are faster, but humans beat the trained model in 153 of 227 speed-win pairs.Optimization RL beats the best humans in 33% of cases, while humans retain a 67% advantage in the reported speed-win pairs.
  • Limitations: 13% of classified optimization-RL versus RLVR pairs show a complexity improvement, but the comparison depends on GPT-OSS labels whose speed-identification accuracy is 68%.Accuracy drops to 59% on tighter human-versus-optimization-RL duration differences, and DMC-Optim excludes repository-scale, memory, multi-language, and long-horizon settings.

7 Conclusion … A.2 A compact noise hypothesis

The paper argues that code-optimization RL becomes trainable by jointly improving tests, timing calibration, rewards, and GRPO, while measurement studies explain why larger tests and relative comparisons help under noise. It also identifies efficiency on real-world software engineering as an unresolved, harder transfer problem.

  • 7 Conclusion: Optimization RL becomes trainable when larger tests, calibrated execution, optimization constraints, collapsed rewards, and stable GRPO jointly propagate timing feedback.The resulting system improves strict optimization while preserving p100 pure-correctness.
  • 7 Conclusion: 43.5% to 7.7% p30 pass@1 on Qwen 2.5 7B and 69.8% to 13.7% on CWM 32B expose a correctness-efficiency gap under standard RLVR.The same gap appears on software-engineering tasks, where Claude 4.5 Sonnet achieved 81% correct patches but only 4.1% of expert speedup on SWE-fficiency.
  • 7 Conclusion: Correctness-oriented RL has transferred from math and competitive programming to real-world software engineering, but SWE-RL replaced execution rewards with text similarity because repository execution was too expensive.GRPO, verifiable rewards, and the <think> template were developed in less compute-intensive settings before this transfer.
  • 7 Conclusion: Efficiency remains unresolved on software-engineering tasks because execution is harder and costlier, while measurement reliability, reward noise, and training instability are exacerbated.The paper frames its competitive-programming methods as an initial step toward transferring efficiency RL to real-world software engineering.
  • A.1 Empirical timing regimes: 1.296 s at p95 and 3.710 s at p99 for generated optimization tests versus 0.145 s and 0.463 s for original DMC tests demonstrate the fast-test construction effect.These timing regimes motivate larger optimization tests for making algorithmic differences more measurable.
  • A.1 Empirical timing regimes: 36,814 optimization tests over 302 problems, or 121.9 per problem, make DMC-Optim substantially denser than LCB’s 10,125 tests over 287 problems, or 35.3 per problem.Typical DMC-Optim tests are around 103 characters, while LCB tests remain in the tens of characters.
  • A.1 Empirical timing regimes: LCB’s fast-execution concentration and 2–10 s survival plateau make timeout changes weakly informative, whereas DMC-Optim’s steadier decay preserves threshold-crossing signal.The comparison supports using larger, slower optimization tests to improve timing discrimination.
  • A.2 A compact noise hypothesis: A compact noise model separates proportional slowdowns from additive fixed overheads, making relative additive burden especially important on fast tests.A 53 ms intercept in stored-to-fresh CES calibration supports a non-negligible fixed-cost term, which calibration removes as a systematic sandbox shift.

A.3 Simulation study: timeout versus win-rate … B.4 Test generation

The paper shows that relative win-rate is more robust than thresholded timeout under noisy timing, while DMC-Optim addresses the underlying data problem by generating separate correctness and optimization tests. This pipeline filters raw DMC into a duration-filterable RL pool with larger workloads and stronger correctness validation.

  • A.3 Simulation study: timeout versus win-rate: Win-rate remains more stable than timeout because it averages noisy pairwise comparisons across tests without requiring an external threshold.Timeout can misrank or fail to distinguish solutions when both cross the threshold, while win-rate allows per-test noise to cancel out.
  • A.3 Simulation study: timeout versus win-rate: Under additive noise on LCB-like problems, timeout approaches random guessing while win-rate remains meaningfully above random guessing.On DMC-Optim-like problems, both metrics remain usable over a much wider range, although win-rate performs better.
  • A.4 Takeaways: Larger inputs, longer runtimes, and more tests per problem improve both metric families by increasing timing signal and averaging test-specific reversals.DMC-Optim provides about 3.5 times more tests per problem than LCB, and additional tests help win-rate more than timeout on fast additive-noise problems.
  • B.1 What the dataset must establish: DMC-Optim separates correctness tests, which reduce false positives, from optimization tests, which create runtime spread among already-correct solutions.The dataset also stores measured reference durations for verified human solutions to support timing-based ranking.
  • B.2 Source data, limitations, and decontamination: The pipeline reduces the source corpus from 12,275 to 11,468 problems through problem-level deduplication and quality filtering before constructing DMC-Optim.Python is retained as a noisier, overhead-heavy setting for testing timing methodology inside an RL loop.
  • B.2 Source data, limitations, and decontamination: The original DMC tests have median input-plus-output sizes of 18, 24, and 31 characters across public, private, and DMC-generated categories, with pooled mean human duration 0.088 s.These tests were designed for functional correctness rather than efficiency measurement and are also weak as a correctness gate.
  • B.3 Overview of DMC-Optim Construction Stages: The construction yields a 2,723-problem cleaned corpus and a 1,302-problem duration-filterable RL pool, resplit into 1,000 training and 302 test problems.Duration filterability selects problems whose optimization tests provide enough duration spread for timing rewards, separating optimization readiness from dataset cleanliness.
  • B.4 Test generation: Each problem receives 10 InputGenerator samples, with up to 150 candidate tests, and separate campaigns target correctness coverage and large optimization workloads.In the final training split, optimization tests have median input-plus-output size 928 characters and mean human-reference runtime 0.334 s, versus 36 characters and 0.137 s for correctness tests.

B.5 Filtering generated tests … B.8 The final duration-filterable RL pool

The pipeline conservatively filters generated tests to improve correctness labels, retains problems with measurable timing spread, and forms a duration-filterable optimization pool whose timing tails are substantially richer than ordinary tests. Production filtering removes substantial data while preserving most correct solutions, and the retained pool’s measurement properties still require learning ablations for validation.

  • B.5 Filtering generated tests: Correctness tests reject timeout-heavy inputs, whereas optimization tests tolerate large-input timeouts because they can separate faster and slower valid implementations.This distinction preserves timing signal without treating every optimization timeout as a correctness failure.
  • B.5 Filtering generated tests: Mean false-positive rate falls from 8.27% to 2.11% on 257 problems with generated correctness tests, while 49 problems reach zero observed false positives.Filtering balances cleaner labels against correct-solution attrition and problem-pool shrinkage.
  • B.5 Filtering generated tests: 19.21 percentage points is the mean correct-solution pass-rate drop among 134 problems that decline after generated-test augmentation.The 25% problem-level attrition cap limits damage from tests that are too slow, invalid, or overly aggressive.
  • B.6 What remains before duration selection: 22.1% of the execution-validated pool is removed during generated-test filtering, leaving 3,061 of 3,928 problems while retaining 85.1% of verified-correct solutions.Incorrect-solution retention is lower at 69.1% because generated correctness tests remove false positives and unreliable negative controls.
  • B.7 Duration filterability: Duration filterability requires robust CV ≥ 0.3, using interquartile runtime spread across tests divided by median runtime for verified-correct human solutions.The criterion measures within-problem timing variation rather than runtime spread across solutions on a fixed test.
  • B.7 Duration filterability: 1,169 problems (48.2%) have duration-filterable optimization tests, and 863 (35.6%) satisfy both duration and length filterability.Original public, private, and generated tests are almost never duration-filterable at scale, while optimization tests remain informative.
  • B.8 The final duration-filterable RL pool: Optimization-test durations reach 1.296 s at p95 and 3.710 s at p99 in the final 1,000-problem RL split, versus 0.145 s and 0.463 s for original DMC tests.Tests above 1 s comprise 6.87% of optimization tests, compared with 0.42% for the original suite.
  • B.8 The final duration-filterable RL pool: 18.9% of final-pool problems have at least 10% of optimization tests above 1 s, compared with 1.2% for original tests and 5.2% for correctness tests.These duration tails establish the retained pool’s measurement property but do not by themselves prove that selection improves learning.

B.9 Training ablations: does DMC-Optim help, and is it enough to solve optimization RL? · C Making runtime measurements trustworthy: code execution backend · C.1 What a code execution backend has to establish

Optimization RL succeeds only when duration-filterable data and problem-relative timing rewards are combined; stronger tests or raw timing alone are insufficient. Reliable execution measurements are likewise essential because small timing perturbations can alter rankings and destabilize training and evaluation.

  • B.9 Training ablations: does DMC-Optim help, and is it enough to solve optimization RL?: Three equal-sized 1,000-problem training pools isolate how problem selection changes optimization-RL learning under fixed reward and environment.
  • B.9 Training ablations: does DMC-Optim help, and is it enough to solve optimization RL?: 9.4% best non-filterable charlen remains below 16.1% ranked p30 on duration-filterable data, showing non-filterable problems are not equally effective.
  • B.9 Training ablations: does DMC-Optim help, and is it enough to solve optimization RL?: 16.1% ranked p30 on duration-filterable data falls to 13.3% on mixed data and 9.1% on non-filterable data.The ranking reward requires a useful within-problem duration profile.
  • B.9 Training ablations: does DMC-Optim help, and is it enough to solve optimization RL?: DMC-Optim helps only jointly: stronger optimization tests with raw timing are insufficient, while ranked timing on non-filterable data falls from 16.1% to 9.1%.
  • B.9 Training ablations: does DMC-Optim help, and is it enough to solve optimization RL?: 10.8% relative p30 drops occur for both base-test raw-duration variants versus MC+MO, so absolute timing on correctness tests is insufficient.Logarithmic remapping mainly converts small-runtime measurement noise into reward noise.
  • B.9 Training ablations: does DMC-Optim help, and is it enough to solve optimization RL?: 17.2–19.4% improvement over MC+MO from optimization-test raw duration still remains 41.9–42.9% below ranked p30.Better tests expose timing signal, but raw duration does not recover problem-relative timing information.
  • C.1 What a code execution backend has to establish: 1.296 s pooled optimization-test p95, 3.710 s p99, and 6.87% exceeding 1 s make sub-second backend perturbations capable of changing rankings.Optimization RL depends directly on measured duration, unlike correctness-only RL, where pass/fail usually dominates reward.
  • C Making runtime measurements trustworthy: code execution backend: CES runs each code-test pair under a fixed 1 GB memory envelope and 10 s hard limit, separating timing from worker-side contention.It returns status and duration while enabling controlled retries and concurrency, despite higher per-call overhead.

C.2 Local sandbox and why it is bad for timing measurements · C.3 Remote execution service · C.4 Fallback after remote execution failures

Local execution is suitable for correctness verdicts but fails as a timing source because it is fast, incomplete, unstable, workload-coupled, and incompatible with CES. The system therefore isolates timing on CES and uses local fallback only conservatively to recover correctness or represent unresolved optimization tests as timeouts.

  • C.2 Local sandbox and why it is bad for timing measurements: Local timing excludes compilation and sandbox startup, replays tests sequentially, and measures worker wall-clock time amid concurrent RL workloads.State, imports, caches, I/O state, inference, orchestration, logging, and worker load can perturb measured durations.
  • C.2 Local sandbox and why it is bad for timing measurements: Local and CES timings are incompatible: local execution changes duration-filterability, reduces usable cells, and cannot be reliably corrected into CES ordering.The paper consequently rejects local timing for optimization rewards and evaluation, as well as mixing local and CES durations.
  • C.2 Local sandbox and why it is bad for timing measurements: 99.62% to 97.41%: local execution reduced timing-job success, while usable per-solution per-test coverage fell from 99.2% to 93.3%.The non-success rate rose from 0.38% to 2.59%, and some problems lost up to 50% of timing-matrix coverage.
  • C.2 Local sandbox and why it is bad for timing measurements: 41.2 percentage points: repeated local re-execution moved the average mean-percentile score peak-to-peak across 23 problems and 425 reruns.The within-problem standard deviation averaged 10.961 percentage points, while the within-problem range averaged 41.173 percentage points.
  • C.3 Remote execution service: CES separates execution from rollout workers through a managed remote queue with controllable concurrency, visible retries, and isolated virtual-machine sandboxes.CES returns execution statuses and durations, while its stored timings can be calibrated against fresh executions despite service overhead and drift.
  • C.4 Fallback after remote execution failures: CES failures trigger CES retries first; local fallback is used only when a code-test pair remains inconclusive and only to recover a correctness verdict.Definitive CES results are retained, and early stopping can skip local reruns after a definitive hard failure.
  • C.4 Fallback after remote execution failures: A locally successful optimization test is conservatively reclassified as a timeout at the time limit, rather than contributing its faster local duration.Correctness-test fallback recovers pass/fail only; local runtime is never imported as timing evidence.

C.5 Quantitative impact of infrastructure failures · C.6 Alternative fallback designs

Rare infrastructure failures can expose many otherwise correct rollouts to fallback, while bursty or silent CES degradation can distort timing rewards. The paper therefore compares category-specific conversion with retries, discarding, quarantine, calibration probes, and reward-design mitigations.

  • C.5 Quantitative impact of infrastructure failures: 45.5% of correct rollouts reach fallback at least once at a 2% per-test failure rate with 30 correctness tests.Even at f = 0.1%, exposure is 3.0% with 30 tests and 9.5% with 100 tests.
  • C.5 Quantitative impact of infrastructure failures: 54.3% CES-only, 41.6% local rerun, and 14.1% timeout rate characterize the worst post-warmup CWM 32B burst.The burst events are treated as service-state events because equivalent configurations do not show them consistently; the worst step had 0.00% hard infrastructure errors but 6.3% unknown results.
  • C.5 Quantitative impact of infrastructure failures: 98.53% mean CES-only versus 97.18% mean CES-only coexists with markedly different minimum CES-only rates of 95.09% and 54.33% across matched CWM 32B runs.Run 1 has 0.0003% local fallback and 0.0001% infrastructure or unknown failures, whereas run 2 has 0.77% and 0.16%, respectively, showing that visible failure rates do not fully explain return volatility.
  • C.6 Alternative fallback designs: Category-specific conversion keeps locally recovered correctness verdicts while converting locally recovered optimization successes to timeouts.Immediate CES retries can avoid mixing timing backends for transient failures, but persistent bursts still require conversion or discarding.
  • C.6 Alternative fallback designs: 80% of trajectories would be discarded at a 2% per-test failure rate with 80 total tests, making blanket discard impractical.The discard rate is 1 −(1 −f)^n_total and reaches 33% even at 0.5%.
  • C.6 Alternative fallback designs: Quarantining degraded windows and within-batch reward comparisons offer additional controls, but quarantine wastes compute while stored human-reference durations still require calibration.Possible controls include pausing collection, dropping batches, or rolling back checkpoints; same-prompt grouping and GRPO advantages help with batch-common service shifts.
  • C.6 Alternative fallback designs: Live calibration probes can detect and rescale silent CES degradation only when they accurately estimate service state, creating a capacity-versus-noise tradeoff.Too few probes are noisy in the sub-second regime, while too many compete with training workload for CES capacity.

C.7 CES noise, drift, and calibration · C.8 Temporal stability of calibration · C.9 Evaluation-time sensitivity to affine calibration

CES timing has modest short-run noise but substantial long-term drift, making affine calibration necessary for comparable rankings. Calibration remains temporally stable, while evaluation scores shift with calibration yet optimization-trained models retain stronger strict-threshold performance and stable ordering.

  • C.7 CES noise, drift, and calibration: 9.1% mean coefficient of variation and 12.4 ms mean standard deviation quantify short-run CES timing noise across repeated measurements.The median coefficient of variation is 8.2%, and the median standard deviation is 9.9 ms.
  • C.7 CES noise, drift, and calibration: 97.1% of raw-duration variation reflects real problem-test-solution differences, versus 0.9% from repeated CES measurement.The between-triple variance is 0.02906, within-triple variance is 0.00027, and total variance is 0.02994.
  • C.7 CES noise, drift, and calibration: 0.96–1.34 fresh-to-stored duration ratios in an early pilot show that long-term CES drift is too heterogeneous for one global multiplier.The pilot mean ratio was 1.15, motivating a more flexible correction.
  • C.7 CES noise, drift, and calibration: 0.6306 slope and 0.0529 s intercept define the affine stored-to-current CES correction, which raises Spearman ranking correlation from 0.54 to 0.96.The correction uses dcorrected = α · dstored + β, with corrected durations clamped to [0, 10] seconds.
  • C.8 Temporal stability of calibration: 1.0% slope change across calibration campaigns and cross-validated R2 above 0.98 indicate temporally stable affine calibration.The slope changes from 0.6306 to 0.6243, while the intercept shifts from 53 ms to 38 ms.
  • C.8 Temporal stability of calibration: ρ = 0.99 shows that the model’s relative problem difficulty remains nearly unchanged between calibration campaigns.The comparison uses each candidate’s fresh-CES mean percentile against human references for each of the 33 problems.
  • C.9 Evaluation-time sensitivity to affine calibration: 15 ms additive shifts can materially affect p10 decisions because evaluation compares executions against the fastest human-reference durations.Stricter calibration lowers absolute p10 scores, but correctness-only performance declines faster than optimization-trained models.
  • C.9 Evaluation-time sensitivity to affine calibration: 56.3%, 55.8%, and 57.8% versus 38.8% baseline are the lenient-beta p10 scores for Filter 2s, QP, and QP train p30.Their relative gains are 45%, 44%, and 49%, respectively.

C.10 Joint training-time and evaluation-time calibration sweeps … D.2 Classes of Optimization RL Environments

The paper finds that post-training scoring calibration dominates strict optimization metrics, while reward-time calibration has weak effects, and it distills timing-service practices for robust evaluation. It then formalizes optimization RL environments around correctness, workload selection, execution limits, and post-execution speed rewards.

  • C.10 Joint training-time and evaluation-time calibration sweeps: 1.9 percentage points: reward-calibration spread for ranked p30 p100, versus 2.5 points for QP, indicating weak training-time calibration effects on correctness.At fixed scoring calibration, strict p10 shows a similar pattern, while scoring changes produce much larger movements.
  • C.10 Joint training-time and evaluation-time calibration sweeps: 35.3 percentage points: ranked-p30 p10 pass@1 falls from 41.1% at s0 to 5.8% at s9, showing scoring calibration dominates strict metrics.For QP, p10 pass@1 similarly falls from 40.1% to 4.6%.
  • C.10 Joint training-time and evaluation-time calibration sweeps: p100 is invariant to scoring calibration, whereas stricter percentiles are more sensitive; p10 retains only 14.1% of the s0 ranked-p30 score and 11.5% of the QP score at s9.The contours are nearly vertical, with no diagonal ridge requiring reward and scoring calibrations to match.
  • C.11 Lessons learned for timing-based RL: Controlled, confined services should measure timing, while local sandbox durations should not enter timing rewards or timing-sensitive metrics.Concurrent local execution can completely corrupt the timing signal, although local runs may recover inconclusive correctness verdicts with generous timeouts.
  • C.11 Lessons learned for timing-based RL: Rare infrastructure bursts and silent slowdowns can affect many rollouts while aggregate service-health counters remain normal, so comparisons require shared concurrent re-execution and recalibration.The affine correction should be refit after moving fleets, upgrading sandboxes, or sustaining service-state changes.
  • C.12 Improvements and experiments we did not have the time to conduct: Fixed-rollout replay, controlled noise injection, duration-variance storage, and adaptive monitoring are proposed to isolate service effects and improve filtering, timeout choices, and recalibration.These experiments were identified as improvements not completed in the paper.
  • D Designing Environments and Rewards for Optimization RL: An optimization RL environment maps a problem and generated program to executed-test statuses and durations, exposing correctness, hard optimization-gate, and duration-quality signals through a common reward-facing interface.Optimization tests generate execution records; reward design determines which records affect learning.
  • D.2 Classes of Optimization RL Environments: Raw optimization tests can become harder correctness checks, produce sparse efficiency rewards, or reward degenerate fast-but-wrong programs; the taxonomy therefore separates correctness tests from optimization-test pools and timing operators.The environment supports pre-execution filtering, intra-execution limits, and post-execution ranking, with calibrated human references supplying comparison distributions.

D.3 How to create a good ranking score based on recorded durations … E.2 Quantifying what a good RL environment is

The paper develops timing-aware RL environments by selecting stable, reference-normalized ranking and reward functions, while using offline simulation to cheaply identify configurations whose activation is neither trivial nor noisy and correlates with solution quality.

  • D.3 How to create a good ranking score based on recorded durations: 17 ranking metrics are screened for balanced severity, effective range, timing sensitivity, and stability under repeated CES measurements and duration calibration.The screening compares direct percentile, top-k, total-duration, slope, win-rate, and filtered-percentile families.
  • D.3 How to create a good ranking score based on recorded durations: Mean percentile is retained for its lowest cross-validation dispersion, comparable rerun noise, and 47-point spread without trimming hyperparameters.It supplies the aggregate for QAR ranked quality and one of the selected post-execution RL signals.
  • D.4 Composing rewards that best balance correctness and optimization objectives: Reward composition balances correctness and optimization by choosing whether efficiency credit is gated on valid programs or exposed through softer blends and multitask mixtures.Strict gates can prevent fast-but-wrong behavior, while relaxed forms may provide earlier optimization signal.
  • D.4 Composing rewards that best balance correctness and optimization objectives: Graded reward families remain in [−1, 1], while bucketed maps discretize quality and range-compressed maps enlarge the failure-to-passing gap relative to the optimization range.The reward interface consumes correctness, hard optimization, and quality signals, with composition families differing in how correctness enters the scalar.
  • D.5 Raw-durations (aka naive) reward baselines: Naive-duration rewards assign raw timing credit without normalizing for problem difficulty or attainable speed distributions.A 0.1s program receives nearly the same credit whether reference solutions run in 0.05s or 5s, although the reward needs no reference distribution or calibration data.
  • D.6 Taxonomy of optimization/efficiency definitions in previously published papers: The taxonomy distinguishes efficiency entering before execution, during execution, or after execution, and separates online policy training from supervised, preference, and inference-time search approaches.The retained training setting uses one-shot generation from the problem description and live sandbox execution with execution-based reward.
  • E Doing offline RL simulations to spare compute of online RL runs: The offline simulator preserves environment-side filtering, timeouts, ranking, and outcome computation while replacing model generation and sandbox execution with human solutions and stored calibrated durations.This prunes the large environment space before costly online GRPO runs.
  • E.2 Quantifying what a good RL environment is: A good RL environment should neither pass or fail everything nor reward an intermediate fraction unrelated to better samples, so evaluation measures activation density, shape, noise, location, and quality correlation.The diagnostics include AUC, steepness, variance around the smoothed curve, deviation from the diagonal, and quality-correlation.

E.3 Do these metrics correlate with downstream online RL performance? · E.4 Using the offline simulator to select the most promising parametrization of each environment

The offline simulator’s diagnostics are weak predictors of pure-correctness RL performance but become more informative under stricter optimization constraints. In practice, it is used mainly to prune degenerate configurations and sweep environment parameters before online RL, rather than reliably rank all viable settings.

  • E.3 Do these metrics correlate with downstream online RL performance?: 20 Qwen 2.5 7B RL-optimization environments were compared across simulator diagnostics and online pass@1 at p100, p80, p50, and p30.The main analysis statistic was Spearman correlation between each offline diagnostic and the corresponding online RL pass@1.
  • E.3 Do these metrics correlate with downstream online RL performance?: At p100, all diagnostic correlations with correctness performance were weak and nonsignificant.The simulator is weak on pure correctness, according to the reported analysis and Table 45.
  • E.3 Do these metrics correlate with downstream online RL performance?: At p30, deviation from y = x reached rs = −0.832 (p = 2 × 10−5), raw quality-correlation reached rs = 0.787 (p = 10−4), and steepness reached rs = 0.723 (p = 7 × 10−4).Curve noise remained uninformative at rs = −0.002 (p = 0.994).
  • E.3 Do these metrics correlate with downstream online RL performance?: Correlations with earlier checkpoint evaluations were weaker, whereas some metrics showed stronger signal by the end of the RL runs.This pattern was consistent with run variability observed at the end of Section 5.
  • E.3 Do these metrics correlate with downstream online RL performance?: The simulator primarily separates highly degenerate environments from configurations that can support online learning, but cannot yet reliably rank the remaining viable configurations.The study lacked enough downstream RL runs for finer-grained analysis across environment families and parameter variations.
  • E.4 Using the offline simulator to select the most promising parametrization of each environment: Within each environment family, offline sweeps explore large parameter spaces; pre-execution environments can vary filter threshold, optimization time limit, and timeout tolerance.The resulting heatmaps support selecting promising parametrizations rather than eliminating entire environment families at once.
  • E.4 Using the offline simulator to select the most promising parametrization of each environment: Figure 45 illustrates heatmaps for pre-execution absolute-duration filtering and intra-execution ranked-worst time limits, varying duration filters, optimization limits, reference percentiles, and timeout settings.The pre-execution example fixes timeout tolerance to 10% while sweeping retained-test duration filters and absolute optimization time limits.
  • E.4 Using the offline simulator to select the most promising parametrization of each environment: The asynchronous trainer-worker architecture executes filtering, calibrated-sandbox timing, human-reference ranking, and per-rollout reward computation before sending rollout groups to trainers.Each worker samples one prompt, generates G rollouts, and processes them through the optimization RL environment.

F Async-RL and training objective … G.2 Cases where optimization-RL beats standard RLVR

The paper specifies an asynchronous GRPO training objective with prompt-level, token-weighted return centering and a fixed token horizon, then evaluates optimization-RL against standard RLVR using structured pairwise judgments and concrete case studies. In both examples, optimization-RL finds algorithmically superior solutions and substantially reduces execution time while preserving correctness.

  • F Async-RL and training objective: GRPO generates same-prompt groups of G rollouts and centers each return against a prompt-level token-weighted mean.
  • F Async-RL and training objective: The clipped surrogate objective uses a fixed token horizon N rather than each rollout’s realized response length.
  • G.1 Judge prompt used for the pairwise analysis: The pairwise judge receives a competitive-programming problem and two solutions, analyzes algorithms and implementation choices, and predicts which solution is faster.
  • G.1 Judge prompt used for the pairwise analysis: The judge also compares best, average, and worst complexities, records whether complexity improves, and classifies the optimization as algorithmic or superficial.
  • G Examples of Optimization-RL improvements: 46.4 s → 28.5 s (×1.63) on Codeforces 1466F, where optimization-RL recovers the intended algorithmic solution while standard RLVR produces a generic correct program.The judge labels the improvement an algorithm change / algorithmic.
  • G.2 Cases where optimization-RL beats standard RLVR: Optimization-RL’s graph reformulation replaces generic GF(2) basis reduction with a structure-aware approach for two-coordinate vectors and component-level singles.Both submissions are correct, but optimization-RL recovers the known intended solution.
  • G.2 Cases where optimization-RL beats standard RLVR: 5.96× speedup on AtCoder ARC085: RLVR takes 55.1 s, whereas optimization-RL takes 9.2 s via a mathematical shortcut.Optimization-RL replaces memoized minimax over prefix choices with a closed form depending only on the last one or two cards.

G.3 Cases where optimization-RL beats the fastest available human

Optimization-RL beats the fastest available human submissions in several competitive-programming cases through mathematical shortcuts or cleaner implementations. The gains range from a modest ×1.02 to ×1.28 speedup, while sometimes changing the asymptotic complexity.

  • Codeforces 571A: Lengthening Sticks: 13.5 s vs. 17.2 s (×1.28): on Codeforces 571A, optimization-RL replaces an O(ℓ) triangular-number sweep with closed-form evaluation, yielding O(1) per invalid side.The human solution uses inclusion–exclusion and an O(ℓ) sweep; the optimization-RL variant evaluates the quadratic polynomial directly.
  • Codeforces 1237B: Balanced Tunnel: 17.4 s vs. 17.7 s (×1.02): on Codeforces 1237B, optimization-RL uses an array of exit positions and a running maximum instead of a two-pointer set-based implementation.Both approaches are O(n), but the optimization-RL solution reduces hashing and implementation complexity.
  • Codeforces 534B: Covered Path: 12.7 s vs. 13.1 s (×1.04): on Codeforces 534B, optimization-RL sums the minimum of two ramp bounds in O(t), replacing an O(td) greedy simulation.The direct two-ramp formulation captures the optimal speed at each time step.
Loading 2607.25970v1…