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

Introduction

Discrete diffusion models generate by iteratively refining a corrupted sequence. Unlike autoregressive generation, decisions need not follow a fixed left-to-right order and can be revised later, while many positions can be updated in parallel [45, 40, 19]. These properties make discrete diffusion attractive for reasoning, planning, and constrained generation [62] (Wever et al. 2025). Yet sample quality at finite inference budgets remains challenging, motivating work on ordering, remasking, planned denoising, and search [27, 58, 30, 3]. We instead focus on a complementary axis: the corruption process itself. How much can be gained by changing the corruption process, and in particular the intermediate representation on which denoising operates? Logic and planning are useful testbeds: they impose global constraints, admit exact solve-rate evaluation, and scale cleanly in difficulty at manageable computational cost, while sharing structure with coding, mathematics, and biological design [42, 2, 51]. They also expose a mismatch in the dominant masked and uniform kernels [40, 48, 45, 41]: a position cannot naturally express that several alternatives remain plausible. A model solving Sudoku, for example, might narrow a cell from $\{2,7,9\}$ to $\{7,9\}$, later reopen 2 as neighboring decisions are revised, and eventually settle on 7.

We propose to make such candidate sets themselves the diffusion states. A clean token is a singleton, while during reverse generation intermediate states can carry several live hypotheses that may be eliminated or restored. More broadly, the corruption kernel does more than specify how examples are noised: it determines what information survives at intermediate times and how the model’s prediction is translated into reverse moves and their rates. Identical architectures can therefore induce qualitatively different iterative computations under different kernels. We instantiate this idea with Binary Discrete Diffusion, representing candidate sets by binary membership vectors in $\{0,1\}^{V}$ (Figure 1). In binary symmetric diffusion, membership bits can switch both on and off, allowing hypotheses to be eliminated and later restored. In binary absorbing diffusion, corruption only adds candidates, so reverse generation progressively prunes the set toward a singleton.

Although each position has a nominal state space of size $2^{V}$, every state has only $V$ single-bit neighbors, and all neighboring reverse rates can be computed in $O(V)$ time from the model’s usual $V$-way prediction, without enumerating subsets. The model learns these dynamics from clean solutions without candidate labels, task-specific deduction rules, or symbolic search. The richer state also enables candidate-aware sampling: we derive exact ancestral updates through a shared clean-token proposal, adapt re-corrupt sampling, and, building on $\Psi$-sampling and confidence-guided remasking [12, 58], develop revision rules that choose both which positions to reconsider and which hypotheses to reopen.

We evaluate Binary Discrete Diffusion on Sudoku-Extreme [57], Boxoban [21], and graph coloring under controlled architectures, training budgets, and sampler tuning, using direct single-attempt solutions without verifier-guided selection. Across all three tasks, a consistent pattern emerges: binary symmetric diffusion outperforms uniform diffusion, and both outperform masked and binary absorbing diffusion. The advantage of binary symmetric over uniform grows on harder regimes, including low-clue Sudoku, long-horizon Boxoban, and graph coloring far beyond the training size. On Text8, TinyStories, and OpenWebText [32, 13, 18], binary diffusion remains competitive with established kernels. These results support candidate sets as an effective intermediate representation for iterative reasoning and show that the corruption process can materially change the computation learned by the reverse model.

Discrete diffusion modeling

We consider a data distribution $p_{\mathrm{data}}$ on sequences of length $L$ over a finite vocabulary $[V] = \{1,\ldots,V\}$. Starting from $Z_0 \sim p_{\mathrm{data}}$, we corrupt its positions independently with a continuous-time Markov chain (CTMC) $Z_t = (Z_t^1,\ldots,Z_t^L)$, whose distribution approaches an easily sampled noise distribution as $t \uparrow1$. We write $q_{t|s}(y \mid z)$ for the one-position transition distribution or kernel between times $s < t$ and states $z,y$. For masked and uniform diffusion we use [1]

Thus $Z_t$ can be sampled directly at any time $t$, without simulating the intervening jumps.

We write $Q_t(z,y)$ for the forward jump rate from $z$ to $y$, so that $q_{t+h|t}(y \mid z) = \mathbb{1}\{y=z\} + hQ_t(z,y) + o(h)$ as $h \downarrow0$. The reverse rates depend on $p_{\mathrm{data}}$, but conditioning on the clean sample $Z_0$ makes them computable from the forward process [5]. For a change at position $i$ from noisy token $Z_t^i$ to another $y \ne Z_t^i$, the clean-conditioned reverse rates are given by

The true reverse rates are obtained by averaging these clean-conditioned rates over $q(Z_0 \mid Z_t)$. Let $a_i^\theta(Z_t,y;t)$ denote learned reverse rates that depend on the noisy sequence $Z_t$ and time $t$ but not on $Z_0$. We train them against the clean-conditioned targets by minimizing the negative of the continuous-time evidence lower bound (ELBO) ([5, 6]):

This upper-bounds the expected negative log-likelihood. More sharply, its excess above the data-entropy floor is exactly the path-space KL between the exact reverse process and the learned reverse process ([6]). In practice, the jump rates can become singular near $t=0$ or $t=1$, so we train on an interior window $0<t_1<t_2<1$. The corresponding finite-window objective includes reconstruction and terminal-prior boundary terms, given in App. § 10.§ 1.

Training. We parameterize the model reverse rates through a network that takes $(Z_t,t)$ as input and outputs, at each position $i$, a strictly positive distribution $\mu_i^\theta(c\mid Z_t;t)$ over clean tokens $c\in[V]$. This induces a noisy-state distribution $m_i^\theta$, which determines the model reverse rates for $y\ne Z_t^i$:

Thus one $V$-way network output determines all allowed reverse moves at a position. Reweighting $\mu_i^\theta$ by the kernel $q_{t\mid0}(Z_t^i\mid c)$ gives a new distribution which we denote by

In terms of this distribution, the model rate $a_i^\theta(Z_t,y;t)$ from (4) becomes an average of the clean-conditioned rate $a_i(Z_0,Z_t,y;t)$ from (2), where tokens with $\pi_i^\theta(c\mid Z_t;t)=0$ contribute zero:

Training then minimizes an empirical estimate of the path integral in (3) by sampling $(t,Z_0,Z_t)$.

Binary discrete diffusion

In binary diffusion, the noisy state at each position is a set of candidate tokens. We represent a clean token $c\in[V]$ by the singleton $\{c\}$, and corruption changes this set by adding or removing candidates, so that an intermediate state can retain several alternatives at a single position. Representing each set by its binary membership vector identifies the noisy state $Z_t^i$ with a vertex of the binary cube $\{0,1\}^V$, and we use the same symbol for a noisy set $z$ and its membership vector, including for a clean singleton $\{c\}$ and its one-hot vector. We consider two corruption processes on this space: binary symmetric diffusion, under which candidates can be both removed and restored, and binary absorbing diffusion, which only adds candidates. We focus primarily on the symmetric process and treat the absorbing process as a simpler monotone counterpart.

Although the bits evolve independently when conditioned on the clean sequence $Z_0$, the true and learned reverse dynamics are generally correlated across positions and depend on the full noisy sequence. Crucially, though, the network still produces only the usual $V$-way distribution $\mu_i^\theta(c\mid Z_t;t)$ over clean tokens at each position, and the construction of § 2 converts this single prediction into all allowed reverse rates on the binary cube. This is what makes candidate-set diffusion tractable, as we explain in more detail in § 3.3.

Binary symmetric diffusion

In binary symmetric diffusion, each membership bit retains its clean value with probability $1-t$ and is otherwise resampled uniformly from $\{0,1\}$. A resampled bit keeps its value half of the time, so a bit differs from its clean value with probability $t/2$, and given $Z_0$ the forward process factorizes over positions and bits with the one-position kernel

where $d_H$ is the Hamming distance. A state at time $t$ thus contains the clean token $c$ with probability $1-t/2$ and every other token independently with probability $t/2$, so it holds $(V-1)t/2$ false candidates on average, and it approaches independent fair bits, a uniformly random subset of the vocabulary, as $t \uparrow1$. More generally, between times $0 \le s < t < 1$ each bit is resampled with probability $(t-s)/(1-s)$, which gives the transition kernel

Forward rates. Each bit is resampled at rate $1/(1-t)$ and changes its value half of the time, so differentiating (8) gives the flip rate

where $z^{(u)}$ is the state $z$ with a single bit $u$ flipped, and every other jump has rate zero. The forward process thus moves along the edges of the binary cube: from $z$, it can only reach the $V$ Hamming neighbors $z^{(1)},\ldots,z^{(V)}$ of $z$ in $\{0,1\}^{V}$.

Clean-conditioned reverse rates. The reverse process traverses the same edges, so each move flips one bit. We write $a^{i,u}_{i,u}$ for the rate of flipping bit $u$ of $Z^i_t$. Since the forward kernel (7) factorizes over bits, all unchanged-bit factors cancel in the kernel ratio in (2). The remaining ratio is $\rho_t=(1-t/2)/(t/2)=(2-t)/t$ when the flip repairs a mismatch with the clean bit $(Z^i_0)_u$, and $\rho_t^{-1}$ when it creates one. With the forward rate $r_t$ introduced above, the clean-conditioned rate is therefore

A repairing flip is therefore favored over a corrupting flip by a factor $\rho_t^2$. This preference strengthens as $t\downarrow0$ and vanishes as $t\uparrow1$, while both directions remain possible for $0<t<1$.

Model reverse rates. Averaging over the denoiser as in (6) replaces each indicator in (10) by its probability, so that, with $P^\theta_i$ the probability under $Z^i_0\sim\pi^\theta_i(\cdot\mid Z_t;t)$, the model reverse rates are

The bit of an active candidate $u$ is wrong unless $u$ is the clean token, and the bit of an inactive token is wrong only if it is the clean token, so removing and restoring a candidate have model reverse rates

where the denoiser $\pi^\theta_i(\cdot\mid Z_t;t)$ is the cavity $\mu^\theta_i(\cdot\mid Z_t;t)$ multiplied by $\rho_t^2$ on the active candidates of $Z^i_t$ and renormalized.

Interpretation. Each rate lies between the slow rate $r_t/\rho_t$ and the fast rate $r_t\rho_t$ of (10). Candidates assigned higher probability by the denoiser are harder to remove when present and faster to restore when absent.

Binary absorbing diffusion

Binary absorbing diffusion only adds candidates: between times $0 \le s < t < 1$, each inactive bit activates independently with probability $(t-s)/(1-s)$, and active bits never flip. Its kernel and forward rates are therefore

and every other jump has rate zero. In particular, $q^{\mathrm{abs}}_{t|0}(z \mid c) = \mathbf{1}\{c \in z\}(1-t)^{V-|z|}t^{|z|-1}$: the clean token $c$ always remains a candidate and every other token becomes one independently with probability $t$, so the state holds $(V-1)t$ false candidates on average and approaches the full vocabulary as $t \uparrow1$.

Since the forward process only adds candidates, the reverse process only removes them. Removing a false candidate gives the kernel ratio $(1-t)/t$ in the clean-conditioned rate (2), while the clean token cannot be removed, so this rate and its average (6) over the denoiser $\pi_i^\theta$ are

where $\pi_i^\theta(\cdot\mid Z_t;t)$ is the renormalized restriction of $\mu_i^\theta(\cdot\mid Z_t;t)$ to the active candidates of $Z_t^i$.

Interpretation. A candidate receiving a larger share of the model probability within the current candidate set has a smaller removal rate. Denoising therefore prunes unlikely candidates while protecting plausible ones.

Efficient computation and embedding with candidate sets

Candidate-set diffusion has $2^V$ possible states per position, which a priori require work exponential in $V$ for computing the model rates and the ELBO loss. However, parameterizing in terms of a clean-data distribution allows us to work in $O(V)$ per position, without enumerating the exponentially many possible candidate sets. For the rates, every reverse jump flips a single bit, so the reverse process can only move from a state $z$ to its $V$ Hamming neighbors $z^{(u)}$. After one network evaluation, the denoiser $\pi_i^\theta$ of a position follows from $\mu_i^\theta$ by reweighting and normalization in $O(V)$ time, and each of the $V$ flip rates $a_{i,u}^\theta$, (12) or (14), then takes constant work. For the same reason, the path loss in (3) sums only over these $V$ moves per position $i$, $\mathcal{J}_t = \sum_i \sum_{u=1}^{V} \Phi(a_{i,u},a_{i,u}^\theta)$. App. B derives all rates and losses in full detail.

Similarly, to avoid materializing an embedding table over the $2^V$ states, we embed a candidate set by applying the input embedding matrix $E \in\mathbb{R}^{V \times d}$, whose row $E_c$ embeds clean token $c \in[V]$, to its $\ell_2$-normalized membership vector,

This costs $O(V)$ and reduces to the ordinary token embedding $E_c$ for a singleton $\{c\}$. Apart from this input layer, we therefore use the same architecture as for the masked and uniform baselines.

Information loss and the time schedule

In binary diffusion, the first false candidate doubles the number of candidates for the clean token, whereas each later one enlarges an already large set. Since false candidates appear at a rate proportional to $V$, the binary kernels thus erase the clean token much faster than masked and uniform diffusion at large vocabularies.

We quantify the retained information by the mutual information $I(Z_0^i;Z_t^i)=H(Z_0^i)-H(Z_0^i\mid Z_t^i)$, the reduction in uncertainty about the clean token from observing its noisy state, where $H$ denotes Shannon entropy. Since $I(Z_0^i;Z_t^i)$ is intractable in general, we do so over a reference distribution of independent, uniformly distributed tokens (App. C.4). Masked and uniform diffusion then lose information roughly linearly in $t$, whereas the binary kernels lose it roughly logarithmically, so that a uniform sample of $t$ places most training times where little information is left (Figure 2, left).

This reference calculation motivates a change of clock [6]: a time reparameterization $\xi\mapsto t$, with $\xi$ drawn uniformly from $[0,1]$, to control how fast information is destroyed. Reweighting the path integrand $J_t$ by $\mathrm{d}t/\mathrm{d}\xi$ then leaves the ELBO objective (3) unchanged, so that only the allocation of training times changes. With a logarithmic map instead of the linear one,

the binary kernels lose their information approximately linearly in $\xi$ (Figure 2, right). We also give $\xi$ to the network as its time input rather than $t$. For $V \ge1024$, the logarithmic schedule substantially improved optimization. For the smaller vocabularies ($V \le9$) of our logic tasks, this choice made no difference and all kernels trained successfully with the linear schedule. We further refine all time schedules with an adaptive time sampler (see Apps. § 10.§ 3 and § 10.§ 5 for the details).

Sampling

Generation runs the learned reverse process on a grid $t_2 = \tau_N > \cdots> \tau_0 = t_1$, starting from a prior distribution $p_{t_2}$ and ending with a final decoding step via the denoiser $\pi_i^\theta(\cdot\mid Z_{t_1};t_1)$. As priors we take the limiting forward distributions, a uniformly random subset of the vocabulary for binary symmetric and the full vocabulary, given by the all-ones vector $\mathbf{1}_V$, for binary absorbing:

Ancestral sampling. Ancestral sampling from a time $t$ to the next time $s<t$ of the grid follows the reverse process learned through the ELBO, so that as $t \downarrow s$, its jump rates approach the model rates (6). At each step, it updates the positions independently given $Z_t$ by averaging the bridge $q_{s|t,0}(y\mid z,c)$, the distribution of $Z_s^i=y$ given $Z_t^i=z$ and $Z_0^i=c$, over the denoiser:

As in § 3.3, we avoid enumerating the $2^V$ states: given the clean token, the forward process corrupts the bits independently, so the bridge factors over bits,

Thus, each bit’s factor accounts for every sequence of jumps between $s$ and $t$, and a step can change many bits without simulating jumps or Poisson counts. The mixture (18) does not factor over bits, but we can still sample it exactly at a cost of $O(V)$ per position without enumerating the $2^V$ possible states: we draw a clean proposal $\widehat{Z}_0\sim\pi_i^\theta(\cdot\mid Z_t;t)$ and then sample each bit independently from (19) with $c=\widehat{Z}_0^i$ (App. § 9.§ 3). Under the symmetric bridge, each bit favors its current value for $s$ close to $t$ and the proposal’s value as $s\downarrow0$, so removed candidates can return, whereas the absorbing bridge always retains the clean proposal and independently retains each other active candidate with probability $s/t$.

Revision by re-corruption. Ancestral sampling conditions each step on the current state $Z_t$, which biases it toward what earlier steps have decided, including their mistakes. Re-corrupt sampling instead forgets the current state: it averages the kernel $q_{s|0}$ rather than the bridge $q_{s|t,0}$,

which we again sample in two steps by drawing a clean proposal $\widetilde{Z}_0^i \sim\pi_i^\theta(\cdot\mid Z_t;t)$ and then corrupting it afresh to noise level $s$. With an exact denoiser, both updates preserve the per-position forward marginals, but re-corruption makes every position revisable at every step. Interestingly, re-corruption alone markedly improves solve rates on logic tasks (Table 10, App. § 13.§ 4).

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.

Sampler	Binary symmetric		Uniform		Binary absorbing		Masked
	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)
Ψ-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)
+ candidate conf.	96.27 (0.21)	92.66 (0.39)	95.47 (0.21)	89.81 (0.47)	91.24 (0.11)	81.37 (0.20)	87.96 (0.16)	76.00 (0.10)
Boxoban
Ancestral	83.80 (0.37)	64.17 (0.57)	80.00 (0.81)	55.33 (1.50)	71.75 (0.91)	43.50 (1.59)	76.39 (0.37)	50.71 (0.58)
Re-corrupt	93.53 (0.39)	81.89 (0.85)	91.68 (0.63)	77.35 (1.30)	84.69 (0.66)	66.14 (1.45)	90.62 (0.37)	75.87 (0.93)
Ψ-sampler	93.53 (0.39)	81.89 (0.85)	91.68 (0.63)	77.35 (1.30)	84.66 (0.65)	66.01 (1.38)	90.66 (0.34)	75.94 (0.88)
+ position conf.	94.38 (0.33)	83.60 (0.78)	92.34 (0.61)	78.39 (1.36)	87.28 (0.80)	68.25 (1.65)	91.24 (0.31)	76.60 (0.70)
+ candidate conf.	94.29 (0.30)	84.14 (0.61)	92.38 (0.64)	78.57 (1.42)	87.30 (0.81)	68.25 (1.65)	91.26 (0.31)	76.60 (0.70)
Graph coloring
Ancestral	97.47 (0.05)	4.70 (0.24)	97.33 (0.03)	4.98 (0.25)	83.17 (0.13)	0.00 (0.00)	63.00 (0.54)	0.00 (0.00)
Re-corrupt	99.38 (0.01)	55.00 (1.01)	98.94 (0.01)	48.16 (0.92)	88.54 (0.33)	0.58 (0.09)	86.95 (0.60)	0.05 (0.03)
Ψ-sampler	99.35 (0.00)	55.10 (1.00)	98.94 (0.01)	48.24 (0.94)	90.64 (0.19)	0.58 (0.09)	86.92 (0.56)	0.05 (0.03)
+ position conf.	99.35 (0.00)	64.49 (1.20)	99.00 (0.01)	61.41 (0.34)	98.83 (0.02)	19.96 (0.97)	97.04 (0.03)	4.94 (0.37)
+ candidate conf.	99.35 (0.00)	64.13 (1.10)	99.01 (0.02)	61.41 (0.34)	98.83 (0.02)	54.77 (0.39)	97.44 (0.04)	4.85 (0.33)

Confidence-guided $\Psi$-sampler. As in the $\Psi$-sampler of Deschenaux et al. [12], we mix the ancestral and re-corrupt updates, but independently at each position $i$ with weight $\kappa_i$:

where we draw the two proposals independently and where $\kappa_i$ may depend on the re-corrupted proposal $\widetilde{Z}_0^i$. A constant $\kappa_i=\eta$ interpolates from ancestral sampling at $\eta=0$ to re-corrupt sampling at $\eta=1$ and preserves the per-position marginals, since both updates do. For masked diffusion, this mixture is the remasking sampler ReMDM (Wang et al. [58]). We extend it with two confidence mechanisms, position confidence with strengths $\gamma$ and $\lambda$ and candidate confidence with strength $\beta$, which recover the plain $\Psi$-sampler at zero (Algorithm 1; full details specified in App. § 11).

• Position confidence: where to reconsider. Following ReMDM-conf, we use the model’s confidence in its clean proposal $\widetilde{Z}_0^i$, read from the cavity or the denoiser, to concentrate revision on uncertain positions. We let $\kappa_i$ decrease with confidence at strength $\gamma$, keeping its mean equal to $\eta$ across positions. We also tilt the noise level $s_i$ to which re-corrupted positions return with the same confidence at strength $\lambda$, keeping the mean noise level at $s$.

• Candidate confidence: which candidates to reconsider. Plain re-corruption reopens alternative candidates uniformly at random, as the forward kernel does. For binary diffusion, we instead reopen candidate $u$ with probability proportional to $p_{i,u}^{\beta}$, keeping the expected number of reopened candidates fixed, where $p_{i,u}$ is the denoiser probability of $u$ when it was last in the candidate set. Uniform diffusion analogously draws the new token $u \ne\widetilde{Z}_0^i$ in proportion to $\pi_i^\theta(u \mid Z_t;t)^\beta$, while masked diffusion has no candidate to reopen. Plausible candidates are thus preferentially restored.

Experiments

We focus on solve rate and sample quality and report negative ELBOs only for completeness: the negative ELBO measures the path-space KL to the exact reverse process (Casado Noguerales et al. [6]), but it need not track the quality of the final samples, especially under non-ancestral samplers, as uniform versus masked diffusion shows (Schiff et al. [45]; Sahoo et al. [41]).

Logic and planning tasks

We evaluate on Sudoku-Extreme [57], Boxoban [21, 17], and four-coloring of random graphs, using matched 43M-parameter diffusion transformers and five training seeds per kernel and task. Besides the full test sets, we report hard subsets to de-saturate the benchmarks: low-clue Sudoku, long-solution Boxoban, and graphs ten times the training size. A sample counts as solved only if it satisfies every constraint, with one attempt per instance and no verifier. For the full and hard settings separately, we select each kernel’s sampler on validation at a reference budget of 256 network evaluations (NFE) for Sudoku and Boxoban and 64 for graph coloring, with the same tuning budget for every kernel and candidate confidence for all but masked diffusion. Parentheses below are standard errors over the five training seeds. Full experimental details are given in App. § 13, and the test negative ELBOs in Table 6.

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)

Table 1 reports the solve rates at the reference NFE, while Figure 3 shows their dependence on inference budget and training progress. Binary symmetric diffusion is the strongest kernel on every task, followed by uniform diffusion, with masked and binary absorbing diffusion behind both. Its margin widens on the hard subsets, especially on long-horizon Boxoban and on large graphs. On the large graphs, masked diffusion nearly fails. Binary symmetric diffusion leads at almost all budgets and training steps (Figure 3), rather than depending on a single NFE or checkpoint. Table 10 ablates the sampling components, while Figure 5 in App. § 13.§ 5 shows that the kernel comparison persists across difficulty bins and graph sizes. We show how each kernel solves a Sudoku board in App. § 14.

Text

We compare the four kernels using unconditional generation on three corpora of increasing sequence length $L$: Text8 [32] at $L = 256$, TinyStories [13] at $L = 512$, and OpenWebText [18] at $L = 1024 ({xref}App. F.6). We train every model on 131B tokens, on Text8 at the character level with $V = 27$ and on TinyStories and OpenWebText with byte-pair-encoding tokenizers of $V = 1024$, using as training objective the path term of the negative ELBO {xref}(3) (except for masked and binary absorbing diffusion on Text8, see {xref}App. C.2). We report MAUVE {citep}[36] against GPT-2 token unigram entropy, with GPT-2 Large {citep}[38] supplying the features. MAUVE compares the distribution of generated samples with held-out text, and we use it as the primary metric given known failure modes of generative perplexity (GenPPL) {citep}[16, 65], which we report with the negative ELBOs in {xref}App. F.6`.

Table 2 gives the test MAUVE of each kernel at the sampler setting selected on validation (App. § 13.§ 4), while Figure 4 traces quality against diversity using sampling settings selected on validation at representative entropies and evaluated on the test split. No kernel leads on all three corpora: binary symmetric diffusion reaches the best MAUVE on Text8, uniform diffusion on TinyStories, and masked diffusion on OpenWebText, each by a small margin. The kernels peak at slightly different entropies, so Table 12 in App. § 13.§ 6 also compares them at one common entropy per corpus, where binary symmetric diffusion reaches the best MAUVE on both Text8 and TinyStories.

Related work

Discrete diffusion was first formulated on a discrete time grid, modeling the reverse transitions directly [23, 1], and its continuous-time formulation instead learns to reverse a categorical jump process [5, 52]. Since then, methods have differed mainly in how they parameterize the reverse rates [31, 33] and in which paths the forward process allows [56, 47]. Closer to our setting, simplex-valued methods represent categorical uncertainty in a continuous state [15, 2], while partial and semantic masking keep residual information about the clean token [8, 66]. Binary diffusion instead changes the state space: each position follows a jump process on the binary cube, whose coordinates express candidate membership. Similar bit-flipping processes have been explored to model binary data, where the cube is the data space [49, 35]. The closest predecessor is the ShortListing Model, which also grows candidate sets, in discrete time [50]. Under the right noise schedule, its corruption process provides a discrete-time formulation of binary absorbing diffusion (App. § 12). Our main contributions are the non-absorbing symmetric process, which allows candidates to be both removed and restored during denoising, and the empirical evaluation on logic and planning tasks.

Discrete diffusion has been applied to Sudoku and other structured problems before [62, 60], and follow-up work improves solving through adaptive token order, remasking, explicit planning, or test-time search [27, 58, 30, 63]. Sudoku is also a standard benchmark for small recurrent reasoners such as HRM and TRM [57, 25], and Lattice Deduction Transformers likewise maintain per-variable candidate sets but train deduction on-policy with search and abstention heuristics [11]. All of these change the sampler, the architecture, or the training signal. Our experiments are instead designed to isolate the effect of the corruption kernel and evaluate direct, verifier-free samples from each kernel’s tuned sampler.

Conclusion

We have introduced Binary Discrete Diffusion, a family of continuous-time discrete-diffusion processes whose noisy states are sets of candidate tokens, represented as binary membership vectors. Parameterizing the reverse process through clean-token predictions lets a single $V$-way output determine all reverse rates and sampling updates, avoiding any $2^V$ enumeration in training and generation. We also introduced a confidence-guided self-correcting sampler that chooses which positions and candidates to reopen. Under controlled architectures, training budgets, and sampler tuning, binary symmetric diffusion outperforms uniform diffusion, and both outperform masked and binary absorbing diffusion on logic and planning tasks, with the largest gains on the hardest instances. Binary diffusion also remains competitive on language modeling. Our results thus show that candidate sets can be an effective intermediate representation for iterative reasoning, and that the corruption process can materially change the computation learned by the model.

Binary diffusion also opens a broader design space for candidate-set and bitwise corruption processes. Future kernels could exploit semantic or task-specific structure to introduce plausible candidates rather than random ones. The bits could also encode tokens differently, for example through their binary indices or an error-correcting code, although each such code defines a different state space whose states are no longer candidate sets. Richer representations of candidate sets than the normalized embedding sum used here may also prove useful at larger scales. Scaling these ideas to larger models and datasets, and to domains such as code, mathematics, and biological sequence design, is a natural next step.

AI use statement

Large language models were used to aid and polish writing (editing and reviewing the manuscript), for retrieval and discovery (finding and summarizing related work), and for research ideation and execution (implementing, running, and analyzing experiments). All AI-assisted work was reviewed by the authors, who verified every technical claim and result and take full responsibility for the final content.

Reproducibility statement

App. § 13 specifies the datasets with their splits and hard subsets, the architectures and training settings, every evaluation procedure, and the selection of learning rates, checkpoints, and sampler settings. App. § 10 describes the training objectives and time sampling, Apps. § 8 and § 9 derive the rates, losses, and ancestral updates of every kernel, and App. § 11 specifies the sampler.

Masked and uniform diffusion

We specialize the results of Campbell et al. [5] and Casado Noguerales et al. [6] using the notation of Sections 2–4. Local noisy states are written $z$, $y$, and the priors are the limiting distributions from which generation starts. We call the noisy-state distribution $m_i^\theta$ in (4) the local model mass.

Masked diffusion

For the masked kernel in (1), the off-diagonal forward rates are (Casado Noguerales et al., [6])

For $0\le s<t<1$, the transition kernel is

The local model masses and denoiser are

For $y\in[\mathcal{V}]$ with $y\ne Z_t^i$, the reverse rates are

All other off-diagonal reverse rates vanish. The path loss reduces to masked cross-entropy:

Plugging $\mu_i^\theta$ into the bridge (47) gives the ancestral update of Sahoo et al. [40]: visible tokens are copied, and a masked position unmasks to $c$ with probability $(1-s/t)\mu_i^\theta(c\mid Z_t;t)$.

Uniform diffusion

For the uniform kernel in (1), the off-diagonal forward rates are (Casado Noguerales et al., [6])

For $0\le s<t<1$, the transition kernel is

The local model mass and induced denoiser are

For $y\ne Z_t^i$, the clean-conditioned and model reverse rates are

The path loss is

All masses in these quotients are positive on an interior time interval.

Plugging $\mu_i^\theta$ into the bridge (47) gives the ancestral update of Schiff et al. [45], which, unlike the masked update, can change a visible token.

Prior term. Corrupting a uniform clean token leaves its distribution uniform. The finite-time and limiting priors thus coincide:

For the product sequence prior,

The uniform prior has full support at every finite cutoff.

Mathematical details of binary diffusion

We use the candidate-set notation and the bitwise loss from § 3. The network probability mass of the candidates in a set $z$ is

and $m_i^\theta$ denotes the local model mass of (4). Superscripts sym and abs specify the kernel, and we omit them in derivations where it is fixed. The cavity $\mu_i^\theta$, the masses $m_i^\theta$, and the denoiser $\pi_i^\theta$ always refer to that kernel.

Binary symmetric diffusion

To compute the model mass, put

As a function of the clean token, the forward kernel is

Toggling bit $u$ gives

The quotient of the two local masses, multiplied by $1/[2(1-t)]$, gives the stated model rate. All local masses are positive for $0<t<1$, so every bit flip has positive model rate.

The denoiser used for decoding and sampling is

Substituting $\mu_i^\theta(u\mid Z_t;t)=\rho_t^{-2z_u}\pi_u[1+(\rho_t^2-1)\nu_i^\theta(z\mid Z_t;t)]$, with $\pi_u=\pi_i^\theta(u\mid Z_t;t)$, turns the ratio of masses in (37) into $1-(1-\rho_t^{-2})\pi_u$ for $u\in z$ and $1+(\rho_t^2-1)\pi_u$ for $u\notin z$. The model rate is therefore $[\rho_t(1-\pi_u)+\rho_t^{-1}\pi_u]/[2(1-t)]$ for removing an active candidate and $[\rho_t\pi_u+\rho_t^{-1}(1-\pi_u)]/[2(1-t)]$ for adding an inactive one, which is (12).

Prior. The prior draws independent fair bits, $p_{t_2}^{\mathrm{sym}}(z)=2^{-V}$. For Bernoulli distributions with success probabilities $a,b\in(0,1)$, the KL divergence is

Conditional on the clean token $c$, the bits of $Z_{t_2}^i$ are independent, with bit $c$ active with probability $1-t_2/2$ and every other bit with probability $t_2/2$. The prior also factors over bits, so the KL is a sum of Bernoulli terms, which coincide because $D_{\mathrm{Ber}}(1-a\mathbin{\|}1/2)=D_{\mathrm{Ber}}(a\mathbin{\|}1/2)$:

This does not depend on $c$ and vanishes as $t_2\uparrow1$.

Binary absorbing diffusion

Proof. A bit that is zero at $s$ remains zero at $t$ with probability

Once activated, it remains one. Multiplication over bits proves (41), and $z = \{c\}$, $s = 0$ gives (42). For a nonempty state $z$,

Deleting an active bit $u$ changes this mass by the factor

Multiplying by the reversed forward activation rate $1/(1-t)$ gives the model rate. For $Z^i_0=c$, the substitution

gives the clean-conditioned rate. Deleting the last bit has zero rate because the empty vector has zero mass.

Proof. Fix $i$, write $Z^i_0=c$, and put

The homogeneity identity $\Phi(a/t,b/t)=\Phi(a,b)/t$ gives the local loss times $t$ as

Because the $h_u$ sum to one, the linear terms cancel, leaving (44). For a singleton, the remaining sum is empty and the loss is zero.

For absorbing diffusion, the local kernel is constant over clean tokens in $Z^i_t$ and zero outside it. Bayes reweighting gives the denoiser

Since $\nu^\theta_i(Z^i_t\setminus\{u\}\mid Z_t;t)/\nu^\theta_i(Z^i_t\mid Z_t;t)=1-\pi^\theta_i(u\mid Z_t;t)$ for $u\in Z^i_t$, the model rate in (43) equals (14). The cavity parameterization applies this support restriction analytically, while a separately predicted denoiser must respect it through explicit masking or learning.

Binary ancestral bridges

By Bayes’ rule and the Markov property, the forward bridge of § 4 is

Averaging it over the denoiser (5) cancels $q_{t\mid0}(z\mid c)$, which gives the plug-in form of the ancestral update (18):

This is the bridge with the cavity in place of the clean token. We now derive the conditional bit bridges from (46).

Symmetric bridge. Conditional on the clean proposal $\widehat{Z}^{i}_{0}=c$, the bits are independent. With $\varepsilon_{s,t}$ from (35), bit $u$ with clean value $b_u=\mathbb{1}\{u=c\}$ and current value $z_u=(Z^{i}_{t})_u$ differs from $b_u$ at $s$ with probability

the chance of differing from the clean bit at $s$ and then flipping, or not, to the current value at $t$. It favors the current value for $s$ close to $t$ and the clean bit as $s\downarrow0$.

A simpler symmetric sampler applies a one-bit Bayes update to each cavity bit marginal and draws the bits independently. This ignores the dependence between the bits through the shared clean token: at $s=0$, the exact bridge draws a single one-hot state from $\pi^\theta_0$, whereas independent bit draws can leave zero or several candidates active. It performed worse in early experiments, and we dropped it.

Absorbing bridge. Conditional on $\widehat{Z}^{i}_{0}=c$, the bit $c$ stays active, and every bit inactive in $Z^{i}_{t}$ remains inactive at $s$. For $u\in Z^{i}_{t}\setminus\{c\}$,

Indeed, a false candidate is active at $s$ with probability $s$, active at $t$ with probability $t$, and activation by $s$ implies activation by $t$. These bit events are independent conditional on $c$ and the current state. The update therefore preserves nonemptiness and produces a subset of the current active set.

Training objectives and time sampling

Finite-window negative ELBO and boundary terms

The idealized objective (3) integrates the reverse process from clean data at $t=0$ to the terminal noise distribution at $t=1$. In practice we use an interior window $0<t_1<t_2<1$ to avoid singular jump rates near the endpoints. The corresponding finite-window negative ELBO, abbreviated NELBO in the appendices, is

where

The first term, with the denoiser as decoder, $p^\theta_{0\mid t_1}(Z_0\mid Z_{t_1})=\prod_i\pi^\theta_0(Z^i_0\mid Z^i_{t_1};t_1)$, accounts for the residual corruption at the clean end of the truncated path, while the second measures the mismatch between the forward distribution at $t_2$ and the prior from which generation starts.

For uniform and binary symmetric diffusion, the terminal-prior term is finite and available analytically (Apps. § 8.§ 2 and § 9.§ 1). With the prior matched to the limiting forward distribution, the boundary contributions vanish as $t_1\downarrow0$ and $t_2\uparrow1$, recovering (3). For masked and binary absorbing diffusion, the limiting prior is a point mass, so the terminal KL is infinite for every $t_2<1$ but zero at $t_2=1$. The terminal endpoint therefore requires separate treatment, and App. § 13.§ 3 describes our likelihood-evaluation convention.

Training objectives

Alongside the path ELBO, we compared a flat ELBO, cross-entropy (xent), and weighted cross-entropy (wxent). For the kernels considered here, the reverse rates share a scalar prefactor, which extends the flip rate $r_t$ of (9) to every kernel,

and the remaining factors are ratios of the forward kernel $q_{t|0}$ at the current noisy token. Since $\Phi(ra, rb)=r\Phi(a,b)$, the prefactor is also the weight of the jump penalties in the path integrand $J_t$ of (3). The flat ELBO drops it, $J_t^{\mathrm{flat}}=J_t/r_t$, which changes the relative weight of the noise levels. Cross-entropy trains the network output directly as a denoiser,

and weighted cross-entropy multiplies it by the prefactor, $J_t^{\mathrm{wxent}}=r_tJ_t^{\mathrm{xent}}$. For masked diffusion the sums run over masked positions. The ELBO and wxent are integrated over time as in (3), while the flat ELBO and xent are averaged over the base schedule of App. § 10.§ 3. All four are estimated with the inverse-density weight defined there, which the adaptive proposal of App. § 10.§ 5 preserves.

We train the logic models on the path ELBO. For text, we selected the objective of each kernel and corpus on the validation NELBO after 10% of the training budget. The path ELBO was best everywhere except on Text8, where we train masked diffusion on xent, which coincides with its flat ELBO, and binary absorbing diffusion on wxent. The latter still bounds the likelihood, as we show next.

Absorbing cross-entropy bound. For binary absorbing diffusion, wxent upper-bounds the path integrand. Fix a position with clean token $Z_i^0=c$. The denoiser is supported on the active set $Z_t^i$, which contains $c$, so

Since $\pi_i^\theta(c\mid Z_t;t)=\mu_i^\theta(c\mid Z_t;t)/\nu_i^\theta(Z_t^i\mid Z_t;t)\ge\mu_i^\theta(c\mid Z_t;t)$, taking negative logarithms, multiplying by $1/t$, and summing over positions in (44) gives $J_t^{\mathrm{abs}}\le J_t^{\mathrm{wxent}}$.

Time schedules

The base schedule reparameterizes corruption time on the clipped window $[t_1,t_2]$ by $\xi\in[0,1]$, which we draw uniformly during training. The linear, logarithmic, and cosine maps are

which give the base sampling densities on $[t_1,t_2]$

Logarithmic sampling assigns equal probability to intervals with the same ratio of endpoints, giving more resolution near clean data. At large vocabularies, this matches how the binary kernels lose information (App. § 10.§ 4). Cosine sampling instead gives more resolution near both ends of the window. To estimate the path integral without bias, we weight each sequence’s loss by the inverse density of its sampled time, namely $t_2-t_1$ for the linear schedule, $t\log(t_2/t_1)$ for the logarithmic schedule, and $\pi\sqrt{(t-t_1)(t_2-t)}$ for the cosine schedule.

We give $\xi$ to the network as its time input:

The adaptive proposal below also acts on $\xi$, while the kernel and rates retain their definitions in corruption time $t$. We choose inference grids separately from training-time sampling. Applying any map in (55) to $j/N$, for $j=0,\ldots,N$, gives a linear, logarithmic, or cosine grid for $N$ reverse steps, traversed in decreasing $j$ as in Algorithm 1. The logarithmic grid has smaller absolute steps near $t_1$, and the cosine grid near both ends of the window. We train with the linear and logarithmic schedules (Table 3 and Table 4) and sample on grids of all three kinds (Table 7).

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
sequence length	Sudoku 81; Boxoban 100 + 128 (flattened board + solution); graph coloring 64
precision	mixed: float32 parameters, normalization, logits, and loss; bfloat16 matmuls, attention, and residual stream
dropout	0
Optimization
optimizer	AdamW, $(\beta_1, \beta_2) = (0.9, 0.999)$
learning rate	$10^{-4}$; Boxoban $3 \cdot10^{-4}$ except binary symmetric
schedule	constant after 1,000 warm-up steps
batch size	512
training steps	Sudoku 1M, Boxoban 2.5M, graph coloring 300k
weight decay	0.05, excluding norms and embeddings
gradient clip	1
EMA decay	0.9999
training seeds	5
Diffusion
objective	path ELBO, cavity parameterization
time window	$[0.01, 0.9999]$
base schedule	linear, low-discrepancy sampling
adaptive sampling	gradient RMS, EMA 0.99

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
vocabulary	Text8 27, TinyStories 1024, OpenWebText 1024
precision	mixed: float32 parameters, normalization, logits, and loss; bfloat16 matmuls, attention, and residual stream
dropout	0
Optimization
optimizer	AdamW, $(\beta_1,\beta_2)=(0.9,0.999)$
learning rate	$3 \cdot10^{-4}$
schedule	constant after 2,500 warm-up steps
batch size	512
training steps	Text8 1M, TinyStories 500k, OpenWebText 250k
weight decay	0.02, excluding norms and embeddings
gradient clip	1
EMA decay	0.9999
training seeds	1
Diffusion
objective	path ELBO, cavity parameterization; Text8: xent for masked, wxent for binary absorbing
time window	Text8 [0.001, 0.9999]; TinyStories and OpenWebText [0.0005, 0.9999]
base schedule	linear; binary kernels logarithmic; low-discrepancy sampling
adaptive sampling	gradient RMS, EMA 0.99

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\}$
Candidate confidence $\beta$	$\{0, 0.5, 1, 2, 3\}$, all but masked	$\{0, 0.5, 1, 2\}$, binary
Confidence coordinate	cavity, denoiser	cavity, denoiser
Grid spacing	linear	cosine, logarithmic
Nucleus top-$p$	1	$\{0.9, 1\}$

Information retained under each kernel

Section 3.4 and Figure 2 consider independent positions whose clean tokens are uniform on $[V]$. The other positions then carry no information about $Z_0^i$, so the true cavity is uniform, $q(Z_0^i=c\mid Z_t^{-i})=1/V$, and the information in the noisy sequence is a sum over positions of

where the posterior of the clean token is the denoiser (5) with a uniform $\mu_i^\theta$, the forward kernel $q_{t|0}(Z_t^i\mid c)$ normalized over $c$.

• Masked. The posterior is a point mass at an unmasked token and uniform at a mask, so $I=(1-t)\log V$.

• Uniform. Given the noisy token, the posterior assigns $a=1-t+t/V$ to it and $b=t/V$ to every other token, so $I=\log V+a\log a+(V-1)b\log b$.

• Binary absorbing. The posterior is uniform on the active set, whose size is $1+K$ with $K\sim\operatorname{Bin}(V-1,t)$, so $I=\log V-\mathbb{E}[\log(1+K)]\ge\log V-\log(1+(V-1)t)$ by Jensen’s inequality.

• Binary symmetric. A state $z$ differs from the clean token $c$ in $d_H(z,c)=|z|+1-2z_c$ bits, so the likelihood $q_{t|0}^{\mathrm{sym}}(z\mid c)$ is proportional to $\rho_t^{-d_H(z,c)}\propto\rho_t^{2z_c}$ as a function of $c$, and with a uniform prior the posterior weighs active candidates by $\rho_t^\theta$ and inactive tokens by one, as (38) with a uniform $\mu_i^\theta$. A state with $k$ active candidates therefore has posterior entropy

and $I=\log V-\mathbb{E}H_{B+K}$ with independent $B\sim\operatorname{Ber}(1-t/2)$, the clean bit, and $K\sim\operatorname{Bin}(V-1,t/2)$, the false candidates. For small $t$, $\rho_t^2$ is large and the posterior is nearly uniform on the active set, so that $I\approx\log V-\log(1+(V-1)t/2)$, as in the absorbing case with half as many false candidates.

These expressions give the curves of Figure 2. With $V=1024$ on the window $[5\cdot10^{-4},0.9999]$, the linear schedule draws 95% of its times where less than half of the information is left under binary symmetric diffusion and 97% under binary absorbing diffusion, against 50% under masked and 60% under uniform diffusion. The logarithmic schedule lowers these fractions to 39% and 46% for the binary kernels. On the other hand, with $V=9$, half of the information is lost at $t\approx0.27$ under binary symmetric, 0.28 under binary absorbing, and 0.29 under uniform diffusion, so the binary kernels lose information about as fast as uniform diffusion.

Adaptive gradient-RMS importance sampling

Adaptive importance sampling replaces the base schedule by a proposal that draws more samples where loss gradients are large. It improved over the base schedule alone in all our experiments, so we train every model, for all four kernels and all tasks, with it. The statistic is the root-mean-square norm of the gradient with respect to the network’s output logits, used as an inexpensive proxy for parameter-gradient norms.

We divide the range of $\xi$ into $K=32$ equal-width bins. Let $g_\theta$ denote a sequence’s contribution to the loss under the base schedule, including token normalization and the base-schedule weight, and let $\ell$ denote its output logits. For the path objective with $L$ scored tokens per sequence, this contribution is

When scored token counts vary across sequences, we replace $L$ by their minibatch mean. In each bin $k$, we maintain exponentially decayed sums $S_k$ of $\lVert\nabla_\ell g_\theta\rVert_2^2$ and counts $C_k$, both with decay 0.99. Their ratio gives the mean squared gradient norm, from which we form the RMS estimate and the bin probability:

Sampling uniformly within each selected bin gives the time density and path-loss weight

The additional factor $1/(K P_k)$ preserves the objective under the base schedule. Mixing in 10% of the base schedule keeps every bin accessible and bounds this factor by 10.

For the first 100 minibatches we sample from the base schedule while collecting statistics. Each minibatch uses the preceding proposal, held fixed during differentiation, and updates the statistics for the next minibatch. We stratify the times within a minibatch in the proposal’s cumulative-probability coordinate. For validation, we draw times from the base schedule.

Confidence-guided Psi-sampler

This appendix specifies each setting of Algorithm 1 for all four kernels. One step maps the state $Z_t$ to $Z_s$, $s < t$, on a sampling grid with linear, cosine, or logarithmic spacing (App. § 10.§ 3). We hold conditioning positions, such as Sudoku clues, fixed and exclude them from every average over positions below.

Temperature $T$ and nucleus top-$p$. For every draw from the denoiser, for the clean proposal, inside the ancestral update, and in the final decoding, we use the tempered denoiser

which on text we further restrict to its top-$p$ nucleus and renormalize, and $T = 0$ selects the most probable token. The clean proposal $\widetilde{Z}_0^i \sim\pi_i^{\theta,T}(\cdot\mid Z_t;t)$ is drawn independently at each position, and the ancestral update draws its own proposal $\widetilde{Z}_0^i$ in the same way.

Re-corrupt fraction $\eta$. Each position is re-corrupted with probability $\kappa_i$ and otherwise takes the ancestral update (18), as in (21). Without position confidence, $\kappa_i = \eta$ at every position, so that $\eta= 0$ is ancestral sampling and $\eta= 1$ re-corrupts every position at every step.

Confidence coordinate. Position confidence and the ordering tilt read the confidence in the proposal from the cavity or from the denoiser,

The cavity reflects the context alone, while the denoiser also accounts for the position’s own noisy state.

Position confidence $\gamma$. The re-corruption probabilities decrease with confidence,

where we set the constant $\zeta$ by bisection so that the mean of $\kappa_i$ over positions equals $\eta$. Positions capped at one thus pass their excess to the others, and $\gamma= 0$ gives $\kappa_i = \eta$. For masked diffusion, masked positions keep $\kappa_i = \eta$, and the redistribution runs over the unmasked positions only, each with the confidence in its token recorded when it was unmasked, since the network is not trained at unmasked positions.

Ordering tilt $\lambda$. A re-corrupted position returns to its own noise level

instead of $s$, with $\zeta'$ set so that the mean of $s_i$ over positions equals $s$. Less confident positions are thus corrupted more while the mean noise level follows the grid, and $\lambda= 0$ gives $s_i = s$.

Candidate confidence $\beta$. Plain re-corruption opens alternatives uniformly at random, as the forward kernel does. With candidate confidence, the binary kernels corrupt the proposal’s own bit as the forward kernel does, dropping it with probability $s_i/2$ under binary symmetric diffusion and keeping it under binary absorbing diffusion, and open each other token $u \ne\tilde{Z}_0^i$ independently with probability $\min\{1,\zeta_i p_{i,u}^{\beta}\}$, where $\zeta_i$ is set so that

The expected number of opened alternatives is thus that of the forward kernel, which $\beta=0$ recovers. The weight $p_{i,u}$ is the denoiser probability of $u$ at the most recent step at which $u$ was a candidate at position $i$, starting from $1/V$, because the binary absorbing denoiser vanishes outside the current set. Without this memory, reopening in proportion to the current cavity or denoiser probability lowers binary symmetric diffusion’s best Sudoku validation solve rate over the same grid to 89.6% and 85.2%, below position confidence alone (95.2%). Uniform diffusion re-corrupts a position by changing its token with the forward probability $(V-1)s_i/V$ and draws the new token $u \ne\tilde{Z}_0^i$ with probability proportional to $\pi^\theta(u \mid Z_t;t)^\beta$, so that $\beta=0$ is again the forward kernel. Masked diffusion has no candidate to reopen.

Final decoding. After the last step, we decode each position from the tempered denoiser at $t_1$, keeping the unmasked tokens of masked diffusion.

Extended related work

Discrete diffusion and corruption-state design. Several lines of work broaden the forward path without introducing candidate sets. Generalized interpolating diffusion and kinetic path design admit richer categorical couplings ([56, 47]), partial masking inserts intermediate corruption states between a token and a full mask ([8]), and sticky jump processes combine discrete jumps with continuous coordinates ([26]). CADD and CANDI go further and augment or hybridize the categorical state with a continuous one ([64, 37]). Even at scale, and with architectures and training budgets matched, the choice between masking, uniform corruption, and interpolating paths remains consequential ([42]).

There is also a substantial simplex-valued lineage, which lifts categories to continuous points on the simplex or updates distribution parameters directly ([15, 2, 51, 20, 7] (Richemon et al. 2022)). Simplax is the closest of these to our setting: it keeps uniform categorical diffusion at its marginal and adds a Dirichlet auxiliary variable to the reverse bridge ([43]). Its denoiser, however, still observes a corrupted category, whereas binary diffusion exposes the candidate set to the denoiser as the noisy state.

Binary diffusion and candidate-set representations. Prior binary diffusion methods treat each bit as part of the object being generated. Bit-flip diffusion of binary data goes back to binomial diffusion ([49]), and DMPM studies its continuous-time form ([35]). BerDiff applies a Bernoulli kernel to binary segmentation masks ([9]), GraphGUIDE adds, removes, or flips graph edges through Bernoulli transitions ([55]), and Blackout diffusion models discrete counts through birth–death processes ([44]). Analog Bits instead encodes one category in $\lceil\log_2 V \rceil$ real-valued bit coordinates and applies continuous diffusion ([10]). In binary diffusion, by contrast, there are $V$ binary coordinates per position and an active bit denotes membership in the noisy subset.

The ShortListing Model (SLM) is the closest predecessor ([50]). It represents a categorical variable by a nonempty candidate set, starts the forward process from the clean singleton, activates false candidates until reaching the full vocabulary, and samples in reverse by progressive candidate pruning. However, the model is formulated in discrete time and identifies sets with simplex-face centroids. To see the correspondence with binary absorbing diffusion, let $n_t$ be SLM’s expected candidate-set size at time $t$ and take the linear noise schedule

The probability of adding a candidate between times $s < t$ is then

and the clean-conditioned probability of retaining a false candidate is

which are the absorbing kernel (41) and bridge (49).

Diffusion for structured reasoning. Beyond Autoregression established masked diffusion baselines on Sudoku and other reasoning and planning tasks [62]. Dirichlet diffusion solves Sudoku in a continuous simplex state [2], and Simplax reports Sudoku generalization across clue densities [43]. Several analyses show that the corruption and the order of updates matter as much as the model: Spatial Reasoning Models find that the order of variable updates strongly affects accuracy [60], and the locality induced by the corruption and factorization changes trainability on Sudoku and graph path-finding [59]. On the theoretical side, masked diffusion models can simulate chain-of-thought under finite precision [53].

A separate line of work changes the reverse-time policy rather than the forward state, through token ordering, planned denoising and path planning, remasking, learned reveal schedules, or search during and around sampling [27, 30, 34, 58, 28, 61, 54, 3, 63]. These methods compose with any corruption kernel, and beyond the confidence-guided re-corruption of § 4 we use none of them: our verifier-free solve rate refers to direct samples from each kernel’s tuned sampler, without search, reranking, or a symbolic solver.

Recurrent reasoning. Sudoku and related benchmarks have also driven a rapidly growing literature on small recurrent reasoners, which allocate computation through repeated latent updates, fixed-point dynamics, or looped layers [57, 25, 46, 24, 14, 22, 4, 29]. These approaches change the architecture, the training dynamics, or the recurrent depth, which is a separate axis from the corruption state that binary diffusion changes, so we do not compare against them directly.

Experimental details

Optimization details

Tables 3 and 4 give the architectures and optimization settings of the models. We embed candidate sets by (15). Dividing the sum by $\lvert z\rvert$ instead, or embedding the signed vector $(2z-1)/V$, made little difference in our experiments.

Learning-rate and checkpoint selection

We selected the learning rate of each task and kernel from $\{10^{-4}, 3\cdot10^{-4}, 10^{-3}\}$ on the validation NELBO of App. § 13.§ 3, computed on 51,200 validation draws and averaged over two training seeds (Table 5). Within each task, kernel, and seed, all learning rates share the data, times, and corruptions, so their differences have a Monte Carlo standard error below $3\cdot10^{-4}$, and the variation between seeds dominates. We tune Sudoku and graph coloring at their full training budget and Boxoban at 1M steps. On Boxoban uniform and binary absorbing, the two lowest learning rates are within seed noise, and in both cases we keep the middle rate $3\cdot10^{-4}$. Since Boxoban validation NELBO was still improving slowly at that point, we trained the selected rates for 2.5M steps and selected a checkpoint for each run on the validation NELBO, evaluated every 100k steps from 1M. We keep the final checkpoint unless an earlier one is lower by more than two standard errors of the paired difference, and only two binary absorbing seeds select an earlier checkpoint, at 2.0M and 1.0M steps.

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	Kernel	$10^{-4}$	$3 \cdot10^{-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)
	Binary absorbing	0.0290 (0.0005)	0.0309 (0.0005)	0.0394 (0.0002)
	Masked	0.0294 (0.0001)	0.0266 (0.0002)	0.0338 (0.0009)
Graph coloring	Binary symmetric	0.0863 (0.0001)	0.0873 (0.0000)	0.0905 (0.0000)
	Uniform	0.0857 (0.0000)	0.0865 (0.0002)	0.0896 (0.0002)
	Binary absorbing	0.0881 (0.0001)	0.0898 (0.0001)	0.0951 (0.0003)
	Masked	0.0837 (0.0001)	0.0845 (0.0001)	0.0880 (0.0005)

Evaluation

NELBO. We evaluate the finite-window NELBO (50) on the training window with the estimators used in training. For the path term, we draw one time per sequence from the training time schedule

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

with inverse-density weighting. We estimate reconstruction from forward corruptions at $t_1$ with the denoiser as decoder, and visible tokens in masked diffusion are copied exactly and have zero reconstruction loss. The prior is the limiting distribution from which generation starts. Its KL from the time-$t_2$ corruption is analytic for uniform and binary symmetric diffusion (Apps. A.2 and B.1). For masked and binary absorbing diffusion the prior is a point mass, so that the KL is infinite for $t_2 < 1$ and zero at $t_2 = 1$, and we omit it. We aggregate the total NELBO over scored tokens, excluding padding and conditioning clues.

Logic solve rate. We score logic models on direct samples, with one attempt per instance and no verifier or selection among attempts, so the reported solve rate is single-attempt success. Sudoku success requires the completed reference grid, and Boxoban success requires legal actions that end with every box on a goal, with the action sequence read up to the first STAY, the no-operation action that pads solutions. Graph coloring accepts any proper coloring. We evaluate the selected EMA checkpoint of each of the five training seeds (App. F.2) with a linear sampling grid on [0.01, 0.9999] and the sampler selected on validation at the reference NFE, 256 for Sudoku and Boxoban and 64 for graph coloring (App. F.4). The tables use the full test splits, and the NFE and training curves use 8,192 and 4,096 test instances, except in their hard columns, which use every hard test instance. We evaluate every kernel on the same instances and fix the difficulty bins on validation data. The hard subsets are defined with the data in App. F.5. We report the mean and standard error over training seeds.

Text sample quality. We tune every sampler setting on the validation split and evaluate on the test split of each corpus (App. F.6). After removing special tokens, we retokenize complete decoded strings with GPT-2 Large for GenPPL and MAUVE features. Each sample set holds 2,000 samples from one generation seed, and each reported value averages the two generation seeds of a sampler setting. Entropy is the unigram entropy, in nats, of the GPT-2 tokens pooled over a sample set rather than a within-string average, so it measures the diversity of the set as a whole. GenPPL is the exponential of the total GPT-2 Large negative log-likelihood of the sample set divided by its total token count, so it is pooled over tokens rather than averaged over strings. We compute MAUVE with 200 buckets and average it over four reference draws and five clustering seeds, with reference subsets sampled without replacement and of the size of the generated sample set. Error bars span the two generation seeds and condition on the checkpoint.

Sampler tuning procedure

We sample every kernel with the confidence-guided $\Psi$-sampler of App. D. Its settings are the temperature $T$, the re-corrupt fraction $\eta$, the confidence coordinate, the position-confidence strength $\gamma$, the ordering tilt $\lambda$, and the candidate-confidence strength $\beta$, which we tune for every kernel but masked diffusion on the logic tasks and for the binary kernels on text. On text, we also tune the nucleus top-$p$ and the spacing of the sampling grid. We apply temperature and top-$p$ to the denoiser rather than to the cavity (Casado Nogueira et al., 2026).

For each task and kernel, we select these settings on validation over the grids of Table 7. On the logic tasks the score is the mean solve rate over the training seeds on a fixed validation split of 2,048 instances (1,024 for the large graphs) at the reference NFE. On text it is MAUVE at NFE $= L$, screened with 512 samples and confirmed with 2,000 samples for the three best candidates. We then freeze the selection for every test measurement, budget, and training seed unless otherwise stated. We select the sampler of the hard columns separately on the hard subsets of the validation splits. The grids are not full products: the ordering and confidence strengths enter through a few sub-grids, and we give masked diffusion, which has no candidate to reopen, a matching number of extra ordering and re-corruption points in place of the candidate-confidence settings (Table 7), so we tune every kernel with the same budget. Because the cavity and the denoiser coincide for masked diffusion, the confidence coordinate has no effect there. Table 10 selects over nested subsets of the logic grid: ancestral sampling, re-corruption alone, the $\Psi$-sampler without confidence, with position confidence, and with every setting, so each row reports what its settings add. Candidate confidence lifts binary symmetric diffusion on Sudoku and binary absorbing diffusion on the large graphs, whereas it is only selected for uniform diffusion on the Boxoban hard subset. Table 8 and Table 9 list the selected settings.

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
Binary symmetric	$\eta$	1	1	1	1	0.8	1
Binary symmetric	coord.	c	c	c	c	c	c
Binary symmetric	$\gamma$	0	0	0	0	0	0
Binary symmetric	$\lambda$	0	0	3	3	0	3
Binary symmetric	$\beta$	0.5	0.5	3	0.5	0	0
Uniform	$T$	1	1	1	1	1	1
Uniform	$\eta$	0.5	0.5	0.5	1	0.5	1
Uniform	coord.	c	c	c	c	d	c
Uniform	$\gamma$	10	10	3	0	3	0
Uniform	$\lambda$	0	0	3	3	0	30
Uniform	$\beta$	0	0	0	2	0	0
Binary absorbing	$T$	0.5	0	0	0	0.5	0
Binary absorbing	$\eta$	1	1	1	1	0.5	1
Binary absorbing	coord.	d	d	c	c	c	c
Binary absorbing	$\gamma$	0	0	0	0	1	0
Binary absorbing	$\lambda$	1	1	1	0	3	0
Binary absorbing	$\beta$	0	0	0	0.5	0	0.5
Masked	$T$	0	0.5	0	0	0.5	0.5
Masked	$\eta$	0.9	0.9	0.5	0.8	0.8	1
Masked	coord.	c	c	c	c	c	c
Masked	$\gamma$	0	0	10	0	3	0
Masked	$\lambda$	3	3	0	3	3	2
Masked	$\beta$	0	0	0	0	0	0

Kernel	Setting	Text8	TinyStories	OpenWebText
Binary symmetric	$T$	1	0.9	0.9
Binary symmetric	top-$p$	1	1	1
Binary symmetric	spacing	log	cosine	log
Binary symmetric	$\eta$	1	0.5	0.8
Binary symmetric	coord.	c	d	c
Binary symmetric	$\gamma$	0	10	0
Binary symmetric	$\lambda$	1	0	1
Binary symmetric	$\beta$	0	0	0
Uniform	$T$	0.9	1	0.8
Uniform	top-$p$	1	1	0.9
Uniform	spacing	cosine	cosine	log
Uniform	$\eta$	0.2	0.2	0.1
Uniform	coord.	c	c	c
Uniform	$\gamma$	0	1	0
Uniform	$\lambda$	0	0	0
Uniform	$\beta$	0	0	0
Binary absorbing	$T$	0.9	1	0.9
Binary absorbing	top-$p$	1	1	1
Binary absorbing	spacing	log	log	log
Binary absorbing	$\eta$	0.8	0.8	1
Binary absorbing	coord.	c	d	c
Binary absorbing	$\gamma$	0	0	0
Binary absorbing	$\lambda$	1	1	1
Binary absorbing	$\beta$	0	0	0
Masked	$T$	0.9	0.9	0.9
Masked	top-$p$	1	1	0.9
Masked	spacing	cosine	cosine	cosine
Masked	$\eta$	0.05	0.5	0.01
Masked	coord.	c	c	c
Masked	$\gamma$	3	1	0
Masked	$\lambda$	0	0	0
Masked	$\beta$	0	0	0

Figure 4 measures each kernel at several entropies: we bin the sampler settings screened on validation by GPT-2 token entropy, evaluate the best of each bin on the test split with 2,000 samples and two generation seeds, and draw the upper envelope of these points over entropy, on which the validation-selected setting lies for every kernel.

Logic tasks

In every task, we condition the model on the given part of the instance: we show it clean, never corrupt it, and exclude it from the loss, so all randomness and revision act on the generated positions.

Sudoku. For Sudoku, we use the Sudoku-Extreme boards of Wang et al. [57], 3.8M training boards and a test pool of 423k, as 81 digit tokens with the clue cells fixed. We mark the clue cells with an embedding added to the input. This changed little for the masked and binary kernels but was necessary for uniform diffusion to train at all, since a clue is otherwise indistinguishable from a uniformly corrupted cell. We partition the test pool into validation and test sets of about 200k and 223k boards that are orbit-disjoint under the augmentation symmetries (digit relabeling, board flips, and rotations), and the hard subset of the test set keeps the boards with at most 22 clues (4.1%).

Boxoban. For Boxoban, we use the 10 $\times$ 10 levels of Guez et al. [21] with the A$^\star$ solutions of Garriga-Alonso et al. [17] and keep the levels whose solution replays to a solved board. Each sequence is the flattened board followed by 128 action tokens, the solution padded with STAY, and we score the whole action region. Because the official test pool holds only 1,000 levels, we partition the 92k solved levels of the official validation pool once into validation and test sets of 25k levels each and fold the remaining 42k into the 936k training levels, and the hard subset keeps the boards whose solution needs at least 40 moves (19.8%).

Graph coloring. Graph coloring instances are random graphs with a planted four-coloring: 64 vertices in four balanced color classes, with each cross-class edge present independently with probability 0.2, so the mean degree is 9.6, just above the Kesten–Stigum threshold $(k - 1)^2 = 9$ for $k = 4$ colors, below which the planted coloring is undetectable. Any proper coloring counts as a solution, not only the planted one. We pass the graph’s adjacency matrix to the model as an attention mask and generate instances on the fly from separate seeded streams for training, validation (2,048 instances), and test (100k). The hard subset consists of 4,096 graphs of 640 vertices at the same mean degree, with the edge probability scaled to 0.02.

During training, we augment Sudoku with the symmetries above and Boxoban with joint board and action rotations and reflections, while validation and test examples are unaugmented. Figure 5 gives the solve rate by difficulty bin and by graph size.

Language modeling

For all text models, we use the diffusion transformer of Sahoo et al. [40] with time conditioning, without about 92M non-embedding parameters on Text8 and TinyStories and 214M on OpenWebText, and train every run on 131B tokens. Table 4 lists the remaining training settings.

Text8. Text8 (Mahoney, [32]) is the first $10^{8}$ characters of a cleaned English Wikipedia dump, over 27 characters, in sequences of $L = 256$. We use the standard split into the first 90M characters for training and 5M each for validation and test.

TinyStories. TinyStories [13] is a corpus of short synthetic stories in simple English. We tokenize it with our own byte-pair-encoding (BPE) tokenizer of $V = 1024$ tokens, trained on the corpus, and hold one story per sequence of $L = 512$: the story tokens, an EOS token, and PAD tokens up to $L$. We keep the train and validation splits of the released corpus and drop the $3.9\%$ of training and $3.6\%$ of validation stories that do not fit. This leaves 2,611,361 training stories and 26,637 validation stories, which we split evenly into validation and test sets. During training, we corrupt and attend to padding like any other token but never score it, so the model does not learn where a story ends. We therefore sample at a known length: each sample takes the padding positions of a validation story, and these positions follow the forward bridge $q_{s|t,0}(\cdot\mid Z_t^i,\mathrm{PAD})$ from the prior down to $t_1$ instead of being shown clean, so the model sees them as it did in training.

OpenWebText. OpenWebText [18] is an open reproduction of the WebText corpus. We tokenize it with our own BPE tokenizer of $V = 1024$ tokens, trained on the corpus, and pack documents into sequences of $L = 1024$. We wrap each document in BOS and EOS tokens, follow it with a uniformly random number of 0 to 127 PAD tokens, and cut the resulting stream into consecutive sequences of $L$ tokens, so a sequence can hold several documents or part of one, and we do not mask attention between documents. As for TinyStories, we corrupt and attend to padding but never score it, and we exclude it from the likelihoods and the decoded text of App. F.3. The corpus has no official split, so we hold out a random 100k documents before packing and split them evenly into validation and test sets, which keeps the three sets document-disjoint. Like Text8, we sample it unconditionally.

Table 11 gives, at the validation-selected setting of each kernel, the pooled entropy, MAUVE, and GenPPL, together with the held-out NELBO of App. F.3, which does not depend on the sampler.

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)
	Binary absorbing	5.800 (0.002)	0.585 (0.001)	15.2 (0.0)	0.684 (0.002)
	Masked	5.751 (0.005)	0.850 (0.009)	8.0 (0.0)	0.452 (0.001)
OpenWebText	Binary symmetric	7.047 (0.005)	0.840 (0.001)	31.3 (0.1)	1.490 (0.003)
	Uniform	7.020 (0.002)	0.822 (0.004)	47.4 (0.0)	1.236 (0.002)
	Binary absorbing	7.168 (0.002)	0.747 (0.004)	54.6 (0.3)	1.499 (0.002)
	Masked	7.250 (0.006)	0.871 (0.013)	51.0 (0.6)	1.179 (0.002)

Figure 6 gives GenPPL at the points of Figure 4.

Table 2 reports each kernel at the setting where its own validation MAUVE is highest, while Table 12 reports every kernel of a corpus at one entropy, chosen where their interpolated MAUVE is jointly highest. On Text8 the kernels peak at different entropies, but the ranking does not change. On TinyStories, uniform diffusion scores lower at the common entropy, and on OpenWebText both uniform and binary symmetric diffusion score lower while masked diffusion stays best.

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 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.

Dataset	Kernel	$H$	MAUVE	GenPPL
Text8	Binary symmetric	6.805 (0.004)	0.913 (0.001)	186 (3)
Text8	Uniform	6.924 (0.003)	0.891 (0.006)	358 (1)
Text8	Binary absorbing	6.803 (0.011)	0.821 (0.007)	329 (10)
Text8	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)
TinyStories	Uniform	5.756 (0.007)	0.877 (0.001)	12.3 (0.0)
TinyStories	Binary absorbing	5.800 (0.002)	0.585 (0.011)	15.2 (0.0)
TinyStories	Masked	5.751 (0.005)	0.850 (0.009)	8.0 (0.0)
OpenWebText	Binary symmetric	7.288 (0.013)	0.800 (0.006)	31.8 (0.5)
OpenWebText	Uniform	7.287 (0.010)	0.808 (0.002)	96.0 (0.3)
OpenWebText	Binary absorbing	7.168 (0.002)	0.747 (0.004)	54.6 (0.3)
OpenWebText	Masked	7.250 (0.006)	0.871 (0.013)	51.0 (0.6)

Sudoku solve trajectories

We show one sample per kernel on the first Sudoku test board in evaluation order, which has 24 clues, in Figure 7. We generate the samples with the seed-0 models of Table 1, using ancestral sampling at temperature $T = 1$ and 256 NFE. All four kernels solve this board.

Kernel	Sudoku All	Sudoku Hard	Boxoban All	Boxoban Hard	Graph coloring All	Graph coloring 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)

Generated samples

We show two samples per kernel from the sample sets of Table 2, drawn uniformly at random from the 2,000 of the first generation seed.

Text8

Binary symmetric diffusion.

ding enemies somewhat convinced by recruiting the other to plan the new world edition of the book of jonah depends on the most wonderful time luke says jonah sleeps for fight jonathan goes for life and takes a holy life in section three three this version

e existence of the universe is held by many people according to and without personal concern about the future of the universe the aim of the family is a creation of a number of possible worlds including unique events shakti chandra s state gandhbar posits

Uniform diffusion.

p down as the leader of lady karel shartlov the russian west in one nine nine three and ended soon in gorbachev s farewell to the boy during the dust early spring of one nine nine nine after replacing the chaotic labor strip in one nine nine nine kasparov

shield which was designed by the backcracker see john taylor blind eyed clecks neckble os with the axecoat pins set outside the neckble clerk stand by automatic guards the first background of which was to be extended to the blind sweep strip size mostly a

Binary absorbing diffusion.

one nine six zero s bill oloyd orca yielded the fairly golden fate setting for a soft lonely appearance with artists in the magazine rogue that good even lee hughes continued the living world bennett s back work following both work that pore brad fox and u

its opposite to the clearing sky due to the dumping of a gase found in exceptionally out-standing appendorenses which combines with the atmosphere such as rydberg thermoboat megasi the temples of samuel m sick and manto benzo by martota sick rock george ler

Masked diffusion.

rustor that so works usually in any heat production applications but the same application as at closed fuel internal combustion is also less expensive in reducing fuels usually from flowering applications the result is considered by some to be quite genera

sical elements of nature from traditional christian experience two in their nature and helped indicate the effect of so falled jesus came to be found there and like christ with his unmentioned child and the father with the father and divine breat with you

TinyStories

Binary symmetric diffusion.

Once upon a time, there was a yellow bird. The bird lived in a big tree. The bird had a rag on a high branch. The rag was full of pretty leaves and leaves. The bird liked to play with the rag and the leaves. One day, the bird saw a big, red ball. The bird wanted to play with the ball. But the ball was too big for the bird. The bird was sad and did not want to play with the ball anymore. The bird tried to be brave. It flew down from the tree and got the ball. The bird put the ball on the rag and started to play. Soon, other birds came to play with the yellow bird. They all played together and had fun. The bird was not sad anymore. The bird was happy and made new friends.

Once upon a time, there was a mommy and a little girl. They liked to admire beautiful things like the leaves, watch the birds and play all kinds of games. Today, they decided to create a special use of nature to keep their attention. The mommy pulled out a special bottle from the table. She gave the little girl a glass with water. It was gentle and gentle, and the little girl watched carefully. The little girl looked closely. She watched the birds soar high in the sky and in different ways. It seemed like it was completely so beautiful to fly. The mommy and the little girl watched in amazement. The little girl smiled, and felt so proud. The birds soared away into the sky, and the little girl was filled with amazement of how she had created so special. From that day onwards, the little girl always remembered to always be gentle with her mommy and the magic of nature.

Uniform diffusion.

Once upon a time, there was a little girl named Mia. She lived in a small house with her mom, dad, and dog, Poppy. Mia was very excited to play with Poppy. One day, Mia found a piece of paper. She wanted to fold it and make a fun bridge. So, Mia showed the paper to Poppy and said, “Poppy, let’s make a bridge!” Poppy smiled and wagged her tail. Mia and Poppy folded the paper into many shapes like animals and stars. They made a beautiful flower bridge with paper. Mia and Poppy were so excited about their flower bridge. They played with their flower bridge all day long, having the best time ever together.

Once upon a time, there was a little girl named Sue. Sue loved to play outside with her friends. One day, Sue and her friends were playing in the mud. They were having a great time, but their clothes and feet got dirty. The clothes were dull and not very nice. “I want to change my game,” said Sue. She went inside her house and got her wet clothes. She left them in the sun to dry them off. But the clothes were still dirty and Sue left the wet clothes outside. The sun was hot and the clothes became wet and dirty. Sue’s mom came to the room and saw the dirty clothes. “You have to change into clean clothes now,” said her mom. Sue was sad because she wanted her clothes to be nice. She went back outside to play with her friends and use clean clothes. The day ended badly, and Sue learned that she should listen to her mom next time.

Binary absorbing diffusion.

Once upon a time, there was a grumpy cat named Tom. He lived in a small house with his friend, a little girl named Sue. They liked to play and eat chores. They were very happy together. One day, Sue found a big chain in the yard. She picked it up and showed it to Tom. “Look, Tom! I found a chain!” Sue said. Tom looked at the chain and saw a big door on the other side. It was like a secret door. He liked the chain because it was all by himself! Sue saw Tom looking at the big chain and asked, “What’s wrong, Tom?” Tom said, “I don’t know. It lost my chair.” Sue looked at the chain and saw that it was gone. She said, “Don’t worry, Tom. We will find your chain and eat it together!” So, Tom and Sue looked everywhere for the chair. Finally, they found the chain under the big tree. Tom was so happy! He hugged Sue and said, “Thank you, Sue! You are the best friend ever!” From that day on, Tom wasn’t grumpy anymore. Sue and Tom played together every day, and they always had lots of fun.

Once upon a time, there was a little dog named Spot. Spot liked to play and run in the park. One day, Spot saw a big tree. The tree had a tie all around it. Spot was very happy and so big. Spot went up to the tree and asked, “Can I play with you, tree?” The tree nodded and said, “Yes, Spot, you can play today.” Spot was very excited and started to run and jump. After some time, Spot was tired. He sat under the tree and licked his fur. Spot felt very fine and happy. Spot and the tree became good friends. And they played together in the park every day.

Masked diffusion.

Once upon a time, in a small nation, there lived a cute cat named Lily. Lily had a best friend, a dog named Max. Lily and Max were always happy and liked to play together. One day, they decided that they would scatter pretty flowers all around their town. Lily said to Max, “Let’s make our nation beautiful!” Max thought it was a great idea. They picked many flowers, brought them to their town, and started scattering them everywhere. Soon, the nation was full of colorful leaves, flowers, and big trees. Lily and Max were very proud of what they did. They learned that when they work together and share, they can create more beauty and turn their nation into a magical place. The moral of the story is that sharing with others can make the world a better place.

Once upon a time, there was a little red car. This car loved to drive fast. One day, the car saw a big, distant hill. The car thought, “I want to go to the top of that hill.” The car tried to go up the hill, but it was too hard. The car was sad. It could not drive up the hill. The car said, “I am sad. I want to go to the top of the hill.” Then, the car saw a big truck. The truck said, “Why are you sad, little car?” The car said, “I can’t go up the big hill.” The truck wanted to help. It pushed the car to the top of the hill. The car was very happy. Now the car could drive down the hill. The car went fast and had fun. The car and the truck became good friends. They drove every day. They had lots of fun together. The end.

OpenWebText

Binary symmetric diffusion.

neighborhood neighborhoods. The first houses, in 1926, had mid-size housing shops in San Francisco, California. As San Francisco’s population grew, new houses were built. The new houses were in the Chicago district’s Southwest in the 1920s and 1930s, with housing in many other neighborhoods added. In the 1930s, many of the new homes opened with mid size housing shops, and, by the late 1940s, many of the middle-size housing shops opened with new housing shops in San Francisco. Old, high-end industrial style houses in Gravestone Bay, shadow shops in Black Rock and Blue Browns Creek were added when packed and cut. These homes were found in many of San Francisco’s finest neighborhoods in the 1940s. However, most of these high-end neighborhoods came in locations like Garden Center in the late 1920s. In the twentieth century, residents started in neighborhoods with mid houses, mid-size housing shops, and main housing shops. Some middle-size neighborhoods had mid-size housing shops. Many of these new residents lived in small, mid-size neighborhoods, with high-level houses. By the late 1930s, residents started in housing shops and high-level shops and housing shops. Many of these residents lived in new houses, mostly in low-level neighborhoods, as well as mid-size housing shops. These residents also lived in other neighborhoods with mid-size housing shops, particularly under high-level houses. A few lived in high-level rental houses, high-level housing houses, and even traditional-size housing shops. Most lived in mid-size neighborhoods and other neighborhoods, such as rental houses, rental houses, and high-level homes. Many lived in different residential neighborhoods and some of these neighborhoods had high-level houses, low-level houses, and high-level houses. Many residential neighborhoods also had large houses, particularly in 70-year-old Yellows houses, and some of the large houses and 70-year-old yellows houses all worked in more than one residential neighborhood. Most of them lived in different neighborhoods, such as residential neighborhoods, with the vast majority of these neighborhoods in mid-size houses. Living in all of those neighborhoods, these three were given the equal opportunity to work in that neighborhood. Many of the families that lived in that neighborhood - and the families that lived in that neighborhood - worked in that neighborhood. Many of them worked in that neighborhood, and these ad

2004, the Washington Post reported that the Democratic Party, among Barack Obama’s closest allies, is considered by some to be one of the most viable candidates in history. As the bad news of the war in 2005 was going to be considered a delay in a broader U.S. presidential debate, on Wednesday, the Democratic Party again argued that Barack Obama was a visible candidate and urged national solidarity with the Americans who funded the war. Obama, without an explanation, allowed himself to have asked to withdraw his king from the war, the first large-scale Sunni terrorist attack on the United States. In February 2002, he declared Afghanistan the country of the past. A few months later, when Obama was re-elected by George W. Bush and Bill Clinton, he marveled about Afghanistan and his foreign policy for the United States might have nothing to do with the Taliban. He told him the Taliban reignited Kuwait and that a young President Barack Obama would offer something that gave a good clue. As for politicians, their attitude was absolutely clear: Barack Obama was confused. They looked at the courts, remnants of the war, and the thousands left behind. That America is certainly not America at all was not popular or even frustrating; it was the Taliban and radical Islam, which most certainly waged a war across the country. Barack Obama, his widow, son and uncle focused on the war in Afghanistan; there is little to any evidence that he and the Democratic Party presidency made bold decisions beyond the reach of Obama. And, most importantly, Barack Obama was passionately loyal to broadly established foreign policies and generous economic support from unfortunately marginalized democracies, while promising a very tight war in the world and a real war against other regions. And America’s foreign policy was balanced by its political hegemony. Obama wasn’t ready to test the foreign policy claims of the richest countries.

Instead, he helped protect the economic interests of the mainstream economic elites that accused Obama of being liars, despite the passage of the snowcracker law. Iran declared a genocide in East Asia and killed its head of arms so Barack Obama did so. In fact, the United Nations upped the table after Iranians were killed in a clash with the Islamic State in Iraq at the top of the table. Obama was just as keen as the pundits about cooking it up. When it came to warfare, Washington Post reporter Sean Hannity’s May 2011 message was like this: In an interview, roughly the one time he was present on the war – the African drone, Hannity said: ’If you go to Arkansas, you

Uniform diffusion.

you need guidelines to address problems that many dependent firms still have, as do most other commercial units. You have to keep developers thinking about the situations in which you need them. Business presentations are missing: you have to separate out the readers from the developers. They need help. This is the usual part of one small online thing: compiling readers together means reviewing a post. In order for things to change you have to provide detailed examples of how developers are supposed to be trusted and have perfect levels of trust. And for you to be totally of the mind that this is a legal review process, this will end up being a milestone. First, when it comes to a new business, community, product or business engine, we all need to be willing to take steps. In a sense, “legal reviewing” means taking action to develop the industry (e.g. writing services, crafting download quality structures, and more without reading the literature). Secondly, if you are a part of it, you should be willing to speak for what you asked for. For example, emailing accessible developer advice in the middle of the day will condemn the goals and aims of your team in the first place. It’s the most academic thing to go along with it however you do it. This is the crucial solution to evolve awareness of what happens in the marketplace. Achieving a progressive business plan by publishing to developers is diminishing the value of what needs to be seen in the marketplace through memory and experience. Every effort is competing with demands, and as long as you have the knowledge that money is after any good, you are living with a long, honest and responsible history of your business. Creating something that makes your business function on the first glance is hard to handle, because you are dealing with a long-term power-shift at a time when credibility is going to fade and it is just a matter of staying benchmark and trust. That’s not to say that there aren’t global shifts towards new values. The privatization of the business requires moving many of the newly recalled keys. This brings product costs down by orders of magnitude because financial service platforms like Sunstar are, unfortunately, no longer capable. With Sunstar and intrigued by the quite popularity of software, we see financial services fail to attract a reward. They are always being used with new-recalled keys. This impacts a system of more generous reporting system and a commitment to adding more experience in order to lift it to the next level. This is a serious problem for us in the world of the product. In some product projects the user has had a younger product because of a lack of financial protection for the financial position and isn’t keeping the job though. Because of fear of an old generation, no rational financial resources can afford to accumulate. Because great projects can re-energy capital, they must be protected by a large corpor

ting to the end... “I know this group of winners very well. They have shown special interest in how to win.” They were very emotionally convincing. “I don’t want to die.” (That’s one of the pictures he had written for me. I’m in the full picture.) It wasn’t the best time, so I gather and think, “Want to breathe out here.” Sure enough, the people there were amazing, including business appearances from all the businessmen and a quote from a magazine. “I hope I can learn more,” he says. “The rest of it is something I’m very excited about, but I also feel that the most important lesson is that you should try to take your time and come home happy.” “You don’t worry though,” he says. “You pay yourself.” “It’s a great thing to put something on the balance card for your friends, but it’s not really an honor.” “Any individual who thrives on property must have one of the fastest operating equipment.” “There are no prizes,” he says. “You play hard, and this is no different. I think they need to have some faith in winning. Unfortunately they have not enough.” The next morning at eight, Jacob is standing in the presence of my childhood mentor, Dwayne Cullen, shooting a guest skit. He’s out of the club as soon as I get to it. “I mean, I’m not starving, I’m working, and I’ve got a lot of time. I’m glad that this place is giving me the hope to go,” I tell him, “but how do I get it back?” “I’m glad that this is my place,” he says. “It’s where I want to live.” He just graduated from New York County College. I show my friend he has to go. But then he has to stop him. I tell him that he has a business deal that can be passed on to the lawyer, that he’s looking for a college, and that he’s going to be reluctant to make any money. “Don’t worry about anything. I’m not sure who will pay me,” he says.

“I’d like to have an effective way of owning a shop here, which is another area,” I remind him. “I’m not pro-gay. I’m doing what I can to help. Every 50-mile drive from downtown, there’s a band in the steel car, and I know my band.” He intends to go to those, rather than the lawyer, if he pays his way, and doesn’t feel guaranteed to be coming back in the future. “I hate to say that I’m a businessman, but that I’m an economist. That’s a lot of work,” he says. “The interesting part is that I also have access to schools. There are a lot of schools that are useful. This is a very powerful position for young kids. I have a doctor, and I have friends offer $10,000 for the uses of their services. They are very prominent to me. They have my best friends as well. You go to something like 6 a.m. a Friday morning, and they’re one of the best forms of schools in town in New York, in Brooklyn. And you know what, guess that was just a joke, at one point. Now I can get a slice of my money. It’s a b

Binary absorbing diffusion.

negative conclusions about the risks of climate change or conflicting conclusions about climate change about the relationship between the causes of climate change and rational conclusions about particular risk factors that measure the effect.” Indeed, research argues that this evidence also supports the belief that climate change is essentially a long-term environmental effect, and evidence from sources such as NASA suggest that global warming is mitigated by temperature reductions and that there is a risk that climate change will increase the long-term impact of global climate change by much lower than the negative, but substantial, long-term long-term effects. Not surprisingly, researchers, however, argue that the effects of global climate change can be substantially restricted and provide evidence for the positive effects of climate change. The research was published in Nature. In December, the researchers produced a report from the EPA that demonstrated that the benefits of climate change are notable everywhere. The study showed that the effects often occur in many areas... it is a matter of ideology that climate change is widespread. The researchers also concluded that the notion that carbon dioxide is causing climate change “weighs underlying trends.” “I did previous research to throw at the problem — of having ice caps tapping off with carbon dioxide and climate change far above what I thought was, dating back to the 1980s — based on long-term carbon emissions trends,” according to the researchers. They included three co-authors, Jeff Deaart and co-authors from University of California, Berkeley and University of New York, Brian Boeggen from California and John King, as well as Anita Panetti from Million Climate Science, University of California at Berkeley, University of Chicago and the Tang Center for Climate Research. Studies in response to the challenges presented by the paper appeared online in 2015 on Fort North. All arguments about the relationship between world levels and temperature alongside the negative effects of global warming are false. The paper was published in the journal Climate Change in January 2015. The researchers conducted a review of the paper and reviewed the paper to see whether the analysis even worked it out. They agreed with their final conclusions and stressed that the paper was published on a major environmental issue. They reviewed the paper in 2013, even though it did not produce conflict and agreed to opt for another review. Lab data The research done by Monica Mroinsky and Chor Camillo was inspired by UCS research that seeks to establish the argument that global climate change is affecting long-term

ironmental impacts, including the drought and environmental impacts, that have apparent state and local impacts on public health. Hundreds of thousands of people now live in Los Angeles and much of southern Los Angeles. Environmental impacts include environmental impacts that affect the overall health of mostly suburban residents or of those living in Los Angeles County. Even in California, gas, dap oil, and other chemicals are used by residents of San Diego County on the impact of climate change. For instance, in New York City, biofuels emit more than 100% of the carbon dioxide level in half of California’s residents. Hundreds of thousands of people have reported a variety of environmental impacts. The California State Environmental Protection Act recognizes both water pollution in parts of Los Angeles and environmental impacts in Los Angeles County, as well as at some rates in California. This is also in line with other environmental impacts that have occurred in California. In Texas alone, one water tank was used to help reduce carbon dioxide emissions from coal reserves, a step seen by Hurricane Katrina. California has 69% of normal carbon dioxide emissions from nuclear power plants, and 83 percent of all chemicals made from coal plants are used to store carbon dioxide. More than a third is from gas, and about a third is from New York. In California, a new study is about to be updated, led by Michael Keays, a candidate for Los Angeles Climate Change in California and a professor of public relations at the University of California, San Diego. The residents of Los Angeles County are particularly dismayed by the study in neighboring areas. In Los Angeles, former Assistant U.S. Attorney Michael Brown of the Los Angeles County Department of Public Health Services conducted a new study of environmental impacts in Los Angeles. However, the study did not disclose how much relative harm occurred in suburban areas or neighborhoods impacted by conditions. In Los Angeles, the study also shows that the most important environmental impact impact in certain parts of California is being south of California, not that of southern California. In parts of the county, areas with the largest environmental impacts may play a role in global warming trends. Along with the impacts in areas with the most environmental impacts, more recent city data show that many of the environmental impacts under study could occur elsewhere in Los Angeles County. As a result, the environmental impacts are expected to escalate more widely in parts of California, stretching over mr

Masked diffusion.

vailable more resources in the country, by giving them to the environment. Either those things make sense to the people that competing borders are essential priorities for an economy that is worth much more than just the environmental economy. There are a little more than half million unemployed, 300,000 in Japan who know they can cause all kinds of pain for themselves. To take them off the maternity care, a family of four people who are ultimately afflicted by homelessness, is a hopeless benefit for the middle families and something they will lose to protect their children and families. But the men gone on this promise will make gains wherever they can, get them the jobs where they can, and protect their dignity. Unfortunately, nobody thinks Japan wants to make it any better to begin separating their well-being from their well-being. These people have lost any interest in being exactly hybrid cultures. Small firms in Japan have adopted the notion that independent manufacturing is the main reason to shape insecurity and advertise for valuable resources over the next two and half centuries. Japan applys this idea to an area where wages are poorer for the unskilled workers in rural districts, as well as in a larger economy which has a large workforce and limited scope to shift wealth from the small economy to rural economy, as well as the prospect of greater political and economic prosperity. Tokyo has begun to seize on its environmentalist socialism, in the face of continuing government medical challenge, and has a largely love affair with the automotive industry. An estimated 90 percent of the population of Japan has far more good and profit to provide than it has elsewhere. Today, the government solutions to cheap and cost-cutting business/welfare etc. that encourages the movement of labor has not proven to be suitable for big businesses. And the Fukuram faction of course has diversity and people aren’t clinging to their approval. At the same time, there is a significant distinction between market “property rights” and actual private rights. The market system’s affects people, and to stricture people in this way is too little, in part because people are so desperate to be allowed to have the protection of bigger recipients. These risks are evident in the overarching values of socialization: are we humans based on mutual forces and to beyond the racial fabric of the universe. Ministers are encouraged that there seems nothing left. Rather, they say that they aren’t threatening to humans, which, as Mone highlights, they are real risks and exemptions from Japan. Its permanent “cultural order” will change the way people live. They argue that they prefer to benefit to themselves, they are increasingly concerned that those who did not have rights to what had been ’personal and taxpayers’ land’ will be judged

visit. Frankenstein Night Races The story of the Boxhorns: A.J., who’s on a hard run to return to a normal life. He leaves his brother’s field, and easily recovers his friendship with Lucky Clark. Frankenstein Night is a movie about A.J. looking for a living as a sophomore. A.J. wants to spend money to build a team and believes he’s capable of getting over there in two years. A.J. decides to return to Thailand and finish the season. In the beginning, he had a crazy time, but he doesn’t want to come back. Frankenstein was once a piece of history which, after its time of racing culminates to this day. August Perriles, the best runner from 1984-1988. Another genius TBP-man. Perriles, the greatest fantasy circuit in history, eventually cracks the heart of the 2012 Japanese movie world in a triple scene. The Mega machine gets back delightfully, carving out the longevity of having got a car, and not feeling hungry because the last of the money flows away from the car. He gets busy being silly, with a car that once had his money. With the TBP riddle, he wants to put on a movie that mars the lines of the hot sport racing landscape and the spirit of the circuit. 9. JFR (1984) (worked by Don Beck) Richard Duffy: Distance, 1,727.35 km Weight: 415 lb in length, two cranes, legs: 60,032. After years of drawing and racing racing vehicles on a bus (and Duffy still dreams about sushi) he finally began playing his own game of magic character vehicles from 1983 to 1986. The game expired in the mid 80s and has a unique timeline of 1987. The early 90s’ racing scene saw a lot of fantasy racers return, until the dangerous Japanese headers arrived. Jay-Hirst : Height: 4.21 m Weight: 110 lb in length. A movie about a hoarder built over 100 miles. 10. Stadio Rueville: Miles 1985 to 2000. Before 1984 non-Japanese circuit. A Spanish woman perches up in a warehouse crying in the roadside warehouse, where dramatic dynamic circuitry is so dangerous, the wind sounds them into rags. JFR drops a mythical mountain of creatures watching the bus. JFR decides to begin the one-shot. 1985 Halle: Distance, 29.7 km Weight: L, bike ride: 1.8 meters. Saga is quite something, for what it’s worth, repetitively fun. Jeffrey Carwich, along with Samuel Zeiss, dabbles in being the world’s greatest