Pith. sign in

REVIEW 12 cited by

Flexible and Efficient Grammar-Constrained Decoding

Not yet reviewed by Pith; the record is open.

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

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2502.05111 v2 pith:2DPUOPBU submitted 2025-02-07 cs.CL cs.AI

Kanghee Park , Timothy Zhou , Loris D'Antoni This is my paper
classification cs.CLcs.AI
keywords outputsalgorithmscomputecontext-freedecodingexistinggivengrammar
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

Large Language Models (LLMs) are often asked to generate structured outputs that obey precise syntactic rules, such as code snippets or formatted data. Grammar-constrained decoding (GCD) can guarantee that LLM outputs matches such rules by masking out tokens that will provably lead to outputs that do not belong to a specified context-free grammar (CFG). To guarantee soundness, GCD algorithms have to compute how a given LLM subword tokenizer can align with the tokens used by a given context-free grammar and compute token masks based on this information. Doing so efficiently is challenging and existing GCD algorithms require tens of minutes to preprocess common grammars. We present a new GCD algorithm together with an implementation that offers 17.71x faster offline preprocessing than existing approaches while preserving state-of-the-art efficiency in online mask computation.

Discussion (0). Sign in to comment.

Forward citations

Cited by 12 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Schema Key Wording as an Instruction Channel in Structured Generation under Constrained Decoding

    cs.CL 2026-04 unverdicted novelty 7.0 of 10

    Schema-key wording functions as an implicit instruction channel under constrained decoding, with experiments showing that rephrasing only the keys can substantially change accuracy on math benchmarks while prompt, mod...

  2. Continuous Diffusion Models Can Obey Formal Syntax

    cs.LG 2026-02 conditional novelty 7.0 of 10

    Training-free gradient guidance, based on the exact regex-acceptance probability under the decoder's unigram distribution, lets continuous diffusion language models satisfy regular-expression constraints.

  3. ToolPRM: Fine-Grained Inference Scaling of Structured Outputs for Function Calling

    cs.AI 2025-10 unverdicted novelty 7.0 of 10

    ToolPRM provides fine-grained intra-call process supervision via a new dataset and reward model, outperforming outcome and coarse-grained alternatives on function-calling benchmarks.

  4. Specification-Guided Synthesis of Deadlock-Free Communication Protocol Refinements with Large Language Models

    cs.SE 2026-07 conditional novelty 6.5 of 10

    Syntropy synthesises asynchronous multiparty session-type subtypes with 95.6–99.5% checker-accepted validity via LoRA fine-tuning and two-level constrained decoding.

  5. Specification-Guided Synthesis of Deadlock-Free Communication Protocol Refinements with Large Language Models

    cs.SE 2026-07 conditional novelty 6.0 of 10

    A fine-tuned LLM plus a two-level semantic checker synthesizes asynchronous multiparty session type refinements with 95.6–99.5% checker-accepted validity.

  6. Mitigating Bias in Locally Constrained Decoding via Tractable Proposals

    cs.CL 2026-06 unverdicted novelty 6.0 of 10

    Introduces (P-)GCD proposals via tensorized automata for SMC sampling that converge faster to target distributions than LCD baselines on function calling, keyword, and SQL tasks.

  7. NCO: A Versatile Plug-in for Handling Negative Constraints in Decoding

    cs.CL 2026-05 unverdicted novelty 6.0 of 10

    NCO enables efficient online pattern matching for negative hard and regex constraints in LLM decoding to prevent forbidden content without state explosion.

  8. The Format Tax

    cs.CL 2026-04 conditional novelty 6.0 of 10

    Structured-output instructions alone impose a large accuracy tax on open-weight LLMs; decoupling freeform reasoning from formatting recovers most of it, while recent closed models largely avoid the tax.

  9. Constrained Adaptive Rejection Sampling

    cs.AI 2025-10 conditional novelty 6.0 of 10

    CARS is an exact constrained-sampling algorithm that prunes all constraint-violating token continuations encountered along sampled paths, monotonically raising acceptance rate while preserving the target conditional d...

  10. The Hidden Cost of Structured Generation in LLMs: Draft-Conditioned Constrained Decoding

    cs.CL 2026-02 conditional novelty 5.0 of 10

    Draft-then-constrain decoding—first generate a free-form draft, then run format-constrained decoding conditioned on that draft—consistently improves structured-output accuracy across 1B–14B models.

  11. Large Databases Need Small, Open-Weight Language Models

    cs.AI 2026-06 unverdicted novelty 4.0 of 10

    Quantized open-weight LMs on consumer hardware match closed-source API accuracy for LM-enhanced relational operators while delivering 390x lower cost and 3.8x lower latency in the BlendSQL framework.

  12. Precise Robot Command Understanding Using Grammar-Constrained Large Language Models

    cs.RO 2026-04 conditional novelty 4.0 of 10

    A fine-tuned LLM plus grammar canonicalizer and feedback loop yields higher valid robot-command rates on HuRIC than a fine-tuned LLM or grammar NLU alone.

Pith tools