  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.
