- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper investigates whether explicitly representing multiple candidate tokens in the intermediate states of discrete diffusion models can improve performance on structured reasoning and planning tasks. The authors propose Binary Discrete Diffusion (BDD), in which each categorical variable is represented by a binary membership vector over the vocabulary. Two variants are introduced: binary symmetric diffusion, which allows candidates to be both added and removed, and binary absorbing diffusion, which progressively prunes candidate sets.
The paper derives the corresponding forward transition kernels, reverse jump rates, and training objectives. Despite the exponentially large state space, the reverse rates can be computed in O(V) time without enumerating all candidate subsets. The authors also develop a confidence-guided sampling procedure that supports candidate revision and re-corruption.
Experiments on Sudoku-Extreme, Boxoban, and graph coloring show that binary symmetric diffusion consistently outperforms masked and uniform diffusion under controlled architectures and training budgets, with larger improvements on difficult instances. Additional experiments on Text8, TinyStories, and OpenWebText demonstrate competitive, although not consistently superior, performance on language generation.
Critical strengths
The paper investigates the corruption-state representation itself rather than focusing exclusively on denoising architectures or sampling schedules. The proposed binary symmetric diffusion process extends candidate-set diffusion by allowing hypotheses to be both eliminated and restored. The mathematical formulation is reasonably clear and well developed, particularly the derivation of the reverse transition rates and the efficient sampling construction that avoids enumerating an exponentially large candidate-set space. This provides a principled and potentially useful extension of existing discrete diffusion frameworks.
The experimental evaluation is a notable strength. The authors compare four diffusion kernels using matched model architectures, training budgets, and sampler-tuning budgets, and report results across five training seeds for the logic tasks. Binary symmetric diffusion achieves consistent improvements on Sudoku, Boxoban, and graph coloring, particularly on more difficult instances. For example, the solve rate on hard Boxoban improves from 78.73% to 84.65% compared with uniform diffusion. The additional analyses across inference budgets, training steps, and task difficulty further support the empirical findings.
Critical weaknesses
Although the paper clearly motivates candidate-set diffusion as a way to represent partially resolved uncertainty, it does not sufficiently explain why explicitly maintaining candidate sets is necessary for effective reasoning. Conventional discrete diffusion models already predict distributions over multiple candidate tokens through their denoisers, even though their intermediate states contain only a single category or a mask. Therefore, the inability to explicitly encode candidate sets does not necessarily imply an inability to represent or revise uncertainty.
Moreover, the proposed candidate sets are generated through independent stochastic bit flips rather than task-aware logical constraints. Consequently, these sets may contain invalid candidates or exclude the correct solution. While the reversible transitions are mathematically well defined, the paper does not provide sufficient evidence that the resulting candidate-set dynamics correspond to more effective logical inference or constraint propagation.
The experimental results establish improvements in solve rate, but they do not fully explain why these improvements arise. A more direct analysis of candidate-set quality, constraint consistency, and error recovery would strengthen the central motivation and clarify the significance of the proposed representation. A central claim is that changing the corruption kernel and intermediate representation can substantially improve the computation learned by the reverse model. However, the strongest experimental results rely on additional candidate-aware sampling mechanisms, making it difficult to isolate the benefits of the proposed kernel itself.
For example, Table 10 shows that, on Sudoku, binary symmetric diffusion achieves 94.37% solve rate after introducing position confidence, while uniform diffusion achieves 95.48%. Binary symmetric diffusion becomes superior only after candidate confidence is introduced, reaching 96.27%.
Furthermore, the candidate-confidence mechanism for binary diffusion retains historical probabilities of individual candidates, whereas the corresponding uniform-diffusion mechanism uses current denoiser probabilities. Although the authors match the tuning budgets, this does not necessarily ensure equivalent access to historical information.
I acknowledge that binary symmetric diffusion also demonstrates advantages without candidate confidence on Boxoban and hard graph coloring. Nevertheless, a more controlled comparison is needed to determine how much of the improvement can be attributed specifically to the candidate-set corruption process rather than the additional sampling mechanisms.
Questions for authors
Q1. Why is an explicit candidate-set state necessary for reasoning?
Conventional discrete diffusion models can already represent uncertainty through their denoising probability distributions and can revise previous predictions through suitable sampling mechanisms. Could the authors clarify what specific computational or representational advantage is obtained by incorporating candidate sets into the diffusion state itself? Is there evidence that this provides capabilities that cannot be achieved as effectively through probabilistic predictions and iterative resampling?
Q2. Can the authors better isolate the contribution of the corruption kernel from the sampling strategy?
Table 10 suggests that candidate confidence plays an important role in the final improvement on Sudoku. Could the authors compare binary symmetric diffusion against a history-aware uniform-diffusion sampler that maintains comparable historical confidence information? Such an experiment would help establish whether the improvement primarily arises from the proposed state representation or the candidate-aware revision mechanism.
Q3. Do the intermediate candidate sets exhibit meaningful reasoning behavior?
Could the authors provide quantitative analyses of candidate-set dynamics, such as the proportion of candidate sets containing the ground-truth token, the degree to which candidates satisfy local constraints, and the frequency of successful recovery after an incorrect candidate elimination? It would also be useful to investigate whether these behaviors correlate with final solve success.
3 comments
W3/Q3. Do the intermediate candidate sets exhibit meaningful reasoning behavior? Under the selected sampler the sets of binary symmetric do, while under the exact ancestral sampler all sets behave as random sets by construction. To measure this, we performed a new experiment that tracks during generation the three quantities the reviewer proposes on 512 test instances per task. As the reference for random sets, which we call the "null", we compute each quantity on the states obtained by applying forward noise to the final solution of the trajectory. We then confirm that, under the exact ancestral sampler, the three quantities are within 0.02 of the null, for all kernels and tasks. Under the selected sampler (see Table A below), we instead measure:
- Containment (share of positions whose set holds the correct token): binary symmetric is above the null on Sudoku (0.70 vs 0.63).
- Consistency (share of candidates not ruled out by a fixed position, i.e. a clue or a single-candidate cell): the sets of binary symmetric satisfy more constraints than the null on Sudoku (0.64 vs 0.43) and on Boxoban (0.54 vs 0.17).
- Recovery (how often the correct/wrong token returns after leaving a set or position): on all tasks, binary symmetric and uniform recover an eliminated correct token far more often than a wrong one (more than 5 times as often).
- Relation to solving: on all tasks, the two kernels that recover the correct token selectively, binary symmetric and uniform, have the highest solve rates on the hard split. On Sudoku, giving uniform memory raises both its recovery and its solve rate.
Presentation. For clarity, we improved the exposition in two places: the submission's §5.3 is now two short subsections (§3.3 and §3.4) that explain in more detail how an O(V) procedure is obtained from 2^V possible states, and the role of the time parameterization; and in §3.1 and §3.2 we streamlined some of the derivations and simplified the expressions of the model reverse rates of the binary kernels (Eqs. 12 and 14).
Table A. Containment and consistency are given as model / null, and recovery as the per-step return rate of an eliminated correct vs wrong token. A single token counts as a one-token set and a masked position as the full set.
| Task | Kernel | Containment, model / null | Consistency, model / null | Recovery per step, correct vs wrong token | Hard solve rate |
|---|---|---|---|---|---|
| Sudoku | Binary symmetric | 0.70 / 0.63 | 0.64 / 0.43 | 0.71 vs 0.10 | 92.66 |
| Uniform with memory | 0.37 / 0.34 | 0.17 / 0.15 | 0.62 vs 0.02 | 91.49 | |
| Uniform without memory | 0.32 / 0.34 | 0.15 / 0.15 | 0.30 vs 0.01 | 89.81 | |
| Binary absorbing | 0.99 / 0.99 | 0.46 / 0.46 | 0.22 vs 0.22 | 81.08 | |
| Masked | 0.98 / 0.98 | 0.30 / 0.30 | 0.20 vs 0.20 | 76.12 | |
| Boxoban | Binary symmetric | 0.65 / 0.62 | 0.54 / 0.17 | 0.68 vs 0.07 | 84.65 |
| Uniform | 0.41 / 0.41 | 0.04 / 0.05 | 0.31 vs 0.03 | 78.57 | |
| Binary absorbing | 0.99 / 0.99 | 0.81 / 0.83 | 0.23 vs 0.22 | 69.13 | |
| Masked | 0.99 / 0.99 | 0.43 / 0.43 | 0.12 vs 0.11 | 75.47 | |
| Graph coloring | Binary symmetric | 0.57 / 0.62 | 0.49 / 0.49 | 0.55 vs 0.09 | 64.13 |
| Uniform | 0.39 / 0.45 | 0.12 / 0.12 | 0.34 vs 0.03 | 61.41 | |
| Binary absorbing | 0.99 / 0.99 | 0.90 / 0.94 | 0.09 vs 0.10 | 54.77 | |
| Masked | 0.99 / 0.98 | 0.65 / 0.62 | 0.17 vs 0.16 | 4.85 |
Dear Reviewer, the author-reviewer discussion ends on 18 November (AoE). We would be grateful to know whether our response addresses your concerns, and we are happy to answer any further questions. Thank you for your time.
We thank the reviewer for their feedback.
W1/Q1. What advantage is obtained by putting candidate sets into the diffusion state itself? With candidate sets the model can reuse its previous computation, since the state itself records which tokens are still possible at each position. A masked or uniform model does predict a distribution over tokens, but it discards this distribution after sampling a single token per position, and thus has to recompute it at every step. We have improved the wording in the introduction to better convey this point. As for evidence, the closest baselines to "probabilistic predictions and iterative resampling" are masked and uniform diffusion with a tuned, confidence-guided re-corruption sampler. These are precisely the baselines in our main results, where binary symmetric leads in most settings. In our answer to Q3 below, we also verify that binary symmetric better leverages candidate sets during denoising.
W2. Candidate sets are generated by random bit flips rather than logical constraints. The sets are indeed random by construction, just like masks and uniform noise. Accordingly, under the exact ancestral sampler, the sets behave like random sets, and the reasoning relies on the model's internal computation. With the confidence-guided sampler the model then becomes able to shape these sets, and we verify in our answer to Q3 that this helps it during denoising.
W3/Q2. Separating the kernel from the sampler, and a history-aware uniform sampler. The revised submission now separates kernel and sampler for each task (§5.1 and the new Table 2, a compact version of the submission's Table 10), where the lead of binary symmetric over uniform requires candidate confidence only on Sudoku.
We also ran the comparison the reviewer proposes regarding the confidence mechanism. We now compare three rules for uniform's confidence:
We re-tuned uniform's sampler with each rule on validation, with the same protocol and budget as the submission, to obtain:
The rules and their selection are detailed in App. F.4. We also checked the remaining Sudoku lead of 1.17 points on more hard boards: it is 1.22 on 218k symmetry-transformed copies of the 9,087 hard test boards, and 1.34 on 5,543 hard validation boards not used for tuning.