REVIEW 6 cited by
Automata-based constraints for language model decoding
Not yet reviewed by Pith; the record is open.
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
Automata-based constraints for language model decoding
read the original abstract
Language models (LMs) are often expected to generate strings in some formal language; for example, structured data, API calls, or code snippets. Although LMs can be tuned to improve their adherence to formal syntax, this does not guarantee conformance, especially with smaller LMs suitable for large-scale deployment. In addition, tuning requires significant resources, making it impractical for uncommon or task-specific formats. To prevent downstream parsing errors we would ideally constrain the LM to only produce valid output, but this is severely complicated by tokenization, which is typically both ambiguous and misaligned with the formal grammar. We solve these issues through the application of automata theory, deriving an efficient closed-form solution for the regular languages, a broad class of formal languages with many practical applications, including API calls or schema-guided JSON and YAML. We also discuss pragmatic extensions for coping with the issue of high branching factor, and extend our techniques to deterministic context-free languages, which similarly admit an efficient closed-form solution. Previous work on this topic (Willard and Louf, 2023) layers bespoke solutions onto automata, leading to problems with speed, correctness, and extensibility. Instead, we reformulate the entire task in terms of automata so we can leverage well-studied and well-optimized algorithms. Our system compiles constraints ~7,000x faster, is provably correct, and can be extended in a modular fashion.
Forward citations
Cited by 6 Pith papers
-
LatticeBridge: Rare-Event Sequential Inference for Faithful Structured Sequence Synthesis
A twisted sequential Monte Carlo decoder with surface automata improves exact constraint satisfaction in structured text generation over standard decoding baselines across three benchmarks.
-
Vectorizing the Trie: Efficient Constrained Decoding for LLM-based Generative Retrieval on Accelerators
Constrained decoding for generative retrieval can be made accelerator-friendly by flattening the trie of valid items into a CSR sparse matrix and doing branch-free vectorized lookups.
-
Correctness-Guaranteed Code Generation via Constrained Decoding
A constrained decoding algorithm using a context-sensitive tree of parsers guarantees generated programs in the sLua language are semantically correct and, for the game API, run without errors.
-
Frustratingly Simple Black-Box Adaptation of Language Models via Logit Bias
A fixed logit-bias vector estimated from black-box rollouts gives small accuracy gains and modest length compression, far below LoRA fine-tuning.
-
Beyond Perplexity: UTF-8 Validity in Byte-aware Language Models
A 355M-parameter byte-level LM on 80B multilingual tokens exhibits UTF-8 validity converging after 4.2B tokens versus 2.1B for perplexity, with higher validity on rare characters than common ones.
-
Precise Robot Command Understanding Using Grammar-Constrained Large Language Models
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.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.