Margin-Driven Edit Scope for Code Performance Agents

Language-model agents that try to speed up real software repositories spend most of their compute checking their own work. They do not spend it writing code. Each candidate patch has to be built, tested, and timed many times inside a container before anyone can tell whether it helped. The agent then usually gets back a single bit: keep the patch or discard it. Numerical optimization met a very similar situation in line search, the inner loop that tries a step size, checks whether the objective went down, and shrinks the step if it did not. That field learned two things. The magnitude of a failed check is free information worth using. And the cost of repeated checking, not the direction of progress, often dominates wall-clock time. We propose carrying both lessons into repository-level performance optimization. The continuous, noise-normalized margin from each timing check should decide two things. It should set how much code the agent may touch next. It should also set how much measurement the next check deserves.

In two sentences: today's performance agents treat "did this patch speed things up?" as pass/fail at a fixed, high measurement cost. We instead turn the signed size of the measured speedup, relative to timing noise, into a rule that widens or narrows the agent's allowed edit region and spends expensive repeated timing only where the answer is still ambiguous. We test whether this yields more speedup per unit of profiling compute on SWE-fficiency and SWE-Perf.

Core Claim

Under a fixed profiling budget, a performance agent whose edit scope and measurement effort are both driven by the signed, noise-normalized margin of the previous check should reach larger verified speedups than an agent with binary accept/reject and uniform measurement. It should also accept fewer false improvements. The mechanism has one part that is not a straightforward transfer from optimization. A neutral result should expand the scope rather than shrink it. In classical backtracking a failed check always means "step smaller." Here a patch that neither helps nor hurts is evidence that the current local region has nothing left to give. That matches the "satisficing" failure that SWE-fficiency documents, where agents stop after nominal local speedups (caching, early exits) and miss the functions where experts actually made their gains.

Motivation and Positioning

Each group of prior work plays a different role here.

Evidence that the problem exists. Two benchmark papers establish the gap. SWE-Perf evaluates agents on 140 repository optimization tasks, timing each candidate over 20 Docker runs with a Mann-Whitney test. It reports that OpenHands with Claude-3.7-Sonnet gains 2.26% against a human 10.85%, with functional correctness kept about 77% of the time. SWE-fficiency evaluates agents on 498 workload-speedup tasks. It finds frontier models reach less than 0.23x of expert speedup, and that over 68% of expert gains lie in functions the agents ignore. Both papers are diagnostic and propose no search procedure. We supply one.

Evidence that binary checking is wasteful. Adaptive backtracking line search replaces the constant shrink factor of backtracking with a factor computed from how badly the descent condition was violated. That violation is a free byproduct of the check. The paper reports up to 57.6% runtime reduction on logistic regression and up to 93.5% on nonconvex matrix factorization. We reuse its principle, a continuous violation driving the next step, but our "step" is an edit region rather than a scalar. We also allow the step to grow on neutral outcomes, which that paper's descent setting never needs. Adaptive Gradient Descent without Descent removes objective evaluations entirely by setting step sizes from successive gradient differences, and it tolerates temporary increases in the objective. It sets the ambition of spending checks sparingly. Its convergence argument is for convex objectives and does not transfer to discrete code edits, so we borrow the motivation and not the guarantee. Empirical risk minimization: probabilistic complexity and stepsize strategy shows that cheap prior bounds can guide an expensive line search. That is the role our cheap first-stage check plays.

Systems we build on and compete with. POLO is the closest system. A Generator Agent proposes rewrites of bottleneck functions, and a Decision Agent compiles, profiles, and rejects patches that do not speed things up, reaching 1.34x to 21.5x over -O3 on six C/C++ projects. Its acceptance is binary and its measurement uniform; we change exactly those two things. MEIC rolls back to the last stable version on any regression in Verilog debugging. MAGIS fixes edit granularity by convention: one developer per file, edits limited to local hunks. Both provide the fixed-scope and hard-rollback behaviour we ablate against.

The cheap oracle. Rethinking Code Refinement: Learning to Judge Code Efficiency trains 1.3B/7B code models to predict, without execution, whether a rewrite is faster. It reports 72.49% Python accuracy and Spearman 0.66 on predicted speedup, and finds that machine refinements slow code down about 30% of the time. That paper evaluates static pairs and never sits inside a search loop. We use it as one input to a cheap first-stage margin. The obvious way to combine it with an agent is as a pre-filter, and we treat that as a strong baseline rather than as our contribution.

The contrasting design. From Search to Policy (TGPR) removes test-time search by moving tree search into reinforcement-learning training. It reports 77.6 on MBPP and 12x faster inference than REx. Its reward includes CodeBLEU against reference code, which open-ended performance tasks lack. Our proposal keeps closed-loop verification at test time and attacks its cost instead.

Research Program

The margin. For a candidate patch, the first stage combines two cheap signals. One is a small number of timed runs $r_0$ (we start with 3). The other is the static judge's predicted speedup. From these we form a standardized margin

$$z = \frac{\hat{s} - 1}{\hat{\sigma}},$$

where $\hat{s}$ is the estimated speedup ratio of the workload (old time over new time) and $\hat{\sigma}$ is its estimated standard error. We estimate the variance once per task from repeated runs of the unmodified code, so that a handful of runs on the patch are enough.

Measurement effort. If $|z|$ exceeds a threshold, the patch is decisively better or worse and no more timing is spent. Otherwise it is escalated to the full 20-run protocol of SWE-Perf. Every patch that is finally accepted must pass the full protocol and the correctness tests. The cheap stage can only save compute on rejections and route ambiguous cases. It can never grant acceptance.

Edit scope. Scope $k$ is the number of functions the agent may modify. Functions are ranked by a call-graph bottleneck score in the spirit of POLO's FuncRank, and the scope is the top-$k$ set plus their callers. The update is

$$k_{t+1} = \mathrm{clip}\big(k_t \cdot g(z_t)\big),$$

where the growth function $g$ behaves differently in three regions of the margin. It is below 1 and decreasing in $|z|$ for clear regressions or test failures. There the agent narrows, and a large regression narrows it faster, which is the violation-sensitive shrinking of adaptive backtracking. It is above 1 for neutral results with $|z|$ small, so the agent widens toward structural changes. It stays near 1 for clear improvements, so the agent keeps exploiting. Test failures use the fraction of failing tests as the violation magnitude. We fit the few parameters of $g$ on a held-out split of SWE-fficiency tasks, never on evaluation tasks.

What is not changed. The generating model, prompts, repository tools, and localization are held identical across all arms. The only thing that varies is the controller that sets scope and measurement. This isolates the contribution from agent quality.

Cost accounting. The primary resource is profiling container-seconds. We also report LLM tokens and end-to-end wall-clock. Every comparison is made at matched profiling budgets, as a full speedup-versus-budget curve rather than a single point.

Baselines

Do nothing / one-shot. The model proposes a single patch with no loop, and we measure it once under the full protocol. This is the floor, and it shows how much any loop adds on these tasks.

Standard agent loop. OpenHands with its default iterate-and-test behaviour, using the same generating model as all other arms. It is the reference that the benchmarks themselves report. For calibration, SWE-Perf reports a 2.26% average gain for OpenHands with Claude-3.7-Sonnet, and SWE-fficiency reports a 0.225x speedup ratio for Claude 4.5 Opus. Those numbers use different models from ours, so we rerun this arm rather than copy the figures.

POLO-style binary loop. This is the strongest direct competitor: every patch is fully profiled, accepted only on significant speedup, and scope is fixed. We reimplement its Decision Agent logic over the same bottleneck ranking in Python repositories, since POLO was evaluated only on C/C++. We also run it on POLO's own six projects, where the reported range is 1.34x to 21.5x over -O3. At equal budget, it represents the best existing design this proposal must beat.

Judge pre-filter. POLO-style full measurement, but only for patches that the efficiency judge predicts are faster. This is the most plausible simpler competitor. The judge's reported 72.49% accuracy and 0.66 Spearman suggest it would prune many regressions cheaply.

Sequential early stopping without scope control. The same two-stage measurement as ours, with fixed scope. This is standard statistics, and it isolates how much of any gain comes from measurement savings alone.

Fixed-factor scope shrinking and hard rollback. The scope halves on every failure, with MEIC-style reversion. This isolates the value of a margin-dependent factor over a constant one.

Shrink-only ablation. Our rule with $g \le 1$ everywhere, so neutral results do not widen the scope. This removes the key ingredient and tests the satisficing hypothesis directly.

Best-of-N sampling. Patches sampled in parallel and fully profiled, with $N$ chosen so the arm spends the same profiling budget.

Every arm uses the same generating model, the same task split, and the same seeds. The same number of held-out tuning tasks is used for any thresholds, including the judge-filter threshold and the best-of-N temperature. Beating the field means a higher verified speedup ratio on SWE-fficiency and a higher gain on SWE-Perf than both the POLO-style and judge-filter arms at every matched budget. Correctness retention must not be lower, and the false-acceptance rate must be no higher.

Why not just…?

Why not just use the efficiency judge as a filter before profiling? This is a real threat. If static prediction alone captured most of the value, our controller would add complexity for little gain. Two considerations suggest it will not be enough, though only experiment can settle it. First, a judge with roughly 72% pairwise accuracy will wrongly discard some true improvements, and the discarded ones may be the large structural rewrites that least resemble its training pairs. Second, a filter only saves measurement; it does nothing about where the agent looks next. The judge-filter arm and the "sequential stopping without scope control" arm together measure the savings-only story. If our method beats them only through measurement savings, the scope rule is not pulling its weight, and we would say so.

Why not just show the agent the measured numbers and let the language model decide how much to edit? Current agents already see test output and timings. SWE-fficiency nonetheless reports that they satisfice on shallow shortcuts, and Yan et al. report that refinement returns fade after three to five rounds. Both suggest that raw feedback in the prompt does not produce scope expansion on its own. We test this directly with an arm that puts $z$ and the timing history into the prompt with no external controller. If that arm matches ours, the contribution reduces to "show the margin," and that is a finding worth reporting.

Why not just spend the budget on best-of-N sampling? Sampling in parallel spends full measurements on every candidate. SWE-Perf's 20-run protocol makes each candidate expensive, and TGPR's authors report that inference-time search is far slower than a trained policy. Best-of-N also never widens the search region deliberately. The matched-budget best-of-N arm settles whether diversity alone recovers the structural gains.

Why not just shrink scope by a fixed factor, as backtracking does? Constant-factor backtracking forces a choice between shrinking too slowly and wasting checks, or shrinking too fast and stalling. The adaptive backtracking paper's gains over constant factors are exactly this effect in the continuous case. More importantly, shrink-only rules cannot address satisficing. The fixed-factor and shrink-only ablations test both points.

Proposed Experiments

The main experiment runs every arm on SWE-fficiency (498 tasks) and SWE-Perf (140 tasks) at four profiling budgets per task. We report speedup ratio and average gain under each benchmark's own full measurement protocol, together with test-pass retention.

The first decisive check is the budget curve. Our method should dominate the POLO-style and judge-filter arms across budgets, with the largest margin at low budgets, where wasted measurements hurt most. If the curves cross or coincide, the core claim fails.

The second decisive check is the source of gains. For each accepted patch we record whether it touched functions outside the initial top-ranked set. SWE-fficiency's observation that over 68% of expert gains lie in ignored functions predicts that the widening rule should raise this fraction and that those patches should carry a disproportionate share of speedup. The shrink-only ablation should lose precisely these patches.

The third check measures false acceptance. We fully re-measure a random sample of patches that were rejected or accepted after the cheap stage. This estimates how often the two-stage scheme misjudges a patch, compared with the roughly 30% machine-regression rate reported by the judge paper. If the cheap stage wrongly rejects large improvements often enough to erase the budget savings, the measurement half of the design fails.

The final check is transfer. We run the controller, with parameters fitted only on the SWE-fficiency tuning split, on POLO's six C/C++ projects under -O3. This tests whether the rule reflects general properties of performance search or overfits Python library workloads.