Skip to content

Improving Diffusion Language Model Decoding through Joint Search in Generation Order and Token Space

Conference: EMNLP 2026
Paper: ACL Anthology
Area: LLM (Other)
Keywords: diffusion language models, masked diffusion models, trajectory search, decoding algorithms, likelihood estimation

TL;DR

Addressing the dilemma where heuristic remasking in diffusion language models gets trapped in a single trajectory or explores blindly, this paper proposes Order-Token Search to jointly search over generation orders and token assignments, utilizing an incremental action likelihood estimator for stable pruning to substantially outperform existing decoding baselines and post-training methods.

Background & Motivation

Discrete Masked Diffusion Models (MDMs) have rapidly emerged as a promising alternative to conventional autoregressive architectures for sequence generation. Unlike autoregressive models, which are strictly constrained to generate text sequentially from left to right, MDMs feature an inherent "order-agnostic" decoding mechanism: at each denoising step, the model predicts token distributions for all masked positions in parallel and adaptively decides which positions to commit and reveal. This flexibility naturally exposes an expansive multi-trajectory solution space, making the intertwined choices of generation order and token values the central determinant of final generation quality.

However, standard MDM decoders commit exclusively to a single trajectory per generation pass, revealing an acute explorationโ€“exploitation trade-off. Greedy heuristics such as low-confidence remasking prioritize early commitment to locally high-confidence tokens and only iteratively revise uncertain positions; while this stabilizes local context and boosts initial pass@1 accuracy, it severely restricts decoding to a narrow set of trajectories, resulting in stagnant pass@k growth as the sample budget increases. Conversely, training-aligned random remasking exposes abundant trajectory diversity and achieves a markedly higher pass@k ceiling, but it suffers from poor pass@1 accuracy due to the total absence of a principled selection mechanism among competing noisy candidates.

This tension demonstrates that MDMs possess substantial latent capability to solve complex tasks across alternative trajectories, which remains untapped under single-trajectory decoding. Core idea: by maintaining beams of partially denoised states, explicitly branching across the joint space of generation orders and token values, and pruning via an incremental denoising action likelihood estimator, Order-Token Search converts the latent multi-trajectory potential of diffusion models into superior single-pass generation accuracy.

Method

Order-Token Search (OTS) adapts the core concept of beam search to the unique parallel, order-agnostic dynamics of discrete diffusion models. Instead of searching purely across token assignments, OTS simultaneously navigates uncertainty in both "where and when to decode" (generation order) and "what to decode" (token value), alternating between branch expansion and trajectory pruning.

Overall Architecture

OTS initializes a beam set of \(K\) identical copies of a fully masked sequence conditioned on the prompt. At designated search intervals, each beam candidate is expanded across multiple denoising steps by proposing diverse denoising actions sampled via perturbed logits. An incremental action likelihood scoring module then evaluates the conditional probability of the newly revealed tokens, accumulating trajectory scores to prune the candidate pool back to the top-\(K\) beams. To balance search power against computational cost, the search process is orchestrated across block boundaries via block diffusion, culminating in the selection of the highest-scoring completed sequence.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Input Prompt & Fully Masked Sequence<br/>Initialize K Beam Candidates"] --> B["Block Diffusion Step<br/>Parallel Stepwise Denoising"]
    B --> C["Joint Action Branch Expansion<br/>Sample Generation Orders & Token Assignments"]
    C --> D["Incremental Action Likelihood Evaluation<br/>Conditional Remasking Log-Likelihood"]
    D --> E["Cumulative Trajectory Pruning<br/>Retain Top-K Candidates"]
    E -->|Intermediate Blocks Remaining| B
    E -->|All Blocks Completed| F["Output Global Top-Scoring Trajectory"]

Key Designs

1. Joint Action Branch Expansion: Simultaneous Exploration of Order and Token Spaces

Standard autoregressive beam search can only explore alternative token branches along a fixed left-to-right causal path, whereas prior MDM decoders fix the generation order via greedy heuristics. OTS breaks this limitation by branching over both degrees of freedom simultaneously. At scheduled search steps, the algorithm injects Gumbel noise into the unmasked logits across all candidate beams and draws multiple sampled completions. Each action selectively transfers a subset of predicted tokens into the unmasked state, generating \(K^2\) diverse candidate trajectories that differ in both which positions are committed first and which tokens are instantiated.

2. Incremental Action Likelihood Evaluation: Low-Variance Scoring of Denoising Steps

Evaluating candidates by computing the full-sequence reconstruction likelihood from an intermediate state introduces massive variance: when many tokens remain masked, the model is evaluated on a globally difficult infilling problem that diverges sharply from the incremental denoising task it learns best. OTS instead formulates a scoring metric focused strictly on the incremental denoising action. For a transition from state \(x_t\) to \(x_s\) where the newly revealed token index set is \(\Delta(s, t)\), the predicted completion \(x_0\) is re-masked at \(\Delta(s, t)\) to form \(\tilde{x}_0\), and scored via:

\[s(x_t; x_s) = \mathbb{E}_{x_0 \sim p_\theta(\cdot \mid x_t)} \left[ \log p_\theta \left( x_0^{\Delta(s,t)} \mid \tilde{x}_0 \right) \right]\]

This objective measures how reliably the model can reconstruct the newly committed tokens given its own predicted surrounding context. By isolating the evaluation to incremental changes rather than global states, it provides a stable, discriminative pruning signal across competing trajectories.

3. Cumulative Trajectory Pruning and Block-Level Complexity Control: Linear Compute Scaling

Branching at every single diffusion step \(S\) would induce a prohibitive computational complexity of \(\mathcal{O}(S \cdot K^2 \cdot L)\). OTS integrates block diffusion, confining the joint branch-and-prune operations exclusively to block boundaries across \(|B|\) blocks while allowing standard greedy denoising within each block. Trajectory scores are accumulated across search intervals \(\mathcal{I}\):

\[S(\text{candidate}) = \sum_{(s,t) \in \mathcal{I}} s(x_t; x_s)\]

This structural decomposition reduces the overall function evaluations (NFE) to \(\mathcal{O}(S \cdot K \cdot L + |B| \cdot K^2 \cdot L)\). Under default settings (\(S = L/2, |B| = L/32, K = 4\)), OTS incurs approximately \(2.5 L^2\) NFEโ€”matching the computational budget of standard 5-sample majority voting while delivering markedly superior accuracy.

Key Experimental Results

Main Results

Evaluated on LLaDA-8B-Instruct and LLaDA-1.5 across GSM8K, MATH500, Countdown, and HumanEval (reporting task averages across sequence lengths 64, 128, 256, 512):

Model / Method GSM8K (Avg) MATH500 (Avg) Countdown (Avg) HumanEval (Avg) Overall Average
LLaDA (8B)
Low-confidence 67.0 29.0 20.5 20.6 34.3
Low-conf + MV (5 samples) 70.7 29.7 20.7 20.9 35.5
Random remasking 54.2 20.5 11.0 21.1 26.7
Random + MV (5 samples) 68.6 26.8 12.7 22.7 32.7
AR + beam-search 68.7 31.0 21.2 27.3 37.1
diffu-GRPO (Post-training) - 36.6* (len=256) 31.3 (len=256) 39.0 (len=256) -
Order-Token Search (Ours) 70.1 32.8 28.4 27.4 39.7
LLaDA-1.5
Low-confidence 67.7 28.8 19.8 21.7 34.5
Low-conf + MV (5 samples) 73.0 31.3 22.5 22.0 37.2
AR + beam-search 71.3 29.9 18.1 24.9 36.1
Order-Token Search (Ours) 72.2 33.8 28.0 27.6 40.4

Ablation Study

Ablation of pruning estimators on LLaDA and LLaDA-1.5 under identical branching and test-time compute budgets:

Pruning Estimator LLaDA Overall Avg LLaDA Countdown LLaDA-1.5 Overall Avg LLaDA-1.5 Countdown Description
Order-Token Search (Ours) 39.7% 28.4% 40.4% 28.0% Evaluates incremental action \(\Delta(s, t)\) conditioned on full context
OTS Future Blocks 33.9% 17.4% 35.3% 19.2% Masks all unrevealed future blocks, scoring without future context
OTS All Blocks 32.6% 16.2% 34.0% 18.4% Scores joint infilling log-likelihood over all revealed positions so far
CumProb (Cumulative Token Prob) 38.0% 25.5% 38.7% 26.3% Accumulates model log-probabilities on committed tokens

Key Findings

  • Superiority Over Single-Trajectory and Autoregressive Baselines: OTS achieves the highest overall accuracy across both base models (39.7% on LLaDA and 40.4% on LLaDA-1.5), outperforming the strongest decoding baseline AR + beam-search by +2.6% and +4.3%, and surpassing standard Low-confidence by +5.4% and +5.9%.
  • Competitive with Post-Training (diffu-GRPO): On sequence length 512, OTS reaches 83.3% on GSM8K (vs. 81.9% for diffu-GRPO) and 42.4% on MATH500 (vs. 39.2% for diffu-GRPO), demonstrating that structured test-time search can match or exceed gains from expensive reinforcement learning fine-tuning.
  • Incremental Likelihood is Vital for Pruning: Reverting to whole-history scoring (All Blocks) or removing future context (Future Blocks) causes overall accuracy to degrade sharply by 5-7 percentage points, with Countdown plunging by more than 11%, confirming that low-variance incremental action scoring is the critical enabler of reliable trajectory pruning.

Highlights & Insights

  • Formulating DLM Decoding as Joint Order-Token Trajectory Search: The work insightfully identifies that the true power of discrete diffusion models lies in their order flexibility, unlocking a joint trajectory search space that autoregressive beam search cannot navigate.
  • Low-Variance Action Scoring via Conditional Remasking: By remasking and evaluating only the newly revealed tokens against the model's own predicted completion, OTS avoids the instability of global sequence evaluation while providing a dependable ranking metric.
  • High Compute-Efficiency Conversion: Rather than expending compute on independent parallel generations that are aggregated post-hoc via voting heuristics, OTS performs early hypothesis pruning during decoding, delivering much steeper returns per function evaluation.

Limitations & Future Work

  • Inference Compute Overhead: Although block diffusion mitigates the combinatorial explosion, OTS requires 2-3x longer wall-clock time compared to single-trajectory greedy decoding, which may pose challenges for latency-critical applications.
  • Boundary Failure on Hard Global Constraints: On 4x4 Sudoku benchmarks, all tested decoding methods including OTS fail to outperform a random baseline (~25% cell accuracy), indicating that search-based decoding cannot compensate when the base model fails to internalize global constraint structures.
  • Unsupervised vs. Learned Verifiers: The current likelihood estimator is entirely unsupervised and model-intrinsic; future exploration could incorporate lightweight learned discriminators or reward models to guide the pruning process.
  • vs Low-confidence & Random Remasking: Low-confidence remasking over-exploits and suffers from trajectory collapse (stagnant pass@k), while random remasking explores without direction (poor pass@1). OTS unifies both paradigms by exploring diverse order-token paths and pruning them using an intrinsic likelihood signal.
  • vs Autoregressive Beam Search: AR beam search restricts decoding order strictly from left to right (equivalent to OTS with block_size = 1). OTS generalizes beam search to arbitrary order-token trajectories, effectively capitalizing on the bidirectional attention capabilities of diffusion language models.

Rating

  • Novelty: โญโญโญโญโญ Formulates the first principled joint order-token decoding search framework tailored to discrete diffusion language models.
  • Experimental Thoroughness: โญโญโญโญโญ Rigorous evaluation across four major benchmarks, two backbone models, comprehensive pruning ablations, compute scaling curves, and constraint boundary analyses.
  • Writing Quality: โญโญโญโญโญ Clear theoretical motivation, elegant algorithmic formulations, and exceptional visual illustrations.
  • Value: โญโญโญโญโญ Establishes a foundational test-time scaling paradigm for diffusion language models.