Binary Discrete Diffusion: Solving Logic and Planning Tasks with Candidate-Set Diffusion

Discrete diffusion models have demonstrated the ability to generate in arbitrary order and self-correct in text generation, but traditional masked diffusion and uniform diffusion completely erase token identity in a single corruption event, causing the noise state to be unable to explicitly express partial uncertainty—that is, "multiple candidates are still possible." This is precisely the bottleneck faced by tasks such as logical reasoning and planning, which require gradually eliminating incorrect options. A recent study proposes Binary Discrete Diffusion, which represents the candidate token set at each position with a binary membership vector and gradually resolves uncertainty through continuous addition and removal operations, achieving performance significantly superior to strong baselines on tasks such as Sudoku, Sokoban, and graph coloring.

The Inherent Flaw of Discrete Diffusion: One-Shot Corruption Loses Partial Information

The core mechanism of discrete diffusion models is iterative denoising: starting from a completely random sequence of categories, a meaningful sequence is gradually recovered through a reverse process. Such models support generation in arbitrary order, infilling, and self-correction, and are therefore regarded as strong candidates for reasoning, planning, and constrained generation tasks such as code and mathematics.

The problem lies in the design of the corruption kernel. Masked diffusion replaces tokens with [MASK], and uniform diffusion replaces them with a uniform distribution over the vocabulary—both completely erase the identity of the original token in a single event. This means that the model's noise state can only express two extremes: "known" or "completely unknown," and cannot represent partial uncertainty such as "this position could be A or B, but definitely not C." For Sudoku or graph coloring, humans rely precisely on this candidate-set elimination method when solving puzzles: first lock in a few possible values, then gradually eliminate them through constraints. The intermediate states of traditional discrete diffusion do not match this reasoning process.

Discrete Diffusion Models are a class of generative models whose core idea is to gradually corrupt data into noise through a forward corruption process, and then learn a reverse denoising process to recover the data from the noise. Unlike continuous diffusion (such as the Gaussian diffusion commonly used in image generation), discrete diffusion operates directly on a discrete state space (such as the vocabulary of text), and its corruption process is usually defined as a Markov chain that jumps between discrete states through a transition probability matrix. Common discrete diffusion includes Masked Diffusion and Uniform Diffusion; the former replaces original tokens with a special [MASK] token, while the latter samples replacements from a uniform distribution over the vocabulary. The advantage of discrete diffusion is that it supports generation in arbitrary order and self-correction, giving it potential in text generation, code synthesis, and constraint satisfaction problems.

Candidate Sets as Intermediate Representations: The Mechanism Design of Binary Diffusion

The core innovation of Binary Discrete Diffusion is to use candidate sets instead of a single token as the diffusion state. Specifically, the noise state at each position is a binary membership vector, where each bit corresponds to a token in the vocabulary: 1 means the token is still in the candidate set, and 0 means it has been eliminated.

The corruption process is no longer "replacing tokens" but performing addition and removal operations on the candidate set: in the forward process, candidate tokens are gradually removed and information is gradually lost; in the reverse process, the model learns to predict which tokens should be re-added to the candidate set. This symmetric add-remove mechanism allows information to be gradually lost and gradually recovered, and the diffusion state itself directly encodes partial uncertainty. The authors define this family of processes as continuous-time discrete diffusion and provide both symmetric and asymmetric formalizations.

Compared with masked diffusion, the candidate-set state retains more structural information at every step—the model does not have to re-infer the entire token from scratch, but instead refines existing candidate hypotheses. This explains why the computation learned by the reverse model changes substantially depending on the corruption kernel.

Continuous-Time Discrete Diffusion is a formal framework for discrete diffusion in which the forward corruption process is modeled as a continuous-time Markov jump process. Specifically, the state at each position jumps at a certain rate along the continuous time axis (for example, a token is replaced or removed), and the jump rate is defined by a transition rate matrix. This continuous-time perspective allows more flexible corruption schedules and can be made equivalent to discrete time steps through time reparameterization. In binary diffusion, the authors define the addition and removal operations of the candidate set as jump processes in continuous time, and distinguish between symmetric (equal addition and removal rates) and asymmetric (different rates) forms, thereby providing a rigorous probabilistic model for candidate-set evolution.

Empirical Results on Logic and Planning Tasks: Comprehensive Lead on Sudoku, Sokoban, and Graph Coloring

The paper conducts systematic evaluations on three constraint satisfaction tasks: Sudoku-Extreme (extremely difficult Sudoku), Boxoban (Sokoban planning), and graph coloring. Under matched architectures and controlled training/sampling/hyperparameter tuning budgets, the symmetric form of binary diffusion consistently outperforms carefully tuned masked diffusion and uniform diffusion baselines.

The distribution of gains is noteworthy: the largest improvements occur on the hardest instances. This aligns with the design motivation of candidate-set representations—when problem constraints are dense and require extensive elimination reasoning, explicitly maintaining candidate sets offers the most obvious advantage; on simple instances, the gap between methods narrows, indicating that the baselines are not universally ineffective but simply struggle in scenarios requiring fine-grained uncertainty.

In language modeling, binary diffusion remains competitive on Text8, TinyStories, and OpenWebText, but does not significantly surpass the baselines. This result is expected: although the next-token distribution in natural language also has uncertainty, it lacks the candidate-elimination structure under hard constraints found in logic tasks, so the marginal benefit of candidate-set representations is therefore limited.

The Corruption Kernel Determines the Computation Learned by the Reverse Model

The most noteworthy argument of this study is not the specific task metrics but the methodological point: the choice of corruption kernel substantially changes the computational content learned by the reverse model. The traditional view tends to treat the corruption kernel as an engineering detail of diffusion models, with emphasis placed on network architecture and samplers. However, the experiments here show that when the corruption kernel changes from "one-shot erasure" to "gradual candidate removal," the model learns different reasoning strategies under the same architecture.

This opens a new dimension for the design of discrete diffusion: customizing the corruption process to the structure of the task may be more effective than simply stacking model capacity. The cost of candidate-set representation is that the state space expands from vocabulary size to a binary vector of size 2^|V|, but experiments show that under controlled budgets the benefits of this expansion exceed the costs. The authors also point out that binary diffusion is only competitive in language modeling, indicating that the method is not a general replacement but a specialized tool for reasoning tasks with clear candidate-elimination structure.

Corruption Kernel is the core component in diffusion models that defines how the forward process gradually corrupts data into noise. In discrete diffusion, the corruption kernel determines the probability distribution of state transitions; for example, the corruption kernel of masked diffusion replaces tokens with [MASK] with a certain probability, while uniform diffusion replaces them with uniformly sampled tokens with a certain probability. The design of the corruption kernel directly affects the amount of information retained in the noise state and the difficulty of denoising that the reverse model must learn. Traditionally, the corruption kernel has often been regarded as an engineering detail, but this study shows that the choice of corruption kernel substantially changes the computational content learned by the reverse model, thereby affecting the model's performance on reasoning tasks. This suggests that customizing the corruption kernel to the structure of the task may become an important direction for improving the reasoning ability of diffusion models.

Implications for Reasoning-Oriented AI

Using candidate sets as an intermediate representation for iterative reasoning resonates with the ideas of neuro-symbolic methods and constraint solvers: rather than having the model output an answer in one shot, it maintains a gradually shrinking hypothesis space. Binary diffusion provides a purely neural, end-to-end trainable framework to realize this process and is compatible with generation in arbitrary order.

The limitations are also clear. The dimensionality of binary vectors grows linearly with the vocabulary, and the memory and computational overhead in long-sequence and large-vocabulary scenarios need 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. In addition, the mediocre performance on language modeling suggests that the value of candidate-set representations depends heavily on whether the task has a decomposable elimination structure.

Nevertheless, the core conclusion of this work is solid enough: in logic and planning tasks, the noise state of diffusion models should not be merely a binary switch of "known/unknown"; the intermediate layer of candidate sets allows the model to gradually eliminate options like a human solving a puzzle. For readers interested in iterative reasoning and constrained generation, this is a direction worth following.

One-line Summary

Binary discrete diffusion uses candidate sets to represent partial uncertainty and significantly outperforms traditional discrete diffusion on logic and planning tasks.

Paragraph Summary

This article introduces Binary Discrete Diffusion, a new discrete diffusion method for logical reasoning and planning tasks. Traditional masked diffusion and uniform diffusion completely erase token identity in a single corruption event, causing the noise state to be unable to express the partial uncertainty that "multiple candidates are still possible." Binary diffusion represents the candidate token set at each position with a binary membership vector and gradually resolves uncertainty through progressive addition and removal operations. On Sudoku, Sokoban, and graph coloring tasks, symmetric binary diffusion consistently outperforms strong baselines under matched budgets, with the largest gains on the hardest instances; it remains competitive but does not significantly surpass baselines in language modeling. The core insight of the study is that the choice of corruption kernel substantially changes the computation learned by the reverse model, opening a new dimension of task-specific customization for discrete diffusion design.