Imagine you're solving a crossword puzzle with a pencil. The standard approach in discrete diffusion is like erasing a letter completely (masked diffusion) or replacing it with a random letter (uniform diffusion) — in both cases, you've destroyed all information about what that cell might be. But real crossword solvers do something smarter: they lightly pencil in two or three candidate letters per cell, gradually narrowing the set as crossing constraints resolve. That's exactly what this paper does to the corruption kernel in discrete diffusion. The committed claim: representing noisy intermediate states as binary candidate sets — where each position holds a subset of plausible tokens rather than a single token or a mask — lets the diffusion model learn better reasoning during denoising, and the gains are largest precisely where reasoning is hardest. This is not a new architecture or a new training objective. It is a new noise process, and the paper argues that the shape of the noise changes what the reverse model learns to compute. The mechanism works in continuous time. At each position, the forward process stochastically adds or removes tokens from the candidate set. A full set (all tokens present) is maximum entropy; a singleton is a committed answer. The reverse process learns to shrink candidate sets toward singletons by removing implausible tokens and occasionally recovering dropped ones. This is a genuinely different inductive bias from masked diffusion (where a token is either known or completely unknown) or uniform diffusion (where corruption replaces the token with a random draw). The binary formulation preserves a spectrum of partial knowledge. On constraint-satisfaction benchmarks — Sudoku-Extreme, Boxoban (a Sokoban variant), and graph coloring — the symmetric binary diffusion variant consistently beats well-tuned masked and uniform baselines under matched architectures, training budgets, and sampling budgets. Crucially, the advantage widens on harder problem instances, which is exactly what you'd want from a representation that encodes richer intermediate uncertainty. The paper is careful to control for architecture and compute, which is more than many diffusion papers bother to do. On language modeling (Text8, TinyStories, OpenWebText), binary diffusion is competitive but does not clearly dominate. This is an honest result and the authors don't oversell it. Language modeling may not stress the constraint-propagation reasoning where candidate sets shine — or the vocabulary sizes may dilute the signal. The paper acknowledges this tradeoff rather than burying it. The integrity story is solid for a machine learning paper. The authors compare against strong, well-tuned baselines (MDLM, uniform diffusion) rather than straw men, match compute and architecture across all comparisons, and report results across multiple domains. Code availability is implied by the reproducibility norms of the venue but not explicitly confirmed at submission. No pre-registration, which is standard for ML. The 42-page paper with 12 tables suggests thorough ablations rather than cherry-picked results. The deeper implication is methodological: in discrete diffusion, the corruption kernel is not just a convenience — it's a design knob that shapes what computation the reverse model learns. This paper provides the cleanest evidence yet for that thesis, and it opens a design space (what other structured corruption processes could work?) that the field has mostly ignored in favor of architecture and training-objective innovations.
