Binary Discrete Diffusion: Candidate-Set Diffusion for Logic and Planning Tasks
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, the symmetric formulation of binary 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.
Related
- Continuous Diffusion Scales Competitively with Discrete Diffusion for Language
- A stabilized scheme satisfying the discrete maximum principle for a time fractional convection-diffusion-reaction equation
- Gradient flow formulation and discrete approximation of reaction-cross-diffusion systems with size exclusion
- Jumping up and down: Denoiser diffusion models for discrete ordinal data
- Discrete Diffusion Models are Minimax Optimal Under Sparsity
BibTeX
@misc{noguerales2026binary,
title = {{Binary Discrete Diffusion: Candidate-Set Diffusion for Logic and Planning Tasks}},
author = {Rodrigo Casado Noguerales and Dimitri von Rütte and Bernhard Schölkopf and Thomas Hofmann and Aran Raoufi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.28543},
eprint = {2610.28543},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.28543},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Binary Discrete Diffusion: Candidate-Set Diffusion for Logic and Planning Tasks
AU - Rodrigo Casado Noguerales
AU - Dimitri von Rütte
AU - Bernhard Schölkopf
AU - Thomas Hofmann
AU - Aran Raoufi
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.28543
UR - https://arxiv.org/abs/2610.28543
AB - 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, the symmetric formulation of binary 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.
ER -