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, discrete diffusion, joint search, likelihood estimation, test-time compute
TL;DR¶
Addressing the exploration-exploitation dilemma in masked diffusion language models where heuristic decoders either collapse into narrow trajectories or explore blindly, this paper proposes Order-Token Search, a decoding algorithm that jointly explores generation order and token space using a stable incremental denoising action likelihood estimator to achieve massive gains across mathematical reasoning and code synthesis without post-training.
Background & Motivation¶
Discrete Masked Diffusion Models (MDMs) have emerged as a compelling alternative to autoregressive architectures for natural language generation. Unlike autoregressive models constrained by strictly causal left-to-right factorization, MDMs generate text via bidirectional parallel denoising over fully masked canvases, allowing tokens to be filled, revised, or reordered adaptively according to semantic context. This order-agnostic flexibility theoretically grants diffusion models access to an immense space of decoding trajectories, making the choice of generation order a central degree of freedom in decoding algorithm design.
However, existing decoding strategies for MDMs remain restricted to committing to a single trajectory per generation run. Empirically, standard heuristic decoders occupy opposite ends of an exploration-exploitation trade-off. Low-confidence remasking prioritizes exploitation by greedily committing to high-confidence tokens while only revising uncertain positions; this produces reasonable single-sample accuracy (pass@1) but causes rapid trajectory collapse and sluggish scaling across sample budgets (pass@k). Conversely, training-time random remasking explores diverse order-token paths and exhibits steep pass@k curves, but achieves very weak pass@1 because it lacks any mechanism to distinguish high-quality candidates from suboptimal ones. Meanwhile, autoregressive decoding completely discards the order-agnostic advantage of diffusion models by enforcing fixed causal generation.
To convert the latent multi-trajectory potential of diffusion models into high-quality deterministic outputs, the central challenge is designing a principled search and pruning mechanism over partial diffusion trajectories. Standard full-sequence likelihood estimation is fatally unstable when applied to intermediate diffusion states: with numerous positions still masked, global infilling evaluations suffer from high variance and penalize valid candidates prematurely. Core idea: formulate discrete diffusion decoding as beam search over the joint space of generation orders and token values, and score candidates using an incremental denoising action likelihood estimator conditioned on model-predicted full-sequence context for stable pruning.
Method¶
Overall Architecture¶
Order-Token Search (OTS) is tailored for discrete masked diffusion models, maintaining a beam of size \(K\) partially denoised candidate sequences and alternating between joint action expansion and likelihood-based pruning. To ensure computational tractability, OTS incorporates the block diffusion framework: generation sequences are partitioned into fixed-size blocks, where parallel diffusion operates within each block and search-pruning interventions occur at block boundaries. This effectively collapses the number of search branching decisions from the total diffusion steps \(S\) down to the number of blocks \(B\).
At each search interval, the algorithm proposes diverse denoising actions across both dimensions for each candidate in the beamโsimultaneously selecting which masked positions to reveal (generation order) and what specific tokens to instantiate (token values). A specialized likelihood estimator then computes the incremental transition log-likelihood of each proposed denoising action. Candidates accumulate action scores along their trajectory, and only the Top-\(K\) best candidates are retained. Upon processing all blocks, the sequence with the highest cumulative likelihood is returned as the final output.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Initial Fully Masked Beam<br/>K identical masked canvas states"] --> B["Block Boundary Joint Expansion<br/>Propose actions over order and token space"]
B --> C["Incremental Denoising Action Scoring<br/>Conditional re-masking and log-likelihood evaluation"]
C --> D["Trajectory Score Accumulation & Pruning<br/>Retain Top-K candidates via cumulative score"]
D -->|More blocks remaining| B
D -->|All blocks completed| E["Final Best Sequence Output<br/>Select candidate with highest cumulative likelihood"]
Key Designs¶
1. Block Boundary Joint Expansion: Branching over both generation order and token choices
Traditional autoregressive beam search branches exclusively over candidate token vocabulary at a fixed causal position, whereas conventional MDM decoders follow fixed single-trajectory heuristics. OTS unifies both dimensions at each block boundary. For an interval transitioning from a more corrupted state \(x_t\) to a less corrupted state \(x_s\) (\(0 \le s < t \le 1\)), the model first samples a full-sequence prediction \(x_0 \sim p_\theta(\cdot \mid x_t)\) by adding Gumbel noise with temperature \(\tau\) to logits. The algorithm then transfers tokens according to the denoising schedule, identifying newly revealed positions: $\(\Delta(s, t) = \{i \mid x_{t,i} = \text{MASK} \land x_{s,i} \neq \text{MASK}\}\)$ By drawing multiple samples, OTS generates competing partial trajectory candidates that diverge in both which positions are updated (\(\Delta(s, t)\)) and which tokens are inserted, escaping local greedy traps.
2. Incremental Denoising Action Scoring: Low-variance action likelihood under predicted context
Directly evaluating the global reconstruction likelihood \(p_\theta(x_0 \mid x_t)\) at intermediate diffusion steps produces severe variance: when many tokens remain masked, the model faces an unnatural global infilling challenge that does not match its training dynamics. Instead of scoring full sequences, OTS isolates and evaluates the incremental denoising action itself. It retains the model-predicted full sequence \(x_0\) as surrounding context, but re-masks only the newly revealed positions \(\Delta(s, t)\) to form \(\tilde{x}_0 = \text{mask}(x_0, \Delta(s, t))\). The transition score is then computed as the expected log-probability of recovering the revealed tokens given this contextualized state: $\(s(x_t; x_s) = \mathbb{E}_{x_0} \left[ \log p_\theta(x^{\Delta(s,t)}_0 \mid \tilde{x}_0) \right]\)$ This design conditions on the model's own future predictions to provide coherent context, while strictly confining scoring to the decisions made during the current step, avoiding unfair global penalties.
3. Trajectory Score Accumulation & Pruning: Stable tracking of globally optimal trajectories
To maintain a competitive beam across multi-stage generation, OTS aggregates the incremental step scores across all active branching intervals \(I\): $\(S(\text{candidate}) = \sum_{(s, t) \in I} s(x_t; x_s)\)$ This cumulative score reflects the total model support for the entire sequence of denoising actions along a trajectory. After expanding to \(K^2\) candidate branches per step, the algorithm executes Top-\(K\) pruning based on \(S\). Because branching occurs only at block boundaries \(B\) rather than every denoising step \(S\), total function evaluations scale as \(\mathcal{O}(S \cdot K \cdot L + B \cdot K^2 \cdot L)\) rather than \(\mathcal{O}(S \cdot K^2 \cdot L)\), achieving structured trajectory pruning with compute comparable to a 5-sample majority voting baseline.
Loss & Training¶
Order-Token Search is an entirely training-free, inference-time decoding algorithm. It operates directly on pre-trained or post-trained discrete masked diffusion language models (e.g., LLaDA-8B-Instruct, LLaDA-1.5, Dream7B) using standard parameterizations \(p_\theta(x_0 \mid x_t)\). In experimental benchmarks, the default configuration sets block size to 32, beam size \(K \in \{3, 4, 5\}\), Gumbel temperature \(\tau \in [0.2, 1.0]\), and follows the standard generation schedule where generation length equals twice the number of diffusion steps (\(\text{gen\_len} = 2 \times \text{diffusion\_steps}\)).
Key Experimental Results¶
Main Results¶
Evaluations were conducted across three mathematical reasoning benchmarks (GSM8K, MATH500, Countdown) and one code synthesis benchmark (HumanEval), utilizing LLaDA-8B-Instruct and the RL-tuned LLaDA-1.5 as backbones.
| Dataset | Metric (Avg) | Ours (OTS, LLaDA) | Low-conf. Remasking | Random Remasking | Autoregressive (AR) | AR + Beam Search | Prev. SOTA (diffu-GRPO, L=512) |
|---|---|---|---|---|---|---|---|
| GSM8K | Accuracy (%) | 70.1 | 67.0 | 54.2 | 62.3 | 68.7 | 81.9 (OTS: 83.3) |
| MATH500 | Accuracy (%) | 32.8 | 29.0 | 20.5 | 26.0 | 31.0 | 39.2 (OTS: 42.4) |
| Countdown | Accuracy (%) | 28.4 | 20.5 | 11.0 | 12.7 | 21.2 | 37.1 (OTS: 25.4) |
| HumanEval | Accuracy (%) | 27.4 | 20.6 | 21.1 | 23.0 | 27.3 | 34.8 (OTS: 37.2) |
| Overall Avg | Accuracy (%) | 39.7 | 34.3 | 26.7 | 31.0 | 37.1 | - |
On the post-trained LLaDA-1.5 backbone, Order-Token Search reaches an overall average accuracy of 40.4% (compared to 34.5% for Low-confidence, 37.2% for Low-conf + MV, and 36.1% for AR + beam-search). At sequence length 512, inference-time OTS consistently surpasses diffu-GRPO post-training on GSM8K (83.3% vs 81.9%), MATH500 (42.4% vs 39.2%), and HumanEval (37.2% vs 34.8%).
Ablation Study¶
To verify the necessity of the proposed incremental likelihood estimator, the authors compared alternative pruning scorers under an identical branching and search pipeline on LLaDA:
| Config | Overall Avg (%) | GSM8K (Avg) | MATH500 (Avg) | Countdown (Avg) | HumanEval (Avg) | Note |
|---|---|---|---|---|---|---|
| Order-Token Search (Full) | 39.7 | 70.1 | 32.8 | 28.4 | 27.4 | Incremental action score with predicted context (Eq. 3) |
| w/ OTS Future Blocks | 33.9 | 66.3 | 29.7 | 17.4 | 22.3 | Masks future blocks, evaluating without predicted context |
| w/ OTS All Blocks | 32.6 | 65.1 | 28.5 | 16.2 | 20.4 | Joint likelihood over all revealed blocks so far |
| w/ CumProb Pruning | 38.0 | 69.9 | 30.6 | 25.5 | 25.8 | Pruning via accumulated token log-probabilities |
| AR-style Token Search (3x) | - | 8.5 (L=256) | 3.8 (L=256) | 0.0 (L=256) | 0.6 (L=256) | Fixed order token search with AR-style scorer; collapses |
| AR-style Order Search (3x) | - | 79.2 (L=256) | 35.8 (L=256) | 15.2 (L=256) | 32.9 (L=256) | Search order only with AR-style scorer; high cost |
Key Findings¶
- Incremental action likelihood is critical for effective pruning: OTS All Blocks (scoring the entire revealed prefix at once) drops overall accuracy by 7.1%, while OTS Future Blocks (removing future predicted context) drops accuracy by 5.8%. On Countdown, performance plunges from 28.4% to 16.2% and 17.4%, proving that conditioning on model-predicted future context while isolating current action tokens is essential for robust ranking.
- Joint order-token search significantly outperforms order-only or token-only variants: The AR + beam-search baseline (equivalent to block size = 1 with fixed left-to-right order) achieves only 37.1% overall accuracy. Directly porting AR causal token likelihood into token-only search causes catastrophic failure (0.0% on Countdown), showing that bidirectional diffusion models cannot be pruned using causal prefix assumptions.
- Compute scaling efficiency outperforms majority voting: Under matched Number of Function Evaluations (NFE), OTS with beam size 6 achieves 29.3% accuracy on Countdown, whereas AR + Majority Voting (5 samples) and Random + Majority Voting reach only 19.9% and 18.4%. Furthermore, wall-clock measurements show OTS (4 beams) is roughly 2x faster than 5-sample majority voting.
- Cross-architecture generalization: On Dream7B, which employs an entirely different diffusion training recipe, OTS attains the highest overall average of 42.7% (beating AR+MV at 42.2% and Low-conf at 39.5%). On MuSR soft-reasoning narratives, OTS achieves 56.8% accuracy, demonstrating benefits beyond formal mathematics and code.
Highlights & Insights¶
- Resolving the exploration-exploitation dilemma in DLM decoding: Explicitly demonstrates why standard decoders stallโlow-confidence over-commits into trajectory collapse, while random remasking explores without selectionโand bridges this gap via structured beam exploration.
- Elegant contextualized action re-masking: Solves the long-standing instability of likelihood estimation on noisy intermediate states by temporarily re-masking only newly revealed tokens against the backdrop of the model's global prediction.
- Test-time compute scaling rivaling post-training: Demonstrates that structured inference-time search can match or exceed the accuracy gains of intensive reinforcement learning post-training (diffu-GRPO), providing a clean test-time compute knob for discrete diffusion.
Limitations & Future Work¶
- Inference latency overhead: While block diffusion prevents quadratic step scaling, maintaining \(K\) candidates and performing \(K^2\) evaluations still incurs 2x-3x higher latency than a single greedy pass.
- Bottlenecks on hard global constraint satisfaction: On 4ร4 Sudoku, where token likelihoods correlate poorly with global grid consistency constraints, all decoding methodsโincluding OTS, beam search, and ARโsaturate at near-random performance (~10%-15%), revealing that inference-time search cannot compensate for missing model-level constraint representations.
- Static scoring heuristic: Pruning relies entirely on the base model's intrinsic logit distributions; integrating learned process verifiers (PRMs) or task-specific value heads could further sharpen trajectory selection.
Related Work & Insights¶
- vs. Low-Confidence Remasking: Low-confidence decoding commits greedily to locally confident tokens and cannot recover when early tokens lead to dead ends; OTS explores multiple competing paths simultaneously and prunes globally unpromising ones.
- vs. Autoregressive Beam Search: Autoregressive beam search is fundamentally restricted to token choices along a strictly unidirectional timeline; OTS operates on the joint space of generation order and token values, unlocking the bidirectional capabilities of diffusion models.
- vs. Majority Voting (Self-Consistency): Majority voting aggregates unguided, independently sampled complete sequences at the end of generation; OTS intervenes at intermediate generation stages to prune suboptimal branches early, yielding higher accuracy under matched compute budgets.
Rating¶
- Novelty: โญโญโญโญโญ Formulates the first unified search framework over generation order and token space for discrete diffusion language models with a dedicated action likelihood estimator.
- Experimental Thoroughness: โญโญโญโญโญ Rigorous comparisons across four reasoning benchmarks, two model families (LLaDA, Dream7B), extensive NFE compute-matching, diversity metrics, and failure diagnostics.
- Writing Quality: โญโญโญโญโญ Exceptionally clear framing of the exploration-exploitation trade-off with thorough methodological derivations and transparent ablations.
- Value: โญโญโญโญโญ Establishes structured test-time search as an essential scaling paradigm for diffusion language models.