acceptodds
Under review as a conference paper at ICLR 2027

Inference-Time Search in Discrete Diffusion Language Models, Guided by Internal-State Signals

Abstract

Inference-time search for diffusion language models assumes that a partially decoded state reveals, early and cheaply, whether a trajectory is worth continuing, and that the model's own internal state is the natural place to read it. We test that assumption on three testbeds spanning four orders of magnitude — two masked-diffusion Sudoku models (0.54M and 6.6M parameters) with an exact symbolic oracle, and LLaDA-8B on GSM8K — and find that internal-state signals track the model's belief, not the partial state's determinacy. We make this precise by splitting the variance of prefix value into a between-prompt part, which only allocation can use, and a within-prompt part, which is all that selection can use. Pooled AUROC, the standard metric, is dominated by the former and so measures difficulty: a difficulty-only signal scores 0.78 pooled and 0.50 within-prompt. Even within-prompt AUROC fails to price a selector: on the small model, confidence ranks branches above chance (0.64), yet choosing its top branch cuts accuracy from 0.69 to 0.36. We introduce a cheap estimator of within-prompt variance from branched rollouts and show it is set by the sampler — zero at temperature 0.3, and at 0.9 half or more of the remaining outcome variance on LLaDA-8B by r=0.5, where a perfect selector would add 15 points. Model confidence recovers none of it at 8B; a task-structural oracle recovers most of it on Sudoku. We recommend reporting any verifier by its realized selection value, at the sampler's operating point.

Primary area:
generative models
Keywords:
Diffusion Language Model, Inference-Time Search, Test-Time Compute, Internal Representations, Verification Language Model Evaluation Residual Stream, GSM8K

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_ptZdOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The authors consider a common idea of inference-time scaling where diffusion language models’ own internal states can be used for deciding when to stop or is still worth continuing. The main theoretical framework for studying it is a variance decomposition of the prefix value. Using this, the authors argue that pooled AUROC mostly measures the prompt difficulty, and even within-prompt AUROC does not determine the value of an argmax selector. This means that the assumption that reading internal states might directly help measuring the partial state’s determinacy is wrong, but rather a proxy of a model’s own belief. The main finding shows that 1) confidence-based selection actually reduces accuracy for some models, 2) within-prompt variance grows with sampling temperature on the small Sudoku model, 3) difficulty-aware allocation gains up to 1.9 points on Sudoku-M.

Critical strengths
  1. The main methodology used here for probing sounds pretty solid. Pooled AUROC rewards ranking easy prompts over hard ones.
  2. The overall measurement protocol is transparent and carefully designed.
  3. The branching estimator is a simple and practical idea to measure the selectable variance without the need to store and recomplete the intermediate states.
Critical weaknesses
  1. Most of the theoretical contribution is mostly shown in prior works and using these on DLLMs seems to be the major contribution here. Decomposition is just the law of total variance. Proposition 1 comes from exchangeability and Jensen’s inequality. And many of the results follow previous works like:
  1. I think the main argument and claim is useful but comes mostly from a small model. The accuracy drop comes from the 0.54M Sudoku-S, which the authors are transparent about. The 6.6M model is also undertrained, which makes me concerned about its generalizability.
  2. The negative results at 8B Llada should test other baseline decoding methods like sequence log-likelihood, majority voting, etc. These are all internal-state based methods. Moreover, the 8B evidence is only shown with one model in one task and one temperature, which DLLMs are known to be selective of.
Questions for authors
  1. Does the 8B results hold on more tasks, over different temperatures and maybe try Dream-7B as well?
  2. What happens when the probes get trained on substantially more data?
Reviewer_BEzoOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies when extra inference compute can help discrete diffusion language models. It separates variation in prompt difficulty from variation among partial trajectories for the same prompt. This explains why a score can predict correctness across prompts yet fail to select a useful trajectory. Experiments on two Sudoku models and LLaDA-8B on GSM8K compare confidence signals, linear probes, compute allocation, and branching under matched compute.

Critical strengths
  1. The paper makes a useful distinction between predicting prompt difficulty and choosing among attempts at the same prompt. A score can do the first well and fail at the second. Measuring actual selection gains gives a more direct test of whether a signal can guide search.

  2. The experiments include careful controls, including prompt-level splits, permutation tests, and corrections for finite-sample variance. The Sudoku oracle also helps separate the limits of the tested confidence scores from the opportunity for better selection.

Critical weaknesses
  1. The main claim about early selection is stronger than the evidence supports. The reported 15-point gain on LLaDA comes from an oracle that chooses among completed answers. It does not show that a selector could achieve this gain halfway through generation. The paper acknowledges this distinction, but the abstract and conclusion blur it. Nonzero variance among partial trajectories shows room for selection to help; it does not establish the claimed gain.

  2. The presentation makes the scope of the results hard to follow. Terms such as “spendable variance” and “pricing a verifier” suggest a direct link between variance and practical gains that the paper does not establish. The discussion also treats pooled AUROC too broadly as a measure of prompt difficulty, although it can reflect both between-prompt and within-prompt differences. These distinctions matter because the large-model evidence covers only one model and task, with just 30 prompts for the linear probes.

Questions for authors
  1. What selection gain can you establish from partial states alone, without using completed-answer labels to choose the candidate? Please distinguish this result from the completed-answer oracle bound.

  2. Can you clarify which conclusions follow from the variance decomposition and which depend on the tested models and signals? In particular, how should we interpret the negative probe results given the small sample? Please also distinguish correctness prediction from learned scheduling methods such as [1], which use model features to guide a different decoding decision.

[1] Xu, et al., Scheduling Thoughts: Learning the Order of Thought in Diffusion Language Models. ICML, 2026. arxiv.org/abs/2606.23567

Reviewer_CGezOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper investigates whether internal-state signals of discrete diffusion language models can reliably identify promising partial generation trajectories for inference-time search. The key observation is that a partially decoded state may reveal the model's confidence without necessarily indicating whether the state is sufficiently determined to lead to a correct final answer. Consequently, a signal that predicts correctness across different prompts may not be useful for selecting among candidate trajectories of the same prompt.

The paper formalizes this distinction by decomposing the variance of prefix value into two components: between-prompt variance, which can be exploited by allocating computation across prompts, and within-prompt variance, which determines the potential benefit of selecting among trajectories for a fixed prompt. The authors argue that pooled AUROC can be dominated by prompt difficulty and therefore does not adequately measure the practical value of a selection signal. They further introduce a branching-based estimator for measuring the within-prompt component using multiple continuations from shared partial states.

The evaluation covers three testbeds: a 0.54M-parameter Sudoku diffusion model, a 6.6M-parameter Sudoku diffusion model, and LLaDA-8B-Instruct on GSM8K. The results show that model confidence can achieve above-chance within-prompt AUROC yet substantially reduce selection accuracy on the smaller Sudoku model. On LLaDA-8B, substantial selection headroom remains, but model confidence captures only a small fraction of the reported upper-bound improvement. In contrast, task-structural oracles perform well on Sudoku, where exact symbolic verification is available.

The paper also evaluates difficulty-aware compute allocation, shared-prefix branching, and different search configurations. Difficulty-aware allocation produces modest gains on Sudoku, while sharing early generation prefixes reduces accuracy on LLaDA under the tested compute budgets. The paper concludes that inference-time search methods should be evaluated by their realized selection value at the intended sampling configuration rather than by pooled prediction metrics alone.

Critical strengths
  1. A clear and relevant research question. The paper identifies an important distinction between predicting which prompts are difficult and identifying which candidate trajectory is more likely to succeed for a given prompt. This distinction is directly relevant to the design of inference-time search methods.

  2. A useful mathematical decomposition. Separating between-prompt and within-prompt variance provides an operational interpretation of the information available for compute allocation and candidate selection. The framework helps explain why pooled AUROC can be misleading when the intended application is within-prompt selection.

  3. Evaluation beyond conventional ranking metrics. The paper emphasizes realized selection accuracy rather than relying exclusively on AUROC. The example in Table 2, where confidence achieves a within-prompt AUROC of 0.640 but reduces accuracy from 0.685 to 0.364 on the smaller Sudoku model, illustrates why this distinction matters.

  4. Careful measurement validation. The use of conservation identities, permutation-based null tests, grouped cross-validation, and debiased variance estimates demonstrates attention to potential sources of statistical error. Appendix E provides useful details about these checks and the measurement problems encountered during development.

  5. Evidence across different model scales and task settings. The two Sudoku models help distinguish task-related effects from model-specific behavior, while the LLaDA-8B experiment demonstrates that substantial within-prompt variation can exist even when the tested internal-state signals fail to exploit it effectively.

  6. Practical implications for search design. The analysis of compute allocation, shared-prefix branching, and branch-selection timing provides useful guidance for evaluating search methods under matched computational budgets.

Critical weaknesses
  1. The experimental scope is insufficient to support broad conclusions about diffusion language models.

    Although the paper describes three testbeds spanning several orders of magnitude in model size, two are controlled Sudoku models with only 0.54M and 6.6M parameters. The only large language-model evaluation uses LLaDA-8B-Instruct on GSM8K at temperature 0.9.

    This leaves several important questions unresolved. The paper does not establish whether the same conclusions hold for other large diffusion language models, other reasoning benchmarks, or different sampling configurations. In particular, the temperature sweep is conducted only on the smaller Sudoku model, even though the paper's central finding is that the amount of exploitable within-prompt variation depends strongly on the sampler and model.

    The results themselves illustrate this dependence: at r=0.5r=0.5, the estimated within-prompt variance for Sudoku-M is below 10−310^{-3}, compared with approximately 0.05 for Sudoku-S at temperature 0.9. Such differences suggest that the availability of selection opportunities is highly model-dependent.

    The paper therefore provides evidence for the proposed framework in the tested settings, but not yet for a general characterization of inference-time search in diffusion language models. Additional experiments on multiple large models, tasks, and sampling temperatures are needed to establish the external validity of its conclusions.

  2. Limited sample sizes and run-to-run variability weaken some quantitative conclusions.

    The smaller Sudoku testbed uses only 50 held-out puzzles. The paper itself reports substantial uncertainty in the perfect-selector ceiling: at r=0.95r=0.95, the estimated accuracy is 0.879 with a 95% confidence interval of [0.780, 0.960]. It also reports that two nominally identical runs on the MPS backend produce selector ceilings of 0.958 and 0.879, respectively.

    Importantly, the reported confidence intervals are bootstrapped over prompts and do not include this run-to-run variability. Thus, they may understate the uncertainty in quantitative estimates when execution-level randomness is material. The large-model branching experiment uses 120 prompts, while the linear-probe analysis is based on a 30-prompt run. These sample sizes limit the precision with which small improvements or null effects can be distinguished.

    These limitations do not invalidate the paper's central observations, but they affect the strength of its quantitative claims. More independent runs and uncertainty estimates that account for both prompt-level variation and run-to-run variability would make the conclusions more robust.

  3. The reported selection headroom should be distinguished from the gain achievable by a partial-state selector.

    On LLaDA-8B, the paper reports a baseline accuracy of 0.768 and an accuracy of 0.919 for its perfect selector, corresponding to an upper-bound improvement of approximately 15 percentage points. Model confidence at r=0.5r=0.5, by contrast, yields an accuracy of 0.785, capturing only about 1.6 percentage points of improvement.

    However, the paper explicitly defines the LLaDA perfect selector by choosing a correct completed candidate whenever one exists. This is an upper bound on selection among the completed trajectories, not the attainable ceiling for a selector operating on partial states at r=0.5r=0.5. The existence of substantial outcome variation among branches does not by itself establish that the same amount of improvement can be achieved using information available at that intermediate step.

    The branching estimator provides evidence that within-prompt variation exists, but the relationship between this variation and the accuracy gain achievable by a realistic partial-state verifier remains incompletely characterized. The paper should more carefully distinguish the measured variance available in principle, the upper bound obtained from completed outcomes, and the gain achievable by a practical selection rule at a specified decoding stage.

  4. The evaluated internal-state signals do not exhaust plausible selection mechanisms.

    The paper evaluates model confidence, entropy, and linear probes over residual-stream representations. These are reasonable baselines, but the negative results do not establish that internal representations generally lack useful information about partial-state correctness.

    In particular, the large-model linear-probe experiments use only 30 prompts. The paper also acknowledges that a trained nonlinear verifier could behave differently. Moreover, the experiments do not establish whether task-aware features, more expressive learned selectors, or alternative readouts could extract information that the tested signals fail to capture.

    The exact symbolic oracle performs well on Sudoku, demonstrating that useful selection information can be extracted from task structure. However, this oracle is not available for general reasoning tasks such as GSM8K. The gap between a strong task-specific oracle and the tested internal-state signals therefore remains unresolved.

    The appropriate conclusion is that the tested signals are ineffective or insufficient at the evaluated operating points, rather than that internal-state information is generally unsuitable for inference-time selection. A broader set of selection mechanisms, or a more explicit characterization of the information available in the model representations, would strengthen the paper's conclusions.

  5. The practical benefits of the proposed framework remain limited, and the branching estimator is primarily diagnostic.

    The downstream experiments provide only modest evidence of practical gains. Difficulty-aware allocation improves Sudoku-M accuracy by approximately 1.5–1.9 percentage points under the reported budgets, but the gains on LLaDA are only 0.7–0.8 percentage points and are not statistically distinguishable from zero. Sharing early generation prefixes reduces LLaDA accuracy by 4.0 percentage points at r⋆=0.5r^\star=0.5 and 4.7 percentage points at r⋆=0.75r^\star=0.75, with the latter result statistically distinguishable from zero under the reported interval.

    Furthermore, the compute frontier in Figure 5 assumes a perfect selector. It therefore illustrates the efficiency of an idealized search strategy rather than the performance of a practical method using the internal-state signals evaluated in the paper. The actual confidence-based selector fails to approach this idealized frontier on the large-model benchmark.

    The branching estimator is useful for diagnosing how much selection value may exist, but it does not itself provide a cheap online signal capable of exploiting that value. Although the paper discusses the cost of branching, the sample efficiency and total overhead required to estimate within-prompt variance reliably across models and sampling configurations remain important practical considerations.

Questions for authors
  1. The paper acknowledges that within-question discrimination and marginal-value allocation have been studied in prior work. Could the authors clarify which aspects of the variance decomposition and branching estimator constitute the principal methodological advance beyond these existing frameworks? This would help establish the incremental novelty of the contribution.

  2. The variance decomposition is exact for prefix value, whereas pooled AUROC is a pairwise ranking metric. Could the authors provide a formal argument connecting the between-prompt and within-prompt components to the behavior of pooled AUROC, or clarify that the claim is an empirical observation rather than a general mathematical consequence?

  3. Have the authors evaluated the proposed framework on additional large diffusion language models, reasoning tasks, or sampling temperatures? Broader evidence would help determine whether the observed failure of confidence-based selection is specific to LLaDA-8B on GSM8K or representative of diffusion language models more generally.

  4. Could the authors provide additional independent runs or uncertainty estimates that account for both prompt-level variation and run-to-run variability? This is particularly relevant given the reported differences between nominally identical MPS runs and the limited number of prompts used in some experiments.

  5. On LLaDA-8B, the reported perfect-selector improvement of approximately 15 percentage points is based on selecting among completed trajectories and is therefore an upper bound rather than a partial-state selection ceiling at r=0.5r=0.5. Can the authors quantify the best achievable selection accuracy using only information available at a specified intermediate decoding step? This would clarify how much of the measured selection headroom is practically exploitable.

  6. Can the authors demonstrate a more expressive verifier or selection rule that captures a substantial fraction of the available improvement on a large diffusion language model under a matched inference-compute budget? Such evidence would strengthen the practical significance of the proposed framework.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.