Language models that write code can often fix their own mistakes if they are allowed to revise a draft several times, especially when they see compiler or test feedback. Each revision, however, is another sequential pass through the model, so this loop multiplies response time. The two current answers are opposite extremes. One bakes the search into the weights during training and then generates once at test time, giving up test-time correction. The other runs search on every query and pays its full latency even on easy problems. This note proposes a middle path built on variational expectation-maximization (EM): an algorithm that alternates between estimating a hidden quantity, here "what a good program for this prompt looks like," and updating the model to match that estimate. It treats revision as a test-time E-step, the estimation half of EM, applied to a hard posterior. It also trains the model to predict, for each prompt and draft, how far its own output distribution still sits from that posterior. Revision runs only when this predicted gap is worth its cost.
The quantity driving the decision is not a heuristic. Define a target distribution that reweights the model's programs by a tempered reward. The Kullback–Leibler (KL) divergence from the model to this target then has a closed form: it is the log of the average exponentiated reward minus the average reward. That is exactly the expected payoff of searching over the model's samples instead of taking one. The quantity can be measured during training from the same importance-weighted samples the E-step already draws, and a small head can learn to predict it at test time without a verifier. The result is a single training loop that does two things. It distills search into the drafter, as in prior amortization work, and it teaches the system where distillation has not yet succeeded, which is where test-time refinement is still worth its latency.
Core Claim
Let $x$ be a prompt, $z$ a program, $p_\theta(z\mid x)$ the drafting model, $r(x,z)$ a training-time reward (test pass rate, optionally shaped), and $\beta$ a temperature. The variational E-step targets the tilted posterior $p^*(z\mid x) \propto p_\theta(z\mid x)\exp(r(x,z)/\beta)$. The per-prompt variational gap is then
$$G(x) = \mathrm{D_{KL}}\big(p_\theta(\cdot\mid x)\,\|\,p^*(\cdot\mid x)\big) = \log \mathbb{E}_{p_\theta}\big[e^{r/\beta}\big] - \mathbb{E}_{p_\theta}\big[r/\beta\big] \;\ge 0,$$
which is non-negative by Jensen's inequality. It is zero exactly when the drafter's samples all receive the same reward, so search can gain nothing. The same expression applies after $k$ revisions, with $p_\theta$ replaced by the distribution of revised programs given the current draft and its feedback, written $G_k(x, z_k)$.
The claim has three parts. First, an amortized predictor $\hat G_k$ can be trained from self-normalized importance-sampling estimates of $G_k$ that the E-step produces at no extra cost. Second, the rule "revise while $\hat G_k > \lambda c$" yields a better accuracy–latency frontier than fixed budgets, confidence-based stopping, or parallel sampling at matched compute. Here $c$ is the wall-clock cost of one revision and $\lambda$ is a price on latency. Third, across EM rounds the M-step distills E-step results into the drafter, so the measured gap shrinks on prompts that have been learned. The fraction of queries routed to refinement should therefore fall while accuracy holds. That third prediction is what separates this proposal from both full amortization and always-on search.
Relation to Prior Work
The method is taken most directly from Diffusion Alignment as Variational Expectation-Maximization. That paper runs a reward-guided search over diffusion trajectories in the E-step and fits the model to the discovered trajectories with a mode-covering forward-KL M-step, so inference needs no search at all. We reuse its E/M split and forward-KL distillation, with three differences. We move it to autoregressive code repair with execution feedback, a setting that paper leaves open. We keep a test-time E-step instead of discarding it. And we use the KL gap that paper implicitly reduces as an explicit routing signal.
Bridge the Inference Gaps of Neural Processes via Expectation Maximization supplies the self-normalized importance-sampling E-step with a monotone-improvement argument. It also supplies a constraint: with too few samples, the latent distribution collapses to a deterministic one. We take that as a warning that a gap estimate built from very few samples will be biased toward zero. The sample count is therefore an explicit ablation.
Two papers motivate the tension we exploit. From Search to Policy: Thompson Sampling Trees for Robust LLM Code Refinement (TGPR) runs tree search only during reinforcement-learning training and reports that the resulting single-shot policy is about 12x faster than test-time search. It also concedes that a single-pass policy cannot react to failing edge cases. Let's Revise Step-by-Step (ReLoc) shows the opposite side. Local search guided by a predicted revision distance raises LiveCodeBench Pass@1 from 33.8% to 38.4% and uses 37% fewer tokens than tree search, but its latency still grows with every search step on every query.
Stopping work constrains the design. TERMINATOR trains a probe to detect when the correct answer first appears in a chain of thought. It cuts reasoning length by 14–55% and roughly halves latency, and it shows that naive confidence signals misfire because confidence dips after the answer appears. Latent Refinement Decoding stops refinement when the KL between consecutive predictions falls below a threshold. Both stopping signals measure whether the output has settled. Ours measures whether more search would pay. These differ when a model confidently settles on a wrong program.
Extrapolative Controlled Sequence Generation via Iterative Refinement and RepoCoder both name stopping without a ground-truth verifier as unresolved. Our predictor is trained with rewards but deployed without them, which is a direct attempt at that problem.
Research Program
The system has three parts that share one backbone, Qwen-7B, chosen so that TGPR's published configuration is a natural reference. The first part is the drafter $p_\theta(z\mid x)$. The second is a reviser that conditions on the prompt, the current draft, and execution feedback from the prompt's visible tests and proposes a new program. The third is a gap head: a small regression head on the final hidden state that, given the prompt and current draft, outputs $\hat G_k$.
At deployment, only visible tests are used as feedback. Hidden tests are never seen, and the gap head makes the stopping decision.
Each training round runs four stages.
E-step. For each training prompt, sample $N$ drafts and up to $K$ revision chains. Score every program with the training reward, using the pass rate on hidden training tests, and form self-normalized importance weights $w \propto \exp(r/\beta)$.
Gap targets. These weights give plug-in estimates of $G_0(x)$ and of $G_k$ at each revision depth, computed as log-mean-exp minus mean of $r/\beta$.
M-step. Fit the drafter by weighted maximum likelihood on the E-step programs. Fit the reviser by weighted maximum likelihood on revision transitions that increased reward. Fit the gap head by regression onto the estimated gaps. A KL penalty to the previous round's drafter, following the regularized variant in the diffusion-alignment work, limits drift.
Re-estimation. Rounds repeat. Gap targets are recomputed after each M-step because distillation changes them.
Because the plug-in log-mean-exp estimate is biased downward for small $N$, we report results at $N \in \{4, 8, 16\}$ and test whether a bias-corrected estimator changes routing decisions.
The temperature $\beta$ sets what "gap" means. A small $\beta$ approaches "best-of-search minus average," and a large $\beta$ approaches reward variance. We sweep $\beta$ and select it on a held-out split.
The latency price $\lambda$ is swept at test time to trace a full accuracy–latency curve. Latency is measured three ways: wall-clock time on fixed hardware, the number of sequential model passes, and total tokens.
Baselines
The naive reference point is the base drafter decoding greedily once, with no revision. It anchors the lowest-latency end of the curve.
The strongest amortization competitor is TGPR, which trains with Thompson-sampling tree search on top of GRPO and decodes once at test time. Its paper reports zero-shot greedy LiveCodeBench 41.2 and MBPP 77.6 for TGPR-enhanced Qwen-7B. Its LiveCodeBench split is Oct 2024–Feb 2025, so we evaluate on that same window. We reimplement it with the same backbone, the same training prompts, and the same total training compute as our E-step plus M-step. Our 41.2 reproduction target is therefore an in-house number, not a borrowed one. Beating it means higher Pass@1 at matched mean latency, or equal Pass@1 with a curve that keeps rising as $\lambda$ falls, which TGPR's single-shot policy cannot do.
The strongest test-time search competitor is ReLoc hill climbing with a revision-distance reward model. It is reported at 38.4% LiveCodeBench Pass@1, up from 33.8%. The file does not state the base model behind those figures, so we rerun ReLoc on our backbone with its search budget matched to our maximum $K$. Beating it means matching its Pass@1 at substantially lower mean latency.
Two compute-matched references come next. Best-of-$N$ uses parallel sampling with selection by visible tests. Fixed-budget refinement always runs $k$ revisions, for $k \in \{1, 2, 3\}$. Both use the same drafter and reviser as our method, so only the routing differs.
Stopping-rule competitors swap our gap head for other signals on the same trained drafter and reviser. One is a token-entropy threshold. One is LRD-style consecutive-draft divergence. One is a TERMINATOR-style hidden-state probe trained to predict whether the current draft already passes.
The key ablation keeps our full EM training but trains the gate on a binary target: did one more revision raise the pass rate. This isolates whether the variational gap adds anything over a direct "will revision help" classifier. A second ablation removes the M-step, so the drafter is frozen and only the gap head and reviser are trained. This tests whether the shrinking-gap dynamic matters.
Why not just…?
Why not just sample $N$ programs in parallel and pick one? Parallel sampling avoids sequential latency, and on GPUs with spare batch capacity it is a real threat at low latency budgets. The corpus does report evidence against it in neighboring settings. Critique-RL finds a critique-and-refine cycle up to 5x more compute-efficient than majority voting on math. ReLoc reports that best-of-$N$ scales more flatly than local search on competitive programming. On LiveCodeBench, GPT-4-Turbo self-repair with feedback rose from 24.5% to 36.9% (LiveCodeBench). Still, none of these matched wall-clock time with batching. We will, and if best-of-$N$ dominates at equal wall-clock time, we report it.
Why not just cap refinement at a fixed number of turns or stop on low entropy? Fixed caps spend the same effort on easy and hard prompts. TERMINATOR documents that confidence-based rules either stop too early or overthink, partly because confidence drops after the correct answer appears. Our stopping-rule comparison on a shared drafter and reviser tests this directly.
Why not just amortize everything with reinforcement learning, as TGPR does? If full amortization closes the gap on nearly all test prompts, routing is pointless. TGPR's own admission that single-pass outputs cannot respond to failing edge cases, together with ReLoc's gains from test-time search, suggests a residual set of prompts where search still pays. The round-by-round routing fraction measures how large that set is. If it shrinks to near zero, the honest conclusion is that amortization suffices.
Why not just train a classifier for "will another revision help"? This is the most serious alternative, because it uses the same data and is simpler. Our hypothesis is that the soft gap carries two signals a binary label merges: how much headroom a prompt has, and how spread out the model's samples are. The gap should therefore rank prompts better when revisions give partial credit. The binary-gate ablation settles this. If the binary gate matches the variational gap, we will credit the gains to EM training and distillation, not to the gate.
Decisive Experiments
The primary benchmarks are three. The first is LiveCodeBench code generation with visible-test feedback, on the post-cutoff window TGPR used, so contamination is controlled. The second is its self-repair scenario. The third is MBPP and HumanEval for comparability with TGPR, Meta-Reflection, and LRD. A secondary transfer study runs on MATH-500, where a learned verifier replaces tests during training only, to check whether the gap head survives a noisier reward.
The headline metric is the area under the Pass@1-versus-mean-wall-clock curve. We also report latency at matched accuracy against TGPR and ReLoc.
Three checks decide the proposal.
Ranking check. On held-out prompts, does $\hat G_k$ rank realized revision gains (Spearman correlation) better than entropy, consecutive-draft divergence, the pass probe, and the binary gate? If not, the core claim fails.
Frontier check. Does gap routing dominate fixed-budget refinement and wall-clock-matched best-of-$N$ across the $\lambda$ sweep, while beating the TGPR reproduction at latency budgets above one pass?
Amortization check. Across EM rounds, does the routed fraction fall while Pass@1 is stable or rising? And does removing the M-step erase that trend?
A failure on the third check, with success on the first two, would still leave a useful stopping rule. It would show, however, that the EM coupling is not what drives the result, and the paper would say so.
References
- Diffusion Alignment as Variational Expectation-Maximization
- Bridge the Inference Gaps of Neural Processes via Expectation Maximization
- From Search to Policy: Thompson Sampling Trees for Robust LLM Code Refinement
- Let's Revise Step-by-Step: A Unified Local Search Framework for Code Generation with LLMs
- TERMINATOR: Learning Optimal Exit Points for Early Stopping in Chain-of-Thought Reasoning
- Latent Refinement Decoding: Enhancing Diffusion-Based Language Models by Refining Belief States
- Extrapolative Controlled Sequence Generation via Iterative Refinement
- RepoCoder: Repository-Level Code Completion Through Iterative Retrieval and Generation
- Critique-RL: Training Language Models For Critiquing Through Two-Stage Reinforcement Learning
- LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code