Language-model coding agents fix bugs by writing a whole patch, running the tests, reading the errors, and trying again. This loop works well for one-line fixes. It breaks down when a correct fix must touch several places at once, such as changing a data structure and every function that uses it. Agents then leave some of those places unchanged, and the refinement loop tends to stall or go in circles. This note proposes a different division of labour. The language model proposes a pool of small, self-contained edits. A selection procedure with a known worst-case guarantee then chooses which edits to combine, using test execution as its scoring signal and respecting explicit structural constraints on which combinations are allowed. The theory is used as a measuring instrument rather than a slogan: we measure, on real repositories, how far the test-based objective departs from diminishing returns, and we report the guarantee that measurement actually supports.
The central bet is about representation. Raw patch fragments interact badly. Two hunks can each be useless alone and correct together, which is the opposite of diminishing returns and voids any greedy guarantee. We hypothesize that grouping each edit with all the code that must change alongside it restores near-diminishing-returns behaviour. The grouping would come from a dependency graph of the program. If that holds, greedy assembly over these groups under a combinatorial constraint should beat both sampling many independent patches and multi-turn conversational repair at an equal test-execution budget. It should win specifically on fixes that span several locations.
Core Claim
Two failure modes recur in the file. The first is "partial migration": a representation is changed in one module but not at the interfaces that consume it (A₂DEPT). The second is "incomplete localization" across files (BOOSTAPR). Both are cases where a subset of necessary edits is applied without the rest. We claim these failures are a selection problem, not only a generation problem, and that three operations address them together:
- Close each proposed edit under its program dependencies to form a bundle.
- Constrain combinations of bundles with a partition matroid and a diff-size knapsack. A partition matroid is a structure that allows at most one choice from each group; a knapsack is a total size budget.
- Assemble bundles greedily with discrete backtracking, driven by execution.
A note on why bundling is needed. The constraint "if you change X you must change all its users" is not itself a matroid, because matroids are closed under removal and this requirement is closed under addition. Bundling moves that requirement inside each ground-set element. What remains outside is genuinely matroid-like: at most one variant per edit site, and at most $m_j$ bundles per module. On top of that sits a knapsack on total changed lines.
The guarantee we can honestly lean on depends on the submodularity ratio. Let $f(S)$ be the execution score of applying bundle set $S$. The submodularity ratio $\gamma \in [0,1]$ is the largest constant such that, for all sets $L$ and $R$,
$$\sum_{e \in R} \big[f(L \cup \{e\}) - f(L)\big] \;\ge\; \gamma \,\big[f(L \cup R) - f(L)\big].$$
In words, the individual gains of a group of edits recover at least a $\gamma$ fraction of their joint gain. For monotone objectives under a size limit, greedy is known to achieve $f(S_k) \ge (1 - e^{-\gamma}) f(S^*)$. This generalizes the classical $1 - 1/e$ bound (Kempe and Tardos) and recovers it at $\gamma = 1$.
The code-repair objective is not monotone, because an edit can break passing tests. The matroid-plus-knapsack setting is also weaker than a simple size limit. We therefore treat the bound as a hypothesis to be tested, not a certificate. The paper's theoretical contribution is an empirical estimate of $\gamma$, with and without bundling, on real multi-hunk bugs.
Research Program
Stage 1: build the candidate pool. A generator model receives the failing tests, the traceback, and localized files. It proposes many small edits, and each edit must be at most one hunk. Three kinds of evidence supply per-site context:
- a program structure graph of cross-module call and type dependencies, reused from POLO;
- branch-dependency analysis in the style of TELPA;
- the line-level attributions produced by BOOSTAPR's credit model.
Stage 2: close edits into bundles. For each edit that changes a signature, type, or shared data layout, we walk the dependency graph. The model is prompted to produce the forced companion edits at every affected site. A bundle is admitted to the pool only if the repository still compiles or imports with the bundle applied alone. Bundles that address the same site in incompatible ways are placed in one partition class.
Stage 3: define the objective using only information available at repair time. The objective uses three test sources:
- the repository's existing tests, which must stay passing;
- a reproduction test written by the model from the issue text;
- tests the model generates to target the changed branches.
For SWE-bench-style evaluation, we never use the hidden evaluation tests in the objective. We define $f(S)$ as the number of target tests passing minus a penalty weight times the number of previously passing tests broken. Because the pass/fail signal is coarse when there are only one or two target tests, we add assertion-level progress within each target test as a tie-breaking term.
Stage 4: assemble greedily. We use lazy marginal-gain evaluation, because each gain costs a test run and the file notes the $O(k \lvert E \rvert)$ oracle burden. Assembly respects the matroid and knapsack constraints. For non-monotone breakage we adapt the discrete backtracking of λ-GREEDY/λ-DGREEDY (Doskoc et al.): when an added bundle breaks tests, only the offending bundles are removed and selection resumes. If assembly stalls, the loop feeds the residual failures back to the generator for a new round of bundles. This makes the process iterative refinement with a principled selection step in the middle.
Stage 5: measure $\gamma$. On a subset of instances small enough for exhaustive enumeration, we compute $\gamma$ and greedy's ratio to the brute-force optimum. We do this for three ground sets: raw hunks, dependency-closed bundles, and whole-patch candidates. This is the analysis that tells us whether the guarantee means anything in this domain.
How this relates to the three literatures.
- Dynamic and robust matroid algorithms. Duetting et al. on dynamic consistency and on deletion robustness supply the constraint vocabulary. Both assume a cheap value oracle over fixed items. Here the items are generated on the fly and the oracle is test execution.
- Continuous relaxations. Methods such as the multilinear extension used by Wilder are ruled out, because a fractional patch cannot be executed. Doskoc et al.'s finding that discrete greedy needed orders of magnitude fewer evaluations than FANTOM is the reason we stay discrete.
- Search-based code systems. A₂DEPT searches over programs with simulated annealing, and POLO chooses optimization sites heuristically. Neither separates proposal from constrained selection, and neither measures how far its objective is from submodular.
- Evidence that the gap exists. The iteration plateau reported by Yan et al. and the erosion documented in SlopCodeBench motivate replacing free-form rewriting with explicit, reversible selection.
Baselines
Do-nothing reference. We report the unassisted generator in a single pass with the same localization. For historical scale, SWE-bench reports Claude 2 at 1.96% resolved, and 4.8% with oracle file localization. These numbers come from a much weaker generation of models and serve only as a floor, not a competitor.
Strongest existing method. The strongest competitor in the file is BOOSTAPR. It uses execution-grounded reinforcement learning with a sequence-level and a line-level reward model. The file reports a 40.7% resolve rate on SWE-bench Verified, a 22.9-point gain over the Qwen2.5-Coder-32B base, and 24.8% on Defects4J v2.0.
It is the right competitor because it attacks the same credit-assignment and localization problem through learned rewards rather than combinatorial selection. To isolate our contribution, we use BOOSTAPR's own policy, or the same Qwen2.5-Coder-32B base if its weights are unavailable, as our generator. The comparison is then BOOSTAPR sampling versus BOOSTAPR proposals with constrained assembly, holding fixed:
- the model;
- the localization;
- the wall-clock budget;
- the number of test executions per instance.
Beating it means a statistically significant gain in resolve rate on SWE-bench Verified at matched execution budget. We expect the gain to concentrate on instances whose reference patch touches two or more files or hunks. We would not count a gain that appears only on single-hunk instances, since that would suggest extra compute rather than selection is doing the work.
Best-of-N with test filtering. The same generator samples full patches until the execution budget is exhausted, and the highest-scoring patch under the same visible-test objective is returned.
Conversational multi-turn repair with rollback. Errors are fed back for $T$ turns, and the code reverts on regression in the manner of Fang et al.. Again the execution budget is matched.
Ablations that isolate the key ingredients. Each removes one piece:
- greedy over raw hunks without bundling, which tests whether bundling is what matters;
- bundles assembled by the language model itself instead of by greedy, which tests whether the selection procedure matters;
- greedy without the partition matroid, allowing conflicting variants and relying only on the penalty;
- greedy without backtracking;
- random-order bundle addition under the same constraints.
Why not just…?
Why not just sample N full patches and keep the best one? This is the most serious threat. With a strong generator and enough samples, one full patch may already contain every coordinated edit. Our argument against it is specific. For a fix spanning $h$ locations, each sampled patch must get all $h$ right simultaneously. Assembly can instead reuse a correct edit at location 1 from one sample and a correct bundle at location 2 from another. So the advantage should grow with $h$. If best-of-N matches us at equal execution budget on the multi-hunk stratum, the proposal's thesis is wrong. We will report exactly that stratified comparison rather than an aggregate number.
Why not just keep iterating conversationally with rollback? Yan et al. find that compiler and execution feedback gains plateau after a few rounds and fall into repetitive edit cycles. SlopCodeBench documents structural erosion under repeated refinement. Rollback prevents regressions but does not recombine partial successes from earlier rounds. Our pool keeps every bundle ever proposed, so later rounds can combine earlier ones. The matched-budget comparison above tests whether this matters. We will also plot resolve rate against iteration count, to see whether our curve continues rising after the conversational curve flattens.
Why not just give the model dependency-graph context and let it write the coordinated patch, as POLO does? This is a fair alternative. It uses the same graph we use for bundling, but leaves selection to the model. The "language model assembles bundles" ablation is designed to be exactly this alternative. If it matches greedy assembly, then the value lies in dependency closure and the approximation-guarantee component should be dropped. We would report that outcome as the finding.
Why not just use a learned reward model instead of an execution objective with a measured guarantee? BOOSTAPR shows that learned line-level credit helps. However, a learned reward carries no statement about how close a selected set is to the best available combination. We use BOOSTAPR's attributions as proposal context and keep execution as the objective, so the two are complementary, not rival.
Proposed Experiments
Main evaluation. We run on SWE-bench Verified, stratified by the number of files and hunks in the reference patch. As a cross-language check we run on Defects4J v2.0, where BOOSTAPR reports 24.8% with Python-only training. The metrics are:
- resolve rate on hidden tests;
- previously passing tests broken;
- diff size;
- test executions consumed.
For a performance-optimization variant, we would use the POLO C/C++ repositories. There the objective is measured runtime reduction and the knapsack is lines changed. The file gives only POLO's 1.34x–21.5x speedup range, not a per-budget figure, so there is no matched reference number for that setting.
First decisive check: does bundling restore diminishing returns? On instances with at most about 12 candidate elements, exhaustive enumeration is feasible. On those instances we compute $\gamma$ and greedy's ratio to the enumerated optimum, for raw hunks versus bundles.
- If bundling raises median $\gamma$ substantially toward 1, the representational hypothesis holds.
- If $\gamma$ stays low, the guarantee is vacuous and the claim reduces to an empirical heuristic. We would state this explicitly.
Second decisive check: does the gain grow with fix size? The resolve-rate gain over matched-budget best-of-N should increase with the number of locations in the reference patch. A flat or negative trend falsifies the core claim.
Third check: do the model's own tests track the hidden ones? We report the correlation between visible-test objective scores and hidden-test outcomes. Assembly that overfits the model's own reproduction tests would appear here as high objective values with no gain in resolve rate.
References
- $A_2$DEPT: Large Language Model–Driven Automated Algorithm Design via Evolutionary Program Trees
- BOOSTAPR: Boosting Automated Program Repair via Execution-Grounded Reinforcement Learning with Dual Reward Models
- Maximizing the spread of influence through a social network
- POLO: An LLM-Powered Project-Level Code Performance Optimization Framework
- Advancing Code Coverage: Incorporating Program Analysis with Large Language Models
- Non-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic Settings
- A General Framework for Dynamic Consistent Submodular Maximization
- Deletion Robust Submodular Maximization over Matroids
- Equilibrium Computation and Robust Optimization in Zero Sum Games With Submodular Structure
- CodeTransOcean: A Comprehensive Multilingual Benchmark for Code Translation
- SlopCodeBench: Measuring Code Erosion Under Iterative Specification Refinement
- SWE-bench: Can Language Models Resolve Real-world Github Issues?
- MEIC: Re-thinking RTL Debug Automation using LLMs