acceptodds
Under review as a conference paper at ICLR 2027

Learning to Re-Draft: A Variational Stackelberg Game for Discrete Diffusion

Abstract

Discrete diffusion models offer the ability to re-draft, revisiting and correcting earlier tokens throughout generation. This capability depends on the forward corruption process that defines what the denoiser learns to correct. Masked diffusion models fix tokens once they are unmasked, while uniform diffusion permits revisions but relies on uniformly random token substitutions. We instead learn which token substitutions are most useful for training the denoiser to re-draft. We introduce Variational Stackelberg Discrete Diffusion (VSDD), a framework for learning for such a semantically aware corruption process. VSDD formulates training as a leader-follower game: the leader defines a Markovian corruption process parameterized by the denoiser’s token embeddings, while the follower optimizes a variational denoising objective with the noise process held fixed. The leader rewards corruptions based on how much the denoiser improves after learning from them, rather than on how easily they can be reconstructed by the current denoiser. We measure these improvements through a variational objective under a fixed reference corruption process. We approximate the follower’s response with a one-step gradient update and optimize the leader using a score-function estimator. We evaluate VSDD on molecular, text, and playlist generation domains. VSDD substantially improves molecular validity over uniform and masked diffusion, reduces text perplexity relative to uniform diffusion while remaining competitive with masked diffusion, and achieves sizeable improvements in offline playlist engagement metrics.

Primary area:
generative models
Keywords:
discrete diffusion, re-drafting, generative models, learned forward processes, Stackelberg games

Reviews

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

This paper proposes Variational Stackelberg Discrete Diffusion (VSDD), which updates the forward corruption process on-policy with learnable embedding matrices, instead of relying on a uniform forward process. The authors formulate training as a leader–follower game, where the leader optimizes the transition matrix (Qt,ϕQ_{t,\phi}) based on the follower's improvement after a single gradient update, evaluated under a fixed reference corruption process. The follower minimizes the standard D3PM loss. Experiments across comparatively small domains (molecular, text, and playlist generation) demonstrate overall improvements, while the gains in the text domain lag behind masked diffusion models.

Critical strengths
  • The proposed game-theoretic formulation is novel and seems to mitigate the issues associated with previous joint learning of the forward process and denoising model. This is a meaningful approach to preventing degenerate corruption processes, supported by the comparison with D3PM-Reinforce and FLDD.

  • VSDD shows improvements in molecular generation and playlist generation while preserving diversity.

Critical weaknesses
  • Only applicable to small vocabulary sizes, with a discrete-time Markov chain (DTMC) setting. This is the main concern that seems difficult for the authors to solve. Constructing QtQ_t requires storing a V×VV \times V matrix, and further calculating Qˉt\bar{Q}_t involves tt matrix multiplications. This is definitely not a scalable choice, which limits its application to domains that require larger vocabulary sizes (i.e., language). Accordingly, the main results only include small-scale experiments. Furthermore, the method is only applicable to the DTMC setting, which is an outdated strategy right now, and extending it to continuous time seems nontrivial.

  • Equations are really hard to follow. This is not about the explanations. The equations themselves are contaminated, making them very confusing for the reader. For example, Equations (5) and (7) omit the exact inputs to the loss (xtx_t and tt are missing). Equation (11) already stops all gradients from flowing through R~k\tilde{R}_k, making the explanations and stop-gradient operations in Equations (7) and (8) redundant.

Questions for authors
  1. Could the authors report training runtime, peak GPU memory, and total GPU-hours for VSDD and the learnable-noise baselines? The Qˉt\bar{Q}_t construction and virtual follower updates may substantially increase computational cost. (W1)

  2. Please explain the equations more rigorously. (W2)

  3. What is the validation batch in Algorithm 1? Can you clarify whether the validation data used for leader optimization overlaps with the reported evaluation data?

  4. Can you clarify the t of QijQ_{ij} in Figure 2? Considering that the QijQ_{ij} is constructed from eje_j and eje_j, this is not a surprising results...

  5. The authors did not mention prior work in the DLM literature related to re-drafting and learning the forward process for masked diffusion (equivalently, the masking order).

    Re-drafting:

    [1] Wang, G., Schiff, Y., Sahoo, S. and Kuleshov, V., 2026. Remasking discrete diffusion models with inference-time scaling. Advances in Neural Information Processing Systems, 38, pp.147282-147339.

    [2] Kim, J., Kim, S., Lee, T., Pan, D.Z., Kim, H., Kakade, S. and Chen, S., 2025. Fine-tuning masked diffusion for provable self-correction. arXiv preprint arXiv:2510.01384.

    [3] Schiff, Y., Belhasin, O., Uziel, R., Wang, G., Arriola, M., Turok, G., Zilberstein, R., Elad, M. and Kuleshov, V., 2026. Learn from your mistakes: Self-correcting masked diffusion models. arXiv preprint arXiv:2602.11590.

    MDM forward process:

    [4] Jing, S., Wu, C., Liu, C., Bahadorinejad, A., Qiao, F., Liu, D. and Geng, T., InfoDLM: an Information-Adaptive Framework for Discrete Diffusion Language Model Pretraining. In Forty-third International Conference on Machine Learning.

    [5] Hong, C., Lee, S. and Ye, J.C., 2026. Unifying masked diffusion models with various generation orders and beyond. arXiv preprint arXiv:2602.02112.

6 comments

We would like to thank the reviewer for their feedback and the suggestions. Below we address the questions raised by the reviewer.

Scalability. We appreciate the reviewer raising this question. To address the reviewer’s scalability concern, we introduced a factorised parameterisation of MtM_t (see Equation (3)):

Mt=UCtW,M_t=UC_tW,

where U∈RV×rU\in\mathbb{R}^{V\times r}, Ct∈Rr×rC_t\in\mathbb{R}^{r\times r}, and W∈Rr×VW\in\mathbb{R}^{r\times V}, with r<<Vr << V. All three matrices are nonnegative and row-stochastic, so their product remains a valid corruption kernel. To keep the transition process semantics-aware, we compute

U=softmax⁡(EθA),W=softmax⁡(BEθ⊤),U=\operatorname{softmax}(E_\theta A), \qquad W=\operatorname{softmax}(BE_\theta^\top),

where EθE_\theta contains the denoiser’s embeddings. Importantly, this also addresses the reviewer’s concern about cumulative matrix multiplication. Sharing U,WU,W across time steps gives an exact representation Q‾t=α‾tI+UHtW,\overline Q_t=\overline\alpha_t I+UH_tW, where Ht∈Rr×rH_t\in\mathbb{R}^{r\times r} is updated recursively using small matrices. Consequently, neither the individual transitions nor their cumulative products require storing V×VV\times V matrices. Their storage scales as O(Vr+Tr2)O(Vr+Tr^2).

Using this factorisation, we carried out an additional TinyStories experiment with a 32k vocabulary, instead of the original 2,048 tokens. VSDD achieves generated-text perplexity 63.68, compared with 79.41 for MDLM and 90.27 for D3PM-Uniform which corresponds to reductions of approximately 19.8% and 29.5% respectively. Thus, the additional experiment directly addresses the vocabulary limitation and strengthens our text-generation results. This factorised version generalises our original approach, so that when U=W=IU=W=I, r=Vr=V and Ct=Mt,ϕC_t=M_{t,\phi} we recover our original kernel in Equation (4) exactly. We will include the factorised parameterisation and the new results in the paper.

Discrete vs. Continuous time. We do not share the belief that discrete-time diffusion is “outdated” and would appreciate clarification of the specific limitation that the reviewer is referring to. The vocabulary-scaling bottleneck comes from how transitions are represented, not from whether time is discrete or continuous. Moving to continuous time does not automatically resolve this: a dense V×VV\times V rate matrix would still require quadratic storage. Our factorisation approach solves this problem directly by reducing storage for both single-step and cumulative transitions . The additional 32k-vocabulary experiment demonstrates that this can be achieved within the discrete-time formulation, without requiring a continuous-time extension.

Training overhead. For the profiled configuration with (K=4) probes and (N=100) follower steps, we measured the following training times at identical batch sizes:

Methods / stepvs. D3PM-Uniform
MDLM0.5810.99×
D3PM-Uniform0.5871.00×
VSDD0.6671.14×

The approximately 14% overhead breaks down into around 7% from learned transition-matrix computations and 6% from leader updates.

For this configuration, each leader update uses (K+2) additional denoiser forward–backward passes: (K) for the probe gradients and two for validation-gradient computations. Amortised over (N) follower steps, this gives approximately ((K+2)/N=6%) additional denoiser computation, consistent with the measured leader-update overhead. We will extend the computational comparison with peak GPU memory, total GPU-hours, and measurements for D3PM-Reinforce and FLDD.

When training a language model with 50K vocab size, the peak memory usage on a single A100 GPU was 50Gb out of 80Gb.

Validation data. The validation minibatch in Algorithm 1 is used to evaluate candidate corruptions through the virtual follower updates and their rewards. In the playlist experiments, these playlists are strictly separate from those used to report NDCG@3 and repair rates. The evaluation playlists are not used for either follower training or leader optimisation. Our use of “validation” for both sets made this distinction unclear; we will explicitly describe their separate roles in the text.

Notation/Equations. We omitted xtx_t and tt from the loss arguments where they were clear from context to keep the notation simple. Both denoising losses depend on the sampled noisy inputs, as already shown in the posterior terms of Equations (5) and (7). We will write these arguments explicitly in the revised manuscript to avoid ambiguity.

Figure 2. We will add the timestep information to the caption (for this figure we used t=25). Regarding the correlation, the transition probabilities are computed from the learned bilinear scores eiAt,ϕejTe_i A_{t,\phi} e_j^T, not directly from cosine similarity. The learned transformation can therefore emphasise or suppress different relationships in the embedding space; a positive correlation with the original cosine similarities is not imposed by our parameterisation. Figure 2 illustrates the structure of the learned process, rather than serving as the main evidence for its effectiveness, and you can think of A as some sort of learned similarity metric in the denoiser's semantic space.

To test this distinction directly, we also ran an additional molecular experiment with At,ϕ=IA_{t,\phi}=I, so that the kernel uses cosine similarity without learning the bilinear transformation. Under the same experimental setup, this achieves 73.2% validity and 0.8565 diversity, compared with 84.3% validity and 0.8679 diversity for VSDD. Thus, embedding similarity already provides useful structure, but learning how to use that structure improves both validity and diversity over the cosine-only variant. We will include this ablation alongside the visual analysis.

Related work. We thank the reviewer for pointing us to these additional papers. We are happy to expand our related-work section and explain how these approaches relate to ours. We will include this discussion in the revised manuscript.

Thank you to the authors for the detailed rebuttal, the newly proposed factorized parameterization, and the additional experiments. While the low-rank factorization and the ablation are helpful steps in the right direction, several critical issues remain unresolved:

  1. Missing diversity metrics in the new 32k-vocabulary TinyStories experiment

In the new V=32kV=32\text{k} TinyStories experiment, you report only generative GPT-2 perplexity (63.68 for VSDD vs. 79.41 for MDLM and 90.27 for D3PM-Uniform) without reporting the corresponding Distinct-1 and Distinct-2 diversity metrics (unlike Table 2a for V=2048). In discrete diffusion, a collapsed transition kernel that repeatedly generates high-frequency tokens artificially lowers generative perplexity by sacrificing output diversity. Reporting generative perplexity alone without diversity metrics is insufficient to verify generation quality on the 32k-vocabulary setting.

  1. Incomplete computational overhead and peak GPU memory comparisons

Uniform/transition-matrix formulations (such as D3PM-Uniform / UDLM) typically require roughly 2x the peak GPU memory of MDLM, which directly restricts the maximum feasible batch size on limited hardware. In your response, you report 50 GB / 80 GB peak memory only for VSDD on a 50K vocabulary, without providing the corresponding peak GPU memory for the baselines (MDLM, D3PM-Uniform, D3PM-Reinforce, and FLDD) under the exact same batch size and vocabulary configuration. Please report a complete side-by-side comparison of peak GPU memory and training runtime across VSDD and all baselines.

  1. Unupdated manuscript and missing explanation regarding redundant stop-gradient (sg) operations

Note that current manuscript has not yet been updated with the promised revisions, and my second point in W2 / Q2 was not addressed in the rebuttal (equation 11). Please clarify this in the text and incorporate all promised revisions into the updated PDF.

Overall, I still think the paper needs further strengthening to meet the bar for acceptance, so I am maintaining my current rating. I thank the authors for their extensive rebuttal and hope these suggestions help improve the work for a future submission.

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

This paper proposes VSDD, a method that learns the forward corruption process of discrete diffusion via a leader–follower game. The leader parameterizes the noise process using the denoiser's token embeddings and rewards corruptions based on how much they improve the denoiser after a one-step virtual update, avoiding the degenerate noise collapse seen in joint optimization. Experiments on molecules, text, and playlists show gains over uniform and learnable-noise baselines, with the largest improvements in molecular validity.

Critical strengths
  • The paper identifies a concrete issue with jointly learning the forward process. The noise can collapse into trivial corruptions that are easy to reconstruct. This is also shown empirically in Appendix D.
  • Corruptions are evaluated by how much they help the denoiser learn rather than how easily the current denoiser reconstructs them. Using a leader-follower setup with stop-gradients cleanly separates the two objectives.
  • Tying the transition kernel to the denoiser's token embeddings yields structured noise. For instance, we see chemically meaningful substitutions in the molecular domain.
Critical weaknesses
  • Incomplete ablations on the noise kernel: The comparison between VSDD and D3PM-Reinforce isolates the benefit of the Stackelberg optimization. However, the benefit of learning the bilinear similarity kernel is not isolated. The paper claims that semantically similar substitutions aid re-drafting. It should therefore compare against a simpler baseline using a fixed, non-learned transition kernel based directly on embedding cosine similarity.
  • Scalability and training overhead: Constructing dense VxV cumulative transition matrices and computing KK virtual gradient updates per block becomes prohibitive for standard vocabulary sizes. Wall-clock training overhead is not reported. Furthermore, the text experiments are restricted to a 2048 token vocabulary on a 100K subset of TinyStories. This makes it hard to tell if the method scales to standard LM benchmarks.
  • Missing hyperparameters: Several critical hyperparameters from Algorithm1 are missing from both the main text and Appendix B. These include the number of probes KK, virtual step size γ\gamma, reward clipping threshold cc, terminal regularization weight λT\lambda_T, and the exact choice of QrefQ_{\text{ref}}.
  • Weak evidence for re-drafting outside molecules: Re-drafting is the core motivation, but the evaluation in Appendix C is thin. The text experiments rely on just 5 synthetic templated stories. In the playlist task (Table 13), the repair rate simply measures whether the model changed the corrupted token to anything else. There is no comparison against baselines like D3PM-Uniform on the same repair task.
Questions for authors
  1. The leader scores a corruption using a single virtual gradient step, but the resulting noise process is held fixed for N=100N=100 follower updates. Does this horizon mismatch bias the leader toward short-term gains?

  2. Each probe yields a single scalar reward over the entire minibatch. Does the learning signal for Qt,ϕQ_{t,\phi} concentrate heavily on frequent tokens, leaving transitions for rare tokens under-optimized?

  3. In the playlist experiments, are the validation sequences sampled for the leader's reward during training strictly separated from the held-out validation playlists used to report NDCG@3 and repair rates?

8 comments

We thank the reviewer for their comments and suggestions. Below we address the questions raised by the reviewer.

Additional ablation. We ran the additional evaluation suggested by the reviewer on the molecular domain when we fixed At,ϕ=IA_{t,\phi}=I in Equation (4) so that the model would only rely on a simple non-learned cosine-similarity kernel. We use the same experimental setup, model sizes etc as in the rest of our molecular evaluations. In this ablation, we observed the validity rate of the generated molecules is 73.2% and the diversity is 0.8565. Interestingly, the validity is significantly higher than of MDLM, D3PM-Uniform or D3PM-Reinforce but still lower than of VSDD while the diversity is the lowest among all baselines.

Scalability. We do appreciate the reviewer raising this question. The exact same question was raised by other reviewers as well, so we did two things to address this: (1) We measured the current training overhead; (2) We slightly modified how we compute the transition matrix in Equation (4) to enable large vocabularies. Below we share more on each of these two points:

(1) Training Overhead. According to our measurement per training step our VSDD costs approximately 1.14x of the uniform D3PM, see the table below:

Methods / stepvs. D3PM-Uniform
MDLM0.5810.99×
D3PM-Uniform0.5871.00×
VSDD0.6671.14×

We also performed a breakdown of this 14% training time overhead of VSDD, and we saw that approx. 7% comes from the learned transition matrix computations, and 6% from the leader updates.

Additionally, we can estimate that, for example, for K=4 probes and N=100 follower steps, each leader update ran K+2 extra forward-backward passes through the denoiser: K for the probe gradients and 2 for the validation gradient. As it only has N follower steps, VSDD adds a fraction of (K+2)/N of the baseline’s training FLOPs which is approx 6% (this estimate is consistent with the runtime measurements above).

(2) Large vocabularies. To address the large vocabulary concerns, we slightly modified our Equation (4) by introducing a factorised variant of matrix M in Equation (3) as follows:

Mt=U⋅Ct⋅W,M_t = U \cdot C_t \cdot W,

where U∈RV×rU \in \mathbb{R}^{V \times r}, Ct∈Rr×rC_t \in \mathbb{R}^{r \times r}, and W∈Rr×VW \in \mathbb{R}^{r \times V} are low-dimensional row-stochastic matrices (i.e., r≪Vr \ll V). To keep the transition process semantics-aware, we compute U=softmax⁡(Eθ⋅A)U = \operatorname{softmax}(E_\theta \cdot A) and W=softmax⁡(B⋅EθT)W = \operatorname{softmax}(B \cdot E_\theta^T), where EθE_\theta corresponds to the denoiser's embeddings (see Section 4).

Using this factorisation we carried out an additional text generation experiment with Tiny Stories dataset with a large 32k vocabulary size instead of our original 2048 vocab size. The additional experiment has significantly strengthened our results: In particular, we see that with large vocab, VSDD achieves perplexity 63.68, compared to 79.41 for MDLM and 90.27 for D3PM-Uniform (those are reductions of approximately 19.8% and 29.5%, respectively). We elaborate more on our interpretation of these results in our response to Reviewer omy2 but we would like to thank the reviewer for their suggestion to look into the large vocab domains - this new factorised computation actually generalises our original idea (see our response to omy2), and we would like to include it in our main text.

Hyperparameters. We used K=4 for the molecular and playlist domains, and we let K=20 for text generation. The virtual step size was equal to 1e-4 in all experiments, and the reward clipping threshold was set to 5 in all experiments as well. We used the terminal regularisation coefficient of 1, and N=50 for text generation and N=100 for the other two domains. We used a uniform transition process as the reference process for all experiments (we mentioned this in line 16 of Alg 1 but will add the respective textual explanation). Thank you for noticing this, we will include all these hyperparameters into the paper.

Re-drafting. Indeed, in the playlist domain we studied whether the model can successfully restore the corrupted tokens. In this specific domain, this is a valid evaluation as we do not know the ground truth preferences. In particular, the semantics of the playlist can be personalised on the user-level, and therefore, not observable by us directly (i.e., we do not know which tracks are substitutable for a particular user in the given context etc). This is why it may be a reasonable assumption that sampling tracks that the user has actually listened to constitutes a valid “error-correction”.

Below we share similar redrafting analysis for MDLM:

CorruptionRepair%Smooth(O)Smooth(C)Smooth(R)Div(O)Div(C)Div(R)
duplicate69.7%0.97970.97880.97992367.52343.92367.8
poor_transition81.3%0.98130.97800.98042407.82388.32401.3
energy_peak85.0%0.97970.97980.98062367.52367.52374.7

and for D3PM-Uniform:

CorruptionRepair%Smooth(O)Smooth(C)Smooth(R)Div(O)Div(C)Div(R)
duplicate75.3%0.97980.98000.98002486.02470.62495.6
poor_transition84.5%0.97970.97630.97912502.52489.02512.3
energy_peak86.0%0.97980.97980.97962486.02486.02479.2

We see that consistent with the rest of our evaluations, VSDD repairs the sequences better, especially w.r.t. duplication.

Q1. Block size. Intuitively, the follower and the leader updates serve different purposes: The follower learns to denoise under the current corruption process, while the leader adjusts that process based on the follower’s progress. Updating the leader less frequently gives the denoiser time to learn from the selected corruptions before its training distribution changes again. So in this case, our one-step probe provides an inexpensive signal for this adjustment; after each block, that signal is recomputed using the updated denoiser. Thus, N=100 determines how often the corruption process changes, rather than the horizon that each virtual update must explicitly simulate.

Q2. Token Frequency. As in many learning problems, frequent tokens provide more training examples - however, we do not learn each token’s transitions separately. All tokens share the same transformation At,ϕA_{t,\phi} applied to their embeddings. And as we explicitly construct the noise process to be semantic-aware (i.e., relying on token similarities), the patterns learned from frequent tokens can also transfer to related rare tokens, rather than requiring each token to learn only from its own occurrences. Consequently, we did not observe any specific problems related to token frequencies, etc.

Q3. Playlist validation sequences. Yes, exactly, the playlists used to compute the leader’s reward are strictly separate from those used to report NDCG@3 and the repair rates. Our evaluation playlists are not used for either follower training or leader optimisation. We think that our use of the word ‘validation’ for both sets made this distinction unclear; we will explicitly explain their separate roles in the text.

Thanks for the detailed response and the new experiments! The fixed-kernel ablation is quite interesting. I think it’s important since it separates the effect of the embedding structure from the effect of learning the kernel, which is the core of the paper’s claim. From the results, a lot of the gain seems to come from the structure itself. Learning the kernel with the Stackelberg setup helps further, but the extra gain is smaller. Given how central this is, I think it should be studied more thoroughly, including in the other domains. Furthermore, on scalability, factorized variant and the larger vocabulary results are nice to see. Since this is a fairly big change to the method, it should be in the manuscript.

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

The paper presents a method to adaptively learn the noising distribution for discrete diffusion along with the denoiser. The formulation is based on Stackelberg game, where the leader picks the noising process that helps the denoiser perform better. The experiments on molecule generation, text generation and playlist generation compare the proposed approach with standard discrete diffusion methods like MDLM, D3PM-Uniform, and with FLDD, which is another method that simultaneously learns the noising process along with the denoiser. The strongest results are on molecule generation (significant improvement in validity). The improvement on text generation is comparatively small.

Critical strengths

Novelty and significance: The use of a fixed noise distribution for training discrete diffusion models limits their performance. Removing this limitation can lead to much faster generation. The proposed training method, inspired by the Stackelberg game, is interesting and tries to address an important problem.

Writing: The paper is well written and easy to follow.

Critical weaknesses

Evaluations: All three experimental setups use small datasets, which makes it difficult to assess whether the improvements scale if the model and data size increase. This is especially important given the modest improvement over MDM on TinyStories. Experiments on at least one real task with a dLLM would better establish the significance of the proposed method. Please see the questions section.

Soundness:

  1. While the experiments support the proposed training objective, it is unclear why LELBOL\mathcal L^L_{ELBO} needs to use forward KL with a fixed qrefq_{ref}. The use of reward as defined in eq 9 could, on its own, prevent the collapse of qϕq_\phi, without using qrefq_{ref} in LELBOL\mathcal L^L_{ELBO}.

  2. The connection to Stackelberg game is only superficial. Specifically, no theoretical arguments regarding convergence of the alternating training procedure are presented.

Questions for authors
  1. VSDD is computationally more expensive than fixed-noise training. Could you provide the exact wall-clock time difference or FLOP analysis for training?
  2. Please consider doing adaptation training on one of the opensource dLLMs like LLaDA or Dream and compare it with vanilla continued training.
  3. Please provide an ablation where qrefq_{ref} is not used and is replaced by qϕq_\phi, while keeping everything else the same. I believe this would still be different from Bartosh et. al. and therefore is a meaningful ablation.

Minor questions and clarifications:

  1. In eq 8, the sgθsg_\theta should be on pp.
5 comments

We would like to thank the reviewer for providing their feedback & the suggestions. We address the raised questions below.

Computational Overhead. When measured per training step on identical batch sizes VSDD costs approximately 1.14x of the uniform D3PM, see the table below:

Methods / stepvs. D3PM-Uniform
MDLM0.5810.99×
D3PM-Uniform0.5871.00×
VSDD0.6671.14×

If we break down this 14% training time overhead of VSDD, we see that approx. 7% comes from the learned transition matrix computations, and 6% from the leader updates.

When we performed a run of our training for K=4 probes and N=100 follower steps, each leader update ran K+2 extra forward-backward passes through the denoiser: K for the probe gradients and 2 for the validation gradient. As it only has N follower steps, VSDD adds a fraction of (K+2)/N of the baseline’s training FLOPs which is approx 6% (this estimate is consistent with the runtime measurements above).

Scalability. We appreciate the reviewer’s suggestion to look into large vocabularies, and we agree that explicitly storing dense matrices would limit the applicability to large vocabs. To address this, we introduced a factorised variant of matrix M in Equation (3) as follows:

Mt=U⋅Ct⋅W,M_t = U \cdot C_t \cdot W,

where U∈RV×rU \in \mathbb{R}^{V \times r}, Ct∈Rr×rC_t \in \mathbb{R}^{r \times r}, and W∈Rr×VW \in \mathbb{R}^{r \times V} are low-dimensional row-stochastic matrices (i.e., r≪Vr \ll V). To keep the transition process semantics-aware, we compute U=softmax⁡(Eθ⋅A)U = \operatorname{softmax}(E_\theta \cdot A) and W=softmax⁡(B⋅EθT)W = \operatorname{softmax}(B \cdot E_\theta^T), where EθE_\theta corresponds to the denoiser's embeddings (see Section 4).

Using such factorisation we carried out an additional text generation experiment using Tiny Stories dataset with a large 32k vocabulary size instead of the 2048 vocab size that we used originally. The additional experiment has actually strengthened our text-generation results: We see that at the vocabulary size of 32k, VSDD achieves perplexity 63.68, compared to 79.41 for MDLM and 90.27 for D3PM-Uniform (those are reductions of approximately 19.8% and 29.5%, respectively).

We think that the original small text vocabulary has probably obscured the advantage over masked diffusion. A larger 32k BPE vocabulary can represent more words and longer word segments directly, rather than splitting them into shorter fragments/prefixes. This changes the units on which our corruption process operates. Our interpretation is that these more complete tokens give the forward corruption process better opportunities to learn useful semantic substitutions (e.g., substituting synonyms is easier than substituting partial word suffixes or prefixes).

In fact, this factorised version generalises our original approach, so that when r=Vr=V, U=W=IVU=W=I_V, and Ct=Mt,ϕC_t=M_{t,\phi}, we recover our original kernel in Equation (4) exactly. We thank the reviewer for this idea, and we would like to include this factorised version in our paper.

Ablation. We agree with the reviewer that it sounds like an interesting ablation. We carried out the respective experiment on the molecular domain, and we see that the validity rate of generated sequences is around 76.5% when using the learned forward process instead of the reference process in the leader’s loss. This is still significantly higher than of all our baselines but somewhat lower than of VSDD that uses the reference process.

Our intuition here goes as follows: Generally speaking, if evaluation uses the learned process rather than the reference process q_{ref}, then the leader controls both: (1) the training corruptions and (2) their evaluation weighting. In this case, the leader can concentrate on a much smaller set of corruptions making improvements on those that dominate the reward, while the rest of the corruptions may gradually disappear from evaluation receiving progressively a smaller weights. Having a fixed reference process separates these roles so that the leader can change what the denoiser trains on, but improvements are measured against the same evaluation distribution.

Stackelberg connection. We find our Stackelberg formulation helpful: Our formulation directly exploits the leader’s first-move advantage, i.e., the noise model selects and commits to a corruption process while anticipating how the denoiser will respond. The one-step better response makes this anticipation practical from the computational perspective as it rewards corruptions for the improvement they induce after learning, rather than how easily the current denoiser reconstructs them. Generally, having similar k-step approximations of the follower’s response in Stackelberg games is well-established: For example, Zuo et al., Adversarial Regularisation as Stackelberg Game (EMNLP 2021) implemented Stackelberg optimisation through unrolled follower updates, and also Liu et al., DARTS paper (ICLR 2019) tackled a similar bi-level optimisation problem via a single-step approximation, etc.

We agree with the reviewer that some sort of convergence theorem could be an interesting game-theoretical contribution but our work primarily targets improving diffusion training in practice via learning the forward process rather than providing a theoretical equilibrium characterisation (but we would still consider this direction as possible future research).

Reviewer_omy2OpenReview ↗

Thank you for answering my questions

Regarding scalability: This is still my main concern. Thank you for running the Tinystories experiment with a larger vocabulary. The results are indeed interesting. Is there any reason not to perform adaptation starting from a pre-trained MDM checkpoint?

Comments on the paper

1 comment

We thank all the reviewers again for their feedback & suggestions - it did help us to improve our paper.

In particular, all reviewers noted that scalability was an issue in the original manuscript. To tackle this, we introduced a factorised version of our noise kernel, and it actually helped us not only to scale the model but also to improve the text generation results. We added the 32K vocab experiment in the main text of the paper, and we also added the 126K vocab (LLaDA) to the Appendix.

We also appreciated the ideas to run two ablations, the reference-process and the fixed cosine-kernel ablation. All those results are in the Appendix as well. We added the training time and memory usage, and also explicitly mentioned the additional training overhead in the main text of the paper.

We incorporated the rest of the comments (missing hyperparameters, clarifying the validation batches, revised some notation etc) in the main text of the paper and in the appendix.

If there are any additional evaluations or clarifications that could be of help, please let us know, we can add those before the end-of-rebuttal. Otherwise, thanks again for the discussion.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.