Guarded Partial Replacement for LLM Code Optimization

When a language model speeds up a program, current pipelines make one binary decision: the rewritten code either replaces the original everywhere or gets thrown away. That decision is expensive. On repository-scale optimization, roughly half of agent patches are rejected for breaking functionality (FormulaCode). Many of those patches are probably fast and correct on most inputs and wrong only on an edge region such as empty arrays, unusual data types, or tiny sizes. This proposal keeps the fast rewrite but runs it only on inputs that pass a simple, checkable condition (a "guard"), and sends every other input to the original slow-but-correct code. The optimizer then needs to be right only inside the guarded region. Testing effort can be concentrated there, and any correctness failure is confined to the fast path rather than to the whole program.

The design comes from partial decode-and-forward relaying in wireless networks. There, a relay node that cannot reliably decode a whole message decodes only part of it, and the rest travels directly to the receiver. In the analogy, the fast rewrite plays the relay, the original program plays the direct link, and the guard decides which part of the input space the relay "carries." The theory has a useful lesson that code optimization has not absorbed: across link qualities, no single forwarding strategy is best. Full relaying, partial relaying, and no relaying each win in a different regime (Constant-gap results and cooperative strategies for a class of Interference Relay Channels). We treat this as a design lens, not a transferred theorem. The claim is that choosing between full replacement, guarded partial replacement, and keeping the original, based on how reliably a candidate can be verified, beats the all-or-nothing accept/reject rule at equal compute.

Core Claim

Let $G$ be a guard predicate over inputs and $\rho$ the fraction of the workload's inputs that satisfy it. Let $T_{fast}$ and $T_{ref}$ be the run times of the rewrite and the reference, and $c_G$ the cost of evaluating the guard. Expected run time is then

$$ T(G) = c_G + \rho\, T_{fast} + (1-\rho)\, T_{ref}, $$

and the probability of a wrong output is at most $\rho\,\epsilon_{fast}(G)$, where $\epsilon_{fast}(G)$ is the rewrite's error rate on inputs satisfying $G$. Current practice sits at one of two corners. Setting $\rho = 1$ is full replacement, the analogue of full decode-and-forward. Setting $\rho = 0$ keeps the original, the analogue of disabling the relay. Our hypothesis is that, for a meaningful share of candidates rejected under full replacement, some simple guard reaches $\epsilon_{fast}(G) \approx 0$ on held-out inputs while $\rho$ stays high enough that $T(G)$ is far below $T_{ref}$.

The interesting object is therefore the speedup-versus-coverage-versus-error frontier traced by varying $G$. It plays the role of a rate region, and it is not the single accept/reject point that existing benchmarks report.

Relation to Prior Work

The closest method is anchor verification (A Problem-Oriented Perspective and Anchor Verification for Code Optimization). It runs model-generated inputs through the original program to obtain trusted input-output pairs, then tests the fast candidate against them and iterates on failures. We reuse that machinery directly, since the original program is both our fallback and our test oracle.

The difference is in how verdicts are used. Anchor verification treats the candidate as a single unit and only accepts or rejects it. We turn a failing candidate's pattern of failures into a proposed guard. We then re-verify inside the guard using fresh anchor inputs drawn from that region.

Two lines of work supply the surrounding evidence and constraints. ECCO shows that execution feedback preserves correctness far better than verbal self-critique (54.6% versus 15.8% for CodeLlama), so our loop is execution-driven throughout. Making Execution Time a Trainable Reward for Code Generation and Afterburner train models under correctness-gated efficiency rewards. Those methods improve the generator, while ours changes what is done with the generator's output, so the two can be combined. The gate in those reward designs discards exactly the partially correct candidates we try to salvage.

The repository benchmarks motivate the gap. FormulaCode reports negative agent advantage and high rejection rates. SWE-fficiency reports a speedup ratio of only 0.225x of human experts for its best model. NoFunEval constrains our design: models are poor at telling correct from incorrect code by inspection (20.7% on a binary choice). We therefore never trust a model's own claim that a guard is safe; every guard is checked by execution.

From the wireless side, partial decode-and-forward with rate splitting (Rate Regions for Relay Broadcast Channels) and the coarse/fine message split of Backhaul-Aware Interference Management in the Uplink of Wireless Small Cell Networks supply the structural idea of sending only part of the load through a constrained intermediate. The regime-switching result above supplies the idea that the split should depend on measured link quality.

Research Program

The system has four stages, all built on a standard execution sandbox.

The first stage generates candidates. Any optimizer can be used: an LLM prompted for rewrites, an agent such as OpenHands on repository tasks, or AlgoTuner-style loops on numerical tasks. Each candidate is verified with anchor verification over a generated input pool.

The second stage proposes guards for failing candidates. A model is shown the failing and passing anchor inputs and asked for a guard in a restricted predicate language. That language allows only conditions on input sizes, data types, shapes, value ranges, sortedness, emptiness, and presence of special values. It does not allow conditions on specific input values. The restriction is the main defense against a guard that simply memorizes failing test cases, which would be a new form of reward hacking.

The third stage re-verifies inside the guard. Fresh anchor inputs are sampled from the guarded region; this concentrates the testing budget where the fast path will actually run. The guard and fallback are then wired in, and whole-program timing is measured on the real workload.

The fourth stage selects a regime. For each task, the system chooses full replacement, guarded replacement, or the original. The decision uses a held-out verification-strength signal: agreement with the anchor on a second independent input pool, plus whether the guard's coverage $\rho$ estimated on the workload matches its coverage on generated inputs. This is the counterpart of switching between full relaying, partial relaying, and no relaying according to link strength.

The analysis question is when guarded replacement wins. We will characterize the frontier as a function of verification strength and expect three regimes. Strongly verifiable candidates should favor full replacement. Weakly verifiable ones should favor keeping the original. The interesting middle band is where guards should dominate. If that middle band turns out to be empty in practice, the proposal fails, and that is itself a clean finding.

Baselines

The naive reference point is the unmodified original program, which gives speedup 1x and no regressions. Every method must beat it on speedup without adding hidden-test failures.

The strongest existing method on single-file tasks is anchor verification with iterative refinement as described by its authors. With DeepSeek-V3 it is reported to reach a peak %OPT of 71.06% on the problem-oriented CodeNet setting (A Problem-Oriented Perspective and Anchor Verification for Code Optimization). It is the strongest competitor because it already uses the original program as an oracle and already salvages failures, through repair rather than guarding. We will run it with the same generator model, the same anchor input generator, and the same total budget of model calls and sandbox seconds. Any compute our method spends on guard proposal and re-verification will instead be given to anchor verification as extra refinement rounds. Beating it means a higher %OPT and a higher mean speedup measured on hidden tests, with a hidden-test failure rate no worse than its own.

On repository tasks, the strongest reported system in the file is OpenHands with Claude 4.0 Sonnet on FormulaCode-V (FormulaCode). For it the file reports only that agent advantage is below zero, not a specific value. For SWE-fficiency the reported speedup ratio is 0.225x for Claude 4.5 Opus (SWE-fficiency). On AlgoTune the AlgoTuner agent reports an average speedup of 1.72x (AlgoTune). In each case we wrap the same agent's patches with our guarding stage and compare at matched agent budget. Beating these baselines means raising agent advantage, the speedup ratio, or the average speedup without increasing the benchmark's own correctness-failure count.

Three ablations isolate the key ingredient. The first, always-guard, removes regime selection; it tests whether switching matters or guards alone carry the gain. The second, unrestricted guards, allows value-level predicates; it measures how much apparent gain comes from memorizing failing tests, and we expect it to look better on visible tests and worse on hidden ones. The third, guard without in-region re-verification, reuses the original anchor pool; it tests whether concentrating verification inside the guarded region matters.

Why not just…?

Why not just keep refining the failing candidate until it passes? This is the real threat, and the matched-budget comparison against anchor verification is designed to settle it. Repair can recover the full speedup, with $\rho = 1$, whereas a guard caps it. If repair succeeds on most rejected candidates within budget, guarding adds little. Our bet rests on ECCO's observation that repeated refinement tends to corrupt program logic. We will report directly the fraction of rejected candidates that repair fixes within budget, compared with the fraction that guarding salvages.

Why not just train a better optimizer with correctness-gated reinforcement learning? Gated rewards raise the share of correct candidates. For example, the binary percentile reward lifts $p_{10}$ from 18.1% to 27.7% (Making Execution Time a Trainable Reward for Code Generation). A better generator still produces candidates that fail on edge regions, so the two approaches are complementary. We will apply guarding on top of a gated-reward-trained generator where one is available. If that generator's rejected candidates no longer have salvageable guards, the method's value shrinks accordingly.

Why not just rely on a compiler or just-in-time compiler? Compilers and just-in-time compilers keep semantics exactly but do not change asymptotic algorithms, which is where the large gains reported in A Problem-Oriented Perspective and Anchor Verification for Code Optimization and AlgoTune come from. Guarded fast paths with fallback borrow the speculation-with-fallback idea from just-in-time compilation, but apply it to model-written algorithmic rewrites rather than to machine-level specialization.

Why not just take the best of n candidates? Best-of-n with anchor filtering is a budget-matched variant of the accept/reject rule, and we include it as a baseline. It helps only if some sample is fully correct. Guarding helps precisely when none is.

Proposed Experiments

The first experiment uses problem-oriented CodeNet pairs and ECCO problems in Python and C++. These are cheap, numerous, and come with hidden tests. We report %OPT, mean speedup, and hidden-test failure rate, and we plot the speedup-coverage-error frontier per task.

The second experiment uses AlgoTune, whose numerical tasks have natural guards on size, data type, and conditioning. We report speedup against the 1.72x AlgoTuner reference.

The third experiment uses FormulaCode-V and a subset of SWE-fficiency. These test whether guards survive real multi-workload repositories, where guard overhead and dispatch complexity are real costs. We report agent advantage, speedup ratio, and the change in patch rejection rate.

Three checks decide the outcome. The first is salvage rate: the fraction of baseline-rejected candidates that become accepted guarded patches with zero hidden-test failures and a speedup above 1.2x. If it is under roughly a tenth of rejections, the idea is not worth its complexity. The second is the memorization gap: hidden-test failures of unrestricted versus restricted guards, which shows whether the predicate restriction is doing real safety work. The third is the regime test: whether the selected strategy changes with measured verification strength as the relaying analogy predicts, with guards winning in a middle band. Alternatively, a single fixed strategy may do just as well, which would mean the switching component, and with it the strongest part of the analogy, should be dropped.