Paper deep dive
Twist, Don't Tilt: Trajectory-Exact Constrained Decoding for Masked Diffusion Models
Aditya Thimmaiah, Lara Marinov, Jayanth Srinivasa, Haris Vikalo, Junyi Jessy Li, Milos Gligoric
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Constrained decoding for Masked Diffusion Language Models (MDLMs) aims to ensure that generated outputs satisfy a specified structure or syntax constraint. MDLMs generate outputs by repeatedly unmasking masked positions present in their current state. Recent strategies for constrained decoding constrain the model's per-step mean-field posterior (which factorizes over masked positions) by enforcing the desired constraint with an automaton. The resulting chain-structured factor graph allows exact constrained sampling via dynamic programming. However, despite each draw being exact and constraint-satisfying, we prove that their composition, in general, tilts away from the model's relative probabilities over valid trajectories, thus leading to trajectory bias. We derive an exact expression for this bias as a product of ratios measuring how valid continuation mass changes when the denoiser is reconditioned, and characterize when the bias vanishes. We then correct the bias by introducing TWISTER, the first automaton-twisted Sequential Monte Carlo decoder for MDLMs, using the step-exact decoder as the proposal. We show that for regular language constraints, the Feynman-Kac correction is exactly computable, with the twists obtained efficiently using quantities pre-computed for step-exact sampling. We prove that the resulting Feynman-Kac model targets the unbiased Doob h-transformed path law conditioned on constraint satisfaction.
Tags
Links
- Source: https://arxiv.org/abs/2609.35609v1
- Canonical: https://arxiv.org/abs/2609.35609v1
Trouble viewing inline? Open PDF directly →
Full Text
114,789 characters extracted from source content.
Expand or collapse full text
Twist, Don’t Tilt: Trajectory-Exact Constra- ined Decoding for Masked Diffusion Models Aditya Thimmaiah Lara Marinov Jayanth Srinivasa Affiliation: Cisco Research Haris Vikalo Junyi Jessy Li Milos Gligoric auditt@utexas.edu, marinov@utexas.edu, jasriniv@cisco.com, hvikalo@ece.utexas.edu, jessy@utexas.edu, gligoric@utexas.edu The University of Texas at Austin Abstract Constrained decoding for Masked Diffusion Language Models (MDLMs) aims to ensure that generated outputs satisfy a specified structure or syntax constraint. MDLMs generate outputs by repeatedly unmasking masked positions present in their current state. Recent strategies for constrained decoding constrain the model’s per-step mean-field posterior (which factorizes over masked positions) by enforcing the desired constraint with an automaton. The resulting chain-structured factor graph allows exact constrained sampling via dynamic programming. However, despite each draw being exact and constraint-satisfying, we prove that their composition, in general, tilts away from the model’s relative probabilities over valid trajectories, thus leading to trajectory bias. We derive an exact expression for this bias as a product of ratios measuring how valid continuation mass changes when the denoiser is reconditioned, and characterize when the bias vanishes. We then correct the bias by introducing Twister, the first automaton-twisted Sequential Monte Carlo decoder for MDLMs, using the step-exact decoder as the proposal. We show that for regular language constraints, the Feynman–Kac correction is exactly computable, with the twists obtained efficiently using quantities pre-computed for step-exact sampling. We prove that the resulting Feynman–Kac model targets the unbiased Doob h-transformed path law conditioned on constraint satisfaction. (a) OWT-130M (b) DreamCoder-7B-Inst (c) Dream-7B-Base Figure 1: Trajectory bias in constrained decoding of MDLMs captured by the Total Variation Distance (TVD) between the Doob h-transformed native path law (rejection sampling) and the step-exact automaton-constrained distribution (Dang and Ermon (2026), Twistersmc4 Twister_ smc4 and Twistersmc8 Twister_ smc8) across denoising steps. For "a.*". 1 Introduction Masked Diffusion Language Models (MDLMs) (Sahoo et al., 2024; Nie et al., 2025; Xie et al., 2025; Ye et al., 2025) are increasingly used for generating text, code, and other data, that may require their outputs to adhere to a specified format structure (syntax), e.g., a JSON schema. Unlike autoregressive Large Language Models (LLMs), MDLMs decode by repeatedly denoising a masked input; they first predict mask-free token-categoricals over the masked positions, and then retain only a scheduled subset of these predictions. Therefore, the generation order depends on the sequence of these scheduled subsets of positions and is not a left-to-right prefix like in LLMs. This creates a different kind of constrained decoding problem. Suresh et al. (2025) introduced DINGO, an MDLM algorithm for regular languages, which used maximum a posteriori (MAP) decoding over the chain-structured factorization of the model’s automaton-constrained posterior. While DINGO is mode-seeking, Dang and Ermon (2026) proposed an algorithm for instead sampling (exactly) from the automaton-constrained posterior at each step using Forward-Filtering Backward-Sampling (FFBS) (Carter and Kohn, 1994). We show that sampling locally from the automaton-constrained posterior at each step, although exact, is still biased when composed across steps, thus deviating from the globally constrained distribution. The bias arises because the denoising process only retains a scheduled subset of the sampled tokens and discards the rest when producing the next intermediate state. The resulting clamped-partition sum is the total constraint-valid probability mass obtained by fixing (or clamping) the retained predictions to the successor state and marginalizing the discarded ones under the current-state-conditioned MDLM. At the next step, the same positions (discarded in the previous step) are reevaluated under the successor-state-conditioned MDLM, producing a new local-partition sum. The ratios of the clamped-partition sum to the local-partition sum tilt the resulting path law relative to the globally constrained one, which we model via the Doob h-transform (Doob, 1957) of the native path law, conditioned on constraint-satisfaction. The tilt manifests as trajectory bias. Figure 1 shows the trajectory bias when sampling locally from the automaton-constrained posterior using a step-exact decoder, relative to the native decoder conditioned on constraint satisfaction, for different models. Unlike locally constrained LLM decoding, which ignores future valid mass (Park et al., 2024; Dang et al., 2026), step-exact MDLM decoding accounts for this mass exactly, but under a denoiser frozen at the current state. When these exact local steps are composed, reconditioning the denoiser can change the valid mass and bias the resulting distribution. We correct the bias by introducing Twister, which uses a Feynman–Kac correction with the local and clamped-partition sum ratios as the incremental potentials. The correction requires quantities already computed by FFBS of the step-exact sampler proposed by Dang and Ermon (2026), making it exactly and efficiently computable. 2 Background In this section, we introduce notation used in the rest of the paper, as well as background on MDLMs and twisted Sequential Monte Carlo. We use [N][N] to denote 1,2,…,N\1,2,…,N\, the set of natural numbers up to NN; and ⟦⋅⟧ · to denote the standard indicator function. For two NN-length sequences x and x′x , we write ⟦x≡rx′⟧ _rx if x(i)=x′(i)x(i)=x (i) for every i∈r⊆[N]i∈ r [N]. For bounded products such as ∏t<TΠ _t<T, we always assume t starts from 00. Unnormalized quantities are generally denoted by a tilde, e.g., π~ π. 2.1 Deterministic Finite Automata and Regular Languages A deterministic finite automaton (DFA) over a finite alphabet Σ is a tuple: ≜⟨Σ,,q0,ℱ,δ⟩,A ,Q,q_ 0.7$0$,F,δ , where Q is a finite set of states, q0∈q_ 0.7$0$ is the initial state, ℱ⊆F is the set of accepting states, and δ:×Σ→δ:Q× is the transition function. A word w is accepted by a DFA if the DFA ends in an accepting state after consuming w, i.e., δ∗(q0,)∈ℱδ^*(q_ 0.7$0$, w)\!∈\!F33 3 δ∗δ^* is the DFA’s transition function δ extended from symbols in Σ to words in Σ∗ ^* (Farzan et al., 2022). . Definition 2.1. [Regular Language] The language C recognized by a DFA is the set of all words accepted by it: ≜∈Σ∗∣δ∗(q0,)∈ℱ.C \ w\!∈\! ^*\! \!δ^*(q_ 0.7$0$, w)\!∈\!F\. A language is regular if it is recognized by a DFA. 2.2 Masked Diffusion Language Models MDLMs generate mask-free (or clean) token sequences from partially/fully masked sequences, by repeatedly unmasking the masked positions (Sahoo et al., 2024). Let V be a finite vocabulary of clean tokens, ⊥ be the mask token, and ≜∪⊥X\! \!V∪\ \ the augmented token space. X∈NX\!∈\!X^N denotes a random state (an NN-length token sequence) and x is its realization. The masked positions of x are given by: ℳ(x)≜i∈[N]:x(i)=⊥,M(x)\! \!\i\!∈\![N] (i)\!=\! \, and x(i)x(i) is the i-th token in x. Starting from a masked state X0∈NX_0\!∈\!X^N, an MDLM evolves as a Markov chain X0→X1→⋯→Xt→⋯→XTX_0 _1→·s _t→·s _T over a finite number of denoising steps TT to produce a clean state XT∈NX_T ^N. The transition (Markov) kernels can be constructed from the three main components of MDLMs. For xtx_t with ℳ(xt)≠∅M(x_t)\!≠\! , the denoiser outputs categoricals Cati(⋅∣xt)∈Δ||−1Cat_i(· _t)∈ -1 over i∈ℳ(xt)i (x_t), where Δ||−1 -1 is the (||−1)( \!-\!1)-simplex. The token predictions are conditionally independent given xtx_t, so the denoiser’s posterior factorizes over ℳ(xt)M(x_t). The scheduler retains some of these factors by drawing a reveal set Rt+1=rR_t+1\!=\!r from some policy st+1(⋅∣xt)s_t+1(· _t) such that r⊆ℳ(xt)r (x_t) and is non-empty. The set r is the subset of xtx_t’s masked positions that will be revealed for step t+1t\!+\!1. The policy st+1(⋅∣xt)s_t+1(· _t) can be uniform (Nie et al., 2025), confidence-based (Wu et al., 2026), entropy-based (Ben-Hamu et al., 2025), etc. Lastly, the decoder independently samples from Cati(⋅∣xt)Cat_i(· _t) for i∈ri\!∈\!r, and commits the sampled tokens (retaining xtx_t’s tokens in the remaining positions) to produce the next state xt+1x_t+1. Since denoising is monotone unmasking, we also use ℛ(xt+1,xt)≜ℳ(xt)∖ℳ(xt+1)R(x_t+1,x_t) (x_t) (x_t+1) to denote the revealed set of positions between steps t and t+1t\!+\!1. Definition 2.2. [Native Joint Kernel] Transition from Xt=xtX_t\!=\!x_t to Xt+1=xt+1X_t+1\!=\!x_t+1 and Rt+1=rR_t+1\!=\!r is: κt+1(xt+1,r∣xt)≜st+1(r∣xt)drawn reveal set×⟦xt+1≡¬rxt⟧MDLMs denoise by unmasking×∏i∈rCati(xt+1(i)∣xt)denoiser predictions over masks. _t+1(x_t+1,r _t) drawn reveal set s_t+1(r_t+1 _t) _t+1 _ rx_t Π _i∈ rCat_i(x_t+1(i) _t)s_t+1(r _t)\;×\!\! MDLMs denoise by unmasking s_t+1(r_t+1 _t) _t+1 _ rx_t Π _i∈ rCat_i(x_t+1(i) _t) _t+1 _ rx_t \!\!×\; denoiser predictions over masks s_t+1(r_t+1 _t) _t+1 _ rx_t Π _i∈ rCat_i(x_t+1(i) _t)Π _i∈ rCat_i(x_t+1(i) _t). (1) MDLMs can denoise only by unmasking which necessitates ⟦xt+1≡¬rxt⟧ _t+1 _ rx_t in Definition 2.244 4 We use [N][N] as the universe for set operations of a state’s positions: ¬r≜[N]∖r,¬ℳ(x)≜[N]∖ℳ(x), r\!\! \![N]\! \!r, (x)\! \![N]\! \!M(x), etc. . The native kernel κt+1(xt+1∣xt) _t+1(x_t+1 _t) is obtained by marginalizing out Rt+1R_t+1 from Eq. (1). A denoising trajectory x1:Tx_1:T is then a sequence of states (x1,…,xT)(x_1,…,x_T) derived through repeated applications of the native kernels κt+1 _t+1 on the corresponding intermediate states xtx_t starting from the initial state x0x_0. Definition 2.3. [Native Path Law] The distribution of denoising trajectories conditioned on x0x_0: p1:Tmdlm(x1:T∣x0)≜ℙ(X1=x1,…,XT=xT∣X0=x0)=∏t<Tκt+1(xt+1∣xt).p_1:T 0.5mdlm(x_1:T _0)\; \;P(X_1\!=\!x_1,…,X_T\!=\!x_T _0\!=\!x_0)=Π _t<T _t+1(x_t+1 _t). (2) 2.3 Twisted Sequential Monte Carlo Sequential Monte Carlo (SMC) is used for approximating trajectory distributions as it performs importance corrections incrementally while building the trajectory (Liu, 2004b)55 5 Importance Sampling performs importance corrections only after a trajectory is built (Liu, 2004a).. It approximates them using weighted particles, by propagating, reweighting, and resampling them as trajectories grow. It implements the Feynman–Kac model (Del Moral, 2004). Definition 2.4. [Feynman–Kac Model] A Feynman–Kac model defines an unnormalized trajectory distribution π~0:t π_0:t for t≤Tt\!≤\!T, as a product of proposal kernels MM and non-negative potentials GG: π~0:t(x0:t)≜M0(x0)G0(x0)×∏s<tMs+1(xs+1∣xs)Gs+1(xs,xs+1). π_0:t(x_0:t)\; \;M_0(x_0)\,G_0(x_0)×Π _s<tM_s+1(x_s+1 _s)\,G_s+1(x_s,x_s+1). (3) However, when the target includes only a terminal weight, standard SMC receives no guidance during intermediate steps. Twisted SMC uses twist functions to move this information into incremental potentials, enabling particles to be guided as their trajectories grow (Whiteley and Lee, 2014). Definition 2.5. [Twist-Constructed Potentials] Consider a Markov path distribution P(x0:t)=ν0(x0)∏s<tκs+1(xs+1∣xs)P(x_0:t)\!=\! _0(x_0) _s<t _s+1(x_s+1 _s) and a non-negative terminal weight h. Let η0:T _0:T be twist functions such that ηt>0 _t\!>\!0 for t<Tt\!<\!T and ηT=h _T\!=\!h. Given proposal kernels MM, the potentials are defined as: G0(x0)≜ν0(x0)M0(x0)η0(x0),Gt+1(xt,xt+1)≜κt+1(xt+1∣xt)Mt+1(xt+1∣xt)ηt+1(xt+1)ηt(xt).G_0(x_0) _0(x_0)M_0(x_0) _0(x_0), _t+1(x_t,x_t+1) _t+1(x_t+1 _t)M_t+1(x_t+1 _t) _t+1(x_t+1) _t(x_t). (4) Substituting the potentials from Eq. (4) into Eq. (3) gives π~0:t(x0:t)=P(x0:t)ηt(xt) π_0:t(x_0:t)\!=\!P(x_0:t)\, _t(x_t). Therefore, the model targets P(x0:T)h(xT)P(x_0:T)h(x_T) at TT. The intermediate twists do not alter it, but move its information into the incremental potentials used to guide particles. The ideal twist at xtx_t is the expected terminal weight under the remaining native transitions, i.e., the exact lookahead or continuation probabilities. 3 Step-Exact Does Not Mean Trajectory-Exact Constrained decoding in MDLMs operates along two axes: state positions i∈[N]i\!∈\![N] and denoising steps ≤t<T0\!≤\!t\!<\!T. At denoising step t, a step-exact decoder draws a clean sequence Y∈NY\!∈\!V^N from the denoiser’s automaton-constrained posterior (conditioned on XtX_t) that satisfies the regular language constraint C, i.e., Y∈Y\!∈\!C. Only Y’s positions in the reveal set Rt+1R_t+1 are committed to Xt+1X_t+1, while the remaining are discarded. A draw can therefore be exact at every step without the resulting trajectory X0:TX_0:T following the native path law (Definition 2.3) conditioned on constraint-satisfaction XT∈X_T\!∈\!C. Throughout the paper, we assume: (1) complete reveal ℳ(xT)=∅M(x_T)\!=\! at the terminal denoising step TT; and (2) full support of the denoiser’s predictions Cati(v∣x)>0Cat_i(v )>0 for all v∈v and for all i∈ℳ(x)i (x). We follow Koo et al. (2024) to lift the DFA from symbols in Σ to tokens in the model’s vocabulary V. We now formally characterize the trajectory bias introduced by step-exact decoding. We start by defining the target path law, i.e., the native decoder’s path law conditioned on constraint-satisfaction, using the Doob h-transform (Section 3.1). Next, we derive the transition kernels of the step-exact decoder (Section 3.2), and show that the involved partition sums are lookaheads (valid-continuation probabilities) under a frozen denoiser, and thus step-exact decoding is a frozen Doob transform re-frozen at every step (Section 3.3). Finally, we show that re-freezing is the trajectory bias (Section 3.4). Definition 3.1. [Unbiased Constrained Decoder] For an initial state x0x_0 and constraint C, let Ω(x0) _C(x_0) be the support of native trajectories x1:Tx_1:T satisfying xT∈x_T\!∈\!C. A constrained decoder with path law q1:T(⋅∣x0;)q_1:T(· _0;C) is unbiased if its support is Ω(x0) _C(x_0) and, for every x1:T′,x1:T′∈Ω(x0)x_1:T ,x_1:T \!∈\! _C(x_0), q1:T(x1:T′∣x0;)q1:T(x1:T′∣x0;)=p1:Tmdlm(x1:T′∣x0)p1:Tmdlm(x1:T′∣x0), q_1:T(x_1:T _0;C)q_1:T(x_1:T _0;C)= p_1:T 0.5mdlm(x_1:T _0)p_1:T 0.5mdlm(x_1:T _0), i.e., the constrained decoder does not alter the relative probabilities of constraint-valid trajectories. 3.1 Doob-Transformed Decoder In order to characterize trajectory bias, we first need the path law of a constrained decoder that is conditioned to satisfy C, and is unbiased in the sense of Definition 3.1. The native path law p1:Tmdlm(⋅∣X0)p_1:T 0.5mdlm(· _0) is unconstrained and so does not satisfy C by itself. We obtain the unbiased constrained decoder by terminally conditioning p1:Tmdlm(X1:T∣X0)p_1:T 0.5mdlm(X_1:T _0) on satisfying C, i.e., XT∈X_T\!∈\!C; using the Doob h-transform (Doob, 1957). The Doob h-transform conditions Markov processes to satisfy specific constraints, by tilting their transition kernels towards states compatible with highly-probable constraint-valid continuations that are given by the lookaheads ht(x)≜ℙ(XT∈∣Xt=x)h_t(x)\, \,P(X_T _t=x). Definition 3.2. [Doob Kernel] For the native kernels κt+1 _t+1 (Definition 2.2) and their exact lookahead ht(x),h_t(x), with ht(x)>0h_t(x)\!>\!0 for all x in the support of κt+1 _t+1, their Doob h-transform gives: κt+1★(xt+1∣xt;)≜κt+1(xt+1∣xt)×ht+1(xt+1)ht(xt).κ 0.6$ $_t+1(x_t+1 _t;C)\; \; _t+1(x_t+1 _t)× h_t+1(x_t+1)h_t(x_t). (5) ht(x)≜∑x′∈Nκt+1(x′∣x)ht+1(x′), h_t(x) Σ _x ^N _t+1(x )\;h_t+1(x ), is the exact lookahead of κt+1 _t+1 and hT(x)≜⟦x∈⟧.h_T(x) . Proposition 3.3. [Doob Path Law] The Doob path law is the product of the Doob kernels: p1:T★(x1:T∣x0;)=p1:Tmdlm(x1:T∣x0)×⟦xT∈⟧h0(x0).p_1:T 0.6$ $(x_1:T _0;C)\;\;=\;\;p_1:T 0.5mdlm(x_1:T _0)× _T h_0(x_0). (6) Proof sketch. The product of the Doob kernels κt+1★κ 0.6$ $_t+1 for t<Tt\!<\!T, gives the native path law from Definition 2.3; and the h-ratios telescope to ⟦xT∈⟧/h0(x0) _T /h_0(x_0), thus giving Eq. (6). ∎ Importantly, the Doob path law p1:T★(X1:T∣x0;)p_1:T 0.6$ $(X_1:T _0;C) from Proposition 3.3 is unbiased as it prunes all trajectories with terminal state XT∉X_T , but does so without altering the relative probabilities of the valid trajectories under p1:Tmdlm(X1:T∣x0)p_1:T 0.5mdlm(X_1:T _0). This follows from Eq. (6), where the Doob path law is proportional to p1:Tmdlm(X1:T∣x0)p_1:T 0.5mdlm(X_1:T _0) up to a factor h0(x0)h_0(x_0) which is constant for a fixed initial state x0x_0. The Doob terminal law can be obtained by marginalizing out the intermediate states X1,…,XT−1X_1,…,X_T-1 of p1:T★(X1:T∣x0;)p_1:T 0.6$ $(X_1:T _0;C). Let Z★(x0)≜h0(x0),Z 0.6$ $(x_0) h_0(x_0), then: pT★(y∣x0;)=pTmdlm(XT=y∣x0)×⟦y∈⟧Z★(x0),p_T 0.6$ $(y _0;C)\;\;=\;\;p_T 0.5mdlm(X_T\!=\!y _0)× Z 0.6$ $(x_0), (7) gives the probability that the terminal MDLM output is a clean sequence y, conditioned on the initial state x0x_0 and on the terminal output satisfying the regular language constraint. When Z★(x0)Z 0.6$ $(x_0) is not too small, this distribution can be sampled efficiently using rejection sampling from the native decoder. 3.2 Automaton-Constrained Step-Exact Decoder Unlike the Doob-transformed decoder which conditions the native path law on the final state XTX_T satisfying the constraint C, the step-exact decoder constrains the denoiser’s mean-field posterior at each denoising step to satisfy C and samples it exactly using FFBS (Dang and Ermon, 2026). Since the denoiser’s published categoricals are conditionally independent given a state x, its mean-field posterior μ(⋅∣x)μ(· ) factorizes over all the positions of x (respecting already committed positions) as: μ(Y=y∣X=x)=⟦y≡¬ℳ(x)x⟧×∏i∈ℳ(x)Cati(y(i)∣x).μ(Y\!=\!y \!=\!x)\;\;=\;\; _ (x)x ×Π _i (x)Cat_i(y(i) ). (8) Sampling the mean-field posterior conditioned on a state x gives a clean sequence y∈Ny ^N. This is because we retain x’s tokens for non-masked positions while sampling from the mean-field’s factors for masked positions. However, this clean sequence may not be in the regular language C, i.e., y∉y . Since the next intermediate state is derived from x and y, it may not satisfy the regular constraint either. Therefore, the step-exact decoder constrains the mean-field posterior to satisfy C at each step. Proposition 3.4. [Automaton-Constrained Posterior] Let the DFA =⟨Σ,,q0,ℱ,δ⟩A\!=\! ,Q,q_ 0.7$0$,F,δ recognize C, and Q∈N+1Q\!∈\!Q^N+1 be a random state chain of A, then the automaton-constrained posterior is: μ(Y=y,Q=q∣X=x;)∝μ(y∣x)×ψ(y,q),μ(Y\!=\!y,Q\!=\!q \!=\!x;C)\;\; \;\;μ(y )× _A(y,q), (9) where ψ(y,q) _A(y,q) is the constraint imposed by A and is given by: ψ(y,q)=⟦q(0)=q0⟧×⟦q(N)∈ℱ⟧×∏i∈[N]⟦q(i)=δ(q(i−1),y(i))⟧. _A(y,q)\;\;=\;\; (0)\!=\!q_ 0.7$0$ × (N)\!∈\!F ×Π _i∈[N] (i)=δ(q(i\!-\!1),y(i)) . (10) The automaton-constrained posterior in Proposition 3.4 is a Conditional Random Field (CRF) (Lafferty et al., 2001) with denoiser categoricals as unary potentials and the DFA A’s transition function providing the compatibility factor for the transfer or pairwise potentials. Since A is deterministic, every constraint-satisfying y∈y\!∈\!C corresponds to exactly one DFA state chain for which ψ(y,q)=1 _A(y,q)\!=\!1. Thus, marginalizing out Q gives ∑q∈N+1ψ(y,q)=⟦y∈⟧.Σ _q ^N+1 _A(y,q)\!=\! \!∈\!C . Definition 3.5. [Clamped Partition Sum] For a state x′x reachable from x, i.e., ⟦x′≡¬ℛ(x′,x)x⟧ _ (x ,x)x , the constraint-valid mass of the completions of x′x under the denoiser conditioned on x is: Z(x′;x)≜∑y∈N⟦y∈⟧×⟦y≡¬ℳ(x′)x′⟧×∏i∈ℳ(x′)Cati(y(i)∣x).Z(x ;x)\; \;Σ _y ^N × _ (x )x ×Π _i (x )Cat_i(y(i) ). (11) When x′=xx =x, the clamped partition sum Z(x,x)Z(x;x) is called the local partition sum. The local partition sum Z(x,x)Z(x;x) is the normalizer of the constrained CRF in Proposition 3.4, and scores the constraint-valid probability mass of the masked positions of x with the denoiser conditioned on the same state x, while the clamped partition sum Z(x′,x)Z(x ;x) scores it for the masked positions of x′x , but with the denoiser conditioned on a different state x. Following Dang and Ermon (2026), we use FFBS both to sample exactly from the constrained CRF and to compute the partition sums. Proposition 3.6. [Step-Exact Kernel] For the native kernels κt+1 _t+1 and partition sums Z(x,x)Z(x;x) with Z(x,x)>0Z(x;x)>0 for all x in the support of κt+1 _t+1, the step-exact transition kernel is given by: κt+1(xt+1∣xt;)= κ 0.56\, $A$_t+1(x_t+1 _t;C)\;=\; κt+1(xt+1∣xt)×Z(xt+1,xt)Z(xt,xt). _t+1(x_t+1 _t)× Z(x_t+1;x_t)Z(x_t;x_t). (12) Proof sketch. Substituting the constrained CRF into the native joint kernel factors out κt+1 _t+1 and leaves Z(xt+1,xt)Z(x_t+1;x_t) as the valid-completion sum. Formal proof in Appendix A. ∎ Interestingly, the step-exact kernel in Eq. (12) looks structurally similar to the Doob kernel in Eq. (5), in the sense that both tilt the native kernel κt+1 _t+1 by a ratio of successor to current constraint-valid probability masses, with the partition sums Z of step-exact kernels paralleling the exact lookaheads h of the Doob kernels. We next show that this structural similarity is not a coincidence, but a consequence of the partition sums Z being lookaheads, but of a different Markov chain. 3.3 Partition Sums are Lookaheads of a Frozen Denoiser Markov Chain The exact lookahead hth_t is intractable because the native Markov chain reconditions the denoiser on new states for each step. In contrast, a clamped partition sum Z(xt+1,xt)Z(x_t+1;x_t) scores the valid completions of xt+1x_t+1 by conditioning the denoiser only once, at xtx_t. We characterize their similarity by freezing the denoiser at a reference state x∗x . Then the frozen native joint kernel for xtx_t reachable from x∗x is: κt+1(x∗)(xt+1,rt+1∣xt)≜st+1(rt+1∣xt)×⟦xt+1≡¬rt+1xt⟧×∏i∈rt+1Cati(xt+1(i)∣x∗).κ^(x )_t+1(x_t+1,r_t+1 _t)\; \;s_t+1(r_t+1 _t)× _t+1 _ r_t+1x_t ×Π _i∈ r_t+1Cat_i(x_t+1(i) ). Here, the denoiser’s conditioning is fixed at x∗x instead of the current state xtx_t as in Definition 2.2. The scheduler is still evaluated at xtx_t. The frozen terminal law is independent of the order of unmasking since the predicted categoricals are fixed due to freezing the denoiser, yielding a tractable lookahead. Proposition 3.7. [Frozen Lookahead] The lookahead for the constraint-satisfying terminal law induced by the frozen native kernels, for any state xtx_t reachable from x∗x is: h^t(x∗)(xt)=∑x∈N⟦x≡¬ℳ(xt)xt⟧×⟦x∈⟧×∏i∈ℳ(xt)Cati(x(i)∣x∗). h_t^(x )(x_t)=Σ _x ^N\; _ (x_t)x_t × ×Π _i (x_t)Cat_i(x(i) ). (13) Therefore, h^t(xt)(xt)=Z(xt,xt) h_t^(x_t)(x_t)=Z(x_t;x_t) and h^t+1(xt)(xt+1)=Z(xt+1,xt) h_t+1^(x_t)(x_t+1)=Z(x_t+1;x_t). Proof sketch. Monotone unmasking and posterior sampling are independent of the scheduler, giving Eq. (13). The two identities follow from Eq. (11) for x∗=xtx \!=\!x_t. Formal proof in Appendix B. ∎ From Proposition 3.7, both partition sums in Eq. (12) are thus lookaheads of the Markov chain frozen at the current state, which agrees with the native chain on the first transition, i.e., when x∗=xtx \!=\!x_t. Proposition 3.8. [Re-Frozen Doob Transforms] Each step-exact kernel is the exact Doob transform of the frozen native kernels at its current state xtx_t: κt+1(xt+1∣xt;)=κt+1(xt+1∣xt)×h^t+1(xt)(xt+1)h^t(xt)(xt).κ 0.56\, $A$_t+1(x_t+1 _t;C)\;=\; _t+1(x_t+1 _t)× h_t+1^(x_t)(x_t+1) h_t^(x_t)(x_t). Proposition 3.8 applies to the chain frozen at the current state. At the next step, however, the denoiser is re-frozen at the new state, replacing the expected successor h^t+1(xt)(xt+1) h_t+1^(x_t)(x_t+1) with h^t+1(xt+1)(xt+1) h_t+1^(x_t+1)(x_t+1). It is this re-freezing that prevents the composition of the step-exact kernels from being the Doob transform of a single Markov chain. Since the partition sums are computed at each step, an intermediate state xt+1x_t+1 is thus scored twice, by Z(xt+1,xt)Z(x_t+1;x_t) as a successor (e.g., 2 in Figure 2(c)) and by Z(xt+1,xt+1)Z(x_t+1;x_t+1) as the current state (e.g., 3 in Figure 2(c)) at step t+1t\!+\!1. We next show how this causes trajectory bias. 3.4 Trajectory Bias =a∗b+C=a^*b^+q0q_0q1q_1q∅q_ aabbbbaaa,ba,b (a) DFA for C. x0x_0⊥ ⊥ ()q (0)q()q (1)q()q (2)q()q (3)Y1Y_1Y2Y_2Y3Y_3aabb1aabbaabb (b) Automaton-constrained posterior. x1ax_1^a⊥ 0.50.5aabbaabbscoredunder x0x_02x1ax_1^a⊥ 0.90.9aabbaabbrescoredunder x1ax_1^a3 (c) Successor x1ax_1^a rescoring at t=0t\!=\!0 and 11. Figure 2: A three-token example of trajectory bias. Let =a,bV\!=\!\a,b\, =a∗b+C\!=\!a^*b^+, T=2T\!=\!2, and x0=(⊥,⊥,b)x_0\!=\!( , ,b), with position 22 revealed before position 11. Revealing a gives x1a=(⊥,a,b)x_1^a\!=\!( ,a,b), with aabaab as its only valid completion under C, while revealing b gives x1b=(⊥,b,b)x_1^b\!=\!( ,b,b), whose completions are both valid. Assuming uniform categoricals at x0x_0 (1), Z(x1a,x0)=0.5Z(x_1^a;x_0)\!=\!0.5 (2) and Z(x1b,x0)=1Z(x_1^b;x_0)\!=\!1, so the step-exact decoder chooses x1ax_1^a with probability 0.5/(+1)=1/30.5/(0.5\!+\!1)\!=\!1/3. After committing x1ax_1^a, the denoiser rescores position 11 as Cat1(a∣x1a)=0.9Cat_1(a _1^a)\!=\!0.9 (3), so x1ax_1^a’s actual valid mass is Z(x1a,x1a)=0.9Z(x_1^a;x_1^a)\!=\!0.9; which is what the Doob path law uses to choose x1ax_1^a, h1(x1a)=0.9h_1(x_1^a)\!=\!0.9, i.e., with probability 0.9/(+1)=9/190.9/(0.9\!+\!1)\!=\!9/19. But step-exact decoding only renormalizes by Z(x1a,x1a)Z(x_1^a;x_1^a) in the next step, thus never correcting Z(x1a,x0)Z(x_1^a;x_0). Since aabaab is the only valid completion of x1ax_1^a, p1:2((x1a,aab)∣x0;)=1/3p_1:2 0.56\, $A$((x_1^a,aab) _0;C)\!=\!1/3 but p1:2★((x1a,aab)∣x0;)=9/19p_1:2 0.6$ $((x_1^a,aab) _0;C)\!=\!9/19, due to the per-step mismatch Z(x1a,x0)/Z(x1a,x1a)=5/9Z(x_1^a;x_0)/Z(x_1^a;x_1^a)\!=\!5/9 in Eq. (14). We identify the tilt of the path law induced by composing the step-exact kernels, relative to the Doob path law, by multiplying them along a trajectory, yielding the native path law and the tilt factor: ∏t<TZ(xt+1,xt)Z(xt,xt)=[ Z(x1,x0) Z(x0,x0)× Z(x2,x1) Z(x1,x1) × Z(x3,x2) Z(x2,x2) × ⋯ ×Z(xT,xT−1) Z(xT−1,xT−1) ]Π _t<T Z(x_t+1;x_t)Z(x_t;x_t)\;\,=\;\, [ 1.5pt$ to40.4pt to11.6pt 20.19998pt -3.3pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-18.89998pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -26.15 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to40.4pt to11.6pt 20.19998pt -3.3pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-18.89998pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -26.15 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to33.52pt to8.6pt 16.7612pt -2.55pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-15.4612pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -21.39 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to28.89pt to6.85pt 14.44444pt -2.29997pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-13.14444pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -18.19 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope $ -1.5pt$ (x_0;x_0)$× 1.5pt$ to40.4pt to11.6pt 20.19998pt -3.3pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-18.89998pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -26.15 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to40.4pt to11.6pt 20.19998pt -3.3pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-18.89998pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -26.15 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to33.52pt to8.6pt 16.7612pt -2.55pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-15.4612pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -21.39 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to28.89pt to6.85pt 14.44444pt -2.29997pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-13.14444pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -18.19 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope $ -1.5pt$ to40.4pt to11.6pt 20.19998pt -3.3pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-18.89998pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -26.15 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to40.4pt to11.6pt 20.19998pt -3.3pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-18.89998pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -26.15 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to33.52pt to8.6pt 16.7612pt -2.55pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-15.4612pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -21.39 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to28.89pt to6.85pt 14.44444pt -2.29997pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-13.14444pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -18.19 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope $× 1.5pt$ to40.4pt to11.6pt 20.19998pt -3.3pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-18.89998pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -26.15 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to40.4pt to11.6pt 20.19998pt -3.3pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-18.89998pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -26.15 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to33.52pt to8.6pt 16.7612pt -2.55pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-15.4612pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -21.39 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to28.89pt to6.85pt 14.44444pt -2.29997pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-13.14444pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -18.19 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope $ -1.5pt$ to40.4pt to11.6pt 20.19998pt -3.3pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-18.89998pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -26.15 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to40.4pt to11.6pt 20.19998pt -3.3pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-18.89998pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -26.15 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to33.52pt to8.6pt 16.7612pt -2.55pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-15.4612pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -21.39 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to28.89pt to6.85pt 14.44444pt -2.29997pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-13.14444pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -18.19 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope $× to7.5pt to9pt 3.75pt -2.0pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-3.75pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -5.19 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to7.5pt to9pt 3.75pt -2.0pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-3.75pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -5.19 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to5.25pt to6.3pt 2.625pt -1.4pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-2.625pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -3.63 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to3.75pt to4.5pt 1.875pt -1.0pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-1.875pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -2.59 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope × 1.5pt$ [rgb]0,0.4688,0.3516Z(x_T;x_T-1)$ -1.5pt$ to57.52pt to11.6pt 28.76117pt -3.3pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-27.46117pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -38 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to57.52pt to11.6pt 28.76117pt -3.3pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-27.46117pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -38 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to45.4pt to8.6pt 22.70009pt -2.55pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-21.40009pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -29.61 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to40.77pt to7.04pt 20.38333pt -2.49443pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces @begingroup@_scopebegin=1 @closescope to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-19.08333pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -26.41 0) @hbox65 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope $ ] The tilt factor is a product of ratios of partition sums. Since all positions are revealed at TT, Eq. (11) gives Z(xT;xT−1)=⟦xT∈⟧ [rgb]0,0.4688,0.3516Z(x_T;x_T-1)\!=\! _T\!∈\!C , the Doob terminal weight of Eq. (6). Each highlighted pair holds the two scores of an intermediate state xtx_t, scored as a successor Z(xt,xt−1) [rgb]0,0.3281,0.5781Z(x_t;x_t-1) and as the current state Z(xt,xt) [rgb]0.6484,0.1094,0.1875Z(x_t;x_t). We call the ratio Z(xt,xt)/Z(xt,xt−1)Z(x_t;x_t)/Z(x_t;x_t-1) the re-freezing ratio of xtx_t. It measures how re-freezing changes the valid mass estimate of xtx_t’s completions. If it is greater than 1, then the valid mass of xtx_t was underestimated, so paths through xtx_t are under-weighted (and vice versa if less than 1): Proposition 3.9. [Re-Freezing Tilt] The step-exact decoder samples the Doob path law tilted by the inverse re-freezing ratios of its intermediate states (for trajectories in common support): p1:T(x1:T∣x0;)= p_1:T 0.56\, $A$(x_1:T _0;C)=\; p1:T★(x1:T∣x0;)×Z★(x0)Z(x0,x0)×∏t=1T−1Z(xt,xt−1)Z(xt,xt). p_1:T 0.6$ $(x_1:T _0;C)× Z 0.6$ $(x_0)Z(x_0;x_0)×Π _t=1^T-1 Z(x_t;x_t-1)Z(x_t;x_t). (14) Proof sketch. Substitute the step-exact and Doob kernels into the ratio of their path laws. ∎ Since Z★(x0)/Z(x0,x0)Z 0.6$ $(x_0)/Z(x_0;x_0) is constant, the two path laws align if every re-freezing ratio equals 11, i.e., Z(xt,xt−1)=Z(xt,xt),for every <t<T. [rgb]0,0.3281,0.5781Z(x_t;x_t-1)= [rgb]0.6484,0.1094,0.1875Z(x_t;x_t), every \;0\!<\!t\!<\!T. However, this generally does not hold, since unmasking tokens changes the denoiser’s predictions for ℳ(xt)M(x_t), and this is structural to the working of MDLMs itself. Trajectory bias thus manifests due to scoring the same positions under two differently conditioned denoisers. Corollary 3.10 gives the exact condition, which only requires the product of ratios to be constant. Corollary 3.10. [Trajectory Exactness] The step-exact decoder is unbiased (Definition 3.1) if and only if the product of re-freezing ratios is constant over Ω(x0) _C(x_0), i.e., for every x1:T∈Ω(x0)x_1:T∈ _C(x_0): ∏t=1T−1Z(xt,xt)Z(xt,xt−1)=Z★(x0)Z(x0,x0).Π _t=1^T-1 Z(x_t;x_t)Z(x_t;x_t-1)\;=\; Z 0.6$ $(x_0)Z(x_0;x_0). (15) Corollary 3.11. [No Bias for Vacuous Constraints] For a vacuous regular constraint =NC\!=\!V^N (does not impose any restrictions), Eq. (16) holds for every t<Tt\!<\!T, and there is no trajectory bias. Proof. Formal proof is in Appendix C.2. ∎ Corollary 3.12. [No Bias for One-Step Reveal All] When all masked positions in every initial state x0x_0 are revealed in a single step, i.e., T=1T\!=\!1, Eq. (16) holds and there is no trajectory bias. Proof. Formal proof is in Appendix C.3. ∎ The trajectory bias introduced by the tilt is correctable because: (1) the tilt factorizes over the steps as shown in Eq. (14) allowing it to be corrected incrementally at each step; and (2) a re-freezing ratio can be computed efficiently and exactly at its step t−1t\!-\!1 when xtx_t is reached by computing the clamped partition sum Z(xt,xt−1)Z(x_t;x_t-1) from the FFBS messages that sampled xtx_t, and the next step’s local partition sum Z(xt,xt)Z(x_t;x_t) from the denoiser query at xtx_t that is needed at the next step t anyway. 4 Twister: Automaton-Twisted Sequential Monte Carlo Since the re-freezing tilt factorizes over steps (Proposition 3.9), it can be corrected incrementally at each step. We first show mathematically that the tilt can be corrected via our proposed Feynman–Kac corrector, and then we describe our Twister algorithm implementing it. 4.1 Feynman–Kac Corrector for the Re-Freezing Tilt We use the tractable step-exact kernels from Proposition 3.8 as the proposals: Mt+1(xt+1∣xt)≜κt+1(xt+1∣xt;)M_t+1(x_t+1 _t)\! \!κ 0.56\, $A$_t+1(x_t+1 _t;C), and correct for the re-freezing ratio formalized in Section 3.4 with an exact twist. Definition 4.1. [Feynman–Kac Twist] The Feynman–Kac twist is given by: ηt(x)≜Z(x,x),t<T,⟦x∈⟧,t=T _t(x)\; \; casesZ(x;x),&t<T,\\ ,&t=T cases The ideal twist is the exact lookahead ht(x)h_t(x) from Definition 3.2, which requires future denoiser calls and is thus intractable. The local partition sum Z(x,x)Z(x;x) is the frozen lookahead h^t(x)(x) h_t^(x)(x) from Proposition 3.7, i.e., a tractable surrogate of ht(x)h_t(x) from a single denoiser call at x at step t. From Definition 4.1, the Feynman–Kac twists are just the local partition sums at each step, thus they are exactly computable using the same FFBS already used for sampling the proposals Mt+1M_t+1. The potentials Gt+1G_t+1 of the Feynman–Kac model can then be constructed from the twists by Eq. (4) as: G0(x0)=Z(x0,x0),Gt+1(xt,xt+1)=κt+1(xt+1∣xt)Mt+1(xt+1∣xt)×ηt+1(xt+1)ηt(xt)=Z(xt+1,xt+1)Z(xt+1,xt),G_0(x_0)=Z(x_0;x_0), _t+1(x_t,x_t+1)= _t+1(x_t+1 _t)M_t+1(x_t+1 _t)× _t+1(x_t+1) _t(x_t)\,=\, Z(x_t+1;x_t+1)Z(x_t+1;x_t), i.e., the re-freezing ratio of xt+1x_t+1, for t<(T−1)t\!<\!(T\!-\!1), and GT=1G_T\!=\!1 since Z(xT;xT−1)=⟦xT∈⟧Z(x_T;x_T-1)= _T . Theorem 4.2. [Twist Fixes the Tilt] The Feynman–Kac twists correct the re-freezing tilt (Proposition 3.9), thus making the Feynman–Kac model target the Doob path law: G0(x0)∏t<TMt+1(xt+1∣xt)Gt+1(xt,xt+1)=p1:T★(x1:T∣x0;)Z★(x0)G_0(x_0)Π _t<TM_t+1(x_t+1 _t)\;G_t+1(x_t,x_t+1)\;\;=\;\;p_1:T 0.6$ $(x_1:T _0;C)\;Z 0.6$ $(x_0) Proof sketch. Substitute for Mt+1M_t+1 and Gt+1G_t+1 in Definition 2.4. Formal proof in Appendix D. ∎ In Figure 2, weighting x1ax_1^a by its re-freezing ratio 9/59/5 turns the step-exact choice 1/:2/31/3\!:\!2/3 into the Doob choice 9/:10/199/19\!:\!10/19. 4.2 Twister Algorithm Algorithm 1 Twister for step-exact decoding (adaptive resampling shown in Appendix E). 1: DFA A recognizing C; initial state x0x_0; number of denoising steps TT; number of SMC particles KK 2: Query denoiser at x0x_0; 3: (x0k,W0k)←(x0,1/K)(x_0^k,W_0^k)←(x_0,1/K) for all k∈[K]k∈[K] 4: for t=0,…,T−1t=0,…,T\!-\!1 do 5: STEP-EXACT FFBS PROPAGATE 6: parallel for k=1,…,Kk=1,…,K do 7: Sample xt+1k∼Mt+1(⋅∣xtk)x_t+1^k _t+1(· _t^k) ⊳ use cached FFBS messages 8: Z^t+1k←Z(xt+1k,xtk) Z_t+1^k (x_t+1^k;x_t^k) ⊳ predecessor clamped-partition sum 9: if t<T−1t<T\!-\!1 then 10: Query denoiser at xt+1kx_t+1^k; Zt+1k←Z(xt+1k,xt+1k)Z_t+1^k (x_t+1^k;x_t+1^k) ⊳ successor partition, cache FFBS messages 11: else 12: ZTk←⟦xTk∈⟧Z_T^k← _T^k 13: RE-FREEZING CORRECTION 14: parallel for k=1,…,Kk=1,…,K do 15: Gt+1k←Zt+1k/Z^t+1kG_t+1^k←Z_t+1^k/ Z_t+1^k 16: W~t+1k←WtkGt+1k W_t+1^k _t^kG_t+1^k 17: Wt+1k←W~t+1k/∑k′=1KW~t+1k′W_t+1^k← W_t+1^k/ _k =1^K W_t+1^k for all k∈[K]k∈[K] 18: return (xT1:K,WT1:K)(x_T^1:K,W_T^1:K) Algorithm 1 captures Twister’s working. It requires a DFA A (lifted to the model’s vocabulary V) that recognizes the regular language C; an initial state x0x_0, i.e., a token block containing the prompt and masked tokens; the number of denoising steps TT; and the number of SMC particles KK. Twister starts by querying the denoiser at x0x_0, and caching its FFBS messages. Following this, it initializes all KK SMC particles to x0x_0 with weight 1/K1/K. The cached FFBS messages are used to sample from the Feynman–Kac proposal Mt+1M_t+1 (Proposition 3.8), and compute the predecessor clamped-partition sum Z^t+1k Z_t+1^k. For each propagated nonterminal particle, the denoiser is queried at the successor state to compute the successor partition sum Zt+1kZ_t+1^k and cache the FFBS messages for the next step. The ratio Gt+1k=Zt+1k/Z^t+1kG_t+1^k=Z_t+1^k/ Z_t+1^k gives the exact Feynman–Kac potential required for fixing the re-freezing tilt (Section 4.1). Each incoming particle weight is multiplied by this potential, and the resulting weights are normalized. Particles are jointly resampled with their caches and assigned uniform weight when resampling is triggered (described in Appendix E). Complexity. One weighted-automaton pass costs (N||||)O(N ), and so, the total automaton cost for KK SMC particles and TT denoising steps is (||||)O(KTN ), in addition to the denoiser evaluations. Twister is parallelizable over the step-exact FFBS propagate and re-freezing correction phases, since the particles are conditionally independent until weight normalization and resampling. 4.3 Trajectory Bias Experiment We measure trajectory bias using regular language constraints defined over token classes. The number of token classes is an experiment configured parameter. Next, we rank the tokens by the probabilities assigned to them by the model conditioned on a fully masked input. We select the most probable tokens and then partition them equally across the token classes. Tokens outside this pool are assigned to the token class x. A model’s generation can then be projected onto a small alphabet of symbols, i.e., token classes a,b,c,d,x\a,b,c,d,x\, etc.. We use such token classes to build regular expressions which are then used to constrain the model’s generation. We permute the token classes to ensure that the results do not depend on a particular token-to-class mapping. Trajectory bias is then measured by using either Dang and Ermon (2026), Twistersmc4 Twister_ smc4, or Twistersmc8 Twister_ smc8 to sample from the automaton-constrained distribution subject to the regular expression; relative to the native decoder conditioned on constraint satisfaction approximated using rejection sampling (Eq. (7)). We use pairwise total variation distance to measure the similarity between the two distributions. We also compare independent splits of the rejection samples to estimate the finite-sample noise floor. Results are averaged with equal weight across partition configurations. Thus, deviations above the rejection noise floor measure trajectory bias rather than token-level validity or Monte Carlo error. For each model and T∈1,2,4,8,16T∈\1,2,4,8,16\ denoising steps, we generate 40,000 native samples and 10,000 constrained samples at temperature 11 under random remasking. The one-step reveal for T=1T=1 is an experimental setting of Corollary 3.12. We evaluate on the models Dream-7B-Base, Dream-7B-Inst, DreamCoder-7B-Inst, LLaDA-8B-Base, LLaDA-8B-Inst, and OWT-130M. 5 Related Work Constrained Decoding for Autoregressive Models. Most recent approaches consist of maintaining a parser or automaton over the generated prefix and masking out invalid next tokens at each step (Willard and Louf, 2023; Koo et al., 2024; Beurer-Kellner et al., 2024; Geng et al., 2023; Ugare et al., 2024; Dong et al., 2025). While this guarantees constraint satisfaction by construction, Park et al. (2024) showed that such locally constrained decoding distorts the model’s distribution over valid sequences. To address this, Loula et al. (2025) approximate the globally constrained posterior with SMC, combining locally constrained decoding with incremental reweighting and resampling to correct the resulting bias. Dang et al. (2026) further improve this setup by constructing stronger automaton-based proposals that encode future constraint satisfaction, yielding faster SMC convergence with fewer particles. Like these approaches, we use SMC to target the model’s globally constrained distribution rather than local constraint enforcement alone, but we focus on the less-explored domain of constrained decoding for MDLMs. Unlike locally constrained LLM decoding, which ignores future valid mass, step-exact MDLM decoding accounts for this mass exactly, but under a denoiser frozen at the current state. Constrained Decoding for Diffusion Models. Suresh et al. (2025) proposed DINGO as the first constrained decoder for MDLMs with formal guarantees. DINGO uses dynamic programming over automaton states to select a constraint-satisfying block that maximizes the per-step mean-field probability. Dang and Ermon (2026) further generalize DINGO’s approach by replacing per-step MAP with exact sampling from the automaton-constrained mean-field posterior at each denoising step. Like DINGO, their method guarantees that the constraint is satisfied by construction, but it further supports stochastic sampling under arbitrary remasking schedules. Crucially, both the DINGO and Dang and Ermon (2026) still constrain generation only at individual steps. We show that such local exactness does not, however, preserve the model’s relative probabilities over valid multi-step denoising trajectories. We address this gap by introducing Twister as the first automaton-twisted SMC constrained decoder for MDLMs that targets the trajectory-exact globally constrained path law. Hasan et al. (2025) apply Feynman–Kac SMC correctors to steer discrete diffusion sampling at inference time through temperature scaling or an external reward. Luo et al. (2026) likewise use SMC for MDLMs, but reweight particles by trajectory-level confidence to improve sample quality. In contrast, Twister uses SMC to enforce formal constraints. 6 Conclusion We showed that sampling locally from an MDLM’s automaton-constrained posterior, despite being exact at each denoising step, still tilts the distribution relative to the globally constrained distribution when composed across steps. We derived this trajectory bias as a product of local and clamped-partition sum ratios, which are a consequence of rescoring the constraint-valid completions of the same intermediate states, but under different denoiser conditionings. We showed that the tilt factorizes across the denoising steps, and thus can be corrected incrementally at each step. We then introduced Twister, an automaton-twisted SMC constrained decoder that corrects this tilt by using the step-exact decoder as its proposal. Further, for regular-language constraints, its incremental Feynman–Kac potentials are exactly computable from partition sums already obtained during step-exact sampling. AI use statement We have not used generative AI tools for this work. Reproducibility statement Our code and data will be made publicly available upon acceptance of the paper. References Ben-Hamu et al. (2025) H. Ben-Hamu, I. Gat, D. Severo, N. Nolte, and B. Karrer Accelerated sampling from masked diffusion models via entropy bounded unmasking. In NeurIPS, External Links: Document Cited by: §2.2. Beurer-Kellner et al. (2024) L. Beurer-Kellner, M. Fischer, and M. Vechev Guiding LLMs the right way: fast, non-invasive constrained generation. In ICML, External Links: Document Cited by: §5. Carter and Kohn (1994) C. K. Carter and R. Kohn On Gibbs sampling for state space models. Biometrika 81 (3), p. 541–553. External Links: Document Cited by: Appendix F, §1. Dang and Ermon (2026) M. Dang and S. Ermon Constrained decoding for diffusion language models via efficient inference over finite automata. arXiv preprint arXiv:2607.07026. External Links: 2607.07026, Document Cited by: Table 1, Table 1, Table 1, Table 1, Table 1, Table 1, Appendix F, Appendix F, Figure 1, §1, §1, §3.2, §3.2, §4.3, §5. Dang et al. (2026) M. Dang, L. Song, H. Zhang, J. Zhao, G. V. den Broeck, and S. Ermon Mitigating bias in locally constrained decoding via tractable proposals. In ICML, External Links: Document Cited by: §1, §5. Del Moral (2004) P. Del Moral Feynman-Kac formulae. In Feynman-Kac Formulae: Genealogical and Interacting Particle Systems with Applications, p. 47–93. External Links: ISBN 978-1-4684-9393-1, Document Cited by: §2.3. Dong et al. (2025) Y. Dong, C. F. Ruan, Y. Cai, R. Lai, Z. Xu, Y. Zhao, and T. Chen XGrammar: flexible and efficient structured generation engine for large language models. In MLSys, External Links: Document Cited by: §5. Doob (1957) J. L. Doob Conditional brownian motion and the boundary limits of harmonic functions. Bulletin de la Société mathématique de France 85, p. 431–458. External Links: Document Cited by: §1, §3.1. Farzan et al. (2022) A. Farzan, D. Klumpp, and A. Podelski Sound sequentialization for concurrent program verification. In PLDI, p. 506–521. External Links: Document Cited by: footnote 3. Geng et al. (2023) S. Geng, M. Josifoski, M. Peyrard, and R. West Grammar-constrained decoding for structured NLP tasks without finetuning. In EMNLP, Cited by: §5. Hasan et al. (2025) M. Hasan, M. Skreta, A. Aspuru-Guzik, Y. Bengio, and K. Neklyudov Discrete Feynman-Kac correctors. In AI4Math@ICML, External Links: Document Cited by: §5. Koo et al. (2024) T. Koo, F. Liu, and L. He Automata-based constraints for language model decoding. In COLM, External Links: Document Cited by: §3, §5. Lafferty et al. (2001) J. D. Lafferty, A. McCallum, and F. C. N. Pereira Conditional random fields: probabilistic models for segmenting and labeling sequence data. In ICML, p. 282–289. Cited by: §3.2. Liu (2004a) J. S. Liu Basic principles: rejection, weighting, and others. In Monte Carlo Strategies in Scientific Computing, p. 23–52. External Links: ISBN 978-0-387-76371-2, Document Cited by: footnote 5. Liu (2004b) J. S. Liu Theory of sequential Monte Carlo. In Monte Carlo Strategies in Scientific Computing, p. 53–77. External Links: ISBN 978-0-387-76371-2, Document Cited by: §2.3. Loula et al. (2025) J. Loula, B. LeBrun, L. Du, B. Lipkin, C. Pasti, G. Grand, T. Liu, Y. Emara, M. Freedman, J. Eisner, R. Cotterell, V. Mansinghka, A. K. Lew, T. Vieira, and T. J. O’Donnell Syntactic and semantic control of large language models via sequential Monte Carlo. In ICLR, External Links: Document Cited by: §5. Luo et al. (2026) Z. Luo, Z. Jin, L. Wang, L. Bing, and T. B. Schön Self-rewarding sequential Monte Carlo for masked diffusion language models. arXiv preprint arXiv:2602.01849. External Links: Document Cited by: §5. Nie et al. (2025) S. Nie, F. Zhu, Z. You, X. Zhang, J. Ou, J. Hu, J. Zhou, Y. Lin, J. Wen, and C. Li Large language diffusion models. In NeurIPS, External Links: Document Cited by: Appendix F, §1, §2.2. NousResearch (2024) NousResearch Json-mode-eval. Hugging Face. Note: https://huggingface.co/datasets/NousResearch/json-mode-eval Cited by: Appendix F. Park et al. (2024) K. Park, J. Wang, T. Berg-Kirkpatrick, N. Polikarpova, and L. D’Antoni Grammar-aligned decoding. In NeurIPS, External Links: Document Cited by: §1, §5. Sahoo et al. (2024) S. S. Sahoo, M. Arriola, A. Gokaslan, E. M. Marroquin, A. M. Rush, Y. Schiff, J. T. Chiu, and V. Kuleshov Simple and effective masked diffusion language models. In NeurIPS, External Links: Document Cited by: §1, §2.2. Suresh et al. (2025) T. Suresh, D. Banerjee, S. Ugare, S. Misailovic, and G. Singh DINGO: constrained inference for diffusion LLMs. In NeurIPS, External Links: Document Cited by: Appendix F, §1, §5. Ugare et al. (2024) S. Ugare, T. Suresh, H. Kang, S. Misailovic, and G. Singh SynCode: LLM generation with grammar augmentation. TMLR. External Links: Document Cited by: §5. Whiteley and Lee (2014) N. Whiteley and A. Lee Twisted particle filters. The Annals of Statistics 42 (1), p. 115–141. External Links: Document Cited by: §2.3. Willard and Louf (2023) B. T. Willard and R. Louf Efficient guided generation for large language models. arXiv preprint arXiv:2307.09702. External Links: Document Cited by: Appendix F, §5. Wu et al. (2026) C. Wu, H. Zhang, S. Xue, Z. Liu, S. Diao, L. Zhu, P. Luo, S. Han, and E. Xie Fast-dLLM: training-free acceleration of diffusion LLM by enabling KV cache and parallel decoding. In ICLR, External Links: Document Cited by: §2.2. Xie et al. (2025) Z. Xie, J. Ye, L. Zheng, J. Gao, J. Dong, Z. Wu, X. Zhao, S. Gong, X. Jiang, Z. Li, et al. Dream-coder 7B: an open diffusion language model for code. arXiv preprint arXiv:2509.01142. External Links: Document Cited by: Appendix F, §1. Ye et al. (2025) J. Ye, Z. Xie, L. Zheng, J. Gao, Z. Wu, X. Jiang, Z. Li, and L. Kong Dream 7B: diffusion large language models. arXiv preprint arXiv:2508.15487. External Links: Document Cited by: Appendix F, §1. Appendix Contents Appendix A Proof for Step-Exact Kernel Proposition 3.6. [Step-Exact Kernel] For the native kernels κt+1 _t+1 and partition sums Z(x,x)Z(x;x) with Z(x,x)>0Z(x;x)>0 for all x in the support of κt+1 _t+1, the step-exact transition kernel is given by: κt+1(xt+1∣xt;)= κ 0.56\, $A$_t+1(x_t+1 _t;C)\;=\; κt+1(xt+1∣xt)×Z(xt+1,xt)Z(xt,xt). _t+1(x_t+1 _t)× Z(x_t+1;x_t)Z(x_t;x_t). Proof. The joint step-exact kernel κt+1(x′,r∣xt;)κ 0.56\, $A$_t+1(x ,r _t;C) is given by: =st+1(r∣xt)⟦x′≡¬rxt⟧×∑y,qμ(y,q∣xt;)⟦x′≡ry⟧ =\;s_t+1(r _t)\; _ rx_t \;×\;Σ _y,q\;μ(y,q _t;C)\; _ry =st+1(r∣xt)⟦x′≡¬rxt⟧Z(xt,xt)×∑y,qμ(y∣xt)ψ(y,q)⟦x′≡ry⟧ =\; s_t+1(r _t)\; _ rx_t Z(x_t;x_t)\;×\;Σ _y,q\;μ(y _t)\; _A(y,q)\; _ry by Eq. (9) =κt+1(x′,r∣xt)×Z(x′,xt)Z(xt,xt) =\; _t+1(x ,r _t)\;×\; Z(x ;x_t)Z(x_t;x_t) by Eq. (11) The step-exact kernel is obtained by marginalizing out the reveal set R from the joint kernels. ∎ Appendix B Proof for Frozen Lookahead Proposition 3.7. [Frozen Lookahead] The lookahead for the constraint-satisfying terminal law induced by the frozen native kernels, for any state xtx_t reachable from x∗x is: h^t(x∗)(xt)=∑x∈N⟦x≡¬ℳ(xt)xt⟧×⟦x∈⟧×∏i∈ℳ(xt)Cati(x(i)∣x∗). h_t^(x )(x_t)=Σ _x ^N\; _ (x_t)x_t × ×Π _i (x_t)Cat_i(x(i) ). Therefore, h^t(xt)(xt)=Z(xt,xt) h_t^(x_t)(x_t)=Z(x_t;x_t) and h^t+1(xt)(xt+1)=Z(xt+1,xt). h_t+1^(x_t)(x_t+1)=Z(x_t+1;x_t).. Proof. Let ℛtR_t be the set of valid reveal-set sequences from t to TT. Then ℙx∗(XT=x∣Xt=xt)P_x (X_T\!=\!x\! \!X_t\!=\!x_t) is =∑rt+1:T∈ℛt∏s=tT−1κs+1(x∗)(xs+1,rs+1∣xs) = _r_t+1:T _t _s=t^T-1κ^(x )_s+1(x_s+1,r_s+1 _s) =⟦x≡¬ℳ(xt)xt⟧∏i∈ℳ(xt)Cati(x(i)∣x∗)×∑rt+1:T∈ℛt∏s=tT−1s+1(rs+1∣xs), = _ (x_t)x_t _i (x_t)Cat_i(x(i) )× _r_t+1:T _t _s=t^T-1s_s+1(r_s+1 _s), =⟦x≡¬ℳ(xt)xt⟧∏i∈ℳ(xt)Cati(x(i)∣x∗), = _ (x_t)x_t _i (x_t)Cat_i(x(i) ), by ∑rt+1:T∈ℛt∏m=tT−1sm+1(rm+1∣xm)=1 _r_t+1:T _t _m=t^T-1s_m+1(r_m+1 _m)=1 Therefore, the frozen lookahead is given by: h^t(x∗)(xt) h_t^(x )(x_t) =∑x∈N⟦x∈⟧ℙx∗(XT=x∣Xt=xt) = _x ^N \,P_x (X_T=x _t=x_t) =∑x∈N⟦x≡¬ℳ(xt)xt⟧⟦x∈⟧∏i∈ℳ(xt)Cati(x(i)∣x∗), = _x ^N _ (x_t)x_t _i (x_t)Cat_i(x(i) ), giving Eq. (13) Substituting x∗=xtx =x_t in Eq. (11) gives h^t(xt)(xt)=Z(xt,xt) h_t^(x_t)(x_t)\!=\!Z(x_t;x_t) and h^t+1(xt)(xt+1)=Z(xt+1,xt) h_t+1^(x_t)(x_t+1)\!=\!Z(x_t+1;x_t). ∎ Appendix C Proofs for Trajectory-Bias Boundary Cases C.1 Kernel-Level Trajectory Exactness Lemma C.1. [Kernel-Level Trajectory Exactness] The step-exact path law composed of step-exact kernels κt+1κ 0.56\, $A$_t+1 equals that composed of the Doob kernels κt+1★κ 0.6$ $_t+1 if and only if, for every t<Tt<T, every state xtx_t reachable with non-zero probability under the path law, with Z(xt,xt)>0Z(x_t;x_t)\!>\!0 and ht(xt)>0h_t(x_t)\!>\!0, and every xt+1x_t+1 in the support of κt+1(⋅∣xt) _t+1(· _t): Z(xt+1,xt)Z(xt,xt)=ht+1(xt+1)ht(xt) Z(x_t+1;x_t)Z(x_t;x_t)\;\;=\;\; h_t+1(x_t+1)h_t(x_t) (16) C.2 Vacuous Constraints Corollary 3.11. [No Bias for Vacuous Constraints] For a vacuous constraining regular language =NC\!=\!V^N, i.e., constrains nothing, Eq. (16) holds for every t<Tt\!<\!T, and there is no trajectory bias. Proof. Since =NC=V^N, every terminal state XT∈X_T , and so hT(x)=1h_T(x)\!=\!1 for all x∈Nx ^N. By backward induction, suppose ht+1(x′)=1h_t+1(x )\!=\!1 for every x′x . ht(x) h_t(x) =∑x′κt+1(x′∣x)ht+1(x′) =Σ _x _t+1(x )\;\;h_t+1(x ) by Definition 3.2 =∑x′κt+1(x′∣x), =Σ _x _t+1(x ), by the backward-induction hypothesis =1 =1 The local partition sum Z(x,x)Z(x;x) is the normalizer of Eq. (9) and so can be written as: Z(x,x) (x;x) =∑y,qμ(y∣x)ψ(y,q) =Σ _y,qμ(y )\;\, _A(y,q) =∑yμ(y∣x), =Σ _yμ(y ), since =NC\!=\!V^N and A is deterministic =∑y⟦y≡¬ℳ(x)x⟧∏i∈ℳ(x)Cati(y(i)∣x), =Σ _y _ (x)x \;\,Π _i (x)Cat_i(y(i) ), from Eq. (8) =∏i∈ℳ(x)∑v∈Cati(v∣x), =Π _i (x)Σ _v Cat_i(v ), by ∑v∈Cati(v∣x)=1Σ _v Cat_i(v )=1 =1 =1 The clamped partition sum Z(x′,x)Z(x ;x) is given as: Z(x′,x) (x ;x) =∑y⟦y∈⟧⟦y≡¬ℳ(x′)x′⟧∏i∈ℳ(x′)Cati(y(i)∣x), =Σ _y \;\, _ (x )x \;\,Π _i (x )Cat_i(y(i) ), from Eq. (11) =∑y⟦y≡¬ℳ(x′)x′⟧∏i∈ℳ(x′)Cati(y(i)∣x), =Σ _y _ (x )x \;\,Π _i (x )Cat_i(y(i) ), since =NC\!=\!V^N =∏i∈ℳ(x′)∑v∈Cati(v∣x), =Π _i (x )Σ _v Cat_i(v ), by ∑v∈Cati(v∣x)=1Σ _v Cat_i(v )=1 =1 =1 Therefore Z(x′,x)=ht+1(x′)=Z(x,x)=ht(x)=1Z(x ;x)\!=\!h_t+1(x )\!=\!Z(x;x)\!=\!h_t(x)\!=\!1 for all t<Tt\!<\!T. ∎ C.3 One-Step Reveal All Corollary 3.12. [No Bias for One-Step Reveal All] For a finite horizon T=1T\!=\!1, where every initial realization x0x_0 is completely unmasked in one step, Eq. (16) holds and there is no trajectory bias. Proof. Since T=1T\!=\!1, we have h1(x′)=⟦x′∈⟧h_1(x )\!=\! from Definition 3.2, and so h0(x0)h_0(x_0) is given by: h0(x0) h_0(x_0) =∑x′κ1(x′∣x0)h1(x′) =Σ _x _1(x _0)\;\;h_1(x ) =∑x′κ1(x′∣x0)⟦x′∈⟧, =Σ _x _1(x _0)\; , by h1(x′)=⟦x′∈⟧h_1(x )\!=\! The clamped partition sum Z(x′,x0)Z(x ;x_0) is given by Eq. (11) as: Z(x′,x0) (x ;x_0) =∑y⟦y∈⟧⟦y≡¬ℳ(x′)x′⟧∏i∈ℳ(x′)Cati(y(i)∣x0) =Σ _y \;\, _ (x )x \;\,Π _i (x )Cat_i(y(i) _0) =∑y⟦y∈⟧⟦x′=y⟧, =Σ _y \;\, \!=\!y , since ℳ(x′)=∅M(x )\!=\! for T=1T\!=\!1 =⟦x′∈⟧ = The local partition sum Z(x0,x0)Z(x_0;x_0) is the normalizer of Eq. (12) and so can be written as: Z(x0,x0) (x_0;x_0) =∑x′κ1(x′∣x0)Z(x′,x0) =Σ _x _1(x _0)\;\;Z(x ;x_0) =∑x′κ1(x′∣x0)⟦x′∈⟧, =Σ _x _1(x _0)\;\, , by Z(x′;x0)=⟦x′∈⟧Z(x ;x_0)\!=\! Since Z(x′,x0)=h1(x′)Z(x ;x_0)\!=\!h_1(x ) and Z(x0,x0)=h0(x0),Z(x_0;x_0)\!=\!h_0(x_0),. ∎ Appendix D Proof for Twist Fixes the Tilt Theorem 4.2. [Twist Fixes the Tilt] The Feynman–Kac twists correct the re-freezing tilt (Proposition 3.9), thus making the step-exact decoder path law target the Doob path law: G0(x0)∏t<TMt+1(xt+1∣xt)Gt+1(xt,xt+1)=p1:T★(x1:T∣x0;)Z★(x0).G_0(x_0)Π _t<TM_t+1(x_t+1 _t)\;G_t+1(x_t,x_t+1)\;\;=\;\;p_1:T 0.6$ $(x_1:T _0;C)\;Z 0.6$ $(x_0). Proof. Substituting the twist-constructed potentials from Eq. (4) into the left-hand side gives: G0(x0)∏t<TMt+1(xt+1∣xt)Gt+1(xt,xt+1) _0(x_0)Π _t<TM_t+1(x_t+1 _t)\;G_t+1(x_t,x_t+1) =η0(x0)∏t<Tκt+1(xt+1∣xt)ηt+1(xt+1)ηt(xt) =\; _0(x_0)Π _t<T _t+1(x_t+1 _t)\; _t+1(x_t+1) _t(x_t) =∏t<Tκt+1(xt+1∣xt)ηT(xT) =\;Π _t<T _t+1(x_t+1 _t)\; _T(x_T) by telescoping the twists =p1:Tmdlm(x1:T∣x0)⟦xT∈⟧ =\;p_1:T 0.5mdlm(x_1:T _0)\; _T by Definition 4.1 =p1:T★(x1:T∣x0;)Z★(x0) =\;p_1:T 0.6$ $(x_1:T _0;C)\;Z 0.6$ $(x_0) by Eq. (6) ∎ Appendix E Twister Algorithm (With Adaptive Resampling) Algorithm 2 Twister for step-exact decoding (with adaptive resampling). 1: DFA A recognizing C; initial state x0x_0; number of denoising steps TT 2: number of SMC particles KK; minimum effective sample size ESSmin∈[0,1]ESS_min∈[0,1] 3: Query the denoiser at x0x_0 4: (x0k,W0k)←(x0,1/K)(x_0^k,W_0^k)←(x_0,1/K) for all k∈[K]k∈[K] 5: for t=0,…,T−1t=0,…,T\!-\!1 do 6: STEP-EXACT FFBS PROPAGATE 7: parallel for k=1,…,Kk=1,…,K do 8: Sample xt+1k∼Mt+1(⋅∣xtk)x_t+1^k _t+1(· _t^k) ⊳ use cached FFBS messages 9: Z^t+1k←Z(xt+1k,xtk) Z_t+1^k (x_t+1^k;x_t^k) ⊳ predecessor clamped-partition sum 10: if t<T−1t<T\!-\!1 then 11: Query the denoiser at xt+1kx_t+1^k 12: Zt+1k←Z(xt+1k,xt+1k)Z_t+1^k (x_t+1^k;x_t+1^k) ⊳ successor partition sum and cache FFBS messages 13: else 14: ZTk←⟦xTk∈⟧Z_T^k← _T^k 15: RE-FREEZING CORRECTION 16: parallel for k=1,…,Kk=1,…,K do 17: Gt+1k←Zt+1k/Z^t+1kG_t+1^k←Z_t+1^k/ Z_t+1^k 18: W~t+1k←WtkGt+1k W_t+1^k _t^kG_t+1^k 19: Wt+1k←W~t+1k/∑k′=1KW~t+1k′W_t+1^k← W_t+1^k/ _k =1^K W_t+1^k for all k∈[K]k∈[K] 20: ADAPTIVE RESAMPLING 21: ESS←(∑k′=1K(Wt+1k′)2)−1ESS← ( _k =1^K(W_t+1^k )^2 )^-1 22: if t<T−1andESS<ESSminKt<T\!-\!1\;\;and\;\;ESS<ESS_minK then 23: xt+11:K←Resample(xt+11:K,Wt+11:K)x_t+1^1:K← Resample(x_t+1^1:K,W_t+1^1:K) ⊳ resample cache jointly 24: Wt+1k←1/KW_t+1^k← 1/K for all k∈[K]k∈[K] 25: return (xT1:K,WT1:K)(x_T^1:K,W_T^1:K) Algorithm 2 gives the complete Twister algorithm. It requires a DFA A (lifted to the model’s vocabulary V) that recognizes the regular language C; an initial state x0x_0, i.e., a token block containing the prompt and masked tokens to be unmasked; the maximum number of denoising steps TT; the number of SMC particles KK; and the minimum effective sample size ESSminESS_min, i.e., the threshold for triggering resampling of the SMC particles. Resampling is used in SMC to mitigate weight degeneracy: when weights of most SMC particles become too small, rendering them useless and thus wasting compute. Twister starts by querying the denoiser at the initial state x0x_0, computing its partition sum Z0Z_0 and caching its FFBS messages. Following this, it initializes all KK SMC particles to the initial state x0x_0 with weight 1/K1/K. The cached FFBS messages are used to sample from the Feynman–Kac proposal Mt+1M_t+1, i.e., the step-exact proposal of Proposition 3.8, and compute the predecessor clamped-partition sum Z^t+1k Z_t+1^k. For each propagated nonterminal particle, the denoiser is queried at the successor state to compute the successor partition sum Zt+1kZ_t+1^k and cache the FFBS messages for the next step. The ratio Gt+1k=Zt+1k/Z^t+1kG_t+1^k=Z_t+1^k/ Z_t+1^k gives the exact Feynman–Kac potential required in Section 4.1 for fixing the tilt from Proposition 3.9. Each incoming particle weight is multiplied by this potential, and the resulting weights are normalized. Particles are jointly resampled with their caches and assigned uniform weight when resampling is triggered by the effective sample size falling below ESSminKESS_minK. Complexity. One weighted-automaton pass costs (N||||)O(N ), and so, the total automaton cost for KK SMC particles and TT denoising steps is (||||)O(KTN ), in addition to the denoiser evaluations. Twister is parallelizable over the step-exact FFBS propagate and re-freezing correction phases, since the particles are conditionally independent until weight normalization and resampling. Appendix F Constraint Satisfaction Experiment Figure 3: Swarm plot of token-prefix DFA state counts on JSON-Mode-Eval. Each point is one datapoint; the diamond marks the mean. ⬇ [system] You are a helpful assistant that answers in JSON. Here’s the json schema you must adhere to: <schema> ’title’: ’WirelessAccessPoint’, ’type’: ’object’, ’properties’: ’ssid’: ’title’: ’SSID’, ’type’: ’string’, ’securityProtocol’: ’title’: ’SecurityProtocol’, ’type’: ’string’, ’bandwidth’: ’title’: ’Bandwidth’, ’type’: ’string’, ’required’: [’ssid’, ’securityProtocol’, ’bandwidth’] </schema> [user] I’m currently configuring a wireless access point for our office network and I need to generate a JSON object that accurately represents its settings. The access point’s SSID should be ’OfficeNetSecure’, it uses WPA2-Enterprise as its security protocol, and it’s capable of a bandwidth of up to 1300 Mbps on the 5 GHz band. This JSON object will be used to document our network configurations and to automate the setup process for additional access points in the future. Please provide a JSON object that includes these details. Only output the JSON object, no other text or comments. Figure 4: Example JSON-Mode-Eval prompt messages (datapoint json-0). The final user-turn line is our appended instruction to emit only the JSON object. As a sanity check that Twister still produces only constraint-satisfying outputs, we evaluate it along with other constrained decoding methods on the JSON-Mode-Eval dataset released by NousResearch (2024). JSON-Mode-Eval consists of 100 zero-shot datapoints, each specifying a given schema and requiring a JSON output that conforms to that schema. Of the 100 datapoints in JSON-Mode-Eval, we exclude six whose schemas cannot be compiled into a regular expression by Outlines (five use a named-root wrapper rather than a valid JSON Schema root, and one is malformed), and evaluate on the remaining 94. For each remaining datapoint, we compile the JSON schema into a regular expression with the Outlines library from Willard and Louf (2023) and transform that regular expression into a token-prefix automaton over the model vocabulary. Figure 3 shows the distribution of token-prefix DFA sizes created for the 94 evaluated schemas. The distribution is concentrated in the low hundreds of states, with most values falling between roughly 100100 and 250250. The mean number of states is 188, with a minimum of 34 states and a maximum of 625 states. We build the dataset prompt for each datapoint, append an instruction to emit only the JSON object, and then decode under each of the constrained strategies described below. Figure 4 shows an example of the prompt message for a JSON-Mode-Eval datapoint given to the model. We compare four constrained decoding strategies. DINGO† , at each denoising step, selects a constraint-satisfying completion that maximizes the automaton-weighted mean-field posterior. DINGO† picks the mode by using dynamic programming over automaton states to select a locally optimal constraint-satisfying block under the mean-field factorization. Our DINGO† implementation follows the original dynamic-programming procedure from Suresh et al. (2025). The original code is not publicly available. Dang and Ermon† instead samples exactly from the automaton-constrained mean-field posterior at each step using FFBS (Carter and Kohn, 1994; Dang and Ermon, 2026), which guarantees local validity but is still subject to the trajectory bias characterized in §3.4. Our Dang and Ermon† implementation follows the setup and procedure described in Dang and Ermon (2026). As with DINGO† , the original code is not publicly available. Finally, Twistersmc1 Twister_ smc1 and Twistersmc4 Twister_ smc4 apply Twister with K=1K\!=\!1 and K=4K\!=\!4 particles, using the step-exact constrained posterior and correcting trajectory bias with the Feynman–Kac twists described in §4. We evaluate all decoding methods on six open MDLMs from the DREAM (Ye et al., 2025), DreamCoder (Xie et al., 2025), and LLaDA (Nie et al., 2025) families: Dream-7B-Base, Dream-7B-Inst, DreamCoder-7B-Base, DreamCoder-7B-Inst, LLaDA-8B-Base, and LLaDA-8B-Inst. We chose these models because they are among the strongest publicly available MDLMs. We set generation length and denoising steps to 1.5×1.5× the gold answer length per datapoint. Table 1: Constraint satisfaction on JSON-Mode-Eval for all decoding methods. The Parse Valid (%) and Schema Valid (%) columns measure whether outputs are valid JSON and satisfy the schema set by the datapoint; Time (s) measures the average time taken to generate the output. Model Method Parse Valid (%) Schema Valid (%) Time (s) Dream-7B-Base DINGO† 100 98 22±4322± 43 Dang and Ermon† 100 98 22±4322± 43 Twistersmc1 Twister_ smc1 100 98 32±6532± 65 Twistersmc4 Twister_ smc4 100 98 42±8642± 86 Dream-7B-Inst DINGO† 100 99 21±4521± 45 Dang and Ermon† 100 99 21±4621± 46 Twistersmc1 Twister_ smc1 100 99 33±7233± 72 Twistersmc4 Twister_ smc4 100 99 42±8742± 87 DreamCoder-7B-Base DINGO† 100 98 21±3821± 38 Dang and Ermon† 100 98 21±3821± 38 Twistersmc1 Twister_ smc1 100 98 31±5731± 57 Twistersmc4 Twister_ smc4 100 98 40±7340± 73 DreamCoder-7B-Inst DINGO† 100 99 22±4722± 47 Dang and Ermon† 100 99 22±4722± 47 Twistersmc1 Twister_ smc1 100 99 34±7634± 76 Twistersmc4 Twister_ smc4 100 98 42±8842± 88 LLaDA-8B-Base DINGO† 100 98 19±3319± 33 Dang and Ermon† 100 98 19±3319± 33 Twistersmc1 Twister_ smc1 100 98 27±5027± 50 Twistersmc4 Twister_ smc4 100 98 36±6136± 61 LLaDA-8B-Inst DINGO† 100 99 18±3718± 37 Dang and Ermon† 100 99 21±4221± 42 Twistersmc1 Twister_ smc1 100 99 29±6229± 62 Twistersmc4 Twister_ smc4 100 99 37±7337± 73 Table 1 shows the results of our evaluation of the different decoding methods on the JSON-Mode-Eval dataset. We report the parse validity, schema validity, and average time in seconds of the generated outputs. Parse validity ensures that the generated output is valid JSON, while schema validity ensures that the generated output conforms to the expected schema set by the specific dataset sample. Importantly, all decoding methods, including Twister, consistently produce outputs that are valid JSON and conform to the expected schema. Although we report average generation times, our implementation is not optimized for performance. There are techniques to speed up the decoding time such as those described in Dang and Ermon (2026). This experiment acts as a confirmation to show that the trajectory-level correction we achieve with Twister does not compromise the constraint satisfaction already guaranteed by step-exact decoding.