Binary Discrete Diffusion

Binary Discrete Diffusion represents the candidate token set at each position with a binary membership vector and gradually resolves uncertainty through add and remove operations.

Binary Discrete Diffusion was systematically evaluated on three constraint satisfaction tasks: Sudoku-Extreme, Boxoban (Sokoban planning), and graph coloring.

Under matched architectures and controlled training/sampling/tuning budgets, the symmetric form of binary diffusion consistently outperformed finely tuned masked diffusion and uniform diffusion baselines.

Binary diffusion yields the largest gains on the hardest instances, while the gap between methods narrows on easy instances.

On language modeling tasks (Text8, TinyStories, OpenWebText), binary diffusion remains competitive but does not significantly surpass the baselines.

The choice of corruption kernel substantively changes what computation the reverse model learns; when the corruption kernel shifts from one-shot erasure to gradual candidate removal, the model learns different reasoning strategies under the same architecture.

The cost of candidate-set representation is that the state space expands from the vocabulary size to 2^|V| binary vectors, but under controlled budgets the benefits outweigh the cost.

Binary diffusion is not a general-purpose replacement but a specialized tool for reasoning tasks with an explicit candidate-exclusion structure.

The dimensionality of the binary vectors grows linearly with the vocabulary, and the memory and compute overhead in long-sequence and large-vocabulary scenarios needs further evaluation.

The paper does not address adaptive control of candidate-set size, and fixed vocabulary membership vectors may be insufficiently flexible in open-domain tasks.

The authors formulate the candidate-set add and remove operations of binary diffusion as a jump process in continuous time and distinguish symmetric (equal add and remove rates) and asymmetric (different rates) forms.