Binary Discrete Diffusion: Candidate-Set Diffusion for Logic and Planning Tasks

Rodrigo Casado Noguerales; Dimitri von Rütte; Bernhard Schölkopf; Thomas Hofmann; Aran Raoufi

cs.LGOct 20, 2026

Binary Discrete Diffusion: Candidate-Set Diffusion for Logic and Planning Tasks

Authors: Rodrigo Casado Noguerales, Dimitri von Rütte, Bernhard Schölkopf, Thomas Hofmann, Aran Raoufi

Organizations: ETH Zurich · Max Planck Institute for Intelligent Systems · ELLIS Institute Tübingen

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.

Figures & tables

Panel of Figure 1 — Figure 1: Denoising process of each kernel over the candidate sets of a three-token vocabulary {A,B,C} , with its allowed moves faded. Each panel highlights one possible denoising path to A.

Figure 2: Fraction of the information retained for independent, uniformly distributed tokens with

V=1024

, against the reparameterized time

\xi

of the linear (left) and logarithmic (right) schedules.

	Sudoku		Boxoban		Graph coloring
Kernel	All	Hard	All	Hard	All	Hard
Binary symmetric	96.27 (0.21)	92.66 (0.39)	94.29 (0.30)	84.65 (0.56)	99.35 (0.00)	64.13 (1.10)
Uniform	95.47 (0.21)	89.81 (0.47)	92.38 (0.64)	78.73 (1.20)	99.01 (0.02)	61.41 (0.34)
Binary absorbing	91.24 (0.11)	81.08 (0.26)	87.30 (0.81)	69.13 (1.66)	98.83 (0.02)	54.77 (0.39)
Masked	87.96 (0.16)	76.12 (0.10)	91.26 (0.31)	75.47 (0.69)	97.44 (0.04)	4.85 (0.33)

Table 1: Solve rate (%) on the full test sets and hard subsets at the reference NFE.

Figure 3: Solve rate against inference budget (NFE, left) and training step (right).

Dataset	Binary symmetric	Uniform	Binary absorbing	Masked
Text8	0.913 (0.001)	0.896 (0.006)	0.821 (0.000)	0.854 (0.008)
TinyStories	0.882 (0.006)	0.904 (0.001)	0.585 (0.011)	0.850 (0.009)
OpenWebText	0.840 (0.001)	0.822 (0.004)	0.747 (0.004)	0.871 (0.013)

Table 2: Test MAUVE of tuned samplers (standard error over two generation seeds).

Figure 4: MAUVE against token entropy with GPT-2 Large as the scorer. We select each point’s sampling configuration on validation at a representative entropy and evaluate it on the test split.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Architecture
transformer layers	12
hidden width	512
attention heads	8
MLP width	2048
time-conditioning width	128
conditioning	Sudoku: clue embedding; Boxoban: board prefix; graph coloring: adjacency in attention

Appendix

Table 3: Training settings of the logic models.

Architecture
transformer layers	12; OpenWebText 16
hidden width	768; OpenWebText 1024
attention heads	12; OpenWebText 16
MLP width	3072; OpenWebText 4096
time-conditioning width	128
sequence length	Text8 256, TinyStories 512, OpenWebText 1024

Appendix

Table 4: Training settings of the text models.

Task	Kernel	$10^{-4}$	$3\!\cdot\!10^{-4}$	$10^{-3}$
Sudoku	Binary symmetric	0.0163 (0.0005)	0.0175 (0.0002)	0.0230 (0.0007)
	Uniform	0.0162 (0.0013)	0.0179 (0.0001)	0.0226 (0.0005)
	Binary absorbing	0.0148 (0.0001)	0.0178 (0.0010)	0.0229 (0.0011)
	Masked	0.0154 (0.0004)	0.0176 (0.0002)	0.0245 (0.0009)
Boxoban	Binary symmetric	0.0286 (0.0017)	0.0306 (0.0034)	0.0358 (0.0006)
	Uniform	0.0267 (0.0026)	0.0256 (0.0009)	0.0332 (0.0007)

Appendix

Table 5: Validation NELBOs for the logic learning-rate sweep in nats per scored token, mean over two training seeds with half their difference in parentheses.

Task	Binary symmetric	Uniform	Binary absorbing	Masked
Sudoku	0.0165 (0.0003)	0.0160 (0.0004)	0.0161 (0.0001)	0.0166 (0.0002)
Boxoban	0.0224 (0.0002)	0.0235 (0.0005)	0.0278 (0.0004)	0.0236 (0.0002)
Graph coloring	0.0860 (0.0001)	0.0857 (0.0001)	0.0877 (0.0001)	0.0837 (0.0000)

Appendix

Table 6: Test NELBOs of the final logic models in nats per scored token, mean and standard error over the five training seeds.

Setting	Logic tasks	Text
Temperature $T$	$\{0,0.5,1\}$	$\{0.8,0.9,1,1.1\}$
Re-corrupt fraction $\eta$	$\{0,0.02,0.05,0.1,0.2,0.5,0.8,1\}$	$\{0,0.01,0.05,0.1,0.2,0.5,0.8,1\}$
masked also	$\{0.9\}$
Position confidence $\gamma$	$\{0,1,3,10\}$	$\{0,1,3,5,10\}$
Ordering tilt $\lambda$	$\{0,1,3,10,30,100\}$	$\{0,1,3,10\}$
masked also	$\{2,5,7,15,20,50,300,1000\}$

Appendix

Table 7: Sampler settings tuned on validation.

Kernel	Setting	Sudoku All	Sudoku Hard	Boxoban All	Boxoban Hard	Graph coloring All	Graph coloring Hard
Binary symmetric	$T$	0	0	0	1	1	0
	$\eta$	1	1	1	1	0.8	1
	coord.	c	c	c	c	c	c
	$\gamma$	0	0	0	0	0	0
	$\lambda$	0	0	3	3	0	3
	$\beta$	0.5	0.5	3	0.5	0	0

Appendix

Table 8: Selected sampler settings on the logic tasks, on the full validation splits and on the hard subsets. The confidence coordinate (coord.) is the cavity (c) or the denoiser (d).

Kernel	Setting	Text8	TinyStories	OpenWebText
Binary symmetric	$T$	1	0.9	0.9
	top- $p$	1	1	1
	spacing	log	cosine	log
	$\eta$	1	0.5	0.8
	coord.	c	d	c
	$\gamma$	0	10	0

Appendix

Table 9: Selected sampler settings on text. The confidence coordinate (coord.) is the cavity (c) or the denoiser (d).

	Binary symmetric		Uniform		Binary absorbing		Masked
Sampler	All	Hard	All	Hard	All	Hard	All	Hard
Sudoku
Ancestral	76.41 (0.33)	59.22 (0.34)	76.66 (0.49)	60.37 (0.42)	71.90 (0.24)	52.25 (0.34)	70.31 (0.29)	50.75 (0.48)
Re-corrupt	94.54 (0.18)	87.78 (0.40)	94.77 (0.31)	88.27 (0.64)	86.03 (0.24)	71.75 (0.54)	80.84 (0.09)	64.39 (0.21)
$\Psi$ -sampler	94.54 (0.18)	87.78 (0.40)	94.77 (0.31)	88.40 (0.68)	86.03 (0.24)	71.89 (0.49)	80.49 (0.13)	63.95 (0.24)
+ position conf.	94.37 (0.18)	87.47 (0.21)	95.48 (0.22)	89.90 (0.48)	91.23 (0.11)	81.24 (0.21)	88.19 (0.19)	76.56 (0.29)

Appendix

Table 10: Solve rate (%) at the reference NFE for each stage of the tuning procedure evaluated on the test splits and the hard subsets of Table 1 , with every sampler selected on the full validation splits, except in the graph-coloring hard column, which selects on the large validation graphs. For masked diffusion, the last row adds the extra ordering and re-corruption settings that replace candidate confidence.

Figure 5: Solve rate by difficulty at the reference NFE, harder to the right: Sudoku by the number of clues, Boxoban by the length of the reference solution, and graph coloring by graph size at a fixed mean degree.

Dataset	Kernel	$H$	MAUVE	GenPPL	NELBO
Text8	Binary symmetric	6.805 (0.004)	0.913 (0.001)	186 (3)	1.454 (0.004)
	Uniform	7.244 (0.008)	0.896 (0.006)	492 (1)	1.428 (0.003)
	Binary absorbing	6.873 (0.003)	0.821 (0.000)	404 (7)	1.476 (0.004)
	Masked	6.650 (0.010)	0.854 (0.008)	272 (3)	1.384 (0.003)
TinyStories	Binary symmetric	5.676 (0.005)	0.882 (0.006)	9.4 (0.1)	0.658 (0.002)
	Uniform	5.682 (0.004)	0.904 (0.001)	9.2 (0.0)	0.493 (0.001)

Appendix

Table 11: Entropy

H

(nats), MAUVE, GenPPL, and NELBO (bits per character) at the validation-selected setting. Parentheses give the standard error over the two generation seeds, and for NELBO the Monte Carlo standard error. The reference entropies are 7.308 (Text8), 5.811 (TinyStories), and 7.535 (OpenWebText).

Figure 6: GPT-2 Large GenPPL against token entropy at the points of Figure 4 .

Dataset	Kernel	$H$	MAUVE	GenPPL
Text8	Binary symmetric	6.805 (0.004)	0.913 (0.001)	186 (3)
	Uniform	6.924 (0.003)	0.891 (0.006)	358 (1)
	Binary absorbing	6.803 (0.011)	0.821 (0.007)	329 (10)
	Masked	6.650 (0.010)	0.854 (0.008)	272 (3)
TinyStories	Binary symmetric	5.676 (0.005)	0.882 (0.006)	9.4 (0.1)
	Uniform	5.756 (0.007)	0.877 (0.001)	12.3 (0.0)

Appendix

Table 12: Common-entropy operating point: the measured sample set closest to the entropy at which the corpus’s kernels are jointly best (Text8 6.80, TinyStories 5.75, OpenWebText 7.25 nats). Parentheses give the standard error over the two generation seeds.

Figure 7: Candidate sets of the first Sudoku test board from $t=0.9$ to the generated sample at $t=0$ , with digit $d$ of a set at keypad position $d$ . Bottom: the candidate set of the outlined cell at every step, with the solution’s digit on a light gray band.

Diffusion Models

Diffusion models learn to reverse gradual data corruption, enabling flexible generation, editing, forecasting, and inference.

See all 1,169 papers

Self-Aware Markov Models for Discrete Reasoning
Mar 17, 2026Gregor Kornhardt, Jannis Chemseddine, Christian Wald +1Masked Diffusion Models Adaptive Computation
Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany
Hierarchical Continuous Diffusion Language Models
Oct 1, 2026Hui Ren, Zihan Li, Chang Liu +2Structured Reasoning in Language Models Diffusion Language Model Decoding
University of Illinois Urbana-Champaign · Amazon.com, Inc.
Let It Go or Learn to Self-Correct: Continuous Diffusion for Constrained Discrete Tasks
Sep 8, 2026Mariia Drozdova, Stéphane Liem Nguyen, François FleuretConstrained Generative Modeling Diffusion Sampling
University of Geneva

Mar 17, 2026J/K move · Enter open · S save

Self-Aware Markov Models for Discrete Reasoning

Gregor Kornhardt, Jannis Chemseddine, Christian Wald, Gabriele Steidl

Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany

Masked Diffusion Models Adaptive Computation LLM Self-Correction

Open paper AskPDF arXiv

Standard masked discrete diffusion models face limitations in reasoning tasks due to their inability to correct their own mistakes on the masking path. Since they rely on a fixed number of denoising steps, they are unable to adjust their computation to the complexity of a given problem. To address these limitations, we introduce a method based on learning a Markov transition kernel that is trained on its own outputs. This design enables tokens to be remasked, allowing the model to correct its previous mistakes. Furthermore, we do not need a fixed time schedule but use a trained stopping criterion. This allows for adaptation of the number of function evaluations to the difficulty of the reasoning problem. Our adaptation adds two lightweight prediction heads, enabling reuse and fine-tuning of existing pretrained models. On the Sudoku-Extreme dataset we clearly outperform other flow based methods with a validity of 95%. For the Countdown-4 we only need in average of 10 steps to solve almost 96% of them correctly, while many problems can be solved already in 2 steps.

Abstract

Diffusion Models

Explore similar work

Self-Aware Markov Models for Discrete Reasoning

Hierarchical Continuous Diffusion Language Models

Let It Go or Learn to Self-Correct: Continuous Diffusion for Constrained Discrete Tasks