acceptodds
Under review as a conference paper at ICLR 2027

Vocabulary-size-independent Convergence of Discrete Diffusion Models: adjoint equations induce the right space

Abstract

Discrete diffusion has become a leading framework for generative modeling in various applications including language, vision, and biology. Existing convergence theory, however, exhibits fundamental limitations. KL-based analyses diverge under singular priors such as the masked distribution, while bounds in total variation (TV) depend on the vocabulary size and become vacuous for modern language tasks, where vocabularies contain hundreds of thousands of tokens. We develop a unified adjoint-equation-based framework that establishes vocabulary-size-independent convergence guarantees in any integral probability metric (IPM). To the best of our knowledge, our bounds are the first to be entirely free of and applicable to both masked and uniform priors. Importantly, our results can extend existing step complexity guarantees to any IPM. In addition, our theory relies only on a single standard rate-matrix regularity assumption and applies to general priors. Five novel techniques drive our improvements: 1. working in the space of observables via adjoint equations rather than directly with probability measures; 2. a regularity analysis that yields bounds on any IPM; 3. a coupling argument that removes -dependence under uniform transitions; and 4. score–marginal cancellation and 5. exit-routing techniques that remove -dependence under masked transitions. Our framework thus sharply departs from prior analyses and avoids the shortcomings of pathspace-KL and existing TV-based approaches. Beyond convergence bounds, our framework provides a versatile toolkit for further theoretical study of discrete diffusion models, including principled choices of loss functions and vocabulary-size-independent step complexity.

Primary area:
learning theory
Keywords:
Discrete Diffusion Models, Convergence Analysis

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_nsG6OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper develops an adjoint-equation framework for analyzing the convergence of score-based discrete diffusion models. By studying errors in observable expectations, it derives bounds for integral probability metrics in terms of initialization and score estimation errors. For masked and uniform transitions, the bounds have coefficients without explicit vocabulary-size dependence, using score–marginal cancellation, exit-rate estimates, and coupling arguments. The analysis also covers early stopping and provides expected step-complexity guarantees for uniformization under additional assumptions. The contribution is theoretical, supported by mathematical proofs rather than empirical experiments.

Critical strengths
  1. The observable-based formulation provides a unified way to separate initialization and score estimation errors and connect them to different IPMs (Lemma 3.2; Theorem 3.1). This makes the analysis useful beyond a single distributional metric.

  2. The score–marginal cancellation exposes an exit-rate coefficient rather than an entrance-rate coefficient, avoiding explicit vocabulary-size growth for masked transitions (Remark 3.2; Corollary E.7). Its interpretation as the expected number of forward jumps provides a useful explanation of how the dynamics affect the error bound (Remark E.8).

Critical weaknesses
  1. Corollary 3.4 omits an essential condition on the time grid. In Eq. (91), the factor (R−1)/log⁡R(R-1)/\log R, where R=max⁡ktk+1/tkR=\max_k t_{k+1}/t_k, is absorbed into a constant without requiring RR to remain bounded independently of the target accuracy. For a single-token masked model with β=1\beta=1 and exact scores, using one interval (δ,T](\delta,T] gives E[N]=(T−δ)/(eδ−1)\mathbb{E}[N]=(T-\delta)/(e^\delta-1). With δ≍ϵ\delta\asymp\epsilon and T≍log⁡(1/ϵ)T\asymp\log(1/\epsilon), this scales as log⁡(1/ϵ)/ϵ\log(1/\epsilon)/\epsilon, rather than the claimed logarithmic complexity. Thus, the stated sampling guarantee requires an explicit restriction on the grid.

  2. The adjoint argument needs a rigorous treatment of the singular endpoint at t=0t=0. Assumption 1 concerns the forward generator and does not ensure that Eq. (13) admits a bounded continuous solution for arbitrary initial observables. For a single-token masked model with data concentrated on a non-mask token aa, β=1\beta=1, and exact scores, the reverse unmasking rate is 1/(et−1)1/(e^t-1). Choosing ψ(a)=0\psi(a)=0 and ψ(m)=1\psi(m)=1 yields ϕm′(t)=−ϕm(t)/(et−1)\phi_m'(t)=-\phi_m(t)/(e^t-1), which has no bounded continuous solution satisfying ϕm(0)=1\phi_m(0)=1. This leaves a gap in the justification of Lemma E.1 and the subsequent error identity on [0,T][0,T]. A truncated-interval argument with a justified endpoint limit is needed; the example does not itself disprove the final distributional bound.

Questions for authors
  1. Does Corollary 3.4 require a time grid with R=max⁡ktk+1/tkR=\max_k t_{k+1}/t_k bounded independently of ϵ\epsilon? Please clarify how the factor (R−1)/log⁡R(R-1)/\log R in Eq. (91) is controlled and specify a grid that achieves the stated complexity. How does the statement account for the single-interval example described above?

  2. How is the adjoint equation in Eq. (13) defined at t=0t=0 when reverse rates are singular, as in the single-token masked example above? Can the authors justify the error identity by working on [δ,T][\delta,T] and passing to the limit δ→0\delta\to0, or specify the additional assumptions or boundary interpretation needed? Please clarify whether this changes the scope of Theorem 3.1.

3 comments

Q1. Time-grid condition in Corollary 3.4. We thank the reviewer. Corollary 3.4 indeed requires a grid whose ratio R=max⁡ktk+1/tkR=\max_k t_{k+1}/t_k is bounded independently of δ\delta; we have stated this assumption explicitly in the updated manuscript. A simple example to achieve this is tk+1=2tkt_{k+1}=2t_k, so (R−1)/log⁡R=1/log⁡2(R-1)/\log R = 1/\log 2 and the stated complexity holds.

Regular grid assumptions are standard in the literature. Theorem 3 of [1] and Theorem 4.9 of [2] similarly impose a regular grid condition in their step-complexity analyses of uniformization, for the constant schedule β=1\beta=1; we consider the more general variable schedule.

This assumption is not restrictive. Refining the grid will not increase the expected step complexity in uniformization. This is because grid points require no network evaluations, and only Poisson events do. Since the Poisson rate only needs to dominate the transition rate within each grid interval, a finer grid allows for a tighter Poisson rate on each interval, and hence fewer expected steps.

The single time interval example has R=T/δR=T/\delta and is excluded by this condition. It is also impractical. This is because a single Poisson rate must dominate the transition rate over the entire horizon [δ,T][\delta, T], resulting in a loose Poisson rate and inefficient simulation.

Q2 Singular endpoint at t=0t=0. We thank the reviewer for pointing this out. This case is already covered in the manuscript, and we will modify the manuscript to make it clearer.

To keep the presentation clear without introducing too many concepts at once, Sections 2, 3.1, and 3.2 first treat an idealized setting without early stopping, in which the data is fully supported at t=0t=0 and the reverse rates are bounded.

Section 3.3 (Eq. (20)) then presents the results with early stopping, which is essential when the data is not fully supported, as in masked diffusion, where the data has no mass on the all-masked sequence. In this setting, the reverse rates are bounded on [δ,T][\delta, T]. The derivation, including Lemma E.1, follows Section 3.1 verbatim with [0,T][0, T] replaced by [δ,T][\delta, T]. And the bound has an extra early-stopping term.

We emphasize that the early-stopping result appears later in Section 3 only for clarity of presentation. Our results already apply to the case the reviewer raised, including the singular endpoint in their example.

Q3 "The contribution is theoretical, supported by mathematical proofs rather than empirical experiments." We thank the reviewer, Please refer to the response to Q3 of reviewer ifzu.

[1] Liang, Y., Huang, R., Lai, L., Shroff, N., & Liang, Y. (2026). Absorb and converge: Provable convergence guarantee for absorbing discrete diffusion models. Advances in Neural Information Processing Systems (NeurIPS 2025), 38, 20283-20318.

[2] Ren, Y., Chen, H., Rotskoff, G., & Ying, L. (2025, May). How discrete and continuous diffusion meet: Comprehensive analysis of discrete diffusion models via a stochastic integral framework. In International Conference on Learning Representations (ICLR 2025), 42904-42941.

AuthorsOpenReview ↗

Follow-up on our responses

Dear Reviewer nsG6,

As the discussion period ends on November 18, we would be grateful to know whether our responses have addressed your concerns. We are happy to clarify anything further.

Best regards,

Authors

Thank you for the clarifications. The bounded-ratio grid condition addresses my concern about the uniformization complexity. The explanation of the early-stopping analysis also substantially alleviates my concern about the singular endpoint. Please make the assumptions and scope of the results without early stopping explicit in the revised manuscript. In light of these responses, I am updating my rating to 3 (weak acceptance).

Reviewer_ifzuOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes a unified framework based on the adjoint equations for convergence analysis of discrete diffusion models. The authors indicate their framework can be adapted to any integral probability metric and achieve vocabulary size S-free bound for masked and uniform rate. The authors also provide the early-stopping bounds and expected number of steps for uniformization sampler. Moreover, the authors state that their analysis only requires a regularity assumption for rate matrix. No experiments for validation are reported in this paper.

Critical strengths
  1. This paper proposes a unified framework based on the adjoint equations, which are applicable to different transition rates and evaluation metrics.

  2. The authors explain how the rate matrix and score ratios affect the dependence on S and therefore apply the existing-routing technique and score marginal cancellation to remove the S dependence.

Critical weaknesses
  1. Although this paper focuses on the theoretical analysis and does not include experiments, a small synthetic experiment will provide stronger supports for the theory and emphasize the contributions.

  2. Besides the regularity assumption of the rate matrix, Theorem 3.1 further requires s~∈[s/2,3s/2]\tilde{s}\in[s/2,3s/2], which is a point-wise score assumption. It is not trivial that this requirement can be guaranteed by an average small training loss.

Questions for authors
  1. Theorem 4 in Sharp Convergence Rates for Masked Diffusion Models (Liang et al., 2026) analyzes the First Hitting Sampler and also provides a S-independent bound. The authors only discuss their Theorem 2 in this paper. Can the author further clarify the differences between frameworks, assumptions, and conditions in two papers?

Liang, Y., Tan, Z., Shroff, N., & Liang, Y. (2026). Sharp convergence rates for masked diffusion models. arXiv preprint arXiv:2602.22505.

  1. Is the assumption s~∈[s/2,3s/2]\tilde{s}\in[s/2,3s/2] essential in the proof? Can the author discuss whether it can be replaced by a weaker assumption?

  2. A numerical experiment with different S will help valid the significance of the proposed framework. Can the authors provide corresponding experiments?

4 comments

Q1 Comparison with Theorem 4 of Liang et al 2026, in terms of framework and conditions.

Key differences:

Liang et al., Theorem 4

  • Setting: first-hitting sampler for the masked rate only, on the infinite horizon [0,∞)[0, \infty), stated in KL. In this setting, it is SS-free.
  • Key Technique: path-space KL with the data-processing inequality, as used in the KL-based works in our Table 1. On a finite horizon, their argument breaks down as the initial KL term is infinite (see also their discussion in Section 3.2).
  • Samplers: does not cover finite-horizon samplers such as τ\tau-leaping and uniformization. Their separate finite-horizon analysis in TV (Theorem 2) is SS-dependent, as we noted.

Ours

  • Setting: sampler-agnostic. masked, uniform, and general rates; SS-free for masked and uniform rates. Applies to all IPMs.

  • Key Technique: adjoint equation, which is new in discrete diffusion. The initial error is measured in TV, which stays finite.

    Our SS-free results directly extend to the infinite horizon setting of Liang et al., by letting T→∞T \to \infty in our finite-horizon bound, under their Assumption 2. In this case, the initialization error vanishes, the coefficient stays bounded, and the result remains SS-free.

  • Samplers: sampler-agnostic. Our results can be used to obtain step complexity for algorithms including uniformization and τ\tau-leaping (see Section 3.4). They also cover the first-hitting sampler with the infinite-horizon extension.

We have added the above discussion together with the infinite-horizon extension, to Appendix A of the updated draft.

Q2 Score-accuracy assumption. We thank the reviewer. Please refer to the response to Q1 of Reviewer 9kZm.

AuthorsOpenReview ↗

Rebuttal Part 2

Q3 Numerical Experiments.

We validate our theory with numerical experiments. We test it in a controlled setting where both the true score and the exact TV metric are computable. We construct synthetic data with sequence length d=5d=5, vocabulary size SS from 44 to 1638416384. We then multiply each entry of the true score by an independent log-normal factor eσZe^{\sigma Z}, Z∼N(0,1)Z\sim\mathcal N(0,1), at various noise levels σ\sigma. Each level yields roughly the same score-entropy loss across all vocabulary sizes.

We compare the generation error in TV with (i) our SS-free bound and (ii) the SS-dependent bound from Theorem 2 of [1].

We aggregate results over multiple seeded runs. We find:

  • The generation error is independent of SS and scales linearly in σ\sigma, as our bound predicts.
  • Our SS-free bound is in fact flat in SS and never violated in all testing. Also, we re-emphasize that, to the best of our knowledge, our result is the first sampler agnostic SS-free bound for masked diffusion with the exact prior.
  • The SS-dependent bound grows with S\sqrt{S} and can easily exceed 11, the maximum possible value of TV, becoming vacuous even under vocabulary size (S=10^3) far below realistic vocabulary sizes (S=10^5) and small training error σ=0.002\sigma=0.002

Thus the experiments both validate our theory and show the practical limitation of existing SS-dependent bounds. The table below reports the numbers; bold entries exceed 1 and are therefore vacuous.

Additional experimental results and more detailed discussion are provided in Section 3.5 of the updated manuscript.

σ\sigmaQuantityS=4S=8S=16S=32S=64S=128S=256S=512S=1024S=2048S=4096S=8192S=16384
0.002Bound (S-dependent)0.08560.1130.1630.2240.3260.4620.6410.9121.291.832.563.655.14
Bound (S-free, ours)0.01610.01510.01530.01490.01530.01540.01510.01520.01510.01520.01510.01520.0151
Empirical TV0.000469 ± 0.0000050.000509 ± 0.0000050.000565 ± 0.0000060.000555 ± 0.0000060.000577 ± 0.0000050.000589 ± 0.0000060.000573 ± 0.0000050.000583 ± 0.0000060.000585 ± 0.0000060.000575 ± 0.0000060.000584 ± 0.0000060.000594 ± 0.0000060.000587 ± 0.000006
0.01Bound (S-dependent)0.4310.570.8231.131.632.313.234.66.499.1912.918.626.1
Bound (S-free, ours)0.08120.07590.07750.07490.07650.0770.0760.07660.07640.07640.07610.07720.0767
Empirical TV0.00228 ± 0.000020.00251 ± 0.000030.00278 ± 0.000030.00276 ± 0.000030.00289 ± 0.000020.00293 ± 0.000030.00292 ± 0.000030.00295 ± 0.000030.00295 ± 0.000030.00292 ± 0.000030.00289 ± 0.000030.00292 ± 0.000030.00294 ± 0.00003
0.05Bound (S-dependent)2.262.974.295.838.4812.116.723.93447.967.895.9136
Bound (S-free, ours)0.4250.3950.4040.3880.3990.4020.3940.3980.3990.3980.3990.3990.401
Empirical TV0.0115 ± 0.00010.0126 ± 0.00010.0142 ± 0.00010.0138 ± 0.00010.0143 ± 0.00010.0145 ± 0.00010.0143 ± 0.00010.0147 ± 0.00010.0147 ± 0.00010.0146 ± 0.00010.0142 ± 0.00010.0147 ± 0.00010.0146 ± 0.0001

[1] Liang, Y., Tan, Z., Shroff, N., & Liang, Y. (2026). Sharp convergence rates for masked diffusion models. arXiv preprint arXiv:2602.22505.

AuthorsOpenReview ↗

Follow-up on our responses

Dear Reviewer ifzu,

As the discussion period ends on November 18, we would be grateful to know whether our responses have addressed your concerns. We are happy to clarify anything further.

Best regards,

Authors

Thank you very much for the clarifications. I maintain my positive rating.

Reviewer_9kZmOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper develops a convergence analysis framework for score-based discrete diffusion models using adjoint equations. The authors establish vocabulary-size-independent convergence bounds for both uniform and masked transition rates, including singular masked priors for which conventional KL analyses may become problematic. The framework provides bounds in integral probability metrics, including total variation, Wasserstein-1, and maximum mean discrepancy. The authors further derive early-stopping guarantees and complexity bounds for uniformization-based sampling.

Critical strengths
  1. This work removes the explicit vocabulary-size dependence from convergence bounds, which is valuable, particularly for discrete diffusion language models with large vocabularies. The treatment of singular masked priors also addresses an important limitation of several existing analyses.

  2. The use of adjoint equations, combined with score-marginal cancellation and coupling arguments, provides a useful alternative to conventional KL and direct total variation analyses.

Critical weaknesses
  1. The score-entropy guarantees seems requir a strong assumption on score estimation accuracy. Theorem 3.1 assumes that the estimated score lies within a fixed multiplicative factor of the true score for every relevant state and transition. This uniform relative-accuracy condition can be restrictive in large discrete state spaces, particularly for rare tokens, and is not implied by a small average score-entropy loss. Consequently, the claimed applicability under mild assumptions requires further qualification.

  2. The extension to arbitrary IPMs follows from controlling test functions through their supremum norms. Thus, the resulting bounds do not exploit metric-specific structure and may be considerably loose for certain IPMs. In particular, the constant CΨC_\Psi can depend on the diameter of the state space under the chosen metric, potentially introducing additional problem-dependent scaling factor.

Questions for authors
  1. How restrictive is the uniform relative-accuracy assumption in Theorem 3.1 for large-vocabulary discrete diffusion models? Can the vocabulary-independent guarantee be established under weaker conditions involving only the average score-entropy loss?

  2. Since the bounds depend on the test-function class only through CΨC_\Psi, can the authors clarify whether the framework offers any advantages over deriving bounds for other IPMs directly from the TV guarantee? Are sharper metric-specific bounds possible?

3 comments

Q1 Score-accuracy assumption. We thank the reviewer. The assumption is removed, leading to more general results. The new proof follows the same roadmap with a couple of modified lemmas, and is included in the updated draft. The main change is that the leading coefficient increases slightly, from 2≈1.41\sqrt{2} \approx 1.41 to 2.52≈1.59\sqrt{2.52} \approx 1.59. All other results and claims remain intact, in particular the SS-free guarantees.

Q2 Advantage over TV-derived IPM bounds. Thank you for raising this question. Our framework indeed offers distinct advantages. These include:

  1. Sharper metric-specific bounds. Indeed, our framework enables sharper metric-specific bounds. Our current bounds use only the crude estimate ∣ϕt(y)−ϕt(x)∣≤2∥ψ∥∞|\phi_t(y)-\phi_t(x)|\le 2\|\psi\|_\infty, hence their TV form. We already have the specific regularity estimates on ϕt\phi_t to improve this, but they require a new set of additional techniques. For example, [1, 2] use PDE regularity theory for achieving sharper metric-specific bounds. We adapted their approach, and developed new technique tools for discrete diffusion for our framework.

    This work focuses on the first SS-free bounds covering both masked and uniform rates. This already introduces five new techniques and an extensive appendix. To avoid making the current paper too dense and losing focus, we defer the metric-specific analysis to an extension paper.

  2. Observable tracking. The adjoint variable (observable) ϕt(x)\phi_t(x) is the expected value of ψ\psi at xx at time tt. Eq. (35) expresses the error in ψ\psi by a time integral of score errors weighted by ϕt(y)−ϕt(x)\phi_t(y)-\phi_t(x). This identifies when and where score errors affect a given observable. Specifically, it identifies when and where matters most for that observable. This can guide the time- and state-weighting of the training loss.

A TV bound, which aggregates over all observables, does not provide these advantages.

[1] Chen, Z., Katsoulakis, M. A., & Zhang, B. J. (2026). Robustness and structure preservation in flow-based generative models via Wasserstein path-space divergences. arXiv preprint arXiv:2410.01244.

[2] Mimikos-Stamatopoulos, N., Zhang, B. J., & Katsoulakis, M. A. (2024). Score-based generative models are provably robust: an uncertainty quantification perspective. Advances in Neural Information Processing Systems, 37, 63154-63183.

AuthorsOpenReview ↗

Follow-up on our responses

Dear Reviewer 9kZm,

As the discussion period ends on November 18, we would be grateful to know whether our responses have addressed your concerns. We are happy to clarify anything further.

Best regards,

Authors

Thank you for your response. I maintain my positive assessment and score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Message to AC and Reviewers

Dear Reviewers and AC,

Thank you all for your time and constructive feedback. We believe we have sufficiently addressed all concerns.

We have also revised the manuscript accordingly; main changes are highlighted in blue. The main changes are:

  • The pointwise score-accuracy assumption is removed. This leads to a more general result. The only cost is that the leading coefficient increases slightly from 2≈1.41\sqrt{2} \approx 1.41 to 2.52≈1.59\sqrt{2.52} \approx 1.59. All claims, including the SS-free guarantees, remain intact.
  • Numerical experiments validating the SS-free bounds are added (Section 3.5).
  • Corollary 3.4 explicitly states the time-grid condition, which is not restrictive.

We welcome further questions or comments during this discussion period. If our responses address your concerns, we would appreciate your re-evaluation.

Best,

Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.