On the $ε$-Free Inference Complexity of Absorbing Discrete Diffusion

This paper introduces Absorbing-Aware Truncated Uniformization (AATU), a novel inference algorithm for absorbing discrete diffusion that achieves $\epsilon$-TV convergence with $\mathcal{O}(d \ln d)$ complexity independent of the error tolerance $\epsilon$, thereby strictly outperforming existing uniform baselines and eliminating restrictive bounded-score assumptions.

The Gist

The Big Picture: Fixing the "Re-doing Work" Problem

Imagine you are a chef trying to recreate a perfect, complex dish (like a lasagna) from a bowl of completely mixed-up, unrecognizable ingredients. This is what Diffusion Models do for text and images: they start with pure noise and slowly "denoise" it back into something meaningful.

There are two main ways to do this "un-mixing" process:

1. Uniform Diffusion (The Old Way): Imagine you have a bowl of mixed ingredients. You taste a spoonful, fix it, taste it again, fix it again, and keep tasting and fixing the same spoonful over and over until it's perfect. Even if the spoonful was already perfect, you might taste it again just to be sure. This is safe, but it's incredibly slow and wasteful.
2. Absorbing Diffusion (The New Way): Imagine you have a bowl where the "bad" ingredients (noise) are marked with a special "Do Not Touch" sticker (the Absorbing State). Your job is to only fix the ingredients without the sticker. Once an ingredient is fixed, it gets the sticker, and you never touch it again. You move on to the next bad ingredient.

The Problem: While the "Absorbing" method (Method 2) works much better in real life, scientists couldn't prove why it was theoretically faster. They thought it was just as slow as the old "Uniform" method because the math was too messy.

The Breakthrough: This paper proves that the "Absorbing" method is actually a super-efficient shortcut. It shows that because you never have to re-fix a piece of text that is already correct, you can generate high-quality results much faster, with a complexity that doesn't get worse even if you demand extreme perfection.

---

Key Concepts Explained with Analogies

1. The "Redundant Re-denoising" Trap

In the old Uniform Diffusion method, the computer acts like a nervous perfectionist. It looks at a sentence, fixes a word, then looks at the whole sentence again. Even if that word is now perfect, the algorithm might try to "fix" it again because it doesn't know it's already done.

• Analogy: It's like a painter who paints a wall, then immediately paints over the same spot again, and again, just to make sure the color is right. They waste time re-painting areas that are already dry and perfect.

2. The "Absorbing" Advantage

In Absorbing Diffusion, once a word is generated correctly, it becomes "absorbed." It turns into a "ghost" that the algorithm ignores. The algorithm only focuses on the remaining "noise" (the missing or wrong words).

• Analogy: Imagine a game of "Whac-A-Mole." In the old way, you might hit the same mole twice. In the absorbing way, once you hit a mole, it disappears forever. You only have to hit the ones that are still popping up. You never waste a swing on a mole that's already gone.

3. The New Algorithm: AATU (Absorbing-Aware Truncated Uniformization)

The authors created a new tool called AATU. Think of AATU as a smart manager for the "Whac-A-Mole" game.

• What it does: It looks at the board, sees exactly how many moles are left, and calculates the exact speed needed to finish the game.
• The "Truncation" Trick: Previous methods were afraid to move too fast because they didn't know if the "score" (how much work is left) was too high. AATU is brave; it says, "If the score is too high, we'll just cap it and move on." This removes the need for strict, limiting rules that slowed down previous methods.
• The Result: The paper proves that AATU can finish the job in time proportional to the length of the text ($d$), regardless of how perfect you want the result to be ($\epsilon$).
  • Old Math: "To get 99.9% perfect, you need 100 steps. To get 99.99% perfect, you need 1,000 steps." (The time grows as you demand more perfection).
  • New Math (AATU): "To get 99.9% perfect, you need 100 steps. To get 99.99% perfect, you still need 100 steps." (The time stays the same because we stop re-doing work).

4. The "Lazy Update" & Random Order

The paper also shows that if you use a specific type of model (Time-Invariant), you can be even lazier.

• Analogy: Imagine you have a list of 100 broken toys to fix.
  • Standard way: You check the list, pick a toy, fix it, check the list again, pick another.
  • Lazy way (AATU): You realize that since you never fix the same toy twice, you can just pick a toy at random, fix it, and throw it in the "Done" pile. You don't need to re-check the "Done" pile.
  • The Magic: The authors prove that picking toys in a random order is actually the most efficient way to do this, and it guarantees the final result is perfect. This explains why many modern AI models work well even when they don't follow a strict order.

---

Why This Matters

1. Speed: This proves that "Absorbing" diffusion models (which are already popular in AI) are theoretically the fastest way to generate text. They don't just feel faster; the math proves they are.
2. Efficiency: It removes the "cost of perfection." In the past, if you wanted a slightly better AI output, you had to wait much longer. With this method, you get high-quality results without the extra wait time.
3. Simplicity: It validates the use of "random order" generation. Instead of trying to force the AI to write word-by-word from left to right (like a human), it's okay to fill in the blanks in any random order, as long as you don't touch the ones that are already filled.

The Bottom Line

This paper is the "proof of concept" that finally explains why Absorbing Diffusion is a winner. It shows that by simply stopping the habit of re-fixing things that are already right, we can generate text faster, cheaper, and with higher quality than ever before. It turns a messy, repetitive process into a clean, one-time fix for every single word.

Technical Summary

1. Problem Statement

Discrete diffusion models have emerged as a powerful alternative to autoregressive models for generating discrete data (e.g., text). There are two primary forward process paradigms:

1. Uniform Diffusion: The forward process converges to a uniform stationary distribution.
2. Absorbing Diffusion: The forward process converges to an absorbing state (e.g., a [MASK] token), where tokens are gradually corrupted until they become indistinguishable.

The Gap: While absorbing discrete diffusion empirically outperforms uniform diffusion, its theoretical understanding lags behind. Existing theoretical analyses for uniform diffusion establish a query complexity of $O(d \ln(d/\epsilon))$ to achieve $\epsilon$-Total Variation (TV) convergence. Recent attempts to analyze absorbing diffusion (e.g., Liang et al., 2025) failed to improve upon this $\epsilon$-dependence, often requiring restrictive bounded-score assumptions (assuming the neural network's output scores are bounded by a constant). Consequently, theory has not yet explained the empirical efficiency gains of absorbing diffusion.

Core Challenge: Can we theoretically prove that absorbing diffusion achieves faster convergence (specifically, independence from $\epsilon$) without relying on unrealistic bounded-score assumptions?

2. Methodology

The authors propose Absorbing-Aware Truncated Uniformization (AATU), a novel inference algorithm that leverages the structural properties of absorbing diffusion.

A. Structural Insight: Single-Pass Denoising

The key theoretical observation is the difference in "outgoing rates" between the two paradigms during the reverse (denoising) process:

• Uniform Diffusion: The model may repeatedly attempt to "re-denoise" tokens that are already valid, leading to redundant computations. The outgoing rate is bounded by a term proportional to $d$ (dimension) regardless of the current state.
• Absorbing Diffusion: The reverse process only updates tokens that are currently in the absorbing state (masked). Once a token is denoised, it remains valid and is never touched again.
• Implication: The expected number of transitions (and thus score evaluations) in absorbing diffusion is strictly lower because the "outgoing rate" decreases as the number of remaining masked tokens decreases.

B. The AATU Algorithm

To exploit this without assuming bounded scores, the authors introduce a state-dependent truncation mechanism:

1. Truncated Uniformization: Standard uniformization simulates a Continuous-Time Markov Chain (CTMC) by sampling Poisson jump times. The efficiency depends on an upper bound $\beta_t$ for the total outgoing rate.
2. State-Dependent Threshold: Instead of using a fixed global constant for $\beta_t$ (which requires bounded scores), AATU sets $\beta_t$ based on the current number of absorbing tokens, $num_K(y)$:
   $$\beta_t(y) \approx num_K(y) \cdot \frac{K}{e^{T-t} - 1}$$
3. Truncation: If the estimated neural score implies a rate higher than $\beta_t(y)$, the rate is truncated. This ensures the simulation remains unbiased and valid without requiring the neural network to be globally bounded.
4. Lazy Updates (Time-Invariant Case): For time-invariant parameterizations (where the score depends only on the state, not time), the authors show that AATU naturally induces an iterative imputation algorithm with a uniformly randomized denoising order. By caching scores (lazy updates), the complexity drops further.

3. Key Contributions

1. $\epsilon$-Free Complexity Bound:
   The authors prove that AATU achieves $\epsilon$-TV convergence with a complexity of $O(d \ln d)$, which is independent of the error tolerance $\epsilon$.

   • Contrast: Uniform diffusion baselines require $O(d \ln(d/\epsilon))$, incurring a $\ln(1/\epsilon)$ overhead.
   • Significance: This confirms that absorbing diffusion is theoretically superior in high-precision regimes.

2. Elimination of Bounded-Score Assumptions:
   Previous uniformization-based analyses required the assumption that neural scores are bounded by a constant. AATU removes this restrictive assumption by using the state-dependent truncation, making the theory applicable to practical, unbounded neural networks.

3. Connection to Iterative Imputation:
   The paper bridges the gap between uniformization-based samplers and iterative imputation algorithms (common in masked language models). It proves that applying AATU to time-invariant parameterizations naturally results in an algorithm equivalent to iterative imputation with a randomized denoising order.

4. Optimal Complexity for Time-Invariant Settings:
   For time-invariant parameterizations coupled with a lazy update strategy, the complexity is reduced to $O(d)$ discrete score evaluations. This is because each token is denoised exactly once, and scores can be reused.

4. Results

Theoretical Results

• Theorem 4.2: Under standard assumptions (well-trained scores, no masks in target distribution), AATU achieves TV distance $\le 2\epsilon$ with an expected number of score calls upper-bounded by:
  $$2K(d - \epsilon^2/4) + 12Kd \ln d$$
  This bound is $O(d \ln d)$ and does not scale with $\ln(1/\epsilon)$.
• Corollary 4.3: Even if the target distribution contains some absorbing states (violating the strict assumption), the complexity remains favorable, scaling with the expected number of initial masks.
• Theorem 5.1: For time-invariant parameterizations with lazy updates, the complexity is strictly $O(d)$.

Empirical Results

• Synthetic Data: Experiments on small vocabularies ($K=3, d=4$) show that AATU converges to the target distribution significantly faster (in terms of Number of Function Evaluations, NFE) than uniform baselines. The "Stopping NFE" (steps to terminate) is drastically lower for the absorbing method.
• Real-World Text Generation: Applied to a text generation task (following SEDD benchmarks), AATU (adapted for practical constraints) achieved lower Perplexity (PPL) and Entropy compared to Euler and $\tau$-leaping baselines, validating the theoretical efficiency gains in a high-dimensional setting ($d=1024$).

5. Significance and Impact

• Theoretical Foundation: This work provides the first rigorous theoretical justification for the empirical success of absorbing discrete diffusion, confirming its efficiency advantage over uniform diffusion in high-accuracy regimes.
• Algorithmic Improvement: AATU offers a practical sampling algorithm that avoids the computational redundancy of re-denoising valid tokens, directly translating to faster inference times.
• Paradigm Shift: By linking uniformization theory to iterative imputation, the paper unifies two major classes of discrete diffusion inference methods, suggesting that random denoising orders are not just heuristic but theoretically grounded.
• Scalability: The $\epsilon$-free complexity suggests that generating high-quality discrete data (e.g., long sequences of text) with diffusion models is computationally more feasible than previously theorized, potentially making them more competitive with autoregressive models.

In summary, the paper resolves a critical theoretical gap by demonstrating that the "absorbing" mechanism inherently prevents redundant computation, allowing for inference complexity that is independent of the desired precision ($\epsilon$) and free from restrictive mathematical assumptions.