Many language-model systems now improve answers by revising them. The model writes a draft, critiques it, and rewrites it, sometimes several times. Each round adds latency, so deployed systems cut the loop short whenever a deadline arrives, and the number of rounds varies from one request to the next. Training procedures do not reflect this. Models are trained on single revision steps, on full revision chains, or on reinforcement-learning rollouts with one fixed number of rounds. None of these teaches the model that any round might be the last. Probabilistic inference studied the same problem decades ago. Parameters fitted for exact inference break when an approximate, truncated inference routine runs at test time, and the fix was to train through the truncated routine itself. That literature also left open a question that matters for latency: a model trained to be good after exactly $N$ steps is not guaranteed to be good after $N' \neq N$ steps.
This note proposes to treat the refinement loop as a truncated inference procedure whose stopping point is random. The model is trained on a single objective that scores the answer at every round, weighted by how likely the deployment is to stop there, plus a penalty on rounds that make a correct answer wrong. If this works, one model would trace an anytime curve, meaning that whenever the loop is stopped, the answer in hand is about as good as a model trained for exactly that budget could produce. Extra rounds would stop causing the over-correction that iterative editing is known for. The test is simple. Train fixed-budget models and the budget-randomized model with equal compute, then compare accuracy at every stopping point.
Core Claim
Let $x_0$ be the first draft and $x_k$ the answer after $k$ refinement rounds. Let $r(\cdot)$ be a task reward, such as answer correctness or unit-test pass. Let $K$ be the random round at which deployment stops, drawn from a budget distribution $p(K)$ over $\{0,\dots,K_{\max}\}$. We train the refinement policy to maximize
$$ J = \sum_{k=0}^{K_{\max}} P(K=k)\, \mathbb{E}[r(x_k)] \;-\; \lambda \sum_{k=1}^{K_{\max}} P(K\ge k)\, \mathbb{E}\big[\max(0,\, r(x_{k-1}) - r(x_k))\big], $$
where $\lambda \ge 0$ sets the price of a regression, meaning a round that lowers reward.
The first term is the expected reward at a random stopping time. It turns into a per-round reward, weighted by the deployment's stopping distribution. The second term penalizes harmful revisions in proportion to how often deployment actually reaches that round.
Fixed-budget training is the special case where $p(K)$ is a point mass at $K = N$. This is the setup in Domke-style truncated fitting and in operator-consistent rollouts. Our claim is therefore empirical and falsifiable. Point-mass training leaves accuracy on the table at $K' \neq N$, and the loss is worst when $K' > N$, which is where over-correction appears. A model trained under a spread $p(K)$ should match each point-mass model at that model's own budget, within noise, and beat it everywhere else.
Relation to Prior Work
Prior work plays three roles here: it motivates the problem, it supplies the methods, and it limits what we can expect.
The motivating evidence comes from classical approximate inference. Learning as search optimization showed that structured predictors trained as if search were exact fail when approximate search runs at test time. Structured Learning with Approximate Inference. showed that plugging an approximate routine into training as a black box can make learning diverge, even when the approximation has good theoretical bounds. In the refinement setting, Extrapolative Controlled Sequence Generation via Iterative Refinement and RepoCoder report drift and over-correction under repeated editing, and both call for better stopping rules.
The method comes from truncated fitting. Learning Graphical Model Parameters with Approximate Marginal Inference backpropagates through a fixed 5 or 10 steps of approximate message passing. Query Training unrolls loopy belief propagation with weights shared across steps and trains on marginal queries. Both fix the number of steps $N$ in advance. Neither asks what happens when the deployed number of steps differs from the trained one. Our contribution is to make $N$ a random variable during training.
The closest work in language models is Rethinking Thinking Tokens. Its Parallel-Distill-Refine method trains with "operator-consistent" rollouts that mimic the test-time loop, and it cuts sequential token cost. Those rollouts follow one fixed loop structure, so they correspond to point-mass training. We make the training loop's length random and reward each round, and we do not change their workspace design. Evolving LLMs' Self-Refinement Capability (EVOLVE) trains models to revise their own outputs. However, it trains on revision transitions and preferences, not on what the answer is worth at the point where the loop is cut off.
The two critic-training papers, Critique-RL and Training Language Model to Critique for Better Refinement (RCO), are complementary. They train the critic while the actor stays fixed. We train the reviser's behavior across rounds, and an RCO- or Critique-RL-trained critic can be dropped in.
Two results limit what we should expect. Query Training reports that fitting a model to its inference procedure yields a "worse" generative model in the likelihood sense. We should therefore expect some loss of single-pass or round-0 quality as the price of a better curve, and we will measure it rather than assume it away. Kulesza and Pereira's expressivity result implies that no training objective rescues an operator that cannot represent the fix. For that reason we expect gains on budget robustness and regression rate, not on peak accuracy at large budgets.
Meta-Reflection takes the opposite route and collapses reflection into one forward pass. It is a baseline here, not a component.
Research Program
The work has three stages.
Stage 1: confirm the mismatch in a clean setting. We start where the failure can be measured exactly. On grid Markov random fields, which are graphical models where each pixel's label depends on its neighbors, we train with mean-field inference unrolled to a fixed $N$, following Domke. We then evaluate at $N'$ from 1 to 20 and compare against training with $N$ drawn from a spread distribution. We repeat this with Query Training on the Adult dataset. If budget-randomized training fails to flatten the off-budget error here, where gradients are exact, the language-model stage is not worth running.
Stage 2: train language-model refinement under random budgets. The loop is sequential revision. Each round produces a short critique and a revised answer. Discrete tokens rule out backpropagation through the loop, so we optimize $J$ with policy-gradient reinforcement learning. Each rollout samples $K \sim p(K)$, and the rollout is scored at every round with weight $P(K=k)$. The regression penalty uses the verifiable reward on math and execution-checked code, where flips from correct to incorrect can be observed directly.
We study three budget distributions: uniform, geometric (deadlines usually come early), and a point mass. The point mass gives the fixed-budget control. We use one 8B-scale base model throughout.
Stage 3: add halting as a secondary question. We add a learned "stop" action whose cost is the expected latency saved. We ask whether, under the anytime objective, a stopping rule adds anything once regressions are already rare. Our hypothesis is that it mostly saves tokens and adds little accuracy.
Baselines
Single pass. The naive reference is the same base model producing one answer, along with the same model after standard reinforcement learning on single answers. Every refinement method must beat these at matched sequential tokens, or refinement is not paying for its latency.
Fixed-budget operator-consistent training. This is the strongest direct competitor. Following Rethinking Thinking Tokens, we train with rollouts that mirror the test-time loop at one fixed round count $N$, with one model for each $N \in \{1,2,4\}$. That paper reports +11% absolute on AIME 2024 over single-pass baselines, equal accuracy to sequential refinement with a 2.57x smaller sequential token budget, and a +3.34-point gain on AIME 2024 from operator-consistent reinforcement learning over baseline reinforcement learning in an 8B model.
We cannot reproduce their exact model and data. We will reimplement the fixed-budget recipe on our base model with the same prompts (Polaris-53K for math, DeepCoder for code, as they used) and the same reinforcement-learning steps and tuning budget as our method. Their numbers serve as a sanity check on scale, not as a direct comparison. To beat this baseline, the budget-randomized model must come within noise of each fixed-$N$ model at that model's own $N$, and be significantly better averaged over the deployment distribution $p(K)$.
Self-refinement trained on revision transitions. EVOLVE (Evolving LLMs' Self-Refinement Capability) is the representative of this family, with 62.3% length-controlled win rate on AlpacaEval 2 and 50.3% on Arena-Hard for Llama-3.1-8B. We will train its supervised-plus-preference recipe on the same base and data and run its chain of self-refinement cut at each $K$.
Critic-guided refinement. For critic-side improvements, we pair a fixed actor with an RCO-trained critic. On MATH, RCO raised actor accuracy from 25.36% to 32.31% with Llama-3-8B-Instruct (Training Language Model to Critique for Better Refinement). We also test our model with that critic plugged in.
Ablations isolating the key ingredient. Three ablations separate the parts of the objective. Uniform per-round reward without the regression term tests whether the penalty matters. The regression penalty alone, on a point-mass budget, tests whether randomizing the budget matters. Training at a large fixed $N$ and then evaluating early-stopped tests whether simply training longer gives the anytime property for free.
Why not just…?
Why not just sample many answers in parallel and vote? Parallel sampling avoids sequential latency entirely, so it is a real competitor whenever wall-clock time, rather than total compute, is the binding constraint. The file's evidence favors refinement at matched compute. Critique-RL reports up to a 5x compute-efficiency advantage over majority voting on MATH, and Teaching Language Models to Self-Improve found that self-refinement tuning beats best-of-N reranking. Neither result addresses wall-clock latency on a parallel machine. We therefore plot best-of-N and majority voting against both total tokens and sequential tokens. If voting dominates on sequential tokens, our contribution shrinks to the compute-bound regime, and we will say so.
Why not just add a verifier-based stopping rule to an ordinary refinement model? This is the most serious threat. If the only problem is that extra rounds hurt, a good verifier could keep the best answer seen so far and stop. On math and code, verification is partly available through answer checks and unit tests, so this could match our method there. We will run the verifier-guided best-so-far baseline with the fixed-$N$ model, both with an oracle verifier and with a learned one.
Our method should only be expected to win where verification is unavailable or noisy. With a learned verifier, keeping the best answer so far inherits the verifier's errors, whereas an operator that rarely regresses needs no verifier. If the learned-verifier baseline matches us on MATH and MBPP, the honest conclusion is that the anytime objective is useful mainly when no verifier is available, as on open-ended instruction following such as AlpacaEval 2.
Why not just train one fixed-budget model per latency tier? If deployments had a few known budgets, separate models trained at exactly those budgets would be simple. The point-mass ablation is exactly this model. Our objective only earns its place if one model matches all of them, which is cheaper to serve, and also handles budgets between and beyond the tiers. If it cannot, the per-tier answer is the right one.
Why not just collapse refinement into a single pass, as Meta-Reflection does? Meta-Reflection reports 63.4% pass@1 on MBPP versus 58.8% zero-shot, and cuts first-token latency to 246ms from 951ms. However, it cannot use execution feedback between rounds. We include it as a reference on MBPP, where unit-test feedback is available at every round, so the comparison checks whether that feedback is worth the extra rounds.
Proposed Experiments and Decisive Checks
Benchmarks and metrics. For graphical models, we use grid Markov random fields and the Adult dataset. For Adult, the reference is Query Training's normalized cross-entropy of 0.167. For Domke's grid setup, the file reports only "lower test error" and gives no specific value. For language models, we use MATH, AIME 2024/2025, and MBPP with execution feedback for verifiable tasks, and AlpacaEval 2 for open-ended quality.
We report the full accuracy-versus-$K$ curve for $K = 0,\dots,6$. We also report expected accuracy under each budget distribution $p(K)$, the regression rate (the fraction of correct answers made incorrect by a later round), round-0 quality to measure the "worse model" cost, and accuracy against both sequential and total tokens.
The first decisive check tests whether the mismatch exists. Fixed-$N$ models must lose measurable accuracy at $K' \neq N$, especially at $K' > N$. If curves are flat across budgets, the problem we target is not real for language-model refinement and the project stops after Stage 1.
The second check tests whether the randomized objective works. The budget-randomized model must match each fixed-$N$ model at its own $N$ within seed variance (three seeds) and beat it in expectation under $p(K)$. Its regression rate must fall, and the fall must be attributable to the penalty term according to the ablations.
The third check tests whether the method is needed at all, by comparing against the verifier-stopping baseline. We expect the method to justify itself on tasks without reliable verification. On verifiable tasks, a tie would be an informative negative result rather than a failure to hide.
References
- Learning as Search Optimization: Approximate Large Margin Methods for Structured Prediction
- Structured Learning with Approximate Inference.
- Extrapolative Controlled Sequence Generation via Iterative Refinement
- RepoCoder: Repository-Level Code Completion Through Iterative Retrieval and Generation
- Learning Graphical Model Parameters with Approximate Marginal Inference
- Query Training: Learning a Worse Model to Infer Better Marginals in Undirected Graphical Models with Hidden Variables
- Rethinking Thinking Tokens: LLMs as Improvement Operators
- Evolving LLMs' Self-Refinement Capability via Synergistic Training-Inference Optimization
- Critique-RL: Training Language Models For Critiquing Through Two-Stage Reinforcement Learning
- Training Language Model to Critique for Better Refinement
- Meta-Reflection: A Feedback-Free Reflection Learning Framework
- Teaching Language Models to Self-Improve by Learning from Language Feedback