When a language model writes code that fails its tests, a system can do three things. It can ask the model to repair the failing draft, sample a fresh attempt from scratch, or give up. Today that choice is made by hand-written rules: a fixed number of repair rounds, a fixed sampling budget, or "keep going until time runs out." Those rules are wrong in both directions. Easy problems pay for passes they do not need. Hard problems are abandoned too early or loop for dozens of rounds without progress. We propose to replace these hand-written stopping rules with a small learned estimator. It reads the current draft and its test feedback and predicts a distribution over how many more model calls it will take to reach passing code. A controller then uses a conservative quantile of that prediction to choose, at each step, between repairing, resampling, and stopping.
The idea borrows its central move from classical search. Planning systems stopped relying on hand-built heuristics once they could learn heuristics that estimate remaining cost and are deliberately biased so they rarely overshoot. We apply the same move to the budget problem in iterative refinement, where diminishing returns are well documented but stopping rules are still manual. In two sentences: learn how far a repair state is from success, as a distribution rather than a point. Then spend compute only where the optimistic end of that distribution still fits within the remaining budget.
Core Claim
The evidence that uniform refinement wastes compute is broad. Vision and parsing refiners saturate after one to three passes (DeFusionNET, Incremental Graph-based Neural Dependency Parsing). Skill-refinement loops plateau after two rounds and then over-correct (Write, Execute, Refine). Lean 4 proof repair in VERINA reaches roughly 20% success only with up to 64 feedback rounds, and it thrashes along the way.
The most direct warning comes from Demystifying GPT Self-Repair. It compares repair against independent resampling at an equal number of programs. Repair gains only about 5–8% on APPS for GPT-4 and loses to resampling for GPT-3.5 and Code Llama-13B, yet it becomes more valuable on the hardest competition problems. The implication is that no single fixed policy is right: the best action depends on the instance and on the state of its repair tree.
Our claim is that a cheap learned estimator of remaining calls-to-success, calibrated at a chosen quantile, can make this decision per state. It should beat both hand-tuned rules and uniform strategies on the pass-rate-versus-compute curve.
Concretely, let $s$ be a node in a repair tree, meaning a draft together with its test or compiler feedback and its repair history. Let $T(s)$ be the random number of further model calls needed to reach a passing program from $s$ under the repair policy. We train a head to output quantiles $q_\alpha(s)$ of $T(s)$, and a separate quantity $q_\alpha(\varnothing)$ for starting over from a fresh sample. With remaining budget $B$, the controller follows three rules:
$$ \text{expand } \arg\min_{s \in \mathcal{F} \cup \{\varnothing\}} q_\alpha(s), \qquad \text{stop if } \min_{s} q_\alpha(s) > B, $$
Here $\mathcal{F}$ is the set of open nodes in the tree, $\varnothing$ stands for a fresh independent sample, and $\alpha$ is a low quantile. The low quantile makes the estimate optimistic, so the controller abandons a problem only when even an optimistic guess does not fit the budget. This is the refinement-loop analogue of an admissible heuristic, one that never overestimates the remaining cost.
Relation to Prior Work
Several papers supply the method. Utilising Uncertainty for Efficient Learning of Likely-Admissible Heuristics learns heuristics from self-generated, suboptimal plans on sliding-tile and pancake puzzles. It separates model ignorance from data noise, uses the noise distribution's quantiles to trade suboptimality for safety, and reports 15-puzzle suboptimality falling from 10.75% to 2.46% at $\alpha=0.9$. We reuse two of its ideas: quantile-controlled estimates, and treating noisy self-generated targets as noise rather than truth. We apply them to a new object, a repair tree, where the "cost" is model calls.
The same paper also constrains our design. It had to drop Bayesian sampling during planning because it was too slow. For that reason we use a single-forward-pass quantile head, plus a small ensemble of heads used only when choosing which training problems to collect.
The older discovery work motivates the framing more than it supplies technique. ABSOLVER's transformational approach derives heuristics by abstraction, and Machine Discovery of Effective Admissible Heuristics shows that machine-found heuristics expand fewer states than human ones. Both show that automated heuristics can beat hand-made ones; we test whether the same holds for stopping rules.
The closest systems differ in what they decide.
SWE-Search runs Monte Carlo tree search over software patches. Its value agent gives a 0–100 quality score, and it uses hand-set depth bonuses and penalties. It achieves a 23% relative gain but raises GPT-4o benchmark cost from about \$41 to \$576. It has no calibrated cost-to-go and no principled abandonment rule. We predict remaining cost rather than quality, and we make stopping a first-class action.
From Search to Policy (TGPR) makes the opposite choice. It moves all search into training and decodes greedily at test time, running 12× faster than test-time search. It cannot spend more compute when the greedy answer fails. Our controller sits on top of such a policy and adds test-time search only where it is predicted to pay.
Meta-Reflection similarly compresses reflection into a single pass, cutting first-token latency on ECID from 951ms to 246ms. It shares the same fixed budget, and we treat it as a complement.
Teaching Language Models to Self-Improve trains models to critique and revise. It notes the added verbosity but never decides whether a critique is warranted, which is exactly the decision we learn.
Research Program
We first build repair-tree datasets in the style of Demystifying GPT Self-Repair, using an open code model (a 7B model, to match TGPR's scale) on APPS training problems. Each root spawns several independent samples, and each failing node spawns several repairs conditioned on test feedback, up to a generous depth. Every node is labeled with the observed number of further calls until any descendant passes, or with a censored label if none passes within the explored budget.
These labels are noisy, because they come from one realization of a stochastic tree. This is the "suboptimal self-generated targets" problem from the likely-admissible heuristics paper. We handle it with quantile regression and a censoring-aware loss, not by trusting the labels as exact.
The estimator is a small code encoder (around 1B parameters) with quantile heads. Its input is the draft, the compact test feedback (failing-test counts, error types, and the trajectory of failure counts across ancestors), and the depth. Epistemic disagreement across a few heads selects which problems to expand more deeply in later data-collection rounds. This is the analogue of the uncertainty-driven task generation in the likely-admissible heuristics paper, and it runs offline only. Inference cost is one encoder pass per new node, which is small next to a generation call, and we report this overhead explicitly.
We then study three questions. The first is calibration: do the predicted quantiles match observed calls-to-success on held-out problems and difficulty levels? The second is control: does the controller dominate fixed policies across the whole budget range? The third is transfer: does an estimator trained on APPS remain useful on LiveCodeBench, and, after light re-training on proof-repair trees, on VERINA's Lean 4 proof generation? VERINA is where long horizons matter and thrashing is documented.
Baselines
The naive reference point is one greedy sample with no repair. This is also what TGPR deploys, and it sets the floor for both quality and latency.
The strongest uniform competitor is independent resampling at equal budget, selecting whichever sample passes the tests. Demystifying GPT Self-Repair shows it matches or beats self-repair for weaker models, and GPT-4 self-repair beats it by only about 5–8% on APPS. We run it with the same generator, the same temperature sweep, and the same total count of generated tokens. Beating it means a higher pass rate at every matched token budget, with the gap concentrated on APPS interview and competition problems.
Second, we run fixed-cap repair with $N=1, 2, 3$ rounds and the best repair-versus-resample split chosen by grid search on a validation set. The grid search gives this baseline the same tuning data as our estimator.
Third, we implement a hand-engineered adaptive rule of the kind practitioners actually write. It resamples when the failing-test count does not drop after a repair, abandons after $k$ consecutive non-improving repairs, and has its thresholds tuned on the same validation split. This is the "manual heuristic engineering" baseline the proposal claims to replace. It is the most important comparison, because it captures most of the obvious signal for free.
Fourth, we run SWE-Search-style value-guided search, adapted to function-level tasks. It uses an LLM-prompted 0–100 score to pick nodes, with depth bonuses and penalties, and receives the same call budget. It isolates whether predicting remaining cost matters, as opposed to predicting quality.
Fifth, as the strongest amortized method, we train TGPR on the same base model if feasible. If not, we compare against its reported numbers: MBPP pass@1 of 77.6 and LiveCodeBench pass@1 of 41.2 for Qwen-7B in From Search to Policy. We also run our controller on top of the TGPR policy to test complementarity.
For VERINA we report against the paper's figures: o3 ProofGen pass@1 of 4.9%, and roughly 20% proof success with up to 64 feedback rounds, as stated in VERINA. We re-run our own generator with a 64-round unguided loop so that comparisons use the same model.
Three ablations isolate the key ingredients. The first replaces the learned encoder with logistic regression on the hand-crafted feedback features, testing whether reading draft content matters. The second replaces the quantile estimate with a point estimate of mean remaining calls, testing whether the conservative quantile matters. The third removes the resample action, testing whether the gain comes from correctly switching between depth and breadth.
Why not just…?
Why not just sample independently and never repair? For weaker models this is a real threat, and on easy problems it may be the right policy; Demystifying GPT Self-Repair found exactly that. Our controller includes a fresh sample as an explicit action, so a well-calibrated estimator should reduce to resampling wherever resampling is better. The same paper finds repair helps most on competition-level problems, so a per-state choice should win where the two strategies disagree. If our curve fails to beat resampling at any budget on the APPS competition split, the proposal fails.
Why not just cap repair at two rounds? Saturation after one to three rounds is well documented, for example in Write, Execute, Refine and DeFusionNET. Those plateaus are averages over instances, though. VERINA shows proof success roughly quadrupling from the single-pass rate only with long horizons, so a cap of two sacrifices those problems. The tuned fixed-cap baseline directly measures what an average-case cap gives up. We also report per-difficulty token spend to show whether the controller saves compute on easy problems while spending more on hard ones.
Why not just hand-write a smarter rule, such as "abandon when failing tests stop decreasing"? This is the alternative most likely to come close. Much of the signal may live in the failure-count trajectory. We therefore tune such a rule on the same validation data and include a learned-but-shallow version over the same features. If the full estimator's area under the pass-versus-tokens curve is within about one point of the tuned rule, we will conclude that learning buys little here. In that case we will report the tuned rule as the practical recommendation instead of arguing around the result.
Why not just amortize everything into the weights, as TGPR and Meta-Reflection do? Amortization removes test-time cost but also removes the option to spend more when the first answer is wrong. TGPR additionally reports more hallucinations from aggressive exploration. We do not compete with amortization; we layer on top of it. Running the controller on a TGPR-style policy tests whether adaptive test-time compute adds pass rate at a small average latency increase, since the controller stops immediately when the first sample passes.
Proposed Experiments
The primary benchmark is APPS, split by difficulty, using the equal-budget protocol of Demystifying GPT Self-Repair. HumanEval serves as an easy-regime check. LiveCodeBench (Oct 2024–Feb 2025) tests transfer without contamination. VERINA ProofGen, from the sunblaze-ucb/verina release, tests the long-horizon regime.
Metrics cover three things. Quality and cost are measured by pass rate as a function of generated tokens and of model calls, summarized as area under that curve. Latency is measured by the median and 95th-percentile wall-clock time per solved and per abandoned problem. Calibration is measured by quantile coverage of $T(s)$ on held-out trees and by the rate of wrongful abandonment, meaning problems the controller abandoned that a larger budget would have solved.
Three results would settle the question.
The first is the competition-level check. On APPS competition problems at matched token budgets, the controller must beat both independent resampling and the tuned hand-written rule. It must also save tokens relative to fixed-cap repair on introductory problems at equal pass rate.
The second is the long-horizon check. On VERINA, the controller should reach the success rate of our re-run 64-round unguided loop with substantially fewer rounds on average. Wrongful abandonment should stay near the rate implied by the chosen quantile, which is the practical meaning of "likely-admissible" in this setting.
The third is the ablation check. The quantile head should beat the point-estimate head specifically on wrongful abandonment. If it does not, the borrowed mechanism from classical heuristic learning is not doing the work we claim for it.
References
- DeFusionNET: Defocus Blur Detection via Recurrently Fusing and Refining Multi-Scale Deep Features
- Incremental Graph-based Neural Dependency Parsing
- Write, Execute, Refine: From Skill Followers to Skill Optimizers via Reinforcement Learning from Execution Feedback
- VERINA: Benchmarking Verifiable Code Generation
- Demystifying GPT Self-Repair for Code Generation
- Utilising Uncertainty for Efficient Learning of Likely-Admissible Heuristics
- Discovering Admissible Heuristics by Abstracting and Optimizing: A Transformational Approach
- Machine Discovery of Effective Admissible Heuristics
- SWE-Search: Enhancing Software Agents with Monte Carlo Tree Search and Iterative Refinement
- From Search to Policy: Thompson Sampling Trees for Robust LLM Code Refinement
- Meta-Reflection: A Feedback-Free Reflection Learning Framework
- Teaching Language Models to Self-Improve by Learning from Language Feedback