- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies constrained sampling with masked discrete diffusion models on combinatorial problems with sparse constraint dependency graphs. It uses the repair-set rule of partial rejection sampling (PRS) as a masking policy and lets the model resample the masked variables conditional on the retained ones. A termination certificate based on weighted induced-path bounds gives almost-sure termination with logarithmic expected rounds and a linear expected number of repaired constraints, and it recovers the classical PRS bounds for product distributions. An acceptance-and-restart correction is proposed for exact sampling from the data distribution conditioned on feasibility. Experimental results cover distributional fidelity on small coloring, SAT, and rooted spanning tree targets, and show that PRS-mask repair with a fine-tuned diffusion kernel outperforms selected one-shot diffusion solvers on SATLIB random 3-SAT.
Critical strengths
-
Comprehensive theory and validation.
Every theorem and corollary comes with a complete proof.
-
Clear separation of feasibility from correct sampling.
The negative results show that exact conditionals and fast termination alone do not guarantee an unbiased output.
Critical weaknesses
-
The theory is not established for trained models.
The termination certificate assumes the contraction it concludes, and the exact-sampling theorem holds only for hand-built count-energy models, not for any trained masked diffusion model.
-
The experiments do not support the motivation.
Most Figure 2 panels train on the target distribution itself, the one test of conditioning with a Transformer MDM has eight variables and a weak AR baseline, the strong 3-SAT result comes from a uniform-noise kernel, and the budgets are unmatched and recent baselines are missing.
Questions for authors
- The hypothesis of Theorem 3.1 (Eqs. 7 and 8) bounds path probabilities under the sampler's own round-t distribution given R_t = S, and summing it already gives E[W(R_{t+1}) | R_t] ≤ κW(R_t) (lines 311 to 312); the symmetric conditions of Corollary C.2 (Eq. 41) are bounds of the same kind. The checkable routes do not cover learned kernels: pointwise bounds give r̄ = 1 once an overlap lies on retained values (lines 1255 to 1262), and Proposition C.5 needs a whole-block probability ratio below 2, which the paper calls restrictive (lines 1270 to 1272). How can the certificate be verified for a trained masked diffusion model before running it?
- κ is reported only for one eight-bit constraint (m = 1, which line 2422 calls rejection sampling) and one pair of clauses (m = 2) in Table 4, and 1.3% of parallel MDM requests in uniform SAT do not terminate within the 100-step cap (line 3071). What are κ, the rounds, and the repaired constraints for the Figure 2 configurations, and do the rounds grow as O(log m) (lines 017 to 019)?
- Theorem 4.1 needs exact, mutually compatible conditionals and an envelope h_S that does not depend on the retained values; only the count-energy models of Appendices G.8 and H.2 satisfy this. For the Transformer MDM on 3 by 3 trees, the conditionals are incompatible (TV discrepancy up to 0.227, lines 3263 to 3265) and acceptance changes TV from 0.09924 to 0.09926 (Table 8). Has the interval-bound envelope of Appendix D.5 been computed for any Transformer, and is its acceptance probability bounded away from zero at realistic block sizes?
- The corrected sampler returns q_w(· | F) (line 3217), which plain rejection sampling from the same q_w also returns, and line 2191 notes that rejection sampling satisfies the same bound. On the cube instance 962 of 4096 assignments are feasible (line 3131). How do acceptance plus restart compare with rejection sampling from the same model in TV and time?
- In Figure 2, constrained AR has lower TV than both MDM samplers on panels a, b, c, d, and g, but there both models are trained on samples of the target conditional itself (lines 2779 to 2780, 2862 to 2863, and 2913 to 2915), so these panels do not test sampling under a constraint the model has not learned. The paper's own setting appears only in panels e and f, where MDM and AR share the same unconditioned training data (lines 2966 to 2969) on an eight-variable instance (line 2979) and the MDM samplers win against an AR that renormalizes the permitted directions at each prefix (lines 2991 to 2992); in panels h and i the "MDM" is a count-energy model built on the statistic H that the TV is computed on (lines 2997 and 3052). How do the MDM samplers compare with rejection sampling or sequential Monte Carlo from the same AR on panels e and f, and with a Transformer MDM on panels h and i?
- Seven of the nine Figure 2 panels report TV of a low-dimensional statistic (clause profile, color counts, or horizontal count, lines 3050 to 3053), which can hide errors in the joint. What do joint-level fidelity measures show?
- The central design choice is the PRS repair mask (lines 232 to 233), but no experiment replaces it with another masking policy for the same model, such as random remasking (ReMDM [2], IPR [3]) or confidence-based remasking (PRISM [7]). Does the PRS mask improve TV or solve rate over these policies at equal cost?
- The strong 3-SAT kernel is the uniform-noise DiffUCO (line 437); the masked kernel (MDNS) reaches 39.6% solved@10 on uf100 and 0.0% on uf200 and uf250 (Table 7). Which result supports "strong empirical results against state of the art diffusion solvers on 3-SAT" (lines 022 to 023) for masked diffusion?
- PRS-mask repair runs 64 rounds of 16 denoising steps per run, the one-shot baselines generate once, and line 464 concedes that "rounds differ in cost"; Section 5.2 also uses one training seed (line 494). What is one round for WalkSAT, probSAT, FMS, and Moser-Tardos, and how do the methods compare in wall-clock time and at an equal sample budget?
- Published methods close to this setting are not compared: NExCO [1], a masked diffusion successor of COExpander; SDDS [4]; Kramer et al. [5], which learn resampling oracles for Moser-Tardos and WalkSAT on random 3-SAT with local-lemma bounds; and Constrained Discrete Diffusion [6] for Figure 2. COExpander was not evaluated on SAT in its own paper, so how were it and DiffUCO adapted and tuned?
- Table 8's caption says acceptance improves fidelity "consistently" (lines 3086 to 3087), but the 3 by 3, c = 2 row gets worse (0.09924 to 0.09926). Line 463 says repair beats WalkSAT and probSAT "at every round budget", but at solved@10 both lead on all four sizes in Table 7, and line 465 reports uf250 only against COExpander. Which statements will be corrected?
- The reproducibility claim does not match the submission. The Reproducibility Statement says the supplementary code includes the training-example frequencies, saved model parameters, and exact output probabilities of the samplers, and that the source archive includes commands to run the checks (lines 490 to 495); Appendix F.3 names the training and verification scripts with their checkpoints and probability tables (lines 2662 to 2667), and Appendix H.5 cites SHA256 receipts and an artifact audit that "passed 17,378 checks" (lines 3290 to 3291). The submission contains no supplementary material and no anonymous link, so none of these exact checks can be verified. Where are these artifacts?
[1] Yu Wang, Yang Li, Jiale Ma, Junchi Yan, and Yi Chang. NExCO: Native solution expansion for diffusion-based combinatorial optimization. In ICLR, 2026.
[2] Guanghan Wang, Yair Schiff, Subham Sekhar Sahoo, and Volodymyr Kuleshov. Remasking discrete diffusion models with inference-time scaling. In NeurIPS, 2025.
[3] Taegu Kang, Jaesik Yoon, and Sungjin Ahn. Inference-time scaling in diffusion models through iterative partial refinement. ICLR 2026 Workshop on AI with Recursive Self-Improvement.
[4] Sebastian Sanokowski, Wilhelm Berghammer, Haoyu Wang, Martin Ennemoser, Sepp Hochreiter, and Sebastian Lehner. Scalable discrete diffusion samplers: Combinatorial optimization and statistical physics. In ICLR, 2025.
[5] Maximilian J. Kramer, Paul Boes, and Jens Eisert. Using deep learning to construct stochastic local search SAT solvers with performance bounds. Machine Learning: Science and Technology, 7, 2026.
[6] Michael Cardei, Jacob K. Christopher, Bhavya Kailkhura, Tom Hartvigsen, and Ferdinando Fioretto. Constrained discrete diffusion. In NeurIPS, 2025.
[7] Jaeyeon Kim, Seunggeun Kim, Taekyun Lee, David Z. Pan, Hyeji Kim, Sham Kakade, and Sitan Chen. Fine-tuning masked diffusion for provable self-correction. In ICML, 2026.
7 comments
response 2/3
Q6. “Seven of the nine Figure 2 panels report TV of a low-dimensional statistic ... which can hide errors in the joint. What do joint-level fidelity measures show?”
Figure 5 now compares complete assignments using MMD. PRS and AR have close observed MMD² on feasible-trained coloring, synthetic SAT, and uniform 6×6 trees, with AR producing more feasible outputs per second. In both biased-tree panels, the two PRS variants have over 100 times lower observed MMD² than prefix AR, which has higher throughput.
Parallel PRS completes every tree request. Joint PRS completes every small-tree request and about 61% on the larger biased trees, so its MMD there describes the outputs that finish within the budget. On unfiltered coloring, both PRS variants complete every request and have MMD estimates close to prefix AR. We show variation between independent target samples to help interpret the finite-sample errors. Appendix J.1 separately reports numerical full-joint TV for the earlier small-tree checkpoints. We have not recomputed those TV values for the continued models.
Q7. “Does the PRS mask improve TV or solve rate over these policies at equal cost?”
We added a controlled coloring study that fixes the Transformer and initial assignments while comparing PRS, truncated PRS, random and confidence masks, and rejection. The budget includes initialization, repair predictions, and confidence-scoring calls, and we report completion together with MMD on complete assignments (Figure 4 and Appendix K). With parallel resampling, PRS and truncated PRS have comparable completion costs and similar observed MMD.
We also revised the SATLIB comparison to include the named remasking methods at equal network-call budgets. On uf100 at 1024 calls, PRS reaches 82.3%/96.6% solved@1/solved@10, ahead of ReMDM (34.8%/60.5%), IPR (42.7%/79.5%), and PRISM (58.8%/81.0%) in Table 1. ReMDM and IPR use the same pretrained model as PRS, while PRISM fine-tunes it.
Q8. “The strong 3-SAT kernel is the uniform-noise DiffUCO ... the masked kernel (MDNS) reaches 39.6% solved@10 on uf100 and 0.0% on uf200 and uf250 ...”
We have updated our SATLIB results. For the masked model, we use PDNS for training and confidence-based unmasking for sampling. On uf100, PRS raises its solved@1/solved@10 from 17.6%/50.6% to 82.3%/96.6%, the highest learned solve rates at 1024 calls in this comparison (Tables 1 and 3). DiffUCO with PRS retains higher solved@1 on uf150 through uf250 and higher solved@10 on uf200 and uf250 (Tables 5 and 6). We therefore compare the two PRS-based solvers across these instance sets and scope the abstract’s solve-rate claim to the tested diffusion methods. Within the masked-model comparison, PRS also gives the largest gain over its base model on all four SATLIB sets.
Q9. “What is one round for WalkSAT, probSAT, FMS, and Moser-Tardos, and how do the methods compare in wall-clock time and at an equal sample budget?”
We now give each method ten runs per formula and compare solved@1 and solved@10 at budgets ranging from 16 to 1024 calls (Table 1 and Appendix E.1). The baseline that resamples all variables uses additional calls for independent draws. WalkSAT and probSAT receive sweeps of n flips, FMS counts proposed flips including rejections, and Moser–Tardos is charged one resampling sweep per call.
Tables 9 and 10 compare three time budgets using diffusion-model runs batched on one GPU and one CPU core for classical runs. We select the diffusion call budget by median elapsed time, and WalkSAT and probSAT have higher solve rates under this protocol. The mask comparisons use one pretrained PDNS checkpoint, with PRISM further fine-tuning it, so variation across independently trained models remains unmeasured.
Q10. “Published methods close to this setting are not compared ... COExpander was not evaluated on SAT in its own paper, so how were it and DiffUCO adapted and tuned?”
We added NExCO, SDDS, and the learned oracle of Kramer et al. to the SATLIB comparison (Tables 1 and 3). DiffUCO uses the number of violated clauses as its energy, while COExpander and NExCO train on CaDiCaL solutions and run on a reduction from SAT to maximum independent set. We also evaluate a direct COExpander SAT adaptation that uses unit propagation. We select inference settings by solved@1 on 200 held-out generated formulas at 1024 calls, with training and adaptation details in Appendix E.1 and Table 2. The requested Constrained Discrete Diffusion comparison for the sampling figure remains outstanding.
response 3/3
Q11. “Table 8’s caption says acceptance improves fidelity ‘consistently’ ... but the 3 by 3, c = 2 row gets worse ... Which statements will be corrected?”
We corrected the acceptance claim to say that it lowers empirical TV in five of six settings and give the small increase from 0.09924 to 0.09926 in Appendix G, Table 12. The updated SATLIB tables report solve rates separately by work and wall-clock budget. These results replace the earlier claim that PRS beats WalkSAT and probSAT at every round budget. On uf250 at 1024 calls, solved@10 is 74.5% for DiffUCO with PRS, 69.0% for the masked model with PRS, and 44.0% for COExpander (SAT). At 1024 sweeps, WalkSAT and probSAT reach 100% and 99%, respectively (Tables 6 and 7).
Q12. “The submission contains no supplementary material and no anonymous link, so none of these exact checks can be verified. Where are these artifacts?”
We apologize for this mistake. We will release the code upon publication.
response 1/3
Thank you for the detailed questions. We revised the theory and experimental comparisons and respond to each question below. References in our responses refer to the revised manuscript; figure numbers inside your quoted questions refer to the original submission.
We clarified how to check the certificate before running the sampler. We first bound the probabilities of new violations and of the paths through which they can enlarge the repair set, accounting for the retained values, and then use those bounds to derive the expected decrease. Section 5 carries out this calculation for trained Transformers on DNA and sinkless cycles using weight bounds and local probability tables. The difficulty of verification varies with the model and problem structure. Extending these checks to more demanding settings offers interesting directions for future work.
We should clarify that we have not established a valid contraction certificate for every coloring, SAT, and tree kernel in the original figure. Those results remain empirical. We therefore added two separately certified model families and a scaling study.
In Section 5, we verify the termination certificate for trained DNA and sinkless-cycle Transformers, with contraction bounds of about 0.84 and 0.91, respectively. These certificates give logarithmic bounds on expected repair rounds and bounds on the total number of selected constraints. We evaluate DNA strings with lengths ranging from 512 to 65,536 letters and cycles with sizes ranging from 16 to 1024 vertices. We also added a circular-ladder scaling experiment (Section 6.1, Figure 3), where every request finishes at all five tested sizes ranging from 60 to 1500 variables, while mean repair rounds increase from 0.66 to 3.02.
We revised Theorem 4.1 so that the acceptance test makes accepted replacements follow the chosen target conditional, allowing more general Transformer proposals. Applying this test requires evaluating the target and proposal probabilities and computing a valid envelope. The earlier small-tree Transformer experiments used the old acceptance rule and remain empirical. Constructing useful envelopes for arbitrary instances remains an open challenge. Our DNA and sinkless-cycle case studies show how to compute them efficiently at scale and obtain useful acceptance bounds (Section 5).
For a clearer comparison, we refer to the case studies in Section 5, which cover DNA strings ranging from 512 to 65,536 letters and sinkless cycles ranging from 16 to 1024 vertices. Corrected repair and rejection from the same learned joint have the same conditional output distribution, so their population TV to any reference target is equal. Figure 2 shows that, for every trained model and tested size, the certified upper bound on expected Transformer predictions per feasible output for corrected repair is below the expected cost of rejection. Appendices L and M give the calculations and sampling times, with setup costs reported separately. The earlier cube and tree timing comparisons remain in Appendix J.3.
We added AR rejection and SMC comparisons, and the larger-tree experiments now use positional Transformers trained on shared, unfiltered examples. In the earlier small-tree comparison, AR rejection had lower full-assignment TV than either MDM variant at both tested biases (Appendix J.1). Those TV calculations use the earlier checkpoints. In the updated larger-tree runs, parallel PRS and prefix AR complete all 90,000 requests at each bias, while AR rejection returns only a small number of feasible outputs (Appendix F.1). The earlier SMC comparison in Appendix J.2 improves completion over AR rejection on the 7×7, bias-4 task.
The revised figure separates models trained on feasible data from those trained on unfiltered data, including paired coloring panels with the same instance and target. We continued MDM training across all six main-figure settings until the validation stopping rule was met, keeping the original data and sampling protocols and retaining each model’s best validation checkpoint (Appendix F.1). In both updated biased-tree panels, the two PRS variants have over 100 times lower observed MMD² than prefix AR.