Paper Review

Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata

July 9, 2026 Meihua Dang, Stefano Ermon Stanford University arXiv:2607.07026

dllmdecodingserving

An exact algorithm samples from the constraint-satisfying mean-field posterior of a diffusion language model for any constraint expressible as a finite automaton, fixing a correctness gap left open by autoregressive-style token masking and lifting Dream-7B's BFCL-Live function-calling accuracy under stochastic sampling from 22.3% to 69.0% with under 5% overhead.

diffusion 언어모델에서 유한 오토마타로 표현 가능한 임의의 제약 조건에 대해, 제약을 만족하는 mean-field posterior에서 정확히 샘플링하는 알고리즘을 제시해 autoregressive 방식의 토큰 마스킹이 남긴 정합성 공백을 메우고, Dream-7B의 BFCL-Live 함수 호출 정확도를 확률적 샘플링 기준 22.3%에서 69.0%로 5% 미만의 오버헤드로 끌어올렸다.

Wall-clock time per exact constrained sample vs. sequence length: the sequential chain (ancestral) sampler grows steeply past 100ms as length increases, while the log-depth tree sampler stays nearly flat around 10ms — the depth reduction is what turns exact inference into a practical GPU operation. 정확한 제약 샘플 1개당 wall-clock 시간 vs 시퀀스 길이: 순차 chain(ancestral) 샘플러는 길이가 늘수록 100ms를 넘어 가파르게 증가하지만, log-depth tree 샘플러는 10ms 근처에서 거의 평평하다 — 이 depth reduction이 exact inference를 실용적인 GPU 연산으로 바꾼다. Figure 3 from arXiv:2607.07026 — authors' figure

Accuracy vs. number of denoising steps on the BFCL Simple split (Dream, Python format): constrained decoding (blue) stays high as steps shrink from 256 to 16, while the unconstrained baseline (green) collapses toward zero — the constraint preserves structure exactly where aggressive parallel decoding destroys it. BFCL Simple split(Dream, Python 형식)에서 denoising 스텝 수 대비 정확도: 제약 디코딩(파란색)은 스텝을 256에서 16으로 줄여도 높게 유지되지만, 제약 없는 baseline(초록색)은 0 근처로 붕괴한다 — 공격적인 병렬 디코딩이 구조를 무너뜨리는 바로 그 지점에서 제약이 구조를 지켜준다. Figure 4 (Dream, Python panel) from arXiv:2607.07026 — authors' figure

Background Constrained decoding is essential for serving LLMs whose outputs must follow a formal grammar, such as JSON-schema function calls or SQL, and existing systems — Outlines (regex/finite automata), XGrammar and Guidance (CFGs) — all assume autoregressive left-to-right generation, masking invalid next-token candidates at each step. Diffusion language models (dLLMs) such as Dream-7B and LLaDA-8B instead sample multiple positions simultaneously from a fully-factorized mean-field distribution at every denoising step, and this parallel commitment is the source of their speed advantage. Since there is no notion of "the next single token", AR-style constraint machinery cannot be transplanted as-is.

배경 constrained decoding은 JSON 스키마 함수 호출·SQL처럼 출력이 형식 문법을 따라야 하는 LLM 서빙의 필수 요소로, Outlines(정규식/유한 오토마타)·XGrammar·Guidance(CFG) 같은 기존 시스템은 모두 autoregressive 모델의 좌→우 생성을 전제하고 매 스텝 무효한 next-token 후보를 마스킹한다. 반면 Dream-7B·LLaDA-8B 같은 diffusion 언어모델(dLLM)은 매 denoising 스텝마다 완전 분해된(fully-factorized) mean-field 분포에서 여러 위치를 동시에 샘플링하며, 이 병렬 확정이 dLLM 속도 이점의 원천이다. "다음 한 토큰"이라는 개념 자체가 없는 생성 방식이라 AR용 제약 장치를 그대로 이식할 수 없다.

Problem In diffusion generation the validity of position i depends on the tokens being sampled simultaneously at all other positions, so masking each position to be locally valid does not keep the joint sample valid under the automaton — in the paper's example, tokens that are individually valid combine into an invalid string like "..". It is like a crossword puzzle where each square's letter is fine for its own word yet clashes at the intersections — per-square filtering cannot guarantee global consistency. Reasoning about the joint distribution induced by the constraint is therefore required.

문제 diffusion 생성에서는 위치 i의 유효성이 같은 스텝에서 동시에 샘플링되는 다른 모든 위치의 토큰에 의존하므로, 각 위치를 개별적으로 유효하게 마스킹해도 결합(joint) 샘플은 오토마타 상에서 무효가 될 수 있다 — 논문의 예처럼 위치별로는 각각 유효한 토큰들이 조합되면 ".."같은 무효 문자열이 나온다. 낱말퍼즐(crossword)에서 각 칸의 글자가 자기 단어로는 유효해도 교차 지점에서 서로 충돌할 수 있는 것과 같다 — 칸별 필터링으로는 전체 정합성을 보장할 수 없다. 따라서 제약이 유도하는 결합 분포에 대한 추론이 필요하다.

Prior limitations AR constrained-decoding methods rest on the premise that sequential generation only ever needs one token masked per step, so they cannot be applied to simultaneous multi-position commitment with any correctness guarantee. The dLLM-specific prior work DINGO supports only MAP (greedy) inference via dynamic programming over deterministic finite automata, while Mündler et al. and Zhang et al. handle CFGs through per-step rejection sampling. Exact stochastic sampling from the constraint-conditioned distribution remained open.

기존 한계 AR용 제약 디코딩은 순차 생성에서 매 스텝 한 토큰만 마스킹하면 된다는 전제 위에 서 있어 동시 다위치 확정에는 정합성 보장 없이 적용될 수 없다. dLLM 전용 선행인 DINGO는 deterministic 유한 오토마타 위에서 dynamic programming으로 MAP(greedy) 추론만 지원하고, CFG를 다루는 Mündler et al.·Zhang et al.은 per-step rejection sampling에 의존한다. 즉 제약-조건부 분포로부터의 정확한 확률적 샘플링은 열려 있었다.

Goal For any constraint expressible as a (possibly nondeterministic) finite automaton, perform exact sampling from the dLLM's constraint-conditioned mean-field posterior that satisfies the constraint 100% by construction, at practical inference overhead. The requirements extend to supporting both greedy and stochastic sampling, and compatibility with parallel and block-wise decoding under arbitrary remasking schedules.

목표 유한 오토마타(비결정적 포함)로 표현 가능한 임의의 제약에 대해, dLLM의 제약-조건부 mean-field posterior에서 구성상(by construction) 제약을 100% 만족하는 exact 샘플링을 실용적 오버헤드로 수행하는 것. greedy와 확률적 샘플링을 모두 지원하고, 임의의 remasking 스케줄 하의 parallel·block-wise 디코딩과 호환되는 것까지가 요구 조건이다.

Method The finite automaton is converted into a chain-structured graphical model (HMM-like) over edge-valued latent states; reweighting its emission factors by the mean-field token probabilities keeps the constraint-conditioned joint distribution chain-structured, so forward–backward inference samples from it exactly. Ancestral sampling has depth linear in sequence length L, but a conditional-independence property — given boundary states, the middle segment decouples through the midpoint state — lets depth-reduction techniques from arithmetic circuit theory cut sampling depth to O(log L), at the cost of FLOPs growing from quadratic to cubic in the automaton state count. The recursion works like planning a road trip by fixing the midpoint city first, after which the two half-routes can be planned independently in parallel. The constrained marginals are additionally recomputed as remasking signals (which positions to commit first).

방법 유한 오토마타를 엣지-값 잠재 상태에 대한 chain 구조 그래프 모델(HMM 형태)로 바꾸고, mean-field 토큰 확률을 emission factor에 재가중해 곱하면 제약-조건부 결합 분포가 chain 구조를 유지해 forward–backward로 exact 샘플링이 가능해진다. 순차(ancestral) 샘플링은 깊이가 시퀀스 길이 L에 선형이지만, 경계 상태가 주어지면 중간 구간이 중점(midpoint) 상태를 통해 조건부 독립이 된다는 성질에 arithmetic circuit의 depth-reduction 기법을 적용해 깊이를 O(log L)로 줄인다 — 대신 FLOPs는 오토마타 상태 수에 대해 제곱에서 세제곱으로 늘어나는 트레이드오프다. 자동차 여행에서 중간 도시를 먼저 확정하면 앞뒤 반쪽 경로를 독립적으로 병렬 계획할 수 있는 것과 같은 재귀 구조다. 추가로 제약-조건부 marginal을 remasking 신호(어느 위치를 먼저 확정할지)로 재계산해 쓴다.

Key idea All the history the constraint check needs is summarized in the automaton state, not in individual tokens — as in a board game, where the validity of the next move is determined by the current board position alone, not the full move history. The product of the chain-structured graphical model over state sequences and the fully-factorized mean-field remains tractable, so joint validity is guaranteed by construction even when many positions are sampled at once.

핵심 아이디어 제약 검사에 필요한 모든 이력은 개별 토큰이 아니라 오토마타 상태에 요약된다는 것 — 보드게임에서 지나온 수순 전체가 아니라 현재 판의 상태만 알면 다음 수의 유효성이 판정되는 것과 같다. 상태 시퀀스에 대한 chain 그래프 모델과 fully-factorized mean-field의 곱은 여전히 tractable하므로, 여러 위치를 동시에 샘플링해도 결합 정합성이 구성상 보장된다.

Validation Evaluated on Dream-7B and LLaDA-8B (Base and Instruct) across function calling (xLAM, BFCL), planning (Sudoku, Countdown), text-to-SQL (Spider), and math reasoning (GSM-Symbolic), under both greedy decoding and stochastic sampling. Ablations cover the remasking-signal choice (constrained marginals vs. the base model's mean-field confidence), robustness as denoising steps shrink from 256 to 16, measured runtime of the chain vs. tree samplers, and a comparison against similarly sized AR models.

검증 Dream-7B와 LLaDA-8B(Base·Instruct)에서 함수 호출(xLAM, BFCL), 계획(Sudoku, Countdown), text-to-SQL(Spider), 수학 추론(GSM-Symbolic)을 greedy와 확률적 샘플링 두 체제로 평가했다. ablation으로 remasking 신호 선택(제약-조건부 marginal vs 기본 mean-field 확신도), denoising 스텝 수를 256→16으로 줄일 때의 강건성, chain vs tree 샘플러의 실측 런타임, 비슷한 크기 AR 모델과의 비교까지 제시한다.

Results On BFCL-Live, Dream-7B's greedy accuracy rises from 63.9% to 71.5% and stochastic sampling from 22.3% to 69.0%, effectively erasing the greedy-vs-sampling gap, at +4% overhead with the tree sampler (+114% for the chain). Gains are largest where format is the bottleneck — Dream greedy on BFCL-Live (Python) 22.4%→69.7%, Sudoku 36.4%→92.4%, Countdown 53.6%→100% — while tasks with semantic errors like Spider (52.7→53.0) and GSM-Symbolic (39.9→40.2) improve little. Constraint satisfaction itself is guaranteed at 100% by construction.

결과 BFCL-Live에서 Dream-7B의 greedy 정확도가 63.9%→71.5%, 확률적 샘플링은 22.3%→69.0%로 올라 greedy-샘플링 격차가 사실상 사라졌고, 오버헤드는 tree 샘플러 기준 +4%(chain은 +114%)다. 형식이 병목인 과제일수록 이득이 커서 Dream greedy 기준 BFCL-Live(Python) 22.4%→69.7%, Sudoku 36.4%→92.4%, Countdown 53.6%→100%인 반면, Spider(52.7→53.0)·GSM-Symbolic(39.9→40.2)처럼 오류가 의미적인 과제에선 이득이 작다. 제약 만족률 자체는 구성상 100%가 보장된다.

Comparison The main comparison is against the same model's unconstrained greedy and sampling decoding; the dLLM prior DINGO is greedy(MAP)-only and is positioned as a special case being generalized rather than a direct baseline. On BFCL-Live (Python), constrained Dream reaches 69.7%, close to Llama-3.1-8B (70.8%) and substantially narrowing the gap to Qwen3-8B (80.1%), showing that once format errors are removed, dLLM function calling approaches same-size AR models. The authors diagnose the baseline gap as "structural, not semantic" — the models know what to call but fail at how to format it.

비교 주 비교 대상은 제약 없는 동일 모델의 greedy·샘플링 디코딩이며, dLLM용 선행 DINGO는 greedy(MAP) 전용이라 직접 baseline이 아닌 일반화 대상으로 포지셔닝된다. BFCL-Live(Python)에서 제약 적용 Dream이 69.7%로 Llama-3.1-8B(70.8%)에 근접하고 Qwen3-8B(80.1%)와의 격차도 크게 줄여, 형식 오류를 걷어내면 dLLM의 함수 호출 능력이 동급 AR 모델에 가깝다는 것을 보인다. 저자들은 baseline 격차가 "구조적이지 의미적이지 않다"고 진단한다 — 모델은 무엇을 호출할지는 알지만 형식을 지키는 데서 무너진다.

Significance Rather than filtering or retrying after generation, the method samples directly from a distribution in which invalid strings are simply not representable — a guarantee like a web form that physically refuses malformed input, not a proofreader that flags it afterwards. This guarantee patches exactly the dLLM weak spot (structural collapse under stochastic sampling and few denoising steps): as steps shrink for speed, the baseline crumbles while constrained decoding holds. As a case of tractable probabilistic inference made practical inside decoding at under 5% overhead, it is a plausible standard component for structured-output dLLM serving.

의의 출력을 만든 뒤 걸러내는 사후 검증·재시도가 아니라 무효 문자열이 아예 표현되지 않는 분포에서 직접 샘플링한다 — 잘못된 형식은 입력 자체가 불가능한 전자 폼과 같은 보장이다. 이 보장이 dLLM의 약점(확률적 샘플링과 적은 denoising 스텝에서의 구조 붕괴)을 정확히 메워, 스텝을 줄여 빨라질수록 baseline은 무너지지만 제약 디코딩은 유지된다. tractable probabilistic inference를 디코딩에 접목해 5% 미만 오버헤드로 실용화한 사례로, dLLM 구조화-출력 서빙의 기본 구성요소가 될 만하다.

Limitations Stated by the authors (§7): the method covers only finite automata, not richer constraints such as context-free grammars, and if misused it could generate syntactically valid but malicious tool calls or database queries. The tree sampler's FLOPs scale cubically with the automaton state count, so cost on very large grammars needs separate verification (reviewer judgment). The constraint also guarantees only syntax, not semantics — hence the ~0.3pt gains on Spider and GSM-Symbolic where errors are semantic.

한계 저자 명시(§7): 유한 오토마타까지만 다루며 context-free grammar 같은 더 풍부한 제약은 미지원이고, 오용 시 문법적으로 유효한 악성 tool call·DB 쿼리 생성에 쓰일 수 있다. tree 샘플러의 FLOPs는 오토마타 상태 수에 세제곱으로 스케일하므로 매우 큰 문법에서의 비용은 별도 검증이 필요하다(리뷰어 판단). 또한 제약은 문법만 보장할 뿐 의미 오류를 고치지 못해 Spider·GSM-Symbolic에서는 이득이 0.3pt 수준에 그친다.

Future work There is no dedicated future-work section (not stated in the paper). The limitation the authors name — no CFG support — points to the natural next step, but CFGs require a pushdown automaton, for which this paper's finite-state chain representation does not directly hold, making a tractable extension non-trivial (reviewer judgment).

향후 과제 별도의 future-work 절은 없다(논문 내 명시 없음). 다만 저자들이 한계로 지적한 CFG 미지원이 자연스러운 다음 단계를 가리키는데, CFG는 pushdown automaton이 필요해 이 논문의 유한-상태 chain 표현이 그대로 성립하지 않으므로 tractable한 확장은 비자명하다(리뷰어 판단).

Released resources No public code or checkpoint link could be verified in the paper HTML (no public release verified) — only the arXiv posting itself is confirmed. The evaluated models (Dream-7B, LLaDA-8B) and benchmarks (BFCL, xLAM, Spider, GSM-Symbolic) are all public assets.

자원 공개 공개 코드·체크포인트 링크는 논문 HTML에서 확인되지 않았다(공개 링크 확인 안 됨) — 확인된 것은 arXiv 게재뿐이다. 평가에 쓰인 Dream-7B·LLaDA-8B 모델과 BFCL·xLAM·Spider·GSM-Symbolic 벤치마크는 모두 공개 자산이다.

The research thread

Where this paper sits 연구의 흐름

This paper sits where two previously separate lines converge. One is the constrained-decoding stack built for autoregressive LLMs — PICARD's incremental parsing for text-to-SQL, Outlines compiling regular expressions into finite automata, the CFG engines Guidance and XGrammar — all variations on a single move: mask invalid next tokens given the current prefix. The other is the tractable probabilistic inference tradition: hidden Markov models and forward–backward message passing, probabilistic circuits, and the arithmetic-circuit depth-reduction results this paper leans on. In between, diffusion-specific predecessors had scouted the terrain — DINGO with dynamic programming over deterministic automata (greedy MAP only), Mündler et al. and Zhang et al. attacking CFGs with per-step rejection and lookahead — but exact stochastic sampling under a constraint remained unclaimed.

The conceptual shift is to promote the constraint from a filter to a model. AR-style constrained decoding treats the grammar as a gatekeeper standing outside the LM, vetoing tokens one position at a time. Here the automaton becomes a first-class probabilistic object: its states are latent variables in a chain-structured graphical model, the dLLM's mean-field probabilities are emission weights, and the product — whose support is exactly the constrained language — admits exact forward–backward sampling. The unit of correctness changes with it: not "every token locally legal" but "the joint sample valid by construction". Even scheduling is absorbed into inference — constraint-conditioned marginals, not raw confidence, decide which positions to unmask first.

What this opens is legible in the paper's own two curves. First, the greedy-versus-sampling cliff disappears (22.3% to 69.0% on BFCL-Live) — and stochastic sampling is what best-of-n, self-consistency, and RL-style pipelines actually consume. Second, and more suggestive: as denoising steps shrink from 256 to 16 the unconstrained baseline collapses while constrained decoding barely moves, because the constraint supplies exactly the structural scaffolding that aggressive parallel decoding destroys. Constrained inference is thus not a tax on dLLM speed but a complement to it — a plausible Outlines/XGrammar-equivalent layer for the dLLM serving stack.

The open edges are clearly marked. Expressiveness: finite automata stop short of context-free grammars, and the pushdown stack a CFG needs breaks the chain-structured product — so the field will likely try bounded-nesting finite approximations of practical grammars before a tractable pushdown analogue appears. Cost: the tree sampler's FLOPs grow cubically in automaton state count, and industrial-scale grammars (a full JSON-schema automaton can be enormous) will push toward automaton minimization and sparsity-aware message passing. And the ceiling: constraints fix form, not meaning — Spider and GSM-Symbolic barely move — so the natural next round couples by-construction syntax with execution- or verifier-based semantic feedback. The authors flag the dual use themselves: a decoder that emits only well-formed tool calls will emit well-formed malicious ones too — the guarantee sharpens the safety question rather than settling it.

이 논문은 그동안 서로 만나지 않던 두 계보가 합류하는 지점에 서 있다. 하나는 autoregressive LLM을 위해 쌓아 올린 constrained decoding 스택이다 — text-to-SQL을 위한 PICARD의 incremental parsing, 정규식을 유한 오토마타로 컴파일하는 Outlines, CFG 엔진인 Guidance와 XGrammar — 전부 "현재 prefix에서 무효한 next token을 마스킹한다"는 한 가지 동작의 변주다. 다른 하나는 tractable probabilistic inference 전통이다: hidden Markov model과 forward–backward message passing, probabilistic circuit, 그리고 이 논문이 기대는 arithmetic circuit depth-reduction 결과들. 그 사이에서 diffusion 전용 선행들이 이미 지형을 훑어놓았다 — DINGO는 deterministic 오토마타 위 dynamic programming으로 greedy(MAP)까지만 지원했고, Mündler et al.과 Zhang et al.은 per-step rejection과 lookahead로 CFG를 공략했다 — 하지만 제약 하에서의 exact stochastic sampling은 여전히 빈자리였다.

개념적 이동은 제약을 '필터'에서 '모델'로 승격시킨 것이다. AR식 constrained decoding은 문법을 LM 바깥에 세워둔 문지기로 취급해 한 위치씩 토큰에 거부권을 행사한다. 이 논문에서 오토마타는 일급 확률 객체가 된다: 상태들이 chain 구조 그래프 모델의 잠재 변수가 되고, dLLM의 mean-field 확률이 emission 가중치가 되며, 그 곱 분포 — support가 정확히 제약 언어와 일치하는 — 에서 forward–backward로 exact 샘플링이 가능해진다. 정합성의 단위도 함께 바뀐다: "모든 토큰이 국소적으로 합법"이 아니라 "결합 샘플이 구성상(by construction) 유효"다. 스케줄링마저 inference 안으로 흡수된다 — 어느 위치를 먼저 unmask할지를 raw confidence가 아니라 제약-조건부 marginal이 정한다.

이것이 무엇을 열었는지는 논문의 두 그래프에서 그대로 읽힌다. 첫째, greedy 대 sampling의 절벽이 사라진다(BFCL-Live 22.3% → 69.0%) — best-of-n, self-consistency, RL류 파이프라인이 실제로 소비하는 것이 stochastic sampling이라는 점에서 중요하다. 둘째, 더 시사적인 쪽: denoising 스텝을 256에서 16으로 줄이면 무제약 baseline은 붕괴하지만 제약 디코딩은 거의 흔들리지 않는다 — 공격적인 병렬 디코딩이 부수는 구조적 골격을 제약이 정확히 그 자리에서 공급하기 때문이다. 그래서 constrained inference는 dLLM 속도에 물리는 세금이 아니라 보완재가 되고, 이 논문은 dLLM 서빙 스택에서 Outlines/XGrammar에 해당하는 층을 차지할 유력한 후보가 된다.

열린 모서리들은 선명하게 표시되어 있다. 표현력: 유한 오토마타는 context-free grammar 앞에서 멈추고, CFG에 필요한 pushdown 스택은 chain 구조 곱을 깨뜨린다 — tractable한 pushdown 대응물이 나오기 전까지 필드는 실용 문법의 bounded-nesting 유한 근사부터 시도할 공산이 크다. 비용: tree 샘플러의 FLOPs는 오토마타 상태 수에 세제곱으로 늘어나므로, 산업 규모 문법(JSON-schema 전체를 컴파일한 오토마타는 거대해질 수 있다)은 오토마타 최소화와 sparsity를 살린 message passing 쪽으로 압력을 만든다. 그리고 천장: 제약은 형식을 고칠 뿐 의미를 고치지 못한다 — Spider와 GSM-Symbolic이 거의 움직이지 않는 이유다 — 그래서 자연스러운 다음 라운드는 구성상 보장되는 문법 위에 실행·검증 기반 semantic feedback을 얹는 결합이다. 저자들 스스로 양날을 지적한다: 잘 갖춰진 형식의 tool call만 내놓는 디코더는 잘 갖춰진 형식의 악성 tool call도 내놓는다 — 이 보장은 안전 문제를 해결하는 게 아니라 더 날카롭게 만든다.

Sparks — where one could take this 아이디어의 씨앗

One could compile bounded-nesting finite-automaton approximations of practical context-free grammars (depth-capped JSON, SQL subsets) and measure where the finite-state approximation actually breaks on real workloads. 실용 CFG(깊이를 제한한 JSON, SQL 부분집합)를 bounded-nesting 유한 오토마타로 근사 컴파일하고, 그 유한-상태 근사가 실제 워크로드의 어디에서 깨지는지 측정해볼 수 있다.
One could attack the tree sampler's cubic scaling in automaton states with automaton minimization and sparsity-aware message passing, profiling the cost of exact constrained sampling on industrial-scale schema grammars. 오토마타 최소화와 transition 구조의 sparsity를 살린 message passing으로 tree 샘플러의 상태 수 세제곱 스케일링을 공략해, 산업 규모 schema 문법에서 exact constrained sampling의 비용을 프로파일링해볼 수 있다.
One could layer execution- or verifier-based semantic feedback on top of by-construction syntactic guarantees, testing how formal and semantic checking compose on tasks like text-to-SQL where the remaining errors are semantic. 구성상 보장되는 문법 위에 실행·검증 기반 semantic feedback을 얹어, 남은 오류가 의미적인 text-to-SQL류 과제에서 형식 보장과 의미 검증이 어떻게 결합되는지 실험해볼 수 있다.

Seeds grounded in the paper's own stated limitations and open questions. 논문이 스스로 밝힌 limitations와 open questions에 뿌리를 둔 씨앗입니다.

arXiv

Notes

The genuinely hard part here is a correctness gap that only exists for diffusion-style decoding: masking each simultaneously-sampled position to be locally valid does not make the joint sample valid, because diffusion LMs commit several positions per step from a factorized approximation. Modeling the automaton over its states (a graphical model) rather than over sequence positions is what makes the joint guarantee possible “by construction” rather than empirically. The full text answers the tractability question the abstract left open: exact sampling costs are quadratic in automaton states for the sequential chain sampler and cubic for the O(log L)-depth tree sampler — a FLOPs-for-depth trade that buys a +114% → +4% overhead reduction on GPUs. The remaining open edge is grammars beyond finite automata (CFGs need a pushdown automaton, where the chain-structured product no longer applies), and the fact that the constraint fixes form, not meaning: Spider and GSM-Symbolic barely move because their errors are semantic.

Linked reviews

diffusion-llm

Fast-dLLM: Training-Free Acceleration of Diffusion LLMs via KV Cache and Parallel Decoding

A block-wise approximate KV cache plus confidence-thresholded parallel decoding accelerates open diffusion LLMs by up to 27.6x end-to-end with 1-2 point accuracy loss, entirely training-free.

Jul 04, 2026 · NVIDIA / MIT / HKU diffusion-llm

LLaDA: Large Language Diffusion Models

An 8B masked-diffusion language model trained from scratch on 2.3T tokens that matches LLaMA3-8B-class autoregressive baselines, showing next-token prediction is not the only recipe for LLM capabilities.

Jun 28, 2026 · RUC GSAI / Ant Group diffusion

Seeing the End at Step Zero: Accelerating Diffusion MLLMs via MLP Sparsity-Aware Truncation

Seer exploits a sharp MLP activation-sparsity jump at diffusion step zero to predict a diffusion multimodal LLM's true output length before generation, then permanently truncates the redundant end-of-text padding and routes batches through a hybrid static/variable-length execution scheme, reaching up to 31x throughput gains across nine vision-language benchmarks without hurting accuracy.

Jul 17, 2026 diffusion-llm

Survival-Guided Length Control for Efficient Diffusion Language Models

Recasts how long a diffusion language model should generate as a discrete-time survival problem over the end-of-sequence token, yielding a training-free plug-in that speeds up decoding 3-7x with no accuracy loss.

Aug 29, 2026

Back to the review vault