Reinforcement Learning for Code Optimization

Motivation

• 89.1% versus 56.9%: o4-mini’s Venus correctness pass@1 exceeds its runtime-efficiency percentile, showing correctness training does not reliably produce fast code.Claude 4.5 Sonnet captures only 4.1% of expert speedup despite 81% correct patches, while Qwen3-32B falls from 70.0% pure-correctness pass@1 to 43.5% under a best-complexity-class requirement.Source: §1 · p. 1

Failure mode

• +0.6 points at p30: rewarding lower average runtime over binary correctness barely changes pass@1, while p100 changes by −0.3 to +1.4 points, motivating a learnable execution-time signal.The pτ evaluation counts a solution only when it is correct and no slower than the τ-th-percentile human reference, with smaller τ stricter.Source: §1 · p. 1

Test and timing stack

• 2,723 cleaned problems and 1,302 duration-filterable problems: DMC-Optim separates correctness tests from larger optimization tests and supports timing-based rewards.The construction adds 430,215 correctness tests and 352,740 optimization tests, with the optimization tests specifically made to take longer to execute.Source: §1 · pp. 2–3

Results

• 31.3/39.6/50.4% from 18.0/21.1/30.7%: DMC-Optim p50 pass@1 improves on Qwen 2.5 7B/32B and CWM 32B while pure-correctness scores stay stable.At p30, CWM 32B rises from 13.7% to 30.9%, a 125% relative gain; on LCB it reaches 83.0% median-sample speed wins against standard RLVR while retaining 54.4% pass@1.Source: §1 · pp. 2–3, Figure 1 · p. 2

Method

• Three stages make optimization RL trainable: pre-execution test filtering, intra-execution time constraints, and post-execution ranking against human references, combined with reward designs and offline simulator screening before online GRPO.The tested rewards include optimization-only, additive, multitask, collapsed, and hard-gated variants, with GRPO adapted to sparse timing rewards.Source: §1 · pp. 1–3

Execution feedback and efficiency measurement

• Efficiency benchmarks expose the gap between correctness feedback and optimization rewards, because expensive tests, instruction counts, and noisy timing complicate training-compatible signals.PIE reports 1.91x spurious speedups on identical code, motivating a more reliable timing signal.Source: §2 · p. 3

Learning efficient code

• Prior efficiency-training methods use performance feedback, curated data, offline edit pairs, or inference-time search, but generally start from existing programs or receive repeated runtime feedback.One-shot generation instead requires selecting the algorithm, data structures, and implementation before observing runtime feedback.Source: §2 · p. 3

Closest RL setting

• Afterburner’s iterative GRPO refinement improves efficiency but raises solutions slower than all human references from 0.33% to 7.33%, whereas this work studies one-shot generation without execution feedback.The proposed setting retains GRPO while emphasizing measurable timing, correctness-preserving rewards, and stable training under sparse noisy returns.Source: §2 · p. 3

• Adding runtime to RLVR on base DMC problems yields at most 5% gains at optimization-constrained p50, while raw tests average only 0.088 seconds.Raw-test p95/p99 durations reach just 0.145/0.463 seconds, so tens-of-milliseconds perturbations can dominate decisions.Source: §3 · p. 4
• DMC-Optim constructs timing feedback from 12,275 DMC problems by re-executing human solutions, adding correctness tests, generating large-input tests, and filtering at test, solution, and problem levels.The filtering trades recall for cleaner labels and sufficient reinforcement-learning scale.Source: §3 · p. 4
• 48.2% of DMC-Optim problems pass duration filterability versus at most 3.8% with original tests, while replacing filterable problems reduces ranked-p30 pass@1 by 43.5%.Optimization tests also raise training-split p95/p99 durations to 1.296/3.710 seconds versus 0.145/0.463 seconds for original tests.Source: §3 · p. 5
• CES raises stored-versus-fresh Spearman from 0.54 to 0.96 through affine drift correction, whereas local timing shifts mean-percentile rankings by 41.2 points.Remote isolated execution avoids worker contention and provides correctness-gated timings for subsequent RL.Source: §3 · p. 5

Where timing enters the environment

• The framework classifies optimization-RL environments by three intervention points: pre-execution filtering, intra-execution time constraints, and post-execution ranking.Pre-execution methods are less reference-dependent but provide less refined pressure; intra-execution limits are literal but can erase learning signals; post-execution ranking is flexible but often needs reference duration distributions.Source: §4 · p. 5

The reward-facing interface

• Correctness and efficiency are exposed through a correctness gate c, optimization gate g, and optional graded signal q, preventing fast-but-wrong programs from receiving optimization credit.The correctness gate checks fixed tests, while the optimization gate checks timeout tolerance and possible percentile thresholds; q can provide a continuous ungated signal.Source: §4 · p. 5
• The mean-based percentile ranking family was retained because repeated-measurement noise was 3.0 ± 1.0 percentile points while strong and weak solutions differed by 47 points on average.Post-execution ranking compares measured durations with calibrated human references and aggregates per-test percentiles.Source: §4 · p. 6

Balancing correctness and efficiency

• Outer-gating correctness and rewarding efficiency only for correct solutions supports continuous, bucketed, or binary optimization rewards while reducing reward-hacking risks.The compared reward families range from binary to collapsed, including multitask and additive formulations.Source: §4 · pp. 6–7

Pruning the space of candidate RL environments

• Offline simulator diagnostics prune environment and reward candidates before online GRPO, with downstream performance correlating most with diagonal deviation, raw monotonicity, and steepness rather than curve noise.The simulator substitutes sampled human solutions and precomputed calibrated durations, testing whether better solutions receive stronger, nonsaturated rewards; curve noise was not predictive at p30 (rs = −0.002, p = 0.994).Source: Figure 3 · p. 6, §4 · p. 7

Experimental setup

• Qwen 2.5 7B experiments explore configurations in detail, while Qwen 2.5 32B and CWM 32B validate selected setups at larger scale; Qwen uses decontaminated reasoning-only SFT data.CWM 32B starts from a released reasoning-RL SFT checkpoint, with decontamination not established for DMC-Optim test data or RL prompts.Source: §5 · p. 8

Replayed evaluation

• Replayed evaluation samples 20 solutions per problem, times shuffled model and human-reference executions together, then reuses stored verdicts and durations across percentile, calibration, budget, and LCB comparisons.This avoids repeated model generation and timing reruns while mitigating noise from small, fast out-of-distribution LCB tests.Source: §5 · p. 9

Exploring baselines

• Naive timing rewards fail on base tests, reaching only 18.9% or 18.0% p50 pass@1 versus 18.0% for standard RLVR, while optimization tests trade correctness for stricter-percentile gains.With optimization tests, direct timing rewards improve p50 by up to 21% and p30 by 44% over base-test RLVR, but the best p50 gain versus enriched-test RLVR is only 5% and p100 degrades 8%.Source: §5 · p. 9, Table 1 · p. 10

Can GRPO be stable enough for sparse, noisy timing rewards?

• Increasing the training batch size improves pure-correctness performance by 10–25% across optimization RL environments, optimization performance at p50 by up to 35%, and at p30 by up to 60%.The recipe also increases same-prompt rollouts, centers returns without standard-deviation normalization, and uses a token-weighted prompt-mean baseline with fixed token horizon N = 32768.Source: §5 · p. 10

What optimization RL environments work best?

• 31.3% p50 and 19.1% p30 pass@1 yield about 75% and 150% relative gains over standard RLVR, while pure-correctness performance remains near 47%.The strongest configuration is the top-30% per-test-percentile post-execution environment; against RLVR with optimization tests, it improves p50 by roughly 50% and p30 by roughly 100%.Source: §5 · p. 11, Table 2 · p. 12
• Pass@10 also rises from 41.1% to 56.1% at p50 and from 7.4% to 18.6% at p10, indicating changed solution distributions rather than only improved first-sample selection.These comparisons use standard RLVR on base tests versus the top-30% per-test-percentile post-execution configuration.Source: §5 · p. 11

How do gains transfer across different optimization evaluation criteria?

• Post-execution percentile ranking and absolute pre-execution filtering produce balanced gains across tightening criteria, whereas some environments improve correctness but transfer poorly to stricter deciles.QP p30/p50 and Abs 2s preserve correctness-oriented gains through roughly the first half of deciles; p50 is an inflection point where most runs begin losing transfer.Source: §5 · p. 13, Figure 4 · p. 13

Cross-model transfer

• 157%: Qwen 2.5 32B improves DMC-Optim p30 over standard RLVR, while CWM 32B improves p30 by 126% and preserves pure-correctness performance.Qwen 2.5 32B also improves p50 by 88% and p10 by 254%; CWM 32B improves p50 by 64%.Source: Table 4 · p. 16, §5 · p. 17
• 82.9%: CWM 32B optimization RL wins median-sample speed comparisons against standard RLVR on LCB, while best-sample win rates remain 66.3–68.1%.Qwen 2.5 7B reaches 68.5% median-sample wins with p30 training; LCB pass@1 can decrease because its short tests do not reward optimization.Source: Table 5 · p. 17, §5 · pp. 17–18

Training dynamics

• p50 rises from 23.4% to 39.6% for Qwen 2.5 32B under top-30% optimization RL, whereas standard RLVR declines from 22.2% to 21.1%.At p30, standard RLVR moves from 10.7% to 9.4%, while optimization RL improves in the same direction; the pattern recurs across models.Source: §5 · p. 18, Figure 7 · p. 22

Training cost

• 25%: optimization-test RLVR increases average wall-clock training time over base-test RLVR, while top-30% optimization RL stays within 5% of it.Added CES calls account for about 15% rollout-generation overhead; equal-wall-clock training still improves Qwen 2.5 7B p30 from 7.7% to 17.6%.Source: §5 · p. 19

Timing robustness

• 50–60%: under a substantially faster evaluation sandbox, top-30% optimization RL still improves p10 over base RLVR, while slower sandboxes increase its relative advantage.Across calibration shifts, base RLVR remains below optimization-test RLVR, which remains below the strongest optimization-RL runs.Source: §5 · p. 19, Figure 6 · p. 20

Statistical reliability

• 19.7 points: top-30% post-execution optimization RL improves p50 over standard RLVR, exceeding conservative combined uncertainty by 4.2×.At p30, the corresponding gains are 17.2 and 13.8 points over standard RLVR and optimization-test RLVR, respectively.Source: §5 · p. 21, Table 7 · p. 21

Difficulty dependence

• At p50, optimization RL raises DMC-Optim pass@1 from 31.9 to 51.3 on Easy, 32.4 to 52.8 on Medium, and 21.9 to 30.6 on Hard.At p100, gains are smaller but positive across all splits, while p30 gains reach 125% on Easy/Medium and 70% on Hard.Source: §6 · p. 23
• On LCB, optimization RL reaches 86.0% WRmed on Hard problems, while its best Easy-problem median-sample win rate is 70.2%.Pure correctness is largely preserved on Easy and Medium, but top-50% and top-30% training reduce Hard pass@1 from 29.8% to about 25.7–25.8%.Source: §6 · p. 23

Learned optimization strategies

• Among 174 classifiable optimization-RL versus RLVR pairs, 47% of speed wins come from I/O optimization, 6% from algorithmic improvements, and 13% from complexity improvements.Constant-factor tweaks account for 34% of cases, while math shortcuts contribute 6%, better data structures 2%, and full algorithm changes 1%.Source: Figure 8 · p. 24, §6 · p. 24

Human comparison

• Humans beat optimization RL in 67% of direct speed-win pairs, although optimization RL still beats the fastest human solution in 33% of cases.On hard problems, humans win 70% of direct comparisons, while optimization RL finds complexity improvements over RLVR in 25% of cases.Source: §6 · pp. 24–25

Evaluation limitations

• The judge labels are imperfect: speed-identification accuracy is 68%, complexity classification accuracy is 94.8%, and 22% of optimization-RL versus RLVR speed wins are unclassifiable.Human-versus-optimization-RL speed-identification accuracy falls to 59% when duration differences are tighter.Source: §6 · p. 25

Limitations and future rewards

• DMC-Optim covers single-file Python tasks with noisy timing and fixed human timing pools, excluding repository-scale, memory, multilingual, and long-horizon optimization settings.The LCB setup also reveals that training removes harness overhead such as wrappers and dispatch, motivating instruction-following rehearsal or interface-preserving constraints.Source: §6 · pp. 25–26

7 Conclusion

• 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 pure-correctness is preserved.At p30, relative gains reach 150% and 125%, respectively; on LCB, optimization gains are similar with mostly preserved pure-correctness.Source: §7 · p. 26
• Optimization-RL beats standard RLVR in 89% of speed-win pairs and achieves complexity improvements in 13% of cases, versus 22% for the best human submissions.Optimization-RL also beats human submissions with a complexity improvement in 7% of cases, suggesting a path toward algorithm discovery.Source: §7 · p. 26
• The correctness-efficiency gap transfers to software engineering: Claude 4.5 Sonnet produced correct patches 81% of the time but captured only 4.1% of expert speedup on SWE-fficiency.Efficiency is harder to master there because execution is more expensive and measurement noise, reward noise, and training instability are exacerbated.Source: §7 · p. 26
• The proposed efficiency-RL path develops methods in competitive programming, where feedback is manageable, for later adaptation to real-world software optimization.This follows earlier transfers of GRPO, verifiable rewards, reasoning scaffolds, and SWE-RL from simpler settings to software engineering.Source: §7 · p. 26

A.1 Empirical timing regimes

• DMC-Optim shifts executions into a measurable timing regime: generated tests reach 1.296 s at p95 and 3.710 s at p99, versus 0.145 s and 0.463 s for original DMC tests.LCB and original DMC remain fast-test regimes, while DMC-Optim’s steadier survival decay makes timeout changes move more tests across the boundary.Source: §A.1 · p. 30
• DMC-Optim uses larger tests and more tests per problem than LCB: 36,814 tests over 302 problems versus 10,125 over 287, or 121.9 versus 35.3 per problem.Typical DMC-Optim tests are around 103 characters, compared with LCB tests typically remaining in the tens of characters.Source: §A.1 · p. 30, A Simulation study of code… · p. 30

A.2 A compact noise hypothesis

• Fixed additive timing noise disproportionately harms fast tests because the same absolute perturbation occupies a larger fraction of their measurements.A 53 ms affine-calibration intercept is consistent with fixed execution overhead; that perturbation reaches at least half of 75.9% of LCB and 52.4% of DMC-Optim executions.Source: A Simulation study of code… · p. 30, §A.2 · p. 31

A.4 Takeaways

• Larger inputs, longer runtimes, and more tests improve timing reliability; win-rate benefits more than timeout on fast additive-noise problems, whereas DMC-Optim strengthens both metrics.DMC-Optim provides about 3.5 times more tests per problem than LCB, and its slower, denser suite makes timing differences more measurable.Source: §A.3 · p. 33, §A.4 · p. 34, Figure 12 · p. 35

A.3 Simulation study: timeout versus win-rate

• Under additive noise, win-rate stays above chance while timeout approaches random guessing on LCB-like problems; on DMC-Optim-like problems both remain usable, but win-rate is consistently higher.Figure 13 summarizes the regime split, while Figure 11 shows timeout’s narrow threshold-sensitive operating band.Source: §A.3 · p. 33, Figure 11 · p. 34, Figure 13 · p. 36

B.1 What the dataset must establish

• DMC-Optim separates correctness tests, which tighten the pass/fail gate, from optimization tests, which create duration spread for ranking correct solutions against stored human reference durations.The construction therefore treats dataset cleanliness and optimization readiness as distinct requirements.Source: §B.1 · p. 38, §B.3 · p. 40

B.2 Source data, limitations, and decontamination

• Raw DMC is inadequate for optimization RL: original tests have median sizes of 18, 24, and 31 characters, mean correct-solution duration 0.088 s, and substantial correctness false positives.The dataset is deduplicated and quality-filtered before augmentation, while Python is retained as a demanding timing setting.Source: §B.2 · pp. 38–39

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 split into 1,000 training and 302 test problems.Duration filterability selects timing-informative problems from the cleaned corpus, rather than merely selecting problems with generated tests.Source: §B.3 · pp. 39–40, Table 10 · p. 40

B.4 Test generation

• DMC-Optim generates correctness and optimization inputs with ten sampled CWM 32B InputGenerator candidates, using small or large cases and up to 150 candidate tests per problem.Expected outputs are produced by trusted human solutions rather than the generator, and optimization campaigns target duration variation rather than only time-limit failures.Source: §B.4 · pp. 40–41
• Each generated test set is retained only when generation succeeds and at least two verified human solutions agree on every output.Later dataset-level filtering removes ambiguous tests, solutions, or entire problems, and the pipeline then adjudicates slow inputs, hidden-constraint violations, and mislabeled solutions.Source: Table 11 · p. 41, §B.4 · p. 42
• The pipeline runs separate correctness and optimization campaigns, with optimization generation targeting large instances near problem constraints after filtering yields a cleaner 3,061-problem pool.Each problem receives 10 independent generator samples, and each accepted sample contributes 15 validated input/output pairs; optimization acceptance rates are not intrinsically easier because earlier filtering removed problematic cases.Source: §B.4 · pp. 41–42, Table 12 · p. 41
• 928 characters and 0.334 s versus 36 characters and 0.137 s: optimization tests impose substantially larger workloads than retained correctness tests.These medians and means come from the final 1,000-problem training split; optimization tests therefore occupy a different feasible-workload range, not merely a larger count.Source: §B.4 · p. 41

B.5 Filtering generated tests

• Correctness filtering removes pathological generated tests, reclassifies solution pools, and rejects problems that retain excessive false positives or correct-solution attrition.Correctness rounds require at least 5 verified-correct solutions, at most 25% correct-solution loss, and false-positive rate below 5%; optimization rounds tolerate more timeouts because duration is the signal.Source: §B.5 · pp. 42–44
• Generated correctness tests reduce mean false-positive rate from 8.27% to 2.11% on 257 problems, but mean correct-solution pass rate falls from 99.99% to 89.98%, requiring multi-level filtering.The raw augmented suite can mix label repair with invalid, oversized, out-of-spec, or ambiguous tests, so the final corpus applies test-, solution-, and problem-level checks.Source: §B.5 · pp. 42, 44, 51
• Optimization tests are useful when diverse workloads create duration spread and partial timeouts while leaving enough successful executions to compare correct solutions.Tests that make nearly every correct solution time out become gates rather than ranking signals, whereas tests that stress none add little optimization information.Source: §B.5 · p. 51

B.6 What remains before duration selection

• 22.1% of problems are removed during test-augmentation filtering, leaving 3,061 of 3,928 problems while retaining 85.1% of verified-correct and 69.1% of incorrect solutions.Generated correctness tests remove 867 problems; the asymmetric solution retention reflects false-positive cleanup and a cap on correct-solution attrition.Source: §B.6 · pp. 51–52
• After correctness cleaning, the remaining selection problem is identifying optimization-test pools with enough timing variation to define a useful objective.At this stage, problems have cleaned labels plus generated correctness and optimization tests but have not yet been restricted to duration-filterable problems.Source: §B.6 · pp. 51–52
• The corpus retains a full approximately 117 GB variant and a lightweight approximately 35 GB variant, with the latter keeping one correct and one incorrect solution per problem and excluding optimization tests.Both variants share the same split; the lightweight form supports faster development iteration before duration selection.Source: §B.6 · p. 52

B.7 Duration filterability

• 48.2% of optimization problems are duration-filterable, and 35.6% satisfy both duration and length filterability, while other test categories are almost never duration-filterable.Duration filterability uses Robust CV ≥0.3 across representative per-test durations; requiring length filterability would discard 306 optimization problems whose runtimes remain informative.Source: §B.7 · pp. 52–53, Table 20 · p. 53

B.8 The final duration-filterable RL pool

• 1,000 retained problems show optimization tests reaching 1.296 s at p95 and 3.710 s at p99, with 6.87% above 1 s versus 0.42% for original tests.At the problem level, 18.9% have at least 10% of optimization tests above 1 s, versus 5.2% for correctness and 1.2% for original tests; the 1 s cutoff is a reference, not a requirement.Source: §B.8 · pp. 55–56, Table 21 · p. 56, Table 22 · p. 56

B.9 Training ablations: does DMC-Optim help, and is it enough to solve optimization RL?

• Character-length filtering reaches 9.5% on duration-filterable data versus 10.4% for Filter 2s and 16.1% for ranked p30, while its non-filterable score is 9.4% versus 8.3% for MC+MO.Removing large tests can discard useful duration-tail signal on filterable problems, but is less costly when non-filterable problems lack a useful timing ladder.Source: §B.9 · pp. 59–60
• Ranked p30 requires duration-filterable problems: replacing that pool with mixed and non-filterable pools lowers p30 from 16.1% to 13.3% and 9.1%, because flat duration profiles make speed ordering noisy.The MC+MO baseline changes only moderately across pools, from 9.3 to 8.9 to 8.3, indicating the issue is specifically the optimization timing signal.Source: §B.9 · pp. 59–60
• Raw duration on optimization tests improves p30 over MC+MO by 17.2–19.4% but remains 41.9–42.9% below ranked p30, showing that stronger tests alone do not recover problem-relative timing.On base tests, both linear and logarithmic raw-duration variants drop 10.8% relative to MC+MO.Source: §B.9 · p. 60, Table 24 · p. 60
• DMC-Optim helps only with downstream reward design: ranked p30 falls from 16.1% on duration-filterable problems to 9.1% on non-filterable problems, while raw-duration controls remain below ranked p30.The dataset must create measurable within-problem duration structure, and the RL recipe must turn it into a stable training signal.Source: §B.9 · p. 60

C Making runtime measurements trustworthy: code execution backend

• The backend appendix replaces the initial local sandbox with calibrated CES and analyzes execution, fallbacks, failure rates, short-run noise, long-term drift, and affine calibration for training and evaluation.These controls make ablation differences interpretable as dataset, reward, or training-recipe changes rather than uncontrolled backend variation.Source: C Making runtime measurements… · p. 61, §C.1 · p. 61

C.1 What a code execution backend has to establish

• Optimization-RL timing requires reliable measurement because the pooled optimization-test p95 is 1.296 s, p99 is 3.710 s, and only 6.87% exceed 1 s, so sub-second perturbations can change rewards and rankings.The backend must isolate code timing from worker contention, expose failures, and support calibration when service state changes.Source: §C.1 · p. 61
• Local execution shares workers with inference and rollout load, whereas CES runs each code-test pair under a fixed 1 GB memory and 10 s hard limit and returns status plus duration.CES separates timing from worker contention and allows controlled retries, concurrency, and independent provisioning; the paper therefore uses calibrated CES for optimization-RL runs.Source: §C.1 · p. 61

C.2 Local sandbox and why it is bad for timing measurements

• At 0.1 s, local execution inflated pass@1 by 21.3×–50.3× across four model checkpoints, placing evaluation in a noisy regime where tiny perturbations dominate.The local harness also reversed the apparent ranking of the 7B baseline and optimization-RL model relative to calibrated DMC-Optim results.Source: §C.2 · p. 62, Table 25 · p. 62
• Local reruns changed mean-percentile scores by 41.2 percentage points peak-to-peak on average, with an 11-point standard deviation and a maximum range of 73.743 points.Across 23 problems and 425 reruns, unchanged code could move from roughly the top 30% to the bottom 30% of the leaderboard.Source: §C.2 · p. 63
• Local and CES timings were incompatible: 81.1% of problems were duration-filterable locally versus 48.2% on CES, while 36,660 paired measurements resisted all tested corrections.All multiplicative, power-law, affine, and polynomial mappings had negative leave-one-problem-out R2, so local timing could not be calibrated to recover CES ordering.Source: §C.2 · pp. 63–64, Table 26 · p. 64
• Under CPU contention, local jobs failed increasingly often: 294/724 without added load, 485/724 at 50%, 531/724 at 100%, and 613/724 at 200%.Observed failures included very slow executions, local out-of-memory events, and worker-side instability that service-side retries cannot isolate.Source: §C.2 · p. 64
• Local optimization RL failed operationally: seven variants exhausted scheduler attempts, ran 12–32 hours, reached only 160–1,620 steps, and were 4–8× slower than CES.The failures involved out-of-memory kills and distributed-communication errors; data loading reached 355 seconds per step versus single-digit seconds in corresponding CES runs.Source: §C.2 · p. 67

C.3 Remote execution service

• CES isolates execution from rollout workers, enforcing 1 GB memory and 10 s hard limits while returning statuses and durations from separately provisioned sandbox capacity.Its queue enables controlled concurrency, visible retries, and reduced interference from model inference, orchestration, and optimizer state.Source: §C.3 · p. 67

C.4 Fallback after remote execution failures

• After CES retries, local fallback recovers correctness verdicts but never imports local timing; timing-sensitive local successes become 10 s timeouts, while correctness fallback remains pass/fail only.This prevents faster local reruns from reversing the remote timing signal; with timeout tolerance 1.0, converted optimization successes affect ranking without causing incorrectness.Source: §C.4 · pp. 67–68

C.5 Quantitative impact of infrastructure failures

• 13.9% per-rollout exposure at f = 0.1% and n = 150 corresponds to roughly 4.5 × 10^4–6.6 × 10^4 consumed snippets, or 0.5–0.7B packed training tokens.The estimate uses 10,000 optimizer steps, 16 replicas, and about two consumed snippets per replica per step; the training path avoids false negatives by preserving locally recovered correctness successes.Source: §C.5 · pp. 68–69
• 45.5% of correct rollouts reach fallback at least once at f = 2% with 30 tests, while f = 0.1% yields 3.0%, 9.5%, and 13.9% for 30, 100, and 150 tests.Table 27 computes per-rollout exposure assuming independent per-test failures; the table notes that fallback exposure can create false negatives if recovered successes become timeouts.Source: §C.5 · p. 68, Table 27 · p. 69
• After step 1,000, CES-only execution averages 99.3% for Qwen 2.5 7B and 98.1% for CWM 32B, with local fallback averaging 0.13% and 0.21%, respectively.Table 28 defines CES-only as parsed rollouts resolved remotely without local fallback and warns that run-wide means can hide degraded intervals.Source: §C.5 · p. 69, Table 28 · p. 70
• The worst burst reduces CWM 32B CES-only execution to 54.3%, raises local rerun to 41.6% and timeout rate to 14.1%, and is driven mainly by inconclusive results rather than hard errors.At the worst logged step, hard infrastructure errors are 0.00%, unknown or inconclusive results are 6.3%, and unknown-triggered local reruns reach 44.5%.Source: Table 29 · p. 70, §C.5 · p. 70, Figure 28 · p. 73
• Silent CES degradation can shift recorded durations even when verdicts and fallback rates appear healthy, so monitoring must include reward streams and duration distributions, not only hard failure rates.Two identical CWM 32B p30 runs show contrasting symptoms: one has 98.53% mean CES-only with volatile returns, while the other has 97.18% mean CES-only and late bursts.Source: §C.5 · p. 70, Table 30 · p. 72, Figure 30 · p. 74

C.6 Alternative fallback designs

• Optimization-test successes recovered locally become timeouts, whereas correctness-test successes retain their local verdict; immediate retries help transient failures but cannot solve persistent bursts.Retries must remain short because delayed rollouts become less comparable within asynchronous RL and prompt groups; category-specific thresholds or trajectory discarding remain possible refinements.Source: §C.6 · p. 75
• Discarding any trajectory with fallback would discard about 80% of trajectories at f = 2% and 80 tests, or 33% at f = 0.5%, while skipping tests risks false positives.Discarding also biases training toward smaller test suites; skipping a bug-detecting test can reward an incorrect solution.Source: §C.6 · p. 75
• Quarantining degraded windows is operationally expensive, while live calibration probes trade monitoring noise and CES capacity against detecting silent slowdowns; probes are better suited to health diagnostics.The paper does not implement routine quarantining, and same-prompt grouping can reduce—but not remove—service-drift sensitivity because stored human-reference durations still require calibration.Source: §C.6 · p. 75

C.7 CES noise, drift, and calibration

• CES repeated-measurement noise has mean coefficient of variation 9.1% and mean standard deviation 12.4 ms, far below local-sandbox instability but material near strict percentile boundaries.The induced mean-percentile standard deviation is 2.1 percentage points, while repeated measurement explains about 0.9% of total duration variance.Source: §C.7 · p. 76, Table 31 · p. 77
• Uncorrected stored rankings reach only 0.54 Spearman correlation with fresh CES rankings, with 29 of 33 problems biased in one direction by 19.6 percentage points on average.Longer tests require a slope below one, while fast tests exhibit a fixed overhead, so a global multiplier is insufficient.Source: §C.7 · p. 77, Figure 31 · p. 78
• Affine correction raises stored-to-fresh ranking correlation from 0.54 to 0.96, while polynomial correction improves held-out R2 only from 0.9933 to 0.9936.The affine map uses α = 0.6306 and β = 0.0529 s; it captures the fixed overhead with one fewer parameter.Source: §C.7 · p. 77, Table 32 · p. 78

C.8 Temporal stability of calibration

• Across calibration campaigns, slope changes only 1.0% and cross-validated R2 remains above 0.98, while the intercept shifts from 53 ms to 38 ms.The intercept change alters predicted duration by roughly 3% at 1 s and 1.5% at 5 s.Source: Table 33 · p. 81, §C.8 · p. 81
• The model-performance profile is highly stable across campaigns, with Spearman ρ = 0.99 for per-problem candidate percentiles.This supports reusing the affine calibration family while allowing its numerical parameters to follow service-state changes.Source: §C.8 · p. 81

C.9 Evaluation-time sensitivity to affine calibration

• Reducing β from 0.0498 to about 0.0344 s drops baseline p10 pass@1 from 38.8% to 1.2%, while reducing α from 0.7019 to 0.5692 drops it from 31.1% to 1.4%.The additive offset dominates fast-reference perturbations, whereas the slope has larger effects on multi-second durations.Source: §C.9 · pp. 81–82
• At stringent calibration, Filter 2s, QP, and QP train p30 retain 4.0%, 3.9%, and 4.2% p10 pass@1 versus 1.2% for baseline, yielding 233%, 225%, and 250% relative gains.At β ≃0.042, the same models score 22.2%, 21.8%, and 22.2% versus 9.2% baseline; Figure 34 reports the corresponding sensitivity sweep.Source: §C.9 · p. 82, Figure 34 · p. 83

C.10 Joint training-time and evaluation-time calibration sweeps

• A 35.3–35.5-point p10 pass@1 drop across scoring calibrations dwarfs reward-calibration effects, while ranked p30 remains modestly stronger than QP for strict optimization.For ranked p30, p10 pass@1 falls from 41.1% to 5.8%; for QP, from 40.1% to 4.6%. The sweep also finds ranked-p30 advantages of 1.2, 2.3, and 0.8 points over QP at s0, s5, and s9.Source: §C.10 · pp. 85, 87, Figure 35 · p. 88

C.11 Lessons learned for timing-based RL

• Controlled, concurrent service execution is required for timing-sensitive training and evaluation because infrastructure bursts or silent slowdowns can corrupt timing signals despite normal aggregate health.Local sandbox durations should not enter timing rewards or timing-sensitive metrics; shared re-execution and calibration refitting are recommended when service conditions change.Source: §C.11 · p. 91

C.12 Improvements and experiments we did not have the time to conduct

• Proposed follow-up studies would inject known timing noise, replay fixed rollouts under service traces, store duration variance estimates, and adaptively monitor or recalibrate service drift.These experiments target reward variance, noisy tests, selective re-execution, advantage normalization, and quarantine or pausing when drift is detected.Source: §C.12 · pp. 91–92

D Designing Environments and Rewards for Optimization RL

• Optimization tests yield execution records rather than rewards; environments determine how correctness, hard optimization gates, and duration quality are converted into learning signals.The framework treats pre-execution filtering, intra-execution limits, and post-execution ranking as environment choices feeding a common reward-facing interface.Source: D Designing Environments and Rewards… · p. 93, §D.1 · p. 93

D.1 Problem taxonomy

• Each test records status and duration against an effective limit, while calibrated human-reference pools provide reference-derived limits and percentile rankings for optimization evaluation.Statuses are success, timeout, or failure; correctness and optimization tests are separated, and reference durations are not model outputs.Source: §D.1 · p. 93

D.2 Classes of Optimization RL Environments

• Useful environments must provide correctness feedback, distinguish correct-but-slow from wrong programs, and progressively reward faster correct solutions; raw duration rewards otherwise become sparse or reward degenerate fast-but-wrong code.Efficiency thresholds that are too strict may never reward early GRPO rollouts, while direct duration addition gives only small strict-threshold gains versus reference-normalized designs.Source: §D.2 · pp. 93–94
• Optimization environments vary constraints across three stages: pre-execution filtering selects tests, intra-execution limits allocate per-test time, and post-execution ranking scores measured durations.Pre-execution filtering changes the workload, whereas intra-execution limits retain the workload but alter timeout conditions; post-execution methods use raw or reference-normalized durations.Source: §D.2 · pp. 94, 96, 97, 98
• Pre-execution filters include absolute-duration, character-length, and relative-duration families, trading workload coverage against reward sparsity and strict optimization pressure.Absolute filtering uses calibrated human runtime, character-length filtering uses serialized input-output size, and relative filtering removes a per-problem fraction of slow calibrated tests.Source: §D.2 · pp. 95–96
• Intra-execution environments use absolute, per-test relative, or ranked-reference timeouts, with timeout tolerance controlling whether the optimization side passes.Absolute timeouts share one deadline; relative timeouts derive deadlines from each test’s reference-duration percentile; ranked-reference timeouts derive them from a coherent selected reference pool, while all inherit reference-pool biases.Source: §D.2 · pp. 96–98
• All optimization classes retain a strict correctness prerequisite, expose the timeout fraction as a hard gate or graded scalar, and can rank durations using QAR or QP.The timeout tolerance ρ=1 disables the hard timeout gate, while post-execution ranking compares raw or reference-normalized durations either per test or at the solution leaderboard level.Source: §D.2 · pp. 97–98
• Post-execution ranking rewards candidates for moving upward against a same-problem reference leaderboard, avoiding pre-execution workload cutoffs and intra-execution budget changes.Its main limitation is dependence on the reference distribution, which may be narrow or biased and can induce overfitting to observed trade-offs.Source: §D.2 · p. 99
• QAR preserves the average per-test percentile, whereas QP ranks that aggregate among references to expand relative reward resolution but saturates at the best existing position.The choice is evaluated by repeated-CES noise, within-problem discrimination, and ordering stability after calibration.Source: §D.2 · p. 99
• The final interface separates correctness from optimization by exposing one hard gate g and one graded scalar q, with inactive factors set to neutral values.The optimization interface combines status-side and duration-side gate factors while selecting duration or time-ordering scalars according to the active ranking mode.Source: §D.2 · p. 99
• Table 38 screens environment families over offline-simulator parameter grids, while Qwen 7B and CWM 32B online runs promote selected configurations instead of rerunning every setting at scale.The environments include optimization tests and impose a 10s correctness cap.Source: §D.2 · p. 99, Table 38 · p. 100

D.3 How to create a good ranking score based on recorded durations

• Mean percentile is retained because it has the lowest cross-validation dispersion, comparable rerun noise to filtered variants, and a 47-point spread without trimming hyperparameters.The selected signal supports QAR and QP scalarizations for post-execution RL rewards.Source: §D.3 · p. 102, Table 39 · p. 102

D.4 Composing rewards that best balance correctness and optimization objectives

• Reward compositions vary in whether optimization credit requires strict correctness, with collapsed and two-gate rewards enforcing correctness while blends and multitask variants expose softer feedback.Quality percentile is a graded two-gate reward using the mean-percentile duration ranking; mapped rewards also vary the relative correctness–optimization scale.Source: §D.4 · pp. 104–105

D.5 Raw-durations (aka naive) reward baselines

• Raw-duration rewards are easy to compute without reference data but fail to normalize timing credit by problem difficulty or attainable speed distributions.A correct 1s average solution receives 0.9 under the linear map, while an incorrect but very fast solution can receive nearly 0.Source: §D.5 · p. 108, Table 42 · p. 108

D.6 Taxonomy of optimization/efficiency definitions in previously published papers

• The taxonomy distinguishes pre-execution test construction, intra-execution limits, and post-execution ranking, while noting that prior systems often simplify training through editing or inference-time selection.The retained setting uses one-shot generation from scratch with live execution feedback and no execution feedback during generation.Source: §D.6 · pp. 108–109, Table 43 · p. 110, Table 44 · p. 111

E.1 Same environment, cheaper executions

• The offline simulator preserves environment-side filtering, timeouts, ranking, and outcome computation while replacing model generation and sandbox execution with reference samples and stored calibrated durations.It is a lightweight computation of environment outcomes, not a model of online learning.Source: E Doing offline RL simulations to… · p. 112, §E.1 · p. 112, Figure 43 · p. 112

E.2 Quantifying what a good RL environment is

• A useful environment should neither pass nor fail everything nor reward intermediate samples without correlation to better generations, motivating simulated pass-rate diagnostics.The simulator evaluates how the environment reacts to increasingly stronger sampled solutions, not how the policy learns from rewards.Source: §E.2 · p. 112, §E.1 · p. 112
• AUC measures pass-outcome density across a simulated run, flagging environments that reward almost everything or are too sparse for useful online updates.The section also defines steepness from a clipped linear fit to the smoothed pass-rate curve.Source: §E.2 · p. 113
• Steepness measures whether activation changes smoothly or abruptly as sampled solutions move from mostly failing to mostly passing.It is the bounded slope of a clipped linear fit to the activation curve, complementing AUC’s measure of total activation.Source: §E.2 · p. 113
• Variance measures local wobble around the smoothed activation trend, indicating reward stability or noise rather than overall environment behavior.This metric evaluates how stable the reward is around the moving-average curve.Source: §E.2 · p. 113
• Deviation from the diagonal measures whether activation progresses gradually across the full quality range and where activation occurs.It is larger when activation is delayed until samples become stronger, while smooth middle-range activation stays closer to the diagonal.Source: §E.2 · p. 113
• Quality-correlation measures whether pass outcomes increase with normalized sample quality, including after smoothing to reduce individual-sample noise.It detects environments whose average reward density appears reasonable but does not useful ordering of sampled solutions.Source: §E.2 · p. 113

E.3 Do these metrics correlate with downstream online RL performance?

• At p30, deviation from y = x, raw quality-correlation, and steepness correlate most strongly with online RL pass@1, whereas curve noise remains uninformative.The corresponding Spearman correlations are rs = −0.832, 0.787, and 0.723, while curve noise has rs = −0.002.Source: §E.3 · p. 113, Table 45 · p. 114
• Offline diagnostics are weak for pure correctness at p100 but become more predictive as optimization constraints strengthen, without establishing that they predict online training-curve shape.The simulator is most useful for pruning degenerate environments; finer-grained ranking remains unresolved because downstream RL runs are insufficient.Source: Table 45 · p. 114, §E.3 · p. 114
• Correlations with earlier RL checkpoints are weaker, whereas end-of-run metrics show stronger signal, consistent with variability during training.Figure 44 qualitatively compares offline simulator curves with online training pass rates for matched Qwen 2.5 7B environments.Source: §E.3 · p. 114, Figure 44 · p. 115

E.4 Using the offline simulator to select the most promising parametrization of each environment

• Parameter sweeps use the simulator primarily to search within environment families, exposing how controls such as thresholds, time limits, and timeout tolerances affect diagnostic behavior.Pre-execution environments can have three continuous controls, while post-execution leaderboard ranking mainly varies its percentile threshold.Source: §E.4 · p. 114, Figure 45 · p. 116
• The sweeps identify degenerate and permissive settings: absolute filtering often rewards too many samples, ranked-worst p10 with low tolerance is too hard, and leaderboard p10 is too strict while p100 and p90 are too permissive.Middle-ground ranked-worst settings occur at higher percentiles with timeout tolerance around 0.1.Source: §E.4 · p. 114
• Variance around trend correlates weakly with downstream online RL performance but remains low across the post-execution leaderboard family.Figure 45 reports the relative diagnostic values across the parameter sweeps and cautions that color scales are not globally comparable.Source: §E.4 · p. 114, Figure 45 · p. 116

F Async-RL and training objective

• GRPO generates a same-prompt group of G rollouts and centers each return against a prompt-level token-weighted mean before optimizing a clipped surrogate objective.The formulation uses a fixed token horizon N rather than the realized response length.Source: F Async-RL and training objective · p. 117

G.1 Judge prompt used for the pairwise analysis

• The judge asks GPT-OSS 120B to compare two solutions’ algorithms, data structures, implementation choices, complexity, speed, categories, and algorithmic versus superficial classification in a single JSON object.The prompt includes predicted faster solution, complexity comparisons, complexity-improvement flags, primary and secondary optimization categories, classification reason, and key differences.Source: §G.1 · p. 118
• The judge’s categories distinguish algorithm changes, data-structure changes, complexity reduction, I/O, caching, constant factors, implementation style, and mathematical shortcuts.Algorithmic solutions use fundamentally different paradigms, whereas superficial solutions retain the core approach and improve implementation-level efficiency.Source: §G.1 · p. 118

G.2 Cases where optimization-RL beats standard RLVR

• On a span-computation problem with n, m ≤ 5 · 10^5, optimization-RL reduces RLVR runtime from 46.4 s to 28.5 s, a 1.63× speedup.Both CWM 32B submissions are correct, but optimization-RL recovers the known intended solution while standard RLVR produces a more generic correct program.Source: §G.2 · p. 119
• Optimization-RL replaces generic GF(2) elimination with a near-linear union–find graph reformulation that tracks component-level single-coordinate vectors.Two-coordinate vectors become graph edges, one-coordinate vectors become component-level singles, and disjoint-set union maintains the rank.Source: §G.2 · p. 120
• On ARC085, optimization-RL collapses memoized minimax over every prefix into a closed form depending only on the last one or two cards.For N = 1, the answer is |a0 −W|; otherwise it is max(|aN−1 −W|, |aN−1 −aN−2|).Source: §G.2 · p. 121

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

• 13.5 s versus 17.2 s (×1.28) on Codeforces 571A, where optimization-RL replaces an O(ℓ) triangular-number sweep with O(1) closed-form evaluation per invalid side.The human solution uses inclusion–exclusion and a valid O(ℓ) sweep; optimization-RL evaluates the quadratic sum directly.Source: §G.3 · pp. 122–123
• Optimization-RL uses a canonical one-pass running-maximum solution with an array of exit positions, whereas the human solution uses two pointers and a set; both are O(n).The Optimization-RL implementation is cleaner, with less hashing and pointer bookkeeping.Source: §G.3 · p. 123
• 12.7 s versus 13.1 s (×1.04) on Codeforces 534B, where optimization-RL sums the minimum of the start- and end-ramp bounds in O(t) rather than using an O(td) greedy simulation.The direct two-ramp formulation is cleaner than the human per-step scan over feasible speed changes.Source: §G.3 · p. 124