Beyond Scattered Acceptance: Fast and Coherent Inference for DLMs via Longest Stable Prefixes — part 1/3

Cleaned-text code points [0, 15483). Bibliography omitted here; source.md includes it.

# Beyond Scattered Acceptance : Fast and Coherent Inference for DLMs via Longest Stable Prefixes

###### Abstract

Diffusion Language Models (DLMs) promise highly parallel text generation, yet their practical inference speed is often bottlenecked by suboptimal decoding schedulers. Standard approaches rely on “scattered acceptance”—committing high-confidence tokens at disjoint positions throughout the sequence. This approach inadvertently fractures the Key-Value (KV) cache, destroys memory locality, and forces the model into costly, repeated repairs across unstable token boundaries. To resolve this, we present the Longest Stable Prefix (LSP) scheduler, a training-free and model-agnostic inference paradigm based on monolithic prefix absorption . In each denoising step, LSP evaluates token stability via a single forward pass, dynamically identifies a contiguous left-aligned block of stable predictions, and snaps its boundary to natural linguistic or structural delimiters before an atomic commitment. This prefix-first topology yields dual benefits: systemically, it converts fragmented KV cache updates into efficient, contiguous appends; algorithmically, it preserves bidirectional lookahead over a geometrically shrinking active suffix, drastically reducing token flip rates and denoiser calls. Extensive evaluations on LLaDA-8B and Dream-7B demonstrate that LSP accelerates inference by up to 3.4 × \times across rigorous benchmarks—including mathematical reasoning, code generation, multilingual (CJK) tasks, and creative writing—while matching or slightly improving output quality. By fundamentally restructuring the commitment topology, LSP bridges the gap between the theoretical parallelism of DLMs and practical hardware efficiency.

## 1 Introduction

Diffusion Language Models (DLMs) have emerged as a compelling alternative to autoregressive generation, offering an intrinsically parallel inference process that leverages bidirectional context ( Austin et al., 2021a ) . This paradigm holds the promise of significant latency reductions over traditional one-token-at-a-time decoding. However, this promise remains largely unfulfilled in practice. The iterative refinement process, central to DLM generation, is frequently bottlenecked not by the model’s architecture, but by the strategy used to commit intermediate predictions. This creates a stark paradox: models designed for parallelism are often constrained by the sequential nature of their own convergence.

At the heart of this inefficiency lies the prevalent strategy of scattered acceptance , where tokens are committed independently based on local confidence ( Nie et al., 2025 ) or in fixed-size, semi-autoregressive blocks ( Arriola et al., 2025 ) . This approach is fundamentally costly in two distinct ways. First, from an algorithmic perspective , it creates a fragmented sequence of frozen and mutable tokens. The numerous boundaries between these regions are unstable, requiring repeated, localized repairs that slow the convergence to a globally coherent output. Second, from a systems perspective , this fragmentation shatters the Key-Value (KV) cache into small, non-contiguous segments, destroying the memory locality that is critical for efficient Transformer inference. Consequently, the active (uncommitted) portion of the sequence remains long, keeping attention computationally expensive for many iterations.

In this work, we argue that overcoming this bottleneck requires a new commitment topology. We introduce the Longest Stable Prefix (LSP), a training-free, model-agnostic scheduling paradigm founded on the principle of monolithic prefix absorption . Instead of accepting scattered islands of confident tokens, LSP identifies and commits the longest contiguous, stable prefix of the remaining active sequence in a single atomic step. This is achieved through a lightweight, single-pass procedure: (1) it computes a logit margin score for each active position; (2) it adaptively selects a margin threshold to target a fractional block size (e.g., 25–50% of the active suffix); and (3) it snaps the candidate block’s boundary to a nearby structural delimiter (e.g., punctuation or a newline) before committing. A simple fallback rule guarantees progress by committing at least one token per iteration, even when the model is highly uncertain.

This prefix-first geometry fundamentally alters the computational dynamics of DLM inference. By design, the frozen prefix grows as a single, contiguous block. This maximizes KV cache reuse and ensures subsequent attention queries are focused on a rapidly shrinking active suffix. The adaptive thresholding strategy encourages the active sequence length to decay geometrically, leading to a near-quadratic total work complexity that scales gracefully with sequence length. Algorithmically, committing structurally-aligned monolithic blocks minimizes the cross-boundary conflicts inherent in scattered acceptance, reducing the number of repair cycles needed to achieve a coherent state.

Our contributions are threefold: • We identify scattered acceptance as a primary bottleneck in DLM inference and propose monolithic prefix absorption as a more efficient commitment topology. We instantiate this principle in LSP, a novel, training-free scheduler that uses a single forward pass, adaptive thresholding, and structural snapping to commit the longest stable prefix.

• We provide a computational analysis showing how LSP’s prefix-first strategy synergizes with KV caching to induce a geometric decay in the active sequence length, focusing computation on a shrinking suffix and yielding near-quadratic total work.

• Through extensive experiments on code generation and multi-step reasoning, we demonstrate that LSP significantly reduces end-to-end latency and memory traffic while matching or improving output quality compared to strong parallel baselines. Ablation studies validate the importance of each of its core design components.

## 2 Related Work

### 2.1 Diffusion Large Language Model

Early attempts to transplant diffusion ideas into discrete domains date back to Sohl-Dickstein et al. (2015) and Hoogeboom et al. (2021) . Building on these foundations, D3PM ( Austin et al., 2021a ) introduced a unifying probabilistic view in which a discrete-state Markov forward process progressively corrupts clean sequences and a parameterized reverse model is trained via an ELBO objective to reconstruct text from noisy inputs. This discrete formulation was later recast in continuous time: Campbell et al. (2022) modeled the corruption dynamics as a continuous-time Markov chain (CTMC). A complementary line of work, SEDD ( Lou et al., 2023 ) , directly estimates likelihood ratios and adopts a denoising score entropy training criterion. Recent analyses—spanning MDLM ( Shi et al., 2024 ; Sahoo et al., 2024 ; Zheng et al., 2024 ) and RADD ( Ou et al., 2024 ) —further reveal that multiple parameterizations of masked/discrete diffusion models are mathematically equivalent, clarifying relationships among prior formulations.

Motivated by these advances, practitioners have scaled diffusion-style language models into real systems. Commercial offerings include Mercury ( Labs et al., 2025 ) , Gemini Diffusion ( DeepMind, 2025 ) , and Seed Diffusion ( Song et al., 2025b ) , while LLaDA ( Nie et al., 2025 ) and Dream ( Ye et al., 2025 ) exemplify open-source counterparts. Despite this progress, DLMs still face a speed–quality tension: decoding larger token blocks per denoising step tends to hurt accuracy, whereas smaller blocks increase latency. Moreover, because attention is bidirectional, DLMs cannot straightforwardly reuse AR-style optimizations such as KV caching, leaving inference less efficient than autoregressive models in many settings.

### 2.2 Acceleration Methods for Diffusion Language Models

Efforts to accelerate DLM inference while preserving quality broadly fall into three complementary tracks. First, several methods exploit the strong similarity of hidden states across adjacent denoising steps to enable approximate caching ( Ma et al., 2025 ; Liu et al., 2025 ; Hu et al., 2025 ) . A closely related strategy restructures generation into semi-/block-autoregressive schedules so that past blocks (or contexts) can be cached and selectively refreshed during decoding ( Wu et al., 2025 ; Arriola et al., 2025 ; Song et al., 2025a ) . Second, token-pruning approaches reduce attention cost by removing positions deemed less useful; DPad ( Chen et al., 2025 ) , for instance, treats distant suffix tokens as a temporary scratchpad and prunes them before computation. Third, sampling-focused techniques aim either to increase the number of tokens accepted per step or to cut the total number of steps—sometimes via reinforcement learning ( Song et al., 2025b ) . Within this vein, the number of simultaneously decoded tokens can be governed by confidence/entropy criteria, adjusted online with denoising dynamics ( Wei et al., 2025 ; Huang and Tang, 2025 ) , dynamically tailor classifier-free guidance via low-confidence re-masking ( Li et al., 2025a ) , or be aligned with small auxiliary AR models ( Israel et al., 2025 ) , or paired with speculative decoding that drafts using the DLM itself ( Agrawal et al., 2025 ) .

Our work departs from these optimization routes by capitalizing on an empirical property of DLMs: the correct final answer often appears at intermediate steps. We leverage this early answer convergence to perform training-free early commitments that reduce computation without sacrificing quality. Concurrently, MidTruth ( Wang et al., 2025 ) also identifies early convergence but pursues temporal ensembling across steps to boost accuracy, whereas we develop an early-commit decoding scheme that shortens inference while maintaining performance. Closely related to our acceleration objective is Prophet ( Li et al., 2025b ) , which similarly introduces an early-commit decoding paradigm, albeit driven specifically by top-2 confidence gaps.

## 3 Method

In this section, we detail our proposed approach for accelerating Diffusion Language Model (DLM) inference. We begin by formalizing the standard discrete diffusion framework and pinpointing the inherent inefficiencies of conventional scheduling strategies. We then introduce the Longest Stable Prefix (LSP) scheduler, a training-free, model-agnostic paradigm designed to overcome these limitations. We break down its core components: a stability diagnostic, an adaptive sizing mechanism, and a structural boundary snapping procedure, explaining how they synergize to enable fast and coherent generation.

### 3.1 Preliminary

Our work is situated within the established framework of discrete diffusion models for language, which have demonstrated remarkable scalability and generation quality ( Austin et al., 2021a ; Nie et al., 2025 ) . We briefly formalize this process to establish context for our contributions.

##### Forward Corruption Process.

The process begins with a clean text sequence 𝐱 0 = ( x 0 1 , … , x 0 L ) \mathbf{x}_{0}=(x_{0}^{1},\dots,x_{0}^{L}) of length L L , sampled from the data distribution p data p_{\text{data}} . A forward Markov process gradually corrupts this sequence over a series of discrete timesteps t ∈ { 1 , … , T } t\in\{1,\dots,T\} . At each step t t , a subset of tokens in the sequence 𝐱 t − 1 \mathbf{x}_{t-1} is replaced by a special ‘[MASK]‘ token to produce a noisier sequence 𝐱 t \mathbf{x}_{t} . The transition probability, q ⁡ ( 𝐱 t | 𝐱 t − 1 ) q(\mathbf{x}_{t}|\mathbf{x}_{t-1}) , is designed such that the degree of masking increases monotonically with t t . By the final step, the sequence 𝐱 T \mathbf{x}_{T} is composed entirely of ‘[MASK]‘ tokens. A key property of this process is that the state at any intermediate step t t can be sampled directly from the original sequence via q ⁡ ( 𝐱 t | 𝐱 0 ) q(\mathbf{x}_{t}|\mathbf{x}_{0}) , which models the probability that each token in 𝐱 0 \mathbf{x}_{0} has been absorbed into the ‘[MASK]‘ state after t t steps. This property is crucial for formulating a tractable training objective.

##### Reverse Generation Process.

The goal of a DLM, parameterized by θ \theta , is to learn the reverse of this corruption process. Given a noisy sequence 𝐱 t \mathbf{x}_{t} , the model is trained to predict the original clean sequence 𝐱 0 \mathbf{x}_{0} by optimizing a loss function based on the negative log-likelihood of the ground-truth tokens, thereby learning the conditional distribution p θ ​ ( 𝐱 0 | 𝐱 t ) p_{\theta}(\mathbf{x}_{0}|\mathbf{x}_{t}) .

Sequence generation, or sampling, is an iterative procedure that inverts the forward process, starting from a fully masked sequence 𝐱 T \mathbf{x}_{T} . For each timestep t t from T T down to 1, a two-stage refinement is performed. First, in a prediction step , the model p θ p_{\theta} is called to predict the entire clean sequence from the current noisy state: 𝐱 ^ 0 ∼ p θ ( ⋅ | 𝐱 t ) \hat{\mathbf{x}}_{0}\sim p_{\theta}(\cdot|\mathbf{x}_{t}) . Second, in a re-masking step , a new, less noisy state 𝐱 t − 1 \mathbf{x}_{t-1} is constructed by combining information from the current state 𝐱 t \mathbf{x}_{t} and the prediction 𝐱 ^ 0 \hat{\mathbf{x}}_{0} .

##### The Inefficiency of Conventional Schedulers.

The critical decision in the re-masking step lies with the scheduling strategy , which determines which tokens from the prediction 𝐱 ^ 0 \hat{\mathbf{x}}_{0} are accepted (or "committed") and which positions are re-masked for further refinement. Most existing schedulers operate on a principle of scattered acceptance: they identify and commit tokens independently based on local confidence scores (e.g., high probability or low entropy). This approach, while intuitive, introduces profound inefficiencies. Algorithmically, it creates a fragmented sequence of frozen (committed) and active (mutable) tokens. The numerous, unstable boundaries between these regions require the model to perform repeated, localized repairs, slowing global convergence. Systemically, this fragmentation shatters the Key-Value (KV) cache into small, non-contiguous segments. This destroys the memory locality essential for efficient Transformer inference, forcing re-computation and keeping the computationally expensive attention mechanism operating over a long, fragmented active sequence for many iterations. This fundamental bottleneck motivates a new commitment topology.

### 3.2 The Longest Stable Prefix (LSP) Scheduler

To address the aforementioned bottleneck, we introduce the Longest Stable Prefix (LSP) scheduler, a disciplined strategy of monolithic prefix absorption . Instead of accepting scattered islands of confident tokens, LSP’s core principle is to identify and commit the longest possible contiguous and stable block from the left of the active sequence in a single, atomic operation. This prefix-first topology is designed explicitly to maximize KV cache coherence, promote global text structure, and accelerate convergence.

At any generation iteration k k , we partition the full sequence into two parts: a frozen prefix X F ( k ) X_{F}^{(k)} , which is cached and immutable, and an active suffix X A ( k ) X_{A}^{(k)} of length N k N_{k} , which is the target of the current refinement step. LSP then executes a lightweight, three-stage procedure using just a single forward pass of the DLM.

##### Single-Pass Prediction and Stability Assessment.