A new arXiv preprint introduces Binary Discrete Diffusion, a family of continuous-time discrete-diffusion models whose noisy state is a set of candidate tokens per position, encoded as a binary membership vector. Unlike masked or uniform diffusion, which erase a token's identity in a single corruption event, binary diffusion changes candidate sets through additions and removals. This lets information be lost and recovered gradually while the state itself explicitly represents partial uncertainty.
The authors report that the symmetric formulation of binary diffusion consistently outperforms strong, well-tuned masked and uniform baselines on Sudoku-Extreme, Boxoban, and graph coloring, under matched architectures and controlled training, sampling, and tuning budgets. The largest gains appear on the hardest instances. On language modeling benchmarks such as Text8, TinyStories, and OpenWebText, the method remains competitive rather than clearly superior.
The results support candidate sets as an effective intermediate representation for iterative reasoning, and suggest that the choice of corruption kernel can materially change what the reverse model learns. The paper is available as arXiv:2610.28543.