Refine or Resample? Calibrated Expansion Control for Program-Refinement Search

When a language model writes a program that fails, a system has two cheap options. It can refine: show the model the error or test result and ask for a fix. Or it can resample: throw the attempt away and draw a fresh one. Much current tooling assumes refining is the smarter move. The evidence is mixed. Independent samples filtered by a sound checker often beat feedback loops outright, and feedback gains tend to stall after a few rounds. Yet on heavily constrained algorithm-design problems, long chains of refinement reach solutions that fresh sampling essentially never finds. Neither fixed policy is right, and no system in the literature decides which to use at each step.

We propose treating every attempt as a node in a search tree and learning a calibrated predictor of one quantity: the probability that expanding this node by refining (or by resampling instead) will produce a program better than the best one found so far. Calibrated means that when the predictor says 20%, roughly one in five such expansions actually improves. A controller spends a fixed budget of model calls and executions on the expansions with the highest predicted gain per unit cost. It prunes refinement lines whose calibrated upper bound falls below a threshold, in the spirit of branch-and-bound. The pruning threshold is set with conformal risk control (a distribution-free procedure that picks a cutoff from held-out data so that an error rate stays below a chosen level). This lets us bound how often we abandon a line that would have paid off. The claim is that this per-node, calibrated choice beats pure resampling, pure refinement, and any fixed mixture of the two at equal compute. It should also tell us where refinement helps, which is the empirical question behind the self-correction debate.

Core Claim

The self-correction literature is usually read as a verdict: either feedback loops work or they don't. We read it as a prediction problem. On the self-verification limitations of large language models on reasoning and planning tasks studies GPT-4 on formal puzzles and planning tasks. It shows that GPT-4 critiquing its own outputs collapses performance, from 16% to 2% on Graph Coloring. It also shows that 25 independent samples checked by a sound verifier reach 44% on the same task. Yan et al. report that compiler and interpreter feedback plateaus and then causes circular repairs and regressions. Pulling the other way, A2DEPT evolves whole combinatorial solvers through deep program trees. It reaches a 0.00% gap on a high-constraint vehicle routing variant (CEVRPTW), where shallow search fails. These results motivate the proposal: the value of refinement varies sharply across tasks and across nodes within one task.

Our hypothesis is that this variation is predictable from cheap signals available at the node. These include the execution feedback type (crash, wrong answer, partial pass, gap on trial instances), the node's improvement history, its depth, and the model's internal state while it reads the program and feedback. If the hypothesis holds, a calibrated predictor should turn a fixed budget into more solved problems or lower optimality gaps than any static policy. Throughout, the verifier stays an external, sound executor. The model is never asked to judge correctness. It is only used to predict whether spending another call on a node is worthwhile.

Research Program

Formalizing the search. We treat search as a tree over programs. The root expansion and any "resample" action draw a fresh program. A "refine" action conditions on a node's program plus its execution feedback. For a node $n$ and action $a \in \{\text{refine}, \text{resample}\}$, let $q(n,a)$ be the probability that one expansion yields a program whose verified score beats the current incumbent, and let $c(a)$ be the expected cost of the action in model tokens plus execution time. The controller repeatedly takes

$$ (n^\*, a^\*) = \arg\max_{n,a} \frac{\hat q(n,a)}{c(a)}, $$

where $\hat q$ is the learned, calibrated estimate. It also removes node $n$ from further refinement when $\hat q(n,\text{refine}) < \lambda$. The threshold $\lambda$ is chosen by conformal risk control on held-out search trees so that the fraction of pruned nodes that would have produced an improvement stays at most a user-set $\alpha$. This guarantee holds when calibration and test trees are exchangeable. We will measure directly how far it degrades under task shift.

Collecting training data. We run deliberately wide, logged searches on training splits. At sampled nodes we perform several refinements and resamples and record which of them improved. Each record pairs node features with improvement outcomes. This gives unbiased labels for $q(n,a)$ rather than labels confounded by a fixed policy.

Building the predictor. We build the predictor in two tiers so that the contribution does not hinge on one feature source. Tier one is a small model, such as logistic regression or gradient-boosted trees, on execution features and search history. Tier two adds a probe on the model's hidden states. The probe follows Uncertainty Calibration for Tool-Using Language Agents, which trains small multi-layer classifiers on hidden activations from 500 calibration examples. On TabMWP it reduces expected calibration error (the average gap between stated confidence and actual accuracy) from 0.690 to 0.035. That work predicts success of a single tool call. We repurpose the technique to predict the marginal value of the next expansion in a multi-step tree, which is a different target. Both tiers are recalibrated with isotonic regression before the conformal step.

Domains. Three domains share the same controller. The first is function-level code with unit-test feedback. The second is formal puzzles and planning with sound verifiers, where the self-verification study supplies reference numbers. The third is LLM-driven solver design on FrontierCO problems, where the score is the optimality gap on trial instances, as in A2DEPT. Open-weights models are required for the hidden-state probe. We use Qwen2.5-Coder-7B and Llama-3-8B, both families used in the cited work. Full-tree experiments in the solver-design domain build on the released PathWise codebase.

Relation to Prior Work

The closest prior work is When Uncertainty Isn't Enough. It tests five uncertainty measures on 1.3B–3B code models and finds that triggering self-correction on uncertainty hurts accuracy in 5 of 6 settings, by nearly 10 points of Pass@1 for Llama-3.2-3B on HumanEval. Only execution-based regeneration reliably helps: DeepSeek-Coder-1.3B on HumanEval goes from 0.61 to 0.87. This paper constrains our design. It is why the verifier is always sound, and why we never use uncertainty to decide whether code is correct. Our predictor targets a different quantity: whether the next unit of compute should go to this node, by refinement or by resampling.

PREGU halts generation on token-entropy spikes and searches in embedding space. It uses an uncalibrated fixed threshold at the token level, whereas we make calibrated decisions at the program level.

TGPR uses Thompson-sampling refinement trees at training time to produce a fast policy. It reports more confident hallucination errors at test time. We stay at test time and make the search budget adaptive.

PathWise and A2DEPT supply the search substrates. Both expand nodes using empirical scores, LLM critiques, or annealing schedules, with no calibrated estimate of expansion value. The rollback agents of Fang et al. undo regressions after they are executed. We aim to avoid spending on them in the first place.

From neural-guided symbolic search, the closest analogue is learned branching and pruning inside exact solvers, such as Learning from Algorithm Feedback and Learning Admissible Heuristics for A*. The second shows that pruning is only safe when a learned estimate comes with a guarantee. Our conformal threshold is the probabilistic counterpart of admissibility for a search whose node values are stochastic.

Baselines

Pure refinement and greedy decoding. The naive reference points are a single greedy sample and pure feedback-driven refinement from one initial sample at the same budget. The second shows directly whether feedback loops plateau or regress in each domain, as Yan et al. report.

Pure independent resampling with a sound verifier. This is the strongest simple competitor, because the self-verification study shows it dominating critique loops. With GPT-4 and $k=25$, On the self-verification limitations of large language models on reasoning and planning tasks reports 42% on Game of 24, 44% on Graph Coloring, 72% on Blocksworld, and 14% on Mystery Blocksworld. On HumanEval, When Uncertainty Isn't Enough reports verification-based regeneration moving DeepSeek-Coder-1.3B from 0.61 to 0.87. We rerun this baseline with our own models at identical token and execution budgets. We beat it only if we solve more problems at the same budget, or reach its success rate with fewer calls, at a margin outside seed-to-seed variance.

The best fixed refine/resample mixture. We tune the global refine fraction and the maximum refinement depth on the same development data the controller is trained on, with the same tuning budget. If per-node control cannot beat a well-tuned constant, the proposal fails. This is therefore the decisive ablation of the key ingredient.

Score-driven tree search without learned prediction. This baseline covers Thompson-sampling or upper-confidence-bound node selection over observed verified scores, as in TGPR's refinement trees, and the evolutionary loops of A2DEPT and PathWise. A2DEPT reports a 9.8% reduction in mean normalized optimality gap relative to ReEvo and MCTS-AHD on FrontierCO. Any controller placed inside the A2DEPT/PathWise loop must keep that advantage and reduce evaluations spent on broken or regressive mutations. No reported result was found on Lacuna for REx's absolute scores, so REx-style search is rerun rather than quoted.

Uncalibrated and self-reported versions of our own controller. The same features without recalibration test whether calibration matters. A variant in which the model verbally states whether further refinement will help tests whether introspection can stand in for a trained estimator. All methods share models, prompts, verifiers, and wall-clock budgets.

Why not just…?

Why not just resample with a verifier and skip refinement entirely? In domains where valid programs have reasonable support in the base distribution, this may be nearly optimal. The Graph Coloring and Game of 24 numbers suggest that. In those domains a good controller should learn to resample almost always, and we count matching resampling there as success, not failure. The threat is real only if resampling also wins in the high-constraint solver-design domain. A2DEPT's CEVRPTW result and FrontierCO's hard-set gaps argue that shallow search is not enough there. Equal-budget curves across the three domains settle the question.

Why not just tune a global refine-to-resample ratio? This is the most serious alternative. If the value of refinement varies mainly between tasks rather than between nodes, a tuned constant captures most of the gain. We test it head-on. We measure how much of the variance in observed improvement is explained by node-level features beyond task identity, and we report the controller's margin over the tuned constant. If that margin vanishes, we will report the per-task ratio map as the result instead of the controller.

Why not just use token entropy or ask the model how confident it is? When Uncertainty Isn't Enough finds that both correlate weakly with correctness and harm accuracy when used to trigger repairs. PROBECAL shows raw output-based confidence badly miscalibrated. We still include both as baselines, because our prediction target differs from theirs and could behave differently.

Why not skip hidden-state probes and use execution features alone? This alternative may work, so the program is designed not to depend on probes. The two-tier comparison reports whether probes add anything beyond feedback type, score trajectory, and depth. If they do not, the cheaper model is the recommendation.

Proposed Experiments

The primary metric is the anytime performance curve: solve rate, or best optimality gap, as a function of cumulative model tokens and executions, summarized by the area under that curve. We also measure the calibration error of $\hat q$ on held-out trees and the realized rate of pruned nodes that would have improved, against the target $\alpha$.

Code experiments use HumanEval, MBPP, and LiveCodeBench. LiveCodeBench matters because TGPR reports 41.2 for its amortized Qwen-7B policy, a reference point for how much test-time control adds on top of a strong single pass. Puzzle and planning experiments use Game of 24, Graph Coloring, Blocksworld, and Mystery Blocksworld via PlanBench. Solver-design experiments use the FrontierCO problems (MIS, CVRP, CFLP, FJSP) as configured by A2DEPT.

Three checks are decisive.

The first is the margin over the tuned fixed mixture at equal budget, in each domain.

The second is a cross-domain transfer test. The predictor is trained on code trees and applied to solver-design trees, with and without a 500-example recalibration set, following PROBECAL's sample size. FrontierCO documents how sharply neural guidance degrades under distribution shift: on TSP, the LEHD solver's gap rises from 0.72% on standard instances to 77% on the hard set. We expect the conformal guarantee to break without recalibration, and we will report by how much.

The third is a diagnostic map of where the controller chooses refinement. The prediction is that it rarely refines on obfuscated planning, where the self-verification study shows feedback is least useful. We expect it to refine deeply on high-constraint solver design and on partial-pass code failures. If the learned choices instead look uniform across these regimes, the hypothesis that refinement value is predictable at the node level is wrong.