acceptodds
Under review as a conference paper at ICLR 2027

Binary Discrete Diffusion: Candidate-Set Diffusion for Logic and Planning Tasks

10 views

Abstract

Discrete diffusion models iteratively denoise a noisy sequence of categorical data such as text, enabling any-order generation with self-correction and in-filling capabilities. This makes them promising candidates for reasoning, planning, and constrained-generation tasks like coding and math. Yet masked and uniform diffusion erase a token's identity in a single corruption event, so their noisy states cannot explicitly represent partially resolved uncertainty in which several alternatives remain plausible. We close this gap with Binary Discrete Diffusion, a family of continuous-time discrete-diffusion processes whose noisy state is a set of candidate tokens per position, represented as a binary membership vector. Binary diffusion changes candidate sets through additions and removals, allowing information to be lost and recovered gradually while the diffusion state itself represents partial uncertainty. On Sudoku-Extreme, Boxoban, and graph coloring, binary symmetric diffusion consistently outperforms strong, well-tuned masked and uniform baselines under matched architectures and controlled training, sampling, and tuning budgets, with its largest gains on the hardest instances, while remaining competitive on language modeling (Text8, TinyStories, OpenWebText). These results support candidate sets as an effective intermediate representation for iterative reasoning and show that the corruption kernel can materially change the computation learned by the reverse model.

Primary area:
generative models
Keywords:
discrete diffusion, candidate sets, binary diffusion, continuous-time Markov chain (CTMC), reasoning, planning, constraint satisfaction, masked diffusion, uniform diffusion, diffusion language models, Sudoku, Boxoban, graph coloring

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_dk1YOpenReview ↗
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

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:

  • No memory: the token's current probability (the submission's rule for uniform).
  • Same memory as binary: its probability the last time it was the token at its position.
  • Last sampled: its probability the last time the model sampled it.

We re-tuned uniform's sampler with each rule on validation, with the same protocol and budget as the submission, to obtain:

  • Boxoban and graph coloring: no memory is selected, so the submission numbers remain unchanged.
  • Sudoku: the same memory as binary is selected. This helps uniform but does not close the gap (uniform goes from 89.81 to 91.49 on the hard split, vs 92.66 for binary symmetric).

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.

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.

TaskKernelContainment, model / nullConsistency, model / nullRecovery per step, correct vs wrong tokenHard solve rate
SudokuBinary symmetric0.70 / 0.630.64 / 0.430.71 vs 0.1092.66
Uniform with memory0.37 / 0.340.17 / 0.150.62 vs 0.0291.49
Uniform without memory0.32 / 0.340.15 / 0.150.30 vs 0.0189.81
Binary absorbing0.99 / 0.990.46 / 0.460.22 vs 0.2281.08
Masked0.98 / 0.980.30 / 0.300.20 vs 0.2076.12
BoxobanBinary symmetric0.65 / 0.620.54 / 0.170.68 vs 0.0784.65
Uniform0.41 / 0.410.04 / 0.050.31 vs 0.0378.57
Binary absorbing0.99 / 0.990.81 / 0.830.23 vs 0.2269.13
Masked0.99 / 0.990.43 / 0.430.12 vs 0.1175.47
Graph coloringBinary symmetric0.57 / 0.620.49 / 0.490.55 vs 0.0964.13
Uniform0.39 / 0.450.12 / 0.120.34 vs 0.0361.41
Binary absorbing0.99 / 0.990.90 / 0.940.09 vs 0.1054.77
Masked0.99 / 0.980.65 / 0.620.17 vs 0.164.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.

Reviewer_mU1iOpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The authors introduce a new alternative akin to discrete diffusion, where, instead of modelling directly the current category, the possible support of the clean point, x0x_0, is diffused. This work introduces the needed formalism for both absorbing and symmetric variants, and show empirically that the method works on standard benchmarks, and even outperforms discrete diffusion on some standard small-scale reasoning benchmarks.

Critical strengths
  • The paper is well-presented and the framework is mathematically sound.
  • It is easy to follow, and the idea is clear and natural.
  • The method is novel, and the results suggest that the method works on standard benchmarks.
Critical weaknesses
  • As the authors suggest, the Gen PPL metric on its own is flawed, the Pareto fronts with entropy are standard and more resilient indicators of quality. While we can agree on its weakness, I think it would largely strengthen the work to report those frontiers too alongside usual baselines. MAUVE on its own is understandable, but as a Pareto front with entropy much less so; therefore, practitioners will be able to assess the model’s unconditional performance much more easily with the Gen PPL fronts.
Questions for authors

See the above for the Gen. PPL.

I think this is a good paper, and, should the Gen PPL concern be addressed, I would be happy to raise my score.

2 comments

We thank the reviewer for their feedback.

W1/Q1. GenPPL–entropy frontiers. The GenPPL–entropy frontiers are now in the main text (§5.2, Fig. 4) for the two binary kernels alongside the masked and uniform baselines, obtained from a temperature sweep of each kernel's selected sampler and scored with GPT-2 Large. On these frontiers, binary symmetric is best on Text8 and OpenWebText, and masked on TinyStories. They now replace the MAUVE–entropy frontiers.

We hope the new GenPPL frontiers address the reviewer's concerns, and we appreciate their openness to reconsidering their score.

I thank the authors for having provided the Pareto frontiers; I think they are much more telling than the previous reported metrics. I raise my score to a 4.

Reviewer_75euOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper propose Binary Discrete Diffusion, a continuous-time discrete diffusion processes whose noisy states are candidate tokens represented by binary membership vector. During the denoising process of standard discrete diffusion, a position is either known or not. Here the noisy state is a set of candidate tokens. In the symmetric kernel candidates get added and dropped, so the true token can vanish and come back. In the absorbing kernel noise only adds candidates and denoising prunes. The network still predicts one clean token per position. The re-corruption sampler is extended so it can also choose which candidates to put back. The method is evaluated on different tasks.

Critical strengths
  • The paper focus on an interesting problem of continuous-time discrete diffusion method
  • The paper is clearly written and easy to follow
Critical weaknesses
  • On Sudoku the gain seems to come from the sampler instead of the kernel. At every sampler stage the two kernels share, uniform matches or beats binary symmetric. The lead only appears once candidate confidence is added. Boxoban show a kernel effect under ancestral sampling, graph colouring only from the re-corruption stage on, Sudoku never. The main text is suggested to separate kernel from sampler per task rather than present all three as kernel results
  • Scale of some experiments appears limited. Logic models have 43M parameters and text runs TinyStories and OpenWebText use a vocabulary of 1024 tokens. The limiting state holds about half the vocabulary as candidates per position, pooled into one embedding that the authors themselves doubt will stay expressive at larger vocabularies in Section 5.3. There is no result at the larger scaled vocabularies where current dLLMs are actually used
Questions for authors

I'm open to change my recommendation should the concerns in weaknesses and the questions here are well addressed.

  • Could you state per task whether the gain over uniform survives without candidate confidence in the main text?
  • What is the per-step wall-clock of each kernel at the reference NFE?
4 comments

We thank the reviewer for their feedback.

W1/Q1. Does the gain over uniform require the confidence-guided sampler, per task? The revised main text now states this clearly for each task in §5.1, which includes a new Table 2: a compact version of the submission's Table 10 that builds the sampler in stages per task. In particular:

  • Boxoban: binary symmetric leads at every stage, from ancestral sampling on.
  • Graph coloring: binary symmetric leads from the re-corruption stage on.
  • Sudoku: binary symmetric leads once candidate confidence is introduced.

Accordingly, the abstract, introduction and conclusion now state the results on the logic tasks as those of binary symmetric diffusion together with the confidence-guided sampler.

W2. Scale. Our main goal in this work is to show the benefits of binary diffusion on logic and planning tasks in a controlled comparison of the four kernels. Our 43M-parameter models are larger than those of relevant prior work on logic tasks such as Sudoku and mazes, which use 6M to 27M parameters (Ye et al., 2025; Kim et al., 2025; Wang et al., 2025; Jolicoeur-Martineau, 2025). On text, our claim is only that the binary kernels can be competitive with the masked and uniform baselines, and our models and training budgets are comparable to those of published work on diffusion language models (Lou et al., 2024; Sahoo et al., 2024; Sahoo et al., 2025; von Rütte et al., 2025). Our comment on expressivity in §5.3 of the submission was meant to point out possible room for improvement in the embedding layer, which we can explore in future work.

Q2. Per-step wall-clock of each kernel at the reference NFE. The binary kernels are at most 3% slower per sampling step than uniform or masked, on every task in the paper (Table A below), since almost all of a step is the forward pass of the network, and this is identical across kernels except for the input embedding.

Table A. Time per sampling step at the reference NFE. We time complete generations under ancestral sampling on one RTX PRO 6000, divide the total time by the NFE, and take the median over at least ten full generations after a warm-up period.

TaskSequence lengthBatch sizeBinary symmetric (ms)Uniform (ms)Binary absorbing (ms)Masked (ms)
Sudoku8125610.9810.9811.0010.97
Boxoban22825625.6725.6725.6625.64
Graph coloring642568.888.888.868.83
Text82566413.7513.7613.7513.75
TinyStories5126428.6328.0628.5727.90
OpenWebText10243260.5159.9960.4959.82

We hope these answers address the reviewer's concerns, and we appreciate their openness to reconsidering their recommendation.

References

  • Alexia Jolicoeur-Martineau. Less is More: Recursive Reasoning with Tiny Networks. arXiv:2510.04871, 2025.
  • Jaeyeon Kim, Kulin Shah, Vasilis Kontonis, Sham M. Kakade, and Sitan Chen. Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions. In Proceedings of the 42nd International Conference on Machine Learning (ICML), volume 267 of Proceedings of Machine Learning Research. PMLR, 2025.
  • Aaron Lou, Chenlin Meng, and Stefano Ermon. Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution. In Proceedings of the 41st International Conference on Machine Learning (ICML), volume 235 of Proceedings of Machine Learning Research, pp. 32819–32848. PMLR, 2024.
  • Subham Sekhar Sahoo, Marianne Arriola, Yair Schiff, Aaron Gokaslan, Edgar Marroquin, Justin T. Chiu, Alexander Rush, and Volodymyr Kuleshov. Simple and Effective Masked Diffusion Language Models. In Advances in Neural Information Processing Systems (NeurIPS), volume 37, 2024.
  • Subham Sekhar Sahoo, Justin Deschenaux, Aaron Gokaslan, Guanghan Wang, Justin T. Chiu, and Volodymyr Kuleshov. The Diffusion Duality. In Proceedings of the 42nd International Conference on Machine Learning (ICML), volume 267 of Proceedings of Machine Learning Research, pp. 52584–52619. PMLR, 2025.
  • Dimitri von Rütte, Janis Fluri, Yuhui Ding, Antonio Orvieto, Bernhard Schölkopf, and Thomas Hofmann. Generalized Interpolating Discrete Diffusion. In Proceedings of the 42nd International Conference on Machine Learning (ICML), volume 267 of Proceedings of Machine Learning Research, pp. 61810–61843. PMLR, 2025.
  • Guan Wang, Jin Li, Yuhao Sun, Xing Chen, Changling Liu, Yue Wu, Meng Lu, Sen Song, and Yasin Abbasi Yadkori. Hierarchical Reasoning Model. arXiv:2506.21734, 2025.
  • Jiacheng Ye, Jiahui Gao, Shansan Gong, Lin Zheng, Xin Jiang, Zhenguo Li, and Lingpeng Kong. Beyond Autoregression: Discrete Diffusion for Complex Reasoning and Planning. In International Conference on Learning Representations (ICLR), 2025.

Dear Reviewer, the author-reviewer discussion ends on 18 November (AoE). Following your questions, we now state in the paper whether the gain over uniform survives needs candidate confidence or not per task, and our reply also reports the per-step wall-clock of every kernel. We would be grateful to know whether this addresses your concerns, and we are happy to answer any further questions. Thank you for your time.

I thank the authors for the response. As promised, I raise my rating to a 3.

Remaining concerns for the final version: the cited diffusion LMs use the 50257-token GPT-2 tokenizer, while the text runs here use 1024. The binary input layer costs O(V·d) per position, so the 3% overhead and the capacity of the pooled embedding are untested at realistic vocabularies. It'd be great if the limitations section state this. Additionally, mean and sd over the five seeds would show whether the 1.17 point lead is robust.

The author's response came in three days ago, and it took me some time to get back to it. I understand the discussion is coming to an end, so please do not feel obliged to respond to the remaining concerns. My score increase does not depend on these points.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.