Pith. sign in

REVIEW 1 major objections 7 minor 41 references

Reviewed by Pith at T0; open to challenge.

T0 means a machine referee read the full paper against a public rubric. The mark states how deep the mechanical check went, never who wrote it. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · glm-5.2

Diffusion LLMs Can Follow Rules: Exact Constrained Decoding via Automata Inference

2026-07-09 21:22 UTC pith:HOU2YRPF

load-bearing objection Solid constrained decoding for diffusion LMs; abstract overclaims 'exact' for NFAs but core method is sound and useful the 1 major comments →

arxiv 2607.07026 v1 pith:HOU2YRPF submitted 2026-07-08 cs.LG

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

Meihua Dang , Stefano Ermon This is my paper
classification cs.LG
keywords decodingconstrainedmodelsaccuracyfiniteinferencesamplingunder
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Diffusion language models (dLLMs) generate text by simultaneously sampling multiple token positions from a fully-factorized distribution at each denoising step, unlike autoregressive models that generate left-to-right. This parallelism breaks existing constrained decoding methods, which work by masking invalid next tokens one at a time: when positions are sampled independently, locally valid tokens can combine into globally invalid sequences. This paper solves the problem for any constraint expressible as a finite automaton (covering JSON schemas, SQL syntax, arithmetic formats, and more). The key insight is that a finite automaton can be viewed as a chain-structured graphical model whose support is exactly the set of constraint-satisfying sequences. The product of the model's mean-field prediction and this automaton-induced distribution admits a tractable chain-structured representation, enabling exact sampling from the constrained posterior at each diffusion step via standard forward-backward message passing. The authors further restructure the linear-depth chain into a binary tree of prefix-suffix state pairs using depth-reduction techniques from arithmetic circuit theory, reducing the number of sequential GPU operations from O(L) to O(log L) in sequence length. The method guarantees constraint satisfaction by construction, supports both greedy and stochastic decoding, and computes per-token marginals under the constrained distribution for use as confidence signals during remasking. Empirically, the method substantially improves accuracy on function calling, planning, text-to-SQL, and math reasoning tasks across two open-weight dLLMs, with under 5% wall-clock overhead, and notably rescues stochastic sampling from near-total collapse to near-greedy performance.

Core claim

The central mechanism is the product construction: multiplying a fully-factorized mean-field distribution from a dLLM by a chain-structured graphical model induced by a finite automaton yields another chain-structured model that can be sampled from exactly in tractable time. This converts the global constraint into local factors that couple adjacent positions through the automaton's state transitions, enabling exact inference via standard message-passing algorithms. The log-depth tree sampling algorithm then exploits the conditional independence structure of the chain: conditioning on a midpoint state makes the left and right halves independent, enabling a divide-and-conquer recursion that采样

What carries the argument

The approach rests on three technical components. First, the automaton-as-graphical-model view: a finite automaton encoding constraint C induces a hidden Markov model over edge-sequences, where transition factors enforce that consecutive edges chain end-to-end and emission factors enforce that emitted tokens match edge labels. Second, the product construction: because the dLLM's mean-field prediction factorizes over positions while the automaton's distribution is chain-structured, their product retains the chain structure, with emission factors reweighted by the dLLM's per-position probabilities. Sampling from this product model yields exact draws from the constrained posterior at each deno

Load-bearing premise

The method enforces constraints at each diffusion step independently, sampling from the constrained posterior given the current noisy state. This per-step projection approximates but does not exactly sample from the true globally-constrained generative distribution of the full diffusion process. The authors acknowledge this gap but argue empirically that the approximation yields strong results.

What would settle it

If the per-step constrained approximation introduces systematic biases that compound across denoising steps, the final output could satisfy the constraint but be semantically degraded compared to samples from the true constrained diffusion distribution. This would manifest as high constraint satisfaction but poor task accuracy, particularly on tasks requiring deep multi-step reasoning where intermediate denoising steps carry significant information.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Diffusion language models become viable for production structured-output tasks (function calling, SQL generation, configuration files) where guaranteed format compliance is non-negotiable, closing a practical gap with autoregressive LLMs.
  • The log-depth parallelization strategy could extend to other chain-structured inference problems in sequence modeling beyond constrained decoding, wherever a linear sequential dependency chain can be restructured as a balanced binary tree.
  • Computing per-token marginals under the constrained distribution provides a principled confidence signal for remasking, potentially improving dLLM decoding quality even in unconstrained settings by better identifying which positions the model is uncertain about.
  • The framework naturally extends to any constraint class that induces a tractable graphical model structure, suggesting a path toward constrained decoding for richer constraint languages if their graphical model representations admit efficient inference.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 7 minor

Summary. This paper addresses constrained decoding for discrete diffusion language models (dLLMs), a setting where the standard autoregressive approach of masking invalid next tokens does not apply because dLLMs sample multiple positions simultaneously from a fully-factorized mean-field distribution. The authors formalize the problem as sampling from a constrained mean-field posterior $p_θ(x_0|x_t, C) ∝ p_θ(x_0|x_t) · 1[x_0 ∈ C]$ at each denoising step, where $C$ is expressed as a finite automaton (FA). By viewing the FA as a chain-structured graphical model (equivalent to an HMM), the product of the mean-field distribution and the FA's path distribution admits a tractable representation, enabling exact forward-backward inference and ancestral sampling. The authors further apply depth-reduction techniques from arithmetic circuit theory to restructure the $O(L)$-depth sequential chain into an $O(˜log L)$-depth binary tree of prefix-suffix state pairs, substantially improving GPU parallelism. The method is evaluated on Dream-7B and LLaDA-8B across function calling (xLAM, BFCL), planning (Sudoku, Countdown), text-to-SQL (Spider), and math reasoning (GSM-Symbolic), showing large accuracy gains—particularly under stochastic sampling where unconstrained baselines collapse—with under 5% wall-clock overhead for the tree variant.

Significance. The paper makes a timely and well-executed contribution to the emerging area of diffusion language models, which are gaining traction as alternatives to autoregressive LLMs. Constrained decoding is a practical necessity for structured output generation, and the absence of a principled solution for dLLMs is a genuine gap. The technical approach—combining HMM forward-backward inference with arithmetic circuit depth-reduction—is clean and the correctness proof (Appendix B) is straightforward. The empirical results are strong and the evaluation is comprehensive across diverse constraint types and tasks. The log-depth tree sampling algorithm is a particularly nice contribution that makes the method practical. The paper ships a falsifiable empirical claim (accuracy and overhead numbers on standard benchmarks) and provides sufficient detail for reproduction.

major comments (1)
  1. The abstract claims an 'exact and tractable algorithm for sampling from the constrained mean-field posterior under any constraint expressible as a finite automaton.' This is correct for deterministic FAs (DFAs), where $p_M$ is uniform over $C$ and the product construction in §4.2 yields exactly Eq. (4). However, for nondeterministic FAs (NFAs), $p_M(x_{1:L})$ weights each accepted sequence by its number of accepting paths, so the sampler draws from $p_θ(x_0|x_t) · p_M(x_0)$ rather than $p_θ(x_0|x_t) · 1[x_0 ∈ C]$. The paper acknowledges this in §4.2 ('sampling from this weighted distribution becomes a soft proxy'), but the abstract's blanket 'exact' claim overcovers the NFA case. Since Spider uses NFAs (~10k states, ~100k edges per Table 7) and its gains are modest (Dream: 52.7→53.0, LLaDA: 53.2→53.6 in Table 1), this is not merely a theoretical subtlety. The authors should either (a) re
minor comments (7)
  1. §4.1: The per-step approximation—enforcing constraints at each denoising step rather than sampling from the globally-constrained diffusion process—is acknowledged but not discussed in depth. A brief remark on why this per-step projection is expected to work well (beyond the analogy to AR constrained decoding) would strengthen the paper, though the paper's transparency on this point is appreciated.
  2. Table 1: The Spider results show very small improvements (Dream: +0.3%, LLaDA: +0.4% greedy). Given that Spider is the only NFA-based task, it would be helpful to note whether the modest gains are attributable to the NFA approximation gap, the difficulty of the SQL task, or high baseline constraint satisfaction (CS=72.2%/73.5%).
  3. Table 3: The chain variant incurs +114% wall-clock overhead while the tree variant incurs only +4%. Since the chain variant is strictly dominated, its inclusion is primarily an ablation. Consider noting explicitly that the chain variant is included only to demonstrate the necessity of the tree optimization, so readers do not mistake it for a recommended configuration.
  4. Figure 4: The y-axis ranges differ across the four subplots (0–100 for Dream Python, 0–100 for Dream JSON, etc.), making cross-panel visual comparison slightly difficult. Consider using consistent axis ranges.
  5. §3.2, Eq. (3): The notation $p_M(x_i=v|z_i=e) := 1[v ∈ label(e)]$ uses $:=$ but these are described as unnormalized factors in the footnote. A brief clarifying remark that these are indicator functions (not probabilities) would help readers unfamiliar with the graphical model formulation.
  6. Table 7: The GSM-Symbolic row reports a single automaton (N=1) with 56 states and 745/748 edges. The P95 column shows '–' for this row, which is correct but could be clarified in the table caption.
  7. The paper would benefit from a brief discussion of how the method scales with automaton size. Table 7 shows automata ranging from 21 states (Sudoku) to ~19k states (Spider), but there is no analysis of how inference cost scales in practice with $|S|$ and $|E|$, which would help practitioners assess applicability to larger schemas.

Circularity Check

0 steps flagged

No significant circularity. The algorithm is derived from standard HMM forward-backward message passing and arithmetic circuit depth-reduction; the one self-citation (Dang et al. [2]) provides a reformulation of FAs as graphical models that is independently verifiable and not load-bearing for the core sampling or complexity claims.

full rationale

The paper's central technical contribution—exact sampling from the constrained mean-field posterior p_theta(x0|xt,C) proportional to p_theta(x0|xt) * 1[x0 in C]—is derived from first principles using standard hidden Markov model forward-backward message passing (Appendix A) and arithmetic circuit depth-reduction techniques (Valiant et al. [30], Zhang et al. [36]). The product construction in Section 4.2 is self-contained: it reweights the emission factors of the FA-induced chain graphical model p_M with the mean-field predictions p_theta, yielding a new chain-structured model from which exact samples are drawn via ancestral sampling. The log-depth tree sampling algorithm (Section 4.3, Algorithm 1) is proven correct in Appendix B by induction on recursion depth, using d-separation in the HMM—no self-citation is invoked for the proof. The one self-citation, Dang et al. [2], is referenced for the FA-as-graphical-model formulation (Section 3.2), but this is a standard reformulation of finite automata as hidden Markov models (attributed to Rabiner and Juang [21]) and is independently verifiable. The empirical evaluation uses external benchmarks (BFCL, Spider, GSM-Symbolic, xLAM) and independent models (Dream-7B, LLaDA-8B) not authored by the present authors. The per-step approximation (enforcing constraints at each diffusion step rather than globally) is transparently acknowledged in Section 4.1 and is analogous to standard autoregressive constrained decoding; this is a modeling choice, not a circularity. The NFA 'soft proxy' issue (where p_M weights sequences by path count rather than being uniform) is acknowledged in Section 4.2 and is a known property of NFAs, not a circular definition. No step in the derivation chain reduces to its own inputs by construction.

Axiom & Free-Parameter Ledger

1 free parameters · 4 axioms · 1 invented entities

The algorithm is derived from standard mathematical axioms (HMM theory, conditional independence) and introduces no free parameters or invented entities. The primary domain assumption is that per-step constrained sampling approximates the global constrained distribution.

free parameters (1)
  • None = N/A
    The algorithm is parameter-free; it uses the pre-trained dLLM's mean-field predictions and the structure of the finite automaton as inputs without introducing fitted constants.
axioms (4)
  • standard math Finite automata can be viewed as chain-structured graphical models (HMMs) encoding constraint C as their support.
    Invoked in Section 3.2 and based on standard automata theory and hidden Markov model formulations.
  • standard math The product of a fully factorized (mean-field) distribution and a chain-structured distribution admits a tractable representation with the same chain structure.
    Invoked in Section 4.2 to justify the tractable product construction.
  • standard math Conditioning on boundary states in a Markov chain renders the internal segments conditionally independent.
    Invoked in Section 4.3 (Equation 6) to enable the divide-and-conquer tree sampling.
  • domain assumption Enforcing constraint satisfaction at each diffusion step is a sufficient proxy for sampling from the true globally constrained generative distribution.
    Invoked in Section 4.1; the paper acknowledges exact global sampling is intractable and adopts this per-step approximation.
invented entities (1)
  • None independent evidence
    purpose: N/A
    No new entities, particles, or forces are introduced. The method operates on existing model architectures and standard mathematical structures.

pith-pipeline@v1.1.0-glm · 22074 in / 2164 out tokens · 230783 ms · 2026-07-09T21:22:46.467523+00:00 · methodology

0 comments
read the original abstract

Constrained decoding is essential for serving LLMs, ensuring that generated outputs follow specific structures such as JSON schema-formatted function calls. Existing systems are designed for autoregressive models and assume left-to-right generation, masking out invalid next tokens at each step. Diffusion language models, however, break this assumption: they sample multiple positions simultaneously from a fully-factorized mean-field distribution at each denoising step. In this paper, we present an exact and tractable algorithm for sampling from the constrained mean-field posterior under any constraint expressible as a finite automaton. Viewing finite automata as graphical models, we obtain tractable representations of the constrained distribution that enable efficient inference. The approach guarantees constraint satisfaction by construction, supports both greedy and sampling-based decoding, and is compatible with parallel and block-wise decoding under arbitrary remasking schedules. Applying depth-reduction techniques from arithmetic circuit theory, we further reduce sampling depth from linear to logarithmic in the sequence length. Empirical evaluations on Dream-7B and LLaDA-8B show substantial accuracy gains across various tasks including function calling (xLAM, BFCL), planning (Sudoku, Countdown), text-to-SQL (Spider), and math reasoning (GSM-Symbolic), with little inference overhead relative to unconstrained decoding. For example, on BFCL-Live, our approach improves Dream-7B's greedy decoding accuracy from 63.9% to 71.5%, and stochastic sampling accuracy from 22.3% to 69.0%, where the unconstrained baseline collapses, with under 5% wall-clock overhead.

Figures

Figures reproduced from arXiv: 2607.07026 by Meihua Dang, Stefano Ermon.

Figure 1
Figure 1. Figure 1: (a) A finite automaton M accepting a(b|c) ∗de∗ . (b) The induced chain-structured graphical model over length-L sequences, with edge-valued latents z1:L emitting observed tokens x1:L. (c) The transition factor p(zt |zt−1), nonzero when consecutive edges chain end-to-end (dst(zt−1) = src(zt)). (d) The emission factor p(xt |zt), nonzero when xt is in the label set of edge zt. by masking each token with proba… view at source ↗
Figure 2
Figure 2. Figure 2: Chain-structured graphical model and its tree-structured equivalent. [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Runtime comparison for chain (ancestral) and tree (log￾depth) sampling on a DFA. Parallelization vs. FLOPs tradeoff. Compared to ancestral sampling, log-depth sampling increases the message-passing FLOPs by a factor of |S|, but reduces the depth of the com￾putation graph from O(L) to O(log L). This tradeoff is favorable on modern GPUs: the additional FLOPs are spent on larger matrix operations, while the n… view at source ↗
Figure 4
Figure 4. Figure 4: Accuracy vs. denoising steps on BFCL Simple split. Our method remains robust as the [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Sudoku 4×4 accuracy versus the number of prefilled digits (fewer digits indicate harder puzzles). Mf uses mean-field confidence from the base model, while Mar uses marginals under the constrained distribution. 19 [PITH_FULL_IMAGE:figures/full_fig_p019_5.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages · 4 internal anchors

  1. [1]

    Structured denoising diffusion models in discrete state-spaces

    Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg. Structured denoising diffusion models in discrete state-spaces. InAdvances in Neural Information Processing Systems, volume 34, pages 17981–17993, 2021

    work page 2021

  2. [2]

    Mitigating bias in locally constrained decoding via tractable proposals

    Meihua Dang, Linxin Song, Honghua Zhang, Jieyu Zhao, Guy Van den Broeck, and Stefano Ermon. Mitigating bias in locally constrained decoding via tractable proposals. InInternational Conference on Machine Learning, 2026

    work page 2026

  3. [3]

    XGrammar: Flexible and efficient structured generation engine for large language models.Proceedings of Machine Learning and Systems, 7, 2025

    Yixin Dong, Charlie F Ruan, Yaxing Cai, Ziyi Xu, Yilong Zhao, Ruihang Lai, and Tianqi Chen. XGrammar: Flexible and efficient structured generation engine for large language models.Proceedings of Machine Learning and Systems, 7, 2025

    work page 2025

  4. [4]

    Gemini diffusion

    Google DeepMind. Gemini diffusion. https://blog.google/innovation-and-ai/ models-and-research/google-deepmind/gemini-diffusion/, 2025. Google AI Blog

    work page 2025

  5. [5]

    Guidance: A guidance language for controlling large language models

    Guidance AI. Guidance: A guidance language for controlling large language models. https://github. com/guidance-ai/guidance, 2023

    work page 2023

  6. [6]

    Hopcroft, Rajeev Motwani, and Jeffrey D

    John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman.Introduction to Automata Theory, Languages, and Computation. Pearson, 3 edition, 2006

    work page 2006

  7. [7]

    Mercury: Ultra-Fast Language Models Based on Diffusion

    Inception Labs, Samar Khanna, Siddhant Kharbanda, Shufan Li, Harshit Varma, Eric Wang, Sawyer Birnbaum, Ziyang Luo, Yanis Miraoui, Akash Palrecha, Stefano Ermon, Aditya Grover, and V olodymyr Kuleshov. Mercury: Ultra-Fast Language Models Based on Diffusion.arXiv preprint arXiv:2506.17298, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  8. [8]

    Spider 2.0: Evaluating language models on real-world enterprise text-to-SQL workflows

    Fangyu Lei, Jixuan Chen, Yuxiao Ye, Ruisheng Cao, Dongchan Shin, Hongjin Su, Zhaoqing Suo, Hongcheng Gao, Wenjing Hu, Pengcheng Yin, Victor Zhong, Caiming Xiong, Ruoxi Sun, Qian Liu, Sida Wang, and Tao Yu. Spider 2.0: Evaluating language models on real-world enterprise text-to-SQL workflows. InInternational Conference on Learning Representations, 2025

    work page 2025

  9. [9]

    APIGen: Automated pipeline for generating verifiable and diverse function-calling datasets

    Zuxin Liu, Thai Hoang, Jianguo Zhang, Ming Zhu, Tian Lan, Shirley Kokane, Juntao Tan, Weiran Yao, Zhiwei Liu, Yihao Feng, Rithesh Murthy, Liangwei Yang, Silvio Savarese, Juan Carlos Niebles, Huan Wang, Shelby Heinecke, and Caiming Xiong. APIGen: Automated pipeline for generating verifiable and diverse function-calling datasets. InAdvances in Neural Inform...

    work page 2024

  10. [10]

    Discrete diffusion modeling by estimating the ratios of the data distribution

    Aaron Lou, Chenlin Meng, and Stefano Ermon. Discrete diffusion modeling by estimating the ratios of the data distribution. InInternational Conference on Machine Learning, 2024

    work page 2024

  11. [11]

    GSM-Symbolic: Understanding the limitations of mathematical reasoning in large language models

    Seyed Iman Mirzadeh, Keivan Alizadeh, Hooman Shahrokhi, Oncel Tuzel, Samy Bengio, and Mehrdad Farajtabar. GSM-Symbolic: Understanding the limitations of mathematical reasoning in large language models. InInternational Conference on Learning Representations, 2025

    work page 2025

  12. [12]

    Constrained decoding of diffusion LLMs with context-free grammars

    Niels Mündler, Jasper Dekoninck, and Martin Vechev. Constrained decoding of diffusion LLMs with context-free grammars. InInternational Conference on Learning Representations, 2026

    work page 2026

  13. [13]

    Large language diffusion models

    Shen Nie, Fengqi Zhu, Zebin You, Xiaolu Zhang, Jingyang Ou, Jun Hu, Jun Zhou, Yankai Lin, Ji-Rong Wen, and Chongxuan Li. Large language diffusion models. InAdvances in Neural Information Processing Systems, 2025

    work page 2025

  14. [14]

    Your absorbing discrete diffusion secretly models the conditional distributions of clean data

    Jingyang Ou, Shen Nie, Kaiwen Xue, Fengqi Zhu, Jiacheng Sun, Zhenguo Li, and Chongxuan Li. Your absorbing discrete diffusion secretly models the conditional distributions of clean data. InInternational Conference on Learning Representations, 2025

    work page 2025

  15. [15]

    Flexible and efficient grammar-constrained decoding

    Kanghee Park, Timothy Zhou, and Loris D’Antoni. Flexible and efficient grammar-constrained decoding. InInternational Conference on Machine Learning, 2025

    work page 2025

  16. [16]

    Patil, Tianjun Zhang, Xin Wang, and Joseph E

    Shishir G. Patil, Tianjun Zhang, Xin Wang, and Joseph E. Gonzalez. Gorilla: Large language model connected with massive apis. InAdvances in Neural Information Processing Systems, 2024

    work page 2024

  17. [17]

    Gonzalez

    Shishir G Patil, Huanzhi Mao, Fanjia Yan, Charlie Cheng-Jie Ji, Vishnu Suresh, Ion Stoica, and Joseph E. Gonzalez. The Berkeley function calling leaderboard (BFCL): From tool use to agentic evaluation of large language models. InInternational Conference on Machine Learning, 2025

    work page 2025

  18. [18]

    Reverend Bayes on inference engines: A distributed hierarchical approach

    Judea Pearl. Reverend Bayes on inference engines: A distributed hierarchical approach. InProceedings of the AAAI Conference on Artificial Intelligence, 1982. 10

    work page 1982

  19. [19]

    Morgan Kaufmann, 1988

    Judea Pearl.Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, 1988

    work page 1988

  20. [20]

    Synchromesh: Reliable code generation from pre-trained language models

    Gabriel Poesia, Alex Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. Synchromesh: Reliable code generation from pre-trained language models. InInternational Conference on Learning Representations, 2022

    work page 2022

  21. [21]

    An introduction to hidden Markov models.IEEE ASSP Magazine, 3(1), 1986

    Lawrence Rabiner and Biinghwang Juang. An introduction to hidden Markov models.IEEE ASSP Magazine, 3(1), 1986

    work page 1986

  22. [22]

    Simple and effective masked diffusion language models

    Subham Sahoo, Marianne Arriola, Yair Schiff, Aaron Gokaslan, Edgar Marroquin, Justin Chiu, Alexander Rush, and V olodymyr Kuleshov. Simple and effective masked diffusion language models. InAdvances in Neural Information Processing Systems, volume 37, pages 130136–130184, 2024

    work page 2024

  23. [23]

    PICARD: Parsing incrementally for constrained auto-regressive decoding from language models

    Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau. PICARD: Parsing incrementally for constrained auto-regressive decoding from language models. InProceedings of the Conference on Empirical Methods in Natural Language Processing, 2021

    work page 2021

  24. [24]

    Tractable operations for arithmetic circuits of probabilistic models

    Yujia Shen, Arthur Choi, and Adnan Darwiche. Tractable operations for arithmetic circuits of probabilistic models. InAdvances in Neural Information Processing Systems, volume 29, 2016

    work page 2016

  25. [25]

    Simplified and generalized masked diffusion for discrete data

    Jiaxin Shi, Kehang Han, Zhe Wang, Arnaud Doucet, and Michalis Titsias. Simplified and generalized masked diffusion for discrete data. InAdvances in Neural Information Processing Systems, volume 37, pages 103131–103167, 2024

    work page 2024

  26. [26]

    Constrained language models yield few-shot semantic parsers

    Richard Shin, Christopher Lin, Sam Thomson, Charles Chen, Subhro Roy, Emmanouil Antonios Platanios, Adam Pauls, Dan Klein, Jason Eisner, and Benjamin Van Durme. Constrained language models yield few-shot semantic parsers. InProceedings of the Conference on Empirical Methods in Natural Language Processing, 2021

    work page 2021

  27. [27]

    Seed Diffusion: A Large-Scale Diffusion Language Model with High-Speed Inference

    Yuxuan Song, Zheng Zhang, Cheng Luo, Pengyang Gao, Fan Xia, Hao Luo, Zheng Li, Yuehang Yang, Hongli Yu, Xingwei Qu, et al. Seed diffusion: A large-scale diffusion language model with high-speed inference.arXiv preprint arXiv:2508.02193, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  28. [28]

    DINGO: Constrained inference for diffusion LLMs

    Tarun Suresh, Debangshu Banerjee, Shubham Ugare, Sasa Misailovic, and Gagandeep Singh. DINGO: Constrained inference for diffusion LLMs. InAdvances in Neural Information Processing Systems, 2025

    work page 2025

  29. [29]

    SynCode: LLM generation with grammar augmentation.Transactions on Machine Learning Research, 2025

    Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, and Gagandeep Singh. SynCode: LLM generation with grammar augmentation.Transactions on Machine Learning Research, 2025

    work page 2025

  30. [30]

    L. G. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff. Fast parallel computation of polynomials using few processors.SIAM Journal on Computing, 12(4):641–644, 1983

    work page 1983

  31. [31]

    A compositional atlas of tractable circuit operations for probabilistic inference

    Antonio Vergari, YooJung Choi, Anji Liu, Stefano Teso, and Guy Van den Broeck. A compositional atlas of tractable circuit operations for probabilistic inference. InAdvances in Neural Information Processing Systems, 2021

    work page 2021

  32. [32]

    Efficient Guided Generation for Large Language Models

    Brandon T. Willard and Rémi Louf. Efficient guided generation for large language models.arXiv preprint arXiv:2307.09702, 2023

    work page internal anchor Pith review Pith/arXiv arXiv 2023

  33. [33]

    Diffusion of thought: Chain-of-thought reasoning in diffusion language models

    Jiacheng Ye, Shansan Gong, Liheng Chen, Lin Zheng, Jiahui Gao, Han Shi, Chuan Wu, Xin Jiang, Zhenguo Li, Wei Bi, and Lingpeng Kong. Diffusion of thought: Chain-of-thought reasoning in diffusion language models. InAdvances in Neural Information Processing Systems, 2024

    work page 2024

  34. [34]

    Dream 7B: Diffusion Large Language Models

    Jiacheng Ye, Zhihui Xie, Lin Zheng, Jiahui Gao, Zirui Wu, Xin Jiang, Zhenguo Li, and Lingpeng Kong. Dream 7B: Diffusion large language models.arXiv preprint arXiv:2508.15487, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  35. [35]

    Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-SQL task

    Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, Zilin Zhang, and Dragomir Radev. Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-SQL task. InProceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, 2018

    work page 2018

  36. [36]

    Restructuring tractable probabilistic circuits

    Honghua Zhang, Benjie Wang, Marcelo Arenas, and Guy Van den Broeck. Restructuring tractable probabilistic circuits. InInternational Conference on Artificial Intelligence and Statistics, 2025

    work page 2025

  37. [37]

    Lookahead-then- Verify: Reliable constrained decoding for diffusion LLMs under context-free grammars.arXiv preprint arXiv:2602.00612, 2026

    Yitong Zhang, Yongmin Li, Yuetong Liu, Jia Li, Xiaoran Jia, Zherui Li, and Ge Li. Lookahead-then- Verify: Reliable constrained decoding for diffusion LLMs under context-free grammars.arXiv preprint arXiv:2602.00612, 2026. 11

    work page arXiv 2026

  38. [38]

    Gonzalez, Clark Barrett, and Ying Sheng

    Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E. Gonzalez, Clark Barrett, and Ying Sheng. SGLang: Efficient execution of structured language model programs. InAdvances in Neural Information Processing Systems, 2024. A Forward-Backward Inference for Chain-Structured Graph...

    work page 2024

  39. [39]

    Samplez m fromp(z m |z ℓ, zr)∝p(z m |z ℓ)·p(z r |z m). 13

    work page

  40. [40]

    Recursively samplex ℓ:m−1 from the left subproblem with endpoints(z ℓ, zm)

    work page

  41. [41]

    name": "calculate_triangle_area

    Recursively samplex m:r−1 from the right subproblem with endpoints(z m, zr). Step 1 is a categorical sampling problem over the finite state space S, and the unnormalized scores can be summed and normalized exactly in O(|S|). By the inductive hypothesis, steps 2 and 3 produce exact samples from their respective conditional distributions. By d-separation in...

    work page 2023