When a language model repairs its own code over several rounds, each round involves a choice: which candidate edit to keep working on, when to undo a change, and when to stop and ship. Today these choices are made against the visible unit tests. Visible tests are an imperfect judge. Code that passes them often fails the hidden edge-case tests, and weaker models produce more of this fragile code. One natural fix is Monte Carlo value estimation, which scores a partial state by sampling many completions from it and counting how often they succeed. The catch is that if "success" means "passes the visible tests," the rollouts inherit the judge's blind spots. They end up rewarding exactly the edits that lead to convincing wrong programs.
This proposal uses the rollouts twice. From each intermediate repair state we sample $K$ completed programs. We check them against the visible tests. We also run the passing programs against each other on freshly generated inputs that have no expected outputs. If the passing completions from a state all compute the same function, a visible-test pass from that state is probably genuine. If they pass the same tests but disagree with one another, at least some of them are false positives. This agreement signal discounts the Monte Carlo value. The discounted value then drives three decisions in the repair loop: which branch to expand, when to roll back, and when to stop under an explicit cost for shipping a bug. In two sentences: Monte Carlo rollouts from a repair state estimate how likely that state leads to passing code, and the behavioral agreement among the passing rollouts estimates how likely those passes are real. Multiplying the two gives a value that no longer climbs toward deceptive states, and it can be used to steer, undo, and stop a code-repair agent.
Core Claim
The claim is narrow and testable. In iterative code repair judged by incomplete tests, a Monte Carlo value computed against visible tests alone becomes biased toward states that produce deceptive passes as the search budget grows. Weighting each passing rollout by the size of its behavioral agreement cluster removes much of that bias. The payoff comes from using the correction inside the loop, not only for final selection.
Concretely, let $s$ be a repair state (the current program plus its execution history). Let $p_1,\dots,p_K$ be programs completed by $K$ stochastic rollouts from $s$, and let $A \subseteq \{1,\dots,K\}$ index those passing the visible tests. On a set $X$ of generated inputs, group the passing programs by identical output behavior. Let $c_i$ be the fraction of passing programs that share program $i$'s behavior. The value is
$$\hat V(s) = \frac{1}{K}\sum_{i \in A} c_i ,$$
which equals the ordinary Monte Carlo pass rate when all passing rollouts agree, and shrinks toward $|A|/K^2$ when every passing rollout computes a different function.
The acceptance rule follows the cost analysis of The Limits of Inference Scaling Through Resampling. That paper shows that when a shipped bug costs more than a correct solution earns, returns from resampling turn negative early. The agent ships a program only when its estimated probability of being genuinely correct exceeds $C_{fp}/(C_{fp}+B)$, where $C_{fp}$ is the cost of a false positive and $B$ the benefit of a correct solution. That threshold is the break-even point of expected utility. Otherwise it keeps repairing or abstains.
The assumption doing the work is that correct programs agree behaviorally while visible-test false positives scatter. This matches the observation reported alongside Better Process Supervision with Bi-directional Rewarding Signals that larger sampling pools produce an increasingly diverse set of deceptive wrong answers. The assumption fails when a model holds a single shared misconception. That case must be measured, not assumed away.
Relation to Prior Work
Two papers motivate the proposal by characterizing the verification ceiling for independent sampling. ROC-n-reroll shows that Best-of-$N$ (sample $N$ candidates, keep the top-scored one) and rejection sampling (sample until one passes) have accuracies fully determined by the verifier's ROC curve, and plateau at a level set by its slope at the origin. The Limits of Inference Scaling Through Resampling shows on HumanEval/MBPP versus their "+" versions that reliability tracks base capability. Both analyze post-hoc selection from finished samples only. We move the verifier-imperfection problem into a closed repair loop, where bad judgments compound across turns rather than being made once.
Three papers supply the Monte Carlo machinery and fix its blind spot. VinePPO replaces a learned critic with rollouts from intermediate steps and finds even one rollout beats a trained critic for math RL. BiRM trains a forward-looking value head on rollout success fractions. VerMCTS prunes Dafny/Coq search using intermediate checks from a sound verifier. All three treat the terminal check as correct: exact-match math answers or formal verifiers. We keep rollouts as the value estimator but stop trusting the terminal check, and estimate its failure from the rollouts themselves.
Three code-refinement systems constrain the design. SWE-Search runs tree search over repository edits with an LLM prompted to output 0–100 value scores. ReVeal trains an agent to write its own tests and refine for 25+ turns. TGPR uses Thompson-sampling trees during RL training with a CodeBLEU-plus-test-pass reward and discards search at inference. None estimates state value from executed rollouts, and none models the visible tests as fallible. ReVeal's self-written tests are the closest in spirit, but a model's tests can share its misconceptions. Our agreement check needs only inputs, not expected outputs, so it does not require the model to know the right answer. The rollback decision generalizes the heuristic revert-on-regression rule in MEIC. The tension between ReVeal's reported 0.0% degradation and SlopCodeBench's finding that 77% of agent trajectories erode structurally suggests that visible-test gains in long loops may partly be overfitting. We test this directly by tracking hidden-test false positives turn by turn.
Research Program
The system is a best-first search over repair states. Each state holds a program and its visible-test feedback. Expanding a state asks the policy model for several candidate edits given the traceback. Each child is scored with $\hat V$ using $K$ rollouts, each a short continuation of the repair loop ending in a completed program. The input set $X$ comes from a cheap input generator: type-directed random inputs plus LLM-proposed boundary inputs, validated only for not crashing the reference-free input parser. The agent expands the highest-$\hat V$ frontier state. It reverts to the parent when a child's $\hat V$ falls below the parent's by more than the estimator's standard error. It stops when the best state's estimated genuine-correctness probability crosses the cost threshold or the budget runs out. Rollouts that finish as agreed-upon passing programs are cached as candidate answers, so rollout compute also produces final solutions.
The study has three parts. First, we measure the bias of naive Monte Carlo values against hidden-test ground truth as $K$ and search depth grow, reproducing the Dorner-style ceiling inside a repair loop. Second, we compare in-loop use of $\hat V$ against using agreement only at final selection. Third, we fit a small value head on $\hat V$ targets, in the style of BiRM, to cut inference-time rollout cost. We report how much of the gain survives amortization, which speaks to the search-versus-distillation argument raised by TGPR.
Baselines
The naive reference point is single-sample generation followed by up to three rounds of vanilla self-debugging on the visible-test traceback. This is the regime where CodeTransOcean reports a gain from 48.57% to only 52.57% after three rounds on LLMTrans. Next is rejection sampling and Best-of-$N$ against visible tests at matched budget. For the HumanEval+ and MBPP+ hidden-test accuracy of these under our models, no reported result was found on Lacuna, so we measure them ourselves. We also report the utility-optimal $K$, which Stroebl et al. find is "often fewer than 10."
The strongest existing method is ReVeal: an agent that interleaves generation, self-written tests, sandbox execution, and refinement. ReVeal reports LiveCodeBench v6 Pass@1 rising from 34.8% at turn 1 to 38.7% at turn 25 on Qwen2.5-32B, and 33.6% Pass@1 on CodeContests. We run our search on top of the same Qwen2.5-32B base, matching generated tokens and sandbox executions. Beating it means higher hidden-test Pass@1 and a lower false-positive rate among accepted programs at equal compute on LCB v6 and CodeContests.
A second strong competitor is an SWE-Search-style prompted value agent substituted for $\hat V$ inside our identical search loop. This isolates whether executed rollouts beat an LLM's guess of value. For the TGPR-trained 7B policy (41.2 on LiveCodeBench Oct 2024–Feb 2025 under greedy decoding), we report a greedy-decoding reference and the same model wrapped in our search.
Two ablations isolate the key ingredient. Naive Monte Carlo sets $c_i = 1$, so the only difference is the agreement discount. Terminal-only agreement runs naive Monte Carlo search and then applies behavioral clustering to the final candidate pool. All methods get the same token and execution budget, with hyperparameters tuned on a held-out split of MBPP.
Why not just…?
Why not just cluster final candidates by behavior and pick the largest cluster? This is the most serious threat. Output-agreement voting over a finished pool may capture most of the gain with no search at all. The terminal-only-agreement ablation tests it directly. The proposal is only worth pursuing if in-loop use produces a clear margin at equal compute, especially on CodeContests and LCB hard problems, where the right branch may never be reached without guidance. If the margin is within noise, the honest conclusion is that agreement is a selection tool and not a value function, and the paper reports that.
Why not just let the model write more tests, as ReVeal does? Generated tests with expected outputs require the model to know the correct answer, so a shared misconception passes both code and test. ReVeal itself lists this as the failure mode of its inference-time verification. Our check needs inputs only. We will quantify the difference by measuring, on the HumanEval/HumanEval+ gap, the false-positive rate among programs accepted by self-written tests versus by agreement.
Why not just train a critic or process reward model instead of running rollouts? VinePPO finds learned critics rank intermediate states poorly and that even single rollouts beat them. Know What You Don't Know finds process reward models overestimate success. Both results are from math, though, and code may differ. The prompted-value baseline and our distilled value head give the answer for code. If the distilled head matches full rollouts, that is a win for cheap deployment, not a refutation.
Why not just stop resampling early, as the cost analysis recommends? Stopping early caps losses but cannot raise the ceiling. The Stroebl et al. finding that no resampling budget lets Llama 3.1 8B match single-call GPT-4o shows that the verifier's blind spot, not the budget, is the binding constraint. We report cost-weighted utility curves for both approaches across $C_{fp}/B$ ratios.
Proposed Experiments and Decisive Checks
Following Stroebl et al., the main testbed is a two-tier setup: visible tests from HumanEval and MBPP drive the agent, and HumanEval+ and MBPP+ judge it. A matching split of public versus hidden tests is used on LiveCodeBench v6 and CodeContests. Models are Llama-3.1-8B, Qwen2.5-7B, and Qwen2.5-32B, which let us check whether the gain grows for weaker models, as the capability-reliability correlation predicts. The metrics are hidden-test Pass@1, false-positive rate among accepted programs, cost-weighted utility across several $C_{fp}/B$ ratios, and abstention rate. Compute is reported in tokens and executions. A secondary pass on SlopCodeBench tracks verbosity and erosion, to see whether agreement-guided search thrashes less.
The first decisive check is on the assumption itself. On pooled rollouts, we plot agreement-cluster share against hidden-test correctness for programs that pass visible tests. If agreement does not separate genuine from deceptive passes, with an area under the curve near chance, the method has no basis. The fraction of false positives lying in the largest cluster directly measures the shared-misconception failure rate.
The second check is bias: naive $\hat V$ should correlate increasingly poorly with hidden-test value as $K$ grows, while the discounted $\hat V$ should not.
The third check is the in-loop versus terminal-only ablation at matched compute.
The fourth check is scaling. Under naive Monte Carlo guidance, hidden-test accuracy should bend down as the budget grows. Under discounted guidance it should keep rising or flatten. That difference is the result the proposal lives or dies on.
References
- The Limits of Inference Scaling Through Resampling
- Better Process Supervision with Bi-directional Rewarding Signals
- ROC-n-reroll: How verifier imperfection affects test-time scaling
- VinePPO: Refining Credit Assignment in RL Training of LLMs
- VerMCTS: Synthesizing Multi-Step Programs using a Verifier, a Large Language Model, and Tree Search
- SWE-Search: Enhancing Software Agents with Monte Carlo Tree Search and Iterative Refinement
- ReVeal: Self-Evolving Code Agents via Reliable Self-Verification
- From Search to Policy: Thompson Sampling Trees for Robust LLM Code Refinement
- MEIC: Re-thinking RTL Debug Automation using LLMs
- SlopCodeBench: Measuring Code Erosion Under Iterative Specification Refinement
- CodeTransOcean: A Comprehensive Multilingual Benchmark for Code Translation
- Know What You Don't Know: Uncertainty Calibration of Process Reward Models
- LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code