- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies diffusion models for globally constrained discrete tasks, where global constraint rules, such as those in Sudoku, are learned from data rather than explicitly supplied to the model. Complementing previous work on solving these tasks with continuous or discrete diffusion models, it uses them to investigate inference failures in continuous diffusion. The authors observe that generated outputs can be locally valid but globally invalid. Their analysis suggests that the denoiser can propose valid solutions that the standard sampling process subsequently undermines. They address this through Tweedie reprojection, which removes the direct previous-state residual during sampling, and self-correction training, which teaches the model to correct its own errors.
Critical strengths
Using the characteristics of generation on discrete tasks to, in turn, analyze some properties of continuous diffusion models is quite an interesting angle.
And then, they develop corresponding methods on the inference and training sides to alleviate this training–inference mismatch problem. This is quite interesting, and the problem and the methods do match.
The writing itself is quite fluent. It is easy to get the main storyline, and it is fairly self-consistent.
Experimentally, the controlled comparisons do support the correctness of the methods and the analysis. For example, on Sudoku, keeping the model fixed and changing only the sampler leads to a substantial improvement, which is quite a convincing observation.
Critical weaknesses
The algorithmic contributions need clearer delineation. The inference update has a direct antecedent in [1] and structural similarities to [2], while the training approach shares its central motivation and elements with [3,4]. The new algorithmic insight in either component remains unclear.
[1] Song, J., Meng, C., & Ermon, S. (2020). Denoising diffusion implicit models. arXiv preprint arXiv:2010.02502.
[2] Song, Y., Dhariwal, P., Chen, M., & Sutskever, I. (2023). Consistency models. arXiv preprint arXiv:2303.01469.
[3] Deng, Y., Kojima, N., & Rush, A. M. (2022). Markup-to-image diffusion models with scheduled sampling. arXiv preprint arXiv:2210.05147.
[4] Ren, Z., Zhan, Y., Ding, L., Wang, G., Wang, C., Fan, Z., & Tao, D. (2024, March). Multi-step denoising scheduled sampling: Towards alleviating exposure bias for diffusion models. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 38, No. 5, pp. 4667-4675).
Questions for authors
- Why do many failed Tweedie trajectories on Sudoku contain an earlier valid denoiser proposal but end with an invalid sample?
- What are the substantive differences between the inference method and [1,2], and between the training method and [3,4]? Under a unified parameterization, please distinguish the state construction, re-noising procedure, time sampling, and loss weighting, and explain which differences are necessary for the results.
Should the main contribution be understood as a training algorithm or as a mechanistic analysis of diffusion on discrete constraint tasks?
4 comments
Thank you for the detailed response and additional experiments.
The additional experiments provide stronger support for the proposed analysis. However, the algorithmic contributions remain closely related to existing methods. Overall, while I appreciate the mechanistic insights, I find the novelty and broader contribution to the community somewhat limited.
Considering these factors, I will maintain my original scores.
Thank you for the follow-up! Over the weekend, we ran additional experiments to compare our approach more directly with [3,4]. In particular, we ablated the recovery input used in training on 21-clue Sudoku:
| Recovery input used in training | DDPM | Tweedie |
|---|---|---|
| Ours: re-noised prediction at a random lower noise level | 0.83 | 0.96 |
| DDPM step to a random lower noise level | 0.77 | 0.97 |
| Ours, restricted to the adjacent noise level | 0.16 | 0.88 |
| Deng-style input: one DDPM step to the adjacent level | 0.22 | 0.90 |
| Ren-style input: model step + analytic steps, at most 5 levels | 0.19 | 0.91 |
Rows 1 and 3 use our self-correction and differ only in the range of the second noise level; rows 2 and 4 make the same comparison using a DDPM-step input. This directly addresses which design choice matters in our setting: sampling the second noise level over a wider range matters much more than whether the recovery input is constructed by re-noising or a DDPM step. Under DDPM, the random lower level variants reach 0.77-0.83 validity, while the short range variants reach only 0.16-0.22, below approximately 0.30 for standard training. Under Tweedie, the difference is smaller but follows the same pattern.
We also want to emphasize why we believe the mechanistic analysis is an important contribution. We explicitly acknowledge the relationships to generalized DDIM and scheduled sampling. However, our main finding is that a denoiser can already predict constraint-satisfying solutions that the standard reverse update fails to use. This changes how reported failures should be interpreted. For example, in SRM, the standard diffusion baseline reaches only 0.8% on MNIST-Sudoku, motivating a spatial sampling order (best: 51.6%). We took that same released baseline checkpoint, which we did not train, and changed only the sampler. Accuracy increased to 65.7%, while sampling remained fully parallel. Thus, the 0.8% result does not mean that the denoiser failed to learn the constraints: the sampling procedure was a major part of the failure.
We believe that identifying this distinction, and showing how it can be addressed from both the sampling and training sides, is an important contribution to understanding continuous diffusion on constrained discrete tasks.
Thank you again for the discussion! We wanted to share two additional results in the new revision that we hope address your remaining concerns.
First, we trained the method from Deng et al. including its mixing schedule. On 21-clue Sudoku, it reaches 20% DDPM validity, compared with 83% for our self-correction, both trained for 400k steps (Appendix Q, Table 19). Together with our previous ablations, this shows that sampling recovery noise level over a wider range makes a substantial difference with respect to using adjacent steps.
We also evaluated our method on Kim et al.'s Sudoku benchmark (see our discussion with q4WJ). Our 6.4M-parameter model reaches 98.8% accuracy with 8 denoiser calls, compared with 89.49% for their published 6M-parameter masked diffusion model at 50 steps (Section 4, Figure 3, Appendix M).
We hope these new results help clarify both the differences from prior work and the practical value of our findings. We would be grateful if you could reconsider your score in light of these additions!
We thank the reviewer for the careful reading and questions!
Our main contribution is a mechanistic analysis identifying an inference failure: a denoiser can predict a constraint-satisfying solution, yet the standard reverse update can turn that prediction into an invalid update center. Our sampling and training interventions investigate this failure from complementary sides.
-
-
\qquad \hat\epsilon = \frac{x_t-\alpha_t\hat x_0}{\beta_t}, \quad \xi\sim\mathcal N(0,I).$$ DDIM sets $\kappa=0$, DDPM sets $\kappa^2$ to the posterior variance, and Tweedie sets $\kappa=\beta_s$, removing the direct state residual. Even though Tweedie is a special case of generalized DDIM[1], we are not aware of prior work showing that this choice of $\kappa$ makes continuous diffusion work on constrained discrete tasks. On the Sudoku-21 baseline checkpoints of Table 1, DDIM ($\kappa=0$) reaches 17% (Table 16 in the revised manuscript, $\rho=0$ column), versus 31% for DDPM and 95% for Tweedie reprojection. In fact, sweeping $\rho$ across all ten configurations and both training regimes (Table 16 in the revised manuscript) shows that validity generally improves toward the Tweedie endpoint. Figure 2 isolates the residual's effect on decoded center validity, while the noise-scale controls show that changing DDPM's noise magnitude alone does not close the gap (Figure 6). Consistency models [2] also alternate prediction and re-noising, but learn a mapping consistent along probability-flow trajectories. At inference, our update shares the predict-and-re-noise structure of multistep consistency sampling, but uses a standard denoiser without consistency training or distillation. Our self-correction directly supervises recovery of the ground-truth solution from a re-noised model prediction. Consistency training instead matches model outputs on two versions of the same data example corrupted at different noise levels. Deng et al. [3] construct inputs through short learned reverse rollouts (one neighboring step in their experiments) and progressively mix these with standard noise-MSE training. Ren et al. [4] also start from the model's own one-step prediction, but instead of running the model again they propagate the resulting error analytically over several further steps, and they add a second output head that learns to predict and subtract this input error at inference. We instead sample $t_1\sim U[0,T]$, $t_2\sim U[0,t_1]$, and directly construct $$\tilde x_{t_2} = \alpha_{t_2}\operatorname{sg}[f_\theta(x_{t_1},t_1)] + \beta_{t_2}\xi.$$ The target is the original $x_0$, with objective $L_{\mathrm{rec}}+\lambda_{\mathrm{simple}}L_{\mathrm{simple}}$ and $\lambda_{\mathrm{simple}}=0.1$ in the main experiments. In our case noise levels are not necessarily adjacent. Figure 8, Appendix I.2 (Figure 9 in the revised manuscript) compares re-noised clean predictions and DDPM-step recovery inputs within our training setup. They produce comparable improvements on Sudoku, showing that the recovery benefit persists across both setups. [1] Song, J., Meng, C., & Ermon, S. (2020). Denoising diffusion implicit models. arXiv preprint arXiv:2010.02502. [2] Song, Y., Dhariwal, P., Chen, M., & Sutskever, I. (2023). Consistency models. arXiv preprint arXiv:2303.01469. [3] Deng, Y., Kojima, N., & Rush, A. M. (2022). Markup-to-image diffusion models with scheduled sampling. arXiv preprint arXiv:2210.05147. [4] Ren, Z., Zhan, Y., Ding, L., Wang, G., Wang, C., Fan, Z., & Tao, D. (2024, March). Multi-step denoising scheduled sampling: Towards alleviating exposure bias for diffusion models. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 38, No. 5, pp. 4667-4675).Removing the residual does not make a valid proposal an absorbing state: subsequent re-noising and imperfect denoising can move away from it. We also realized that the meaning of "valid" in line 355 (375 in revised) was different from the rest of the paper. Here, it meant satisfying the Sudoku rules, while elsewhere it also requires satisfying the given clues. Under this latter definition, a valid proposal appears in only 10% of failed Sudoku-Extreme trajectories. We updated the wording in the revised manuscript.
Appendix B.1 gives the unified parameterization, we clarify it further in the Appendix N (revised manuscript):