PaperlayerView exact revision on arXiv

Source-linked AI summary

Locally Confident, Globally Stuck: The Quality-Exploration Dilemma in Diffusion Language Models

Liancheng Fang, Aiwei Liu, Henry Peng Zou, Yankai Chen, Enze Ma, Leyi Pan, Chunyu Miao, Wei-Chieh Huang, Xue Liu, Philip S. Yu

arXiv:2604.00375v1cs.CL

TL;DR

dLLM decoding faces a quality–exploration dilemma: confidence-based remasking improves individual samples but constrains sequence diversity. The paper derives a balanced target distribution and uses Independent Metropolis–Hastings with lookahead correction to approximate it, achieving better trade-offs across reasoning benchmarks.

  • Problem

    Confidence-based remasking improves a myopic quality proxy but imposes an entropy cap on the induced sequence distribution, limiting exploration.

  • Method

    The paper characterizes an entropy-regularized target distribution balancing quality and exploration, then approximates it during decoding with Independent Metropolis–Hastings and a tractable lookahead correction.

  • Results

    Across reasoning benchmarks, the approach consistently achieves superior exploration–quality trade-offs and establishes a new Pareto frontier for dLLM decoding.

  • Takeaways & Limitations

    Global sequence-level tempering expands the effective reasoning frontier beyond local remasking heuristics.

  • Takeaways & Limitations

    Exact sequence-level MCMC is impractical because both the normalizing constant and dLLM sequence likelihood are intractable.

Abstract

from arXiv · show

Diffusion large language models (dLLMs) theoretically permit token decoding in arbitrary order, a flexibility that could enable richer exploration of reasoning paths than autoregressive (AR) LLMs. In practice, however, random-order decoding often hurts generation quality. To mitigate this, low-confidence remasking improves single-sample quality (e.g., Pass@$1$) by prioritizing confident tokens, but it also suppresses exploration and limits multi-sample gains (e.g., Pass@$k$), creating a fundamental quality--exploration dilemma. In this paper, we provide a unified explanation of this dilemma. We show that low-confidence remasking improves a myopic proxy for quality while provably constraining the entropy of the induced sequence distribution. To overcome this limitation, we characterize the optimal distribution that explicitly balances quality and exploration, and develop a simple Independent Metropolis--Hastings sampler that approximately targets this distribution during decoding. Experiments across a range of reasoning benchmarks including MATH500, AIME24/25, HumanEval, and MBPP show that our approach yields better exploration-quality tradeoff than both random and low-confidence remasking.

1 Introduction

dLLMs can decode tokens in arbitrary positions, potentially supporting nonlinear reasoning, but practical decoding faces a quality–exploration dilemma. The paper addresses this by targeting a globally balanced distribution and sampling it approximately with a lookahead-corrected strategy.

  • Motivation: Arbitrary-position decoding gives dLLMs flexibility beyond autoregressive left-to-right token commitment.dLLMs iteratively denoise whole sequences and may finalize tokens at arbitrary positions.
  • The quality–exploration dilemma: Low-confidence remasking improves Pass@1 but quickly saturates Pass@k, whereas random remasking explores more broadly with weaker individual samples.These opposing behaviors create the paper’s central quality–exploration dilemma.
  • Research question: The paper asks whether dLLM decoding can preserve high per-sample quality without collapsing exploration.This question is motivated by the contrast between uncertainty-based and random remasking.
  • Approach: The proposed strategy derives an optimal quality–exploration target distribution and approximately samples it using a lookahead correction favoring globally promising sequences.The correction adjusts local token choices according to the promise of resulting completion spaces.
  • Empirical outcome: Across LLaDA and WeDLM experiments on MATH500, AIME, HumanEval, and MBPP, the method achieves superior exploration–quality trade-offs.The contribution passage reports consistent superiority over random and uncertainty-based remasking.

2 Preliminaries

dLLMs generate sequences by iteratively refining masked tokens, with remasking strategies determining which positions are revealed. The preliminaries distinguish random and uncertainty-based choices and motivate Pass@k as a measure of exploration.

  • Diffusion language models: dLLMs reverse a masking process by predicting all masked positions from partially revealed sequences.The model is trained to reverse independently applied token masking.
  • Sampling process: At each decoding step, the model samples marginal predictions and unmasks a subset of positions, gradually producing a complete sequence.The subset-selection rule determines the decoding strategy.
  • Remasking strategies: Random remasking selects positions uniformly, while uncertainty-based remasking selects positions using high token or distribution uncertainty.The table passage identifies uncertainty heuristics as a taxonomy of scoring and operational choices.
  • Exploration metric: Pass@k measures the probability that at least one of k independent generations is correct and serves as a proxy for exploration capability.Its unbiased estimator uses c correct solutions among n samples.
  • Exploration metric: A low Pass@k indicates a fundamental barrier to exploring valid reasoning trajectories.This connects multi-sample success directly to the availability of diverse valid solutions.

3 Formalizing the Quality–Exploration Dilemma

Confidence-based decoding improves a myopic quality proxy by committing peaked token distributions, but the same gating imposes a hard entropy ceiling that restricts sequence-level exploration. This formalizes the quality–exploration dilemma through local entropy reduction and global diversity collapse.

  • 3 Formalizing the Quality–Exploration Dilemma: Confidence gating unifies uncertainty heuristics by allowing a token to be committed only when its marginal distribution is sufficiently peaked.Entropy- and margin-based criteria reduce to this form under suitable choices of δ.
  • 3.1 The Local Benefit: Improving Quality via Myopic Optimization: The generation objective is expected log loss under a reference model, with GenPPL obtained by exponentiating that expected trajectory-dependent loss.GenPPL evaluates sequence-level surprisal under the reference model.
  • 3.1 The Local Benefit: Improving Quality via Myopic Optimization: Under self-scoring with pref = pθ, each one-step expected loss equals the entropy of the selected token marginal distribution.Thus, Ex[−log pθ(x | st)] = H(pθ(· | st)).
  • 3.1 The Local Benefit: Improving Quality via Myopic Optimization: Confidence gating bounds each commit distribution’s entropy by hV(δ) = hb(δ) + δ log(|V| −1), yielding a GenPPL ceiling of exp(hV(δ)).The bound is the maximum entropy for a vocabulary distribution whose largest probability mass is at least 1 −δ.
  • 3.1 The Local Benefit: Improving Quality via Myopic Optimization: The local quality benefit is myopic because each commit decision changes the context available to future decoding steps rather than directly optimizing the global sequence objective.The resulting bound controls worst-case one-step uncertainty and accumulated self-crossentropy.
  • 3.2 The Global Cost: Suppressing Exploration via Entropy Collapse: Confidence gating also bounds sequence entropy and effective branching factor, so mode-seeking behavior that improves single-sample quality restricts multi-sample diversity.The effective branching factor is the per-token perplexity of the induced sequence distribution.
  • 3.2 The Global Cost: Suppressing Exploration via Entropy Collapse: The entropy budget depends only on δ and |V|, imposing a sharp ceiling on the number of effective token choices under strong gating.The induced effective branching factor measures the geometric-mean number of effective tokens available at each decoding step.
  • 3.2 The Global Cost: Suppressing Exploration via Entropy Collapse: With |V| = 5 × 104 and δ = 0.05, Beff < 2.1, so strongly gated decoding concentrates probability on fewer than three candidates per step.This ceiling limits simultaneous exploration of multiple valid reasoning paths and explains poor Pass@k scaling.

4 Principled Exploration via Global Tempering

The paper formulates quality and exploration over complete-sequence distributions, deriving a globally tempered optimum and approximating its decoding conditionals with batched Independent Metropolis–Hastings. The resulting sampler uses lookahead corrections to favor promising continuation spaces rather than only locally confident tokens.

  • The Optimal Target Distribution: The quality–exploration trade-off is optimized directly over complete-sequence distributions using expected log-likelihood and sequence entropy.The entropy-regularized objective treats quality as E_x∼p[log q(x)] and exploration as H(p).
  • The Optimal Target Distribution: The unique optimum is a power distribution q(x)^α, where α controls global sequence-level tempering.α<1 flattens the distribution, whereas α>1 sharpens it.
  • Corrected Conditionals: Exact global sampling is obstructed because both the normalizing constant and dLLM sequence likelihood are intractable.This prevents direct application of standard sequence-level MCMC methods.
  • Corrected Conditionals: The corrected one-step conditional combines local tempering with a suffix lookahead correction measuring the tempered mass of reachable completions.The correction favors tokens that preserve promising continuation spaces, mitigating premature collapse onto one reasoning path.
  • Corrected Conditionals: A mean-field approximation makes the lookahead correction computable with one network evaluation at each proposed state.The approximation exploits conditionally independent masked-token marginals.
  • Independent Metropolis–Hastings: Independent Metropolis–Hastings samples from locally tempered proposals and accepts candidates using differences in suffix corrections.The sampler targets a one-dimensional categorical distribution and evaluates proposals in batches, avoiding sequential overhead.

5 Experiments

Experiments evaluate IMH across mathematical reasoning and code-generation benchmarks with two architecturally distinct dLLMs. IMH generally provides the strongest Pass@k and the most favorable quality–exploration trade-off, while producing more diverse trajectories and larger gains on hard problems.

  • Experimental Setup: The evaluation covers MATH500, AIME24/25, HumanEval, and MBPP using LLaDA-8B-Instruct and WeDLM-8B.Baselines include random remasking and confidence, entropy, and margin heuristics.
  • Benchmarks: IMH achieves the strongest exploratory performance on nearly every task for both WeDLM and LLaDA.Figure 2 reports the corresponding Pass@k scaling curves.
  • Benchmarks: On AIME24/25, IMH substantially outperforms WeDLM’s default entropy heuristic in both Pass@1 and Pass@k.This shows gains in both single-sample quality and repeated-sampling performance on challenging benchmarks.
  • Benchmarks: On LLaDA MATH500, IMH performs best on both Pass@1 and Pass@k, while low-confidence remasking has a slight Pass@1 advantage on HumanEval and MBPP.That advantage comes with a substantial Pass@k cost on the code-generation tasks.
  • The Quality-Diversity Pareto Frontier: IMH strictly dominates local strategies on the MATH500 quality–diversity Pareto frontier across swept temperature parameters.The comparison evaluates Pass@1 against Pass@k for IMH and local baselines.
  • Expanding the Reasoning Boundary: IMH’s largest AIME24 gains occur on Hard problems, while Easy-tier performance is largely saturated across methods.Trajectory analysis also finds local baselines highly correlated at scores 73–83, versus IMH similarities of 68–72.
  • IMH Convergence and Mixing: Pass@1 and Pass@8 rise until T = 7 and then remain roughly stable, while mean acceptance stays above 97.0% across chain lengths.These results characterize rapid task-level convergence and efficient internal mixing.

6 Conclusion

The paper presents IMH as a principled response to myopic decoding that aligns local token commitments with globally promising completion spaces. Across demanding reasoning benchmarks, it reports a new quality–exploration frontier and expanded effective reasoning on AIME datasets.

  • Conclusion: The proposed paradigm addresses trajectory-diversity collapse by combining a lookahead correction with an Independent Metropolis–Hastings sampler.The method aligns local token commitments with the global promise of resulting completions.
  • Conclusion: Evaluations on rigorous reasoning benchmarks show that the strategy establishes a new Pareto frontier for quality and exploration.The conclusion also reports expansion of the effective reasoning frontier on exceptionally demanding AIME datasets.
  • Related Work: Prior work attributes weak dLLM Pass@k scaling to flexibility traps, single-trajectory decoding, parallel–sequential conflicts, and myopic unmasking heuristics.These studies motivate the paper’s focus on preserving exploration during decoding.
  • Related Work: Recent methods include stable-span parallel decoding, revokable decoding, and globally tempered MCMC for autoregressive generation.The paper distinguishes its dLLM setting from AR MCMC because dLLMs lack tractable sequence likelihoods.

B Experimental Details

The experiments use controlled one-token-at-a-time decoding, benchmark multiple dLLM architectures and tasks, and formalize several token-selection heuristics through δ-gating bounds.

  • Decoding configurations: Baseline decoding methods generate exactly one token per step, while LLaDA uses a semi-autoregressive strategy with a fixed block length.The supplied passage states that parallel decoding is disabled for Confidence, Entropy, Margin, and Random baselines; the block length is truncated.
  • Decoding configurations: IMH uses chain length T = 4 for LLaDA and T = 8 for WeDLM, with LLaDA’s benchmark-specific maximum generation lengths reported in Table 4.The supplied table caption identifies Table 4 as reporting maximum generation lengths for LLaDA across benchmarks.
  • Heuristic formalization: The δ-gating framework unifies Sample-then-Filter and Rank-then-Sample heuristics through the implied bound maxv pi(v) ≥ 1 −δ.The framework contrasts filtering after sampling with restricting sampling to the highest-scoring positions.
  • Heuristic formalization: The confidence heuristic directly imposes maxv pi(v) ≥ 1 −δ, whereas entropy gating derives an implied confidence bound from H(pi) ≤ε.For fixed maximum probability, entropy is maximized when the remaining mass is distributed uniformly across the other |V| −1 tokens.
  • Heuristic formalization: The margin heuristic thresholds the gap between the two highest probabilities and yields α = [1 + (|V| −1)γ]/|V| under its extremal construction.The derivation sets β = α −γ and distributes the remaining probabilities at β.

D Derivation of the IMH Acceptance Ratio

The IMH derivation starts from the target and proposal distributions, then shows that local tempered-logit terms cancel, leaving acceptance governed by suffix-correction differences.

  • Acceptance-ratio setup: The derivation introduces the general IMH acceptance ratio for proposing a move from state x to state y.The ratio is presented before substituting the paper’s target and proposal distributions.
  • Target distribution: The one-step target uses local logits with inverse temperature α and a suffix correction term b∆i,v(s).The supplied prose explicitly defines α, ℓi,v(s), and b∆i,v(s).
  • Proposal distribution: The proposal is the locally tempered categorical distribution without the suffix correction.This construction aligns the proposal’s local terms with those in the target.
  • Acceptance simplification: Substitution into the IMH ratio cancels the local tempered-logit terms in the numerator and denominator.The resulting acceptance probability depends strictly on the difference between proposed and current suffix corrections.
  • Acceptance simplification: The simplified acceptance probability therefore depends on the suffix-correction difference between the proposed and current states.This is the structural consequence identified after cancellation.

E Variance of the pass@k Estimator

The paper bounds pass@k estimator noise using worst-case binomial variance and reports benchmark-specific 95% margins of error, concluding that n ≥2k to 4k is sufficiently stable.

  • Estimator: The unbiased pass@k estimator uses n total generated samples and c samples that pass the unit tests.The estimator is evaluated with n = 32 for k ≤16 on LLaDA and n = 128 for k ≤32 on WeDLM.
  • Variance analysis: The estimator’s single-problem variance is determined by the binomial model c ∼Binomial(n, p), with worst-case variance at the most uncertain pass probability.The supplied passage states that p is the true underlying pass probability.
  • Variance analysis: The maximum dataset-level standard error is bounded by SEmax = q maxp Var( P̂k)/M, and the corresponding 95% margin of error is 1.96 × SEmax.The bound is taken over all p ∈[0, 1] and a dataset of M problems.
  • Reported uncertainty: Table 5 reports absolute worst-case 95% margins of error for each evaluated benchmark and model setting.Its caption describes these values as the theoretical maximum noise from the finite-sample estimator.
  • Reported uncertainty: Because practical variance is lower than the worst-case bound, the paper concludes that n ≥2k to 4k provides a sufficiently stable pass@k estimate.The passage notes that p is rarely adversarial across all problems and is often exactly 0 for hard problems such as AIME.

F Detailed Analysis of Hard Problems

The case studies compare baseline and IMH reasoning on difficult AIME-style problems, showing that global tempering can preserve alternative solution paths when local methods make brittle commitments. IMH reaches correct answers in several examples, although one case reveals fabricated intermediate reasoning despite a correct final answer.

  • Case studies: IMH successfully solved a challenging AIME 2024 problem across all 128 samples, while Confidence, Entropy, Margin, and Left-to-Right failed completely.The case study presents this as evidence that global tempering can expand the reasoning boundary on difficult problems.
  • Triangle-circle problem: In the triangle-circle problem, the intended solution uses harmonicity, Ptolemy’s theorem, and the Law of Cosines to obtain AP = 96/17 and m + n = 113.The cited baseline and IMH excerpts describe alternative coordinate and geometric solution paths for the same target.
  • Geometry problem: Global tempering lets IMH abandon hallucination-prone synthetic geometry and complete a coordinate-geometry proof without logical gaps.Baseline methods confidently invoked mathematically unfounded geometry claims, whereas IMH explored an analytic alternative.
  • Box optimization: On the box-optimization problem, the baseline assumed integer dimensions and committed to S = 9, whereas IMH identified the continuous optimum with two equal dimensions and obtained 721.The correct derivation uses a double root of the cubic and yields r2 = 657/64, so p + q = 721.
  • Tetrahedron problem: The tetrahedron case exposes a key limitation: IMH returned the correct answer 104, but its intermediate coordinates and volume were mathematically fabricated.The analysis describes this as working backward from a memorized answer rather than establishing a valid derivation.

G Trajectory Similarity Analysis

The trajectory-similarity analysis compares high-level reasoning strategies across methods using LLM-generated summaries and pairwise scores. The resulting normalized similarity matrix is reported in Figure 3.

  • Evaluation design: The evaluation samples one generated trajectory per method for each of 30 AIME 2024 problems.The methods are Confidence, Margin, Entropy, and IMH.
  • Evaluation design: Claude Opus 4.6 first summarizes each trajectory into its applied strategy and intermediate results.These summaries provide the inputs for the subsequent pairwise comparison.
  • Scoring: Pairwise comparisons rate similarity on a six-point scale based on the high-level strategy applied.The scale ranges from almost identical to totally different.
  • Scoring: Final similarity scores are averaged across all 30 problems and normalized to a 0–100 scale, with self-similarity fixed at 5.The resulting similarity matrix is reported in Figure 3 (right).

H.2 Proof of Proposition 2

This section proves that confidence gating imposes a hard entropy ceiling on the sequence distribution. It then characterizes the power-distribution optimizer and the globally corrected conditional used for tempering.

  • Entropy cap: Under confidence gating, each committed token distribution has maximum probability at least 1 −δ, constraining per-token uncertainty.The proof models block commits as conditionally independent given the decoder state and uses the gating condition at every position.
  • Entropy cap: The resulting effective branching factor is bounded by a function of δ and vocabulary size, formalizing how strong gating restricts sequence diversity.The bound is expressed through hV(δ) = hb(δ) + δ log(|V| −1).
  • Entropy cap: The entropy bound follows by maximizing categorical entropy subject to the largest probability mass being at least 1 −δ.For residual mass m ≤δ, entropy is maximized by spreading that mass uniformly over the other V −1 vocabulary outcomes.
  • Optimal distribution: The unique optimizer of the entropy-regularized objective is a power distribution proportional to q(x)^α.The variational derivation obtains p(x) = e^(λ−1) q(x)^α before normalization.
  • Global tempering: The corrected conditional weights each candidate token by its local marginal raised to α and the summed α-weighted probability of its possible completions.The construction combines local logits with a lookahead correction for the remaining positions.
Loading 2604.00375v1…