acceptodds
Under review as a conference paper at ICLR 2027

How Good Are Masked Discrete Diffusion Models at Constrained Sampling?

Abstract

We study constrained sampling with masked discrete diffusion models in combinatorial domains with sparse constraint dependency graphs. Adopting the masking policy of partial rejection sampling (PRS), we extend its classical repair guarantees from fixed product distributions of independent variables to an adaptive repair process driven by the conditional distributions of masked diffusion. We obtain Lov\'asz local lemma–like conditions under which masked diffusion efficiently reaches a feasible assignment. Under the symmetric conditions, the expected number of repair rounds is at most logarithmic in the number of constraints, and the expected total number of constraints selected across rounds is at most linear, matching the classical PRS bounds for product distributions. We also give conditions for tractable exact sampling from the data distribution conditioned on feasibility. We test the distributional fidelity of the model for hypergraph coloring, uniform SAT, and rooted spanning trees, and show strong empirical results against state of the art diffusion solvers on 3-SAT.

Primary area:
generative models
Keywords:
masked discrete diffusion, sparse dependencies, Lovasz local lemma, partial rejection sampling, combinatorial optimization

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_DugJOpenReview ↗
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
  1. Comprehensive theory and validation.

    Every theorem and corollary comes with a complete proof.

  2. 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
  1. 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.

  2. 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
  1. 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?
  2. κ 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)?
  3. 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?
  4. 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?
  5. 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?
  6. 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?
  7. 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?
  8. 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?
  9. 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?
  10. 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?
  11. 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?
  12. 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
AuthorsOpenReview ↗

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.

Q1. “How can the certificate be verified for a trained masked diffusion model before running it?”

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.

Q2. “What are κ, the rounds, and the repaired constraints for the Figure 2 configurations, and do the rounds grow as O(log m) ...?”

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.

Q3. “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?”

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).

Q4. “How do acceptance plus restart compare with rejection sampling from the same model in TV and time?”

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.

Q5. “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?”

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.

AuthorsOpenReview ↗

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.

AuthorsOpenReview ↗

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.

Reviewer_J38zOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies constrained sampling by combining the mask-selection rule of partial rejection sampling (PRS) with learned conditional resampling kernels. It provides sufficient conditions for efficient termination and an acceptance-and-restart correction for sampling the target distribution conditioned on feasibility. Evaluation includes finite-state verification, distributional comparisons on SAT, coloring, and rooted trees, and SATLIB feasibility experiments using DiffUCO and MDNS.

Critical strengths
  1. A useful distinction between feasibility and distributional correctness. The paper demonstrates that even exact conditional predictions can produce biased feasible outputs when repair locations are selected adaptively. This identifies an algorithmic source of error that cannot be eliminated merely by improving prediction accuracy, making the analysis informative beyond constraint-satisfaction rates.

  2. The correction has concrete small-scale validation. The acceptance-and-restart construction provides an exactness guarantee under explicit assumptions. Table 9 supports the mechanism through full-joint distribution calculations: correction reduces TV error for all six trained checkpoints on the small SAT instance. This is substantive evidence, although its scope is limited.

Critical weaknesses
  1. The experiments do not isolate the benefit of PRS-specific repair. Table 1 allows up to 64 generation/repair rounds, including the initial draw, with 16 denoising steps per round, while the diffusion baselines without repair generate once. The paper does not report matched-cost comparisons against independent restarts or simpler masking policies. At 64 rounds, DiffUCO-based repair achieves 88.9% solved@1 versus 85.5% and 86.1% for WalkSAT and probSAT, but its solved@10 is lower: 96.9% versus 99.7% for both. Since round costs differ, these results do not establish an efficiency advantage. The strongest diffusion result also uses uniform-noise DiffUCO rather than masked MDNS, which reaches 39.6% solved@10; it therefore provides limited direct support for masked-diffusion performance. Overall, the independent empirical contribution of PRS mask selection remains unclear.

  2. The distributional results leave the practical accuracy–cost benefit insufficiently established. Figure 2 includes a constrained-AR baseline, but improvements over Uniform PRS on biased targets alone do not isolate the proposed mechanism, since Uniform PRS targets a different distribution. Most panels evaluate summary-statistic TV; only the two 3×33\times3 biased-tree panels evaluate full-joint TV. Table 9 provides meaningful full-joint evidence for the correction, but the correction experiments do not establish whether corrected local repair is computationally more efficient than direct rejection sampling from the same learned joint distribution. Moreover, Appendix H.5 establishes common-joint compatibility for the structured count-energy models but reports discrepancies for the 3×33\times3 biased-tree Transformer models. Thus, the demonstrated scope of the exactness guarantee and the practical value of the correction for native neural MDMs remain limited.

Questions for authors
  1. What constitutes one round for WalkSAT and probSAT, and how does its computational cost compare with a neural repair round? Are matched-wall-clock SAT results available?

  2. Using the same trained kernel and inference budget, does PRS masking outperform independent full restarts, random remasking, or resampling only variables in violated constraints? This comparison would materially affect my assessment of the repair framework.

  3. For the count-energy configurations that satisfy common-joint compatibility, how does corrected repair compare with direct rejection sampling from the same learned joint distribution in computational cost per feasible sample? Can the authors also provide a non-vacuous lower bound on acceptance probability over reachable repair states?

4 comments
AuthorsOpenReview ↗

response 1/2

Thank you for the detailed feedback. We revised the experiments to make the comparisons between sampling methods and masking policies clearer. References in our responses below refer to the revised manuscript.

“What constitutes one round for WalkSAT and probSAT, and how does its computational cost compare with a neural repair round? Are matched-wall-clock SAT results available?”

We have revised the SATLIB experiment to compare methods at matched computational budgets. We charge WalkSAT and probSAT one sweep of n variable flips per network call. A full neural draw costs 16 calls, and one repair round costs 16 for DiffUCO or min(16, |B|) for the masked model with repair mask B.

Appendix E.1 also compares 0.1, 1, and 10 seconds per formula, with ten diffusion-model runs batched on one GPU and ten classical runs sharing one CPU-core budget (Tables 9 and 10). For the diffusion models, we select the largest call budget whose median time fits each limit. On uf100, WalkSAT reaches 96.2% solved@1 and 99.9% solved@10 at 0.1 seconds, exceeding the measured learned methods even at 10 seconds. Local search heuristics are known to be extremely strong baselines for random 3-SAT. These instances also provide a challenging test for neural methods and help reveal differences in their ability to find satisfying assignments.

“Using the same trained kernel and inference budget, does PRS masking outperform independent full restarts, random remasking, or resampling only variables in violated constraints?”

We now compare PRS, full restarts, and violated-clause masks using the same pretrained masked model. At 1024 calls on uf100, PRS reaches 82.3%/96.6% solved@1/solved@10, compared with 71.3%/88.5% for full restarts and 29.8%/62.1% for resampling variables in all currently violated clauses (Table 1).

In the controlled coloring experiment, every policy uses the same Transformer, initial assignments, and model-evaluation budget. With parallel resampling, PRS performs similarly to resampling only variables in violated constraints, which we call truncated PRS, with comparable completion costs and observed MMD on complete assignments. Both reach feasibility with substantially fewer model evaluations than random remasking or independent full restarts, which we evaluate as rejection sampling (Figure 4 and Appendix K).

“For the count-energy configurations that satisfy common-joint compatibility, how does corrected repair compare with direct rejection sampling from the same learned joint distribution in computational cost per feasible sample? Can the authors also provide a non-vacuous lower bound on acceptance probability over reachable repair states?”

For the compatible count-energy models, corrected repair and rejection have the same conditional target, and Appendix J.3 gives positive acceptance minima for each fixed model. Excluding setup, rejection is faster on the cube. On the 7×7 trees, corrected repair returns all 30,000 outputs in times ranging from 4.2 to 29.6 seconds, while rejection returns between 1588 and 2627 outputs within 180 seconds.

In the DNA and sinkless-cycle case studies, we compute acceptance lower bounds for each trained model and tested instance, then apply Theorem 4.1 to bound the expected number of Transformer predictions per feasible output. Figure 2 shows that these upper bounds are below the expected cost of rejection at every tested size. The method includes full rejection sampling as the special case in which we restart after every infeasible assignment. Local structure can let us retain most of an assignment and repair violations at substantially lower cost, as the exact-sampling case studies demonstrate. The uncorrected remasking experiment provides complementary empirical evidence, with low observed MMD on complete assignments and substantially fewer model evaluations than full rejection (Figure 4).

“The distributional results leave the practical accuracy–cost benefit insufficiently established. Figure 2 includes a constrained-AR baseline, but improvements over Uniform PRS on biased targets alone do not isolate the proposed mechanism, since Uniform PRS targets a different distribution.”

We updated the original Figure 2, now Figure 5, to use the same model family, positional Transformers, throughout the learned-sampler comparisons. We replaced TV on summary statistics with MMD on complete assignments, so we compare outputs across the full set of variables. The figure also reports sampling speed and variation between independent target samples.

PRS and AR have close observed MMD² on coloring (trained on feasible instances) , 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 significantly lower observed MMD² than prefix AR. Parallel PRS returns valid trees with every single sample. We now include Uniform PRS only for uniform targets to avoid confusion.

AuthorsOpenReview ↗

response 2/2

We establish exact corrected sampling for the trained DNA and sinkless-orientation Transformers and derive upper bounds on running time that are much lower than the expected running time of rejection sampling. The feasibility/distributional comparison against AR models can also be clearly seen in figure 3 in our circular ladder experiment.

“The strongest diffusion result also uses uniform-noise DiffUCO rather than masked MDNS, which reaches 39.6% solved@10; it therefore provides limited direct support for masked-diffusion performance.”

The updated SATLIB study uses a masked model trained with PDNS. With this model, PRS raises solved@1/solved@10 from 17.6%/50.6% at 16 calls to 82.3%/96.6% at 1024 calls (Table 1).

Thank you for the detailed responses and additional experiments. I appreciate the effort the authors have put into addressing the reviewers' concerns. While the revisions clarify several points, I still have reservations about the novelty and significance of the contribution. I will therefore maintain my original rating.

Even if you maintain your original rating, could you please explain what could potentially help address the reservations around significance and novelty? We would really appreciate if you could provide some more specific directions for improvement.

Is this result already somewhere in the literature? Have masked diffusion models been certified in any capacity in previous work on combinatorial instances? Is there prior work that resolves exact sampling from combinatorial distributions conditioning on feasibility?

Given that both empirically (e.g, satlib results and other ablations/figures) and conceptually (we draw a connection to partial rejection sampling from masked diffusion that wasn't highlighted before and we show case studies where we explicitly convert the theory to practical certificates) the paper achieves its stated goals, it is unclear to us how we could proceed to make this contribution more significant or novel.

Do you believe there is no room for improvement and the paper shouldn't be accepted regardless of any fixes or changes?

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

This paper draws a connection between constrained sampling with masked discrete diffusion models and partial rejection sampling (PRS). More precisely, it provides an algorithm that is inspired by PRS, along with analysis that proves Lovász local lemma–style conditions under which iteratively masking and resampling variables involved in violated constraints reaches a feasible solution efficiently; under symmetric assumptions, the repair process requires logarithmically many rounds and a linear total number of repaired constraints. It further distinguishes feasibility from exact conditional sampling, giving additional conditions for sampling from the data distribution conditioned on feasibility, and evaluates the approach on SAT, hypergraph coloring, and rooted spanning-tree tasks, with strong feasibility results on harder 3-SAT instances.

Critical strengths

1.) The authors use the PRS repair/masking policy to determine which variables a masked discrete diffusion model should resample after constraint violations are detected. This is an idea that is perhaps natural at first glance, but to get it to work in a context where the distribution is not a product distribution is not obvious/straightforward.

2.) The authors characterize both the termination of the resampling and the correctness of its distributional output.

Critical weaknesses

1.) The certificate condition is demonstrated analytically for the PRS special case (product distribution) and checked exactly in small finite-state/enumerable settings, but not verified for the large learned-model experiments that drive the practical performance claims. If I'm understanding correctly, the condition (equation 8) amounts to a drift condition that provides a κ\kappa- factor contraction in potential. What remains unclear is how prevalent this condition is for realistic learned conditional kernels, and whether it can be checked or bounded at useful scale.

2.) As the authors state, their experiments do not demonstrate that exact certificate checks scale to large models, and their SATLIB study measures feasibility rather than the output distribution.

Questions for authors

I appreciate the paper’s extension of PRS-style repair guarantees to masked-diffusion resampling, as well as its distinction between feasibility and exact constrained sampling.

My question concerns the practical scope of the certificate condition in Theorem 3.1. For a trained masked-diffusion kernel, what quantities would need to be computed or bounded to verify the condition? Can the authors provide a non-product, learned-kernel example in which the certificate is verified without exhaustive state-space enumeration, or discuss a scalable sufficient surrogate? This would help clarify whether the analysis is intended primarily as a conceptual characterization or as an operational guarantee for realistic models.

1 comment

We would like to thank the reviewer for their feedback. To address the concerns regarding the certificates we added two case studies to make the practical implications of the theory clearer. References in our responses below refer to the revised manuscript.

Regarding your question, the condition itself provides some insight. Since the condition depends on paths and probability bounds there are couple of imporant properties that determine how easy the condition might be to verify:

  • Can constraint violations propagate/overlap easily? If yes then repairs will be harder to bound. For our case studies the paths in the condition are short which makes it easier to verify. Calculating probabilities along paths can be computationally expensive. One way around that is to use crude upper bounds but they may be too loose to establish a contraction. So in general, the constraint structure of the problem plays a crucial role. If constraint repairs can't propagate violations easily, then the certificate may scale quite well (as in our case studies).
  • Can we control the output probabilities of the model? If we can obtain bounds on the probabilities of the events this can help us control the contributions in the sum to some extent.

“What remains unclear is how prevalent this condition is for realistic learned conditional kernels, and whether it can be checked or bounded at useful scale.”

“Can the authors provide a non-product, learned-kernel example in which the certificate is verified without exhaustive state-space enumeration, or discuss a scalable sufficient surrogate?”

We added two case studies in Section 5 that show how to check the certificate for trained Transformers using their weights. For the DNA strings case study, a condition on the final normalization and output layers bounds each letter probability and gives a contraction factor of about 0.84. A similar computation can be carried out for sinkless orientations. We also compute acceptance bounds and implement corrected sampling for DNA strings with up to 65,536 letters and cycles with up to 1024 vertices.

These examples show that the connection to PRS has both conceptual value and practical implications. Efficient verification and corrected sampling depend on the model and the combinatorial structure of the problem, so whether they are practical will vary. For instance, we do not expect simple, efficiently verifiable conditions to give useful guarantees for dense Transformers on random 3-SAT instances near the hardness threshold.

“As the authors state, their experiments do not demonstrate that exact certificate checks scale to large models, and their SATLIB study measures feasibility rather than the output distribution.”

In our case studies we verify termination and exact corrected sampling from the learned distribution conditioned on feasibility for DNA strings with lengths ranging from 512 to 65,536 letters and sinkless orientations on cycles with sizes ranging from 16 to 1024 vertices. The broader coloring, tree, and SAT sampling experiments measure completion, computational cost, and distributional error empirically. Our revised SATLIB study measures the fraction of formulas solved to investigate whether this PRS-based approach can inform the design of diffusion based solvers.

Comments on the paper

2 comments
AuthorsOpenReview ↗

update on the paper

Dear Reviewers,

Thank you for your valuable feedback. We have taken your concerns into consideration and we have updated the manuscript with the following:

  • Case studies on DNA sequence repair and sinkless orientations that certify termination and exact sampling from the target feasible conditional using transformers.
  • Experiment that compares various masking policies to PRS.
  • Scaling experiment against AR model.
  • Updated the distributional experiments to use more accurate distributional fidelity metrics and a more consistent setup.
  • Updated the SATLIB experiment.

We hope those address the main concerns expressed regarding practical certification of our termination conditions and our corrected sampler. We also hope that the additional/improved experiments provide a clearer picture about the empirical viability of the PRS-based approach.

We will be happy to address any further comments and concerns!

Dear Reviewers,

Since we're near the end of the discussion period we would appreciate if you could reconsider your evaluations given all the new results we provided. Here are some of the key takeaways (figures and tables are numbered according to the revision):

  • Case studies for certification. We provided examples where termination can be easy to certify because it yields explicit conditions on the weights of the model. Furthermore, we showed how models can certifiably sample from the feasible target distribution on DNA repair instances (strings) of length up to ~65k and find sinkless orientations on graphs of size up to ~1k.

  • We provided a masking study as requested that show clear benefits over alternatives such as confidence based or random masking.

  • Generalized acceptance correction. We extended the exact-sampling guarantee to proposal kernels that don't satisfy joint compatibility. The original acceptance rule and envelope condition are recovered exactly when the original assumption holds.

  • We provided examples in the case studies where the acceptance mechanism can be certifiably much faster than rejection sampling. Table 15 in the appendix provides a clear example of the corrected mechanism though the benefits over rejection become apparent as the scale of the instances increases. The masking policy ablation in figure 4 also compares against a rejection baseline and shows how PRS achieves feasibility much more efficiently.

  • We provided multiple pieces of evidence for the scalability of the PRS approach, including the case studies and Figure 3 that shows how consistently PRS masking returns feasible samples much more reliably than the baselines as the size of the instances grows while maintaining good distributionaal fidelity. Furthermore, in the update figure 5 PRS based sampling, while sometimes weaker than AR on sampling fidelity and feasibility on small instances, it often overtakes the AR (especially when it comes to feasibility) baseline on larger sizes (e.g., see panels e and f in figure 5 in the revision.).

  • We added several baselines to the SATLIB experiments and refined the comparisons in response to reviewer feedback. Among the neural methods, our PRS-based methods achieve the highest solved @1 on all budgets and the highest solvest @10 on the 2 largest budgets.

We believe those results provide substantial support for our contribution and open up several possibilities for future work. We hope they address the reviewer's concerns and welcome any additional feedback and comments for improvement.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.