# Automata-based constraints for language model decoding

**Authors:** Terry Koo, Frederick Liu, Luheng He  
**arXiv:** [2407.08103](https://arxiv.org/abs/2407.08103)  
**Date:** 2024-07-11  
**Summary page:** https://www.summarizepaper.com/en/arxiv-id/2407.08103v1/

## Key points

- Growing demand for language models that can generate strings in formal languages such as structured data, API calls, or code snippets
- Challenge of ensuring complete conformance to formal syntax, especially for smaller language models intended for widespread deployment
- Proposal to leverage automata theory to develop an efficient solution for regular languages and deterministic context-free languages
- Approach focuses on pre-computing matches based on per-token decoding logits to reduce computational complexity and facilitate easy deployment at scale
- Comparison with existing methods like Outlines and SynCode, highlighting the more generalized and user-friendly framework with support for wildcard matching enhancements
- Efficiency in handling grammars compared to systems like Synchromesh or Guidance, without sacrificing speed for flexibility

## Summary

, , , , 

In the field of language modeling, there is a growing demand for models that can generate strings in formal languages such as structured data, API calls, or code snippets. While language models (LMs) can be fine-tuned to improve their adherence to formal syntax, ensuring complete conformance remains a challenge. This is especially true for smaller LMs intended for widespread deployment. Tuning LMs requires substantial resources and may not be feasible for uncommon or task-specific formats. To address the issue of downstream parsing errors caused by invalid output from LMs, our ideal solution would restrict the LM to produce only valid strings. However, this task is complicated by tokenization, which often does not align perfectly with formal grammar rules. To tackle these challenges effectively, we propose leveraging automata theory to develop an efficient solution for regular languages—a class of formal languages with practical applications like API calls and schema-guided JSON and YAML. By applying automata-theoretic principles, we can ensure that the generated outputs adhere to the specified grammar rules while also addressing issues related to high branching factors. Furthermore, we extend our techniques to deterministic context-free languages, offering a closed-form solution that is both flexible and powerful. Our approach stands out for its simplicity and scalability across different LM architectures. Unlike some existing methods that rely on bespoke algorithms or dynamic vocabulary matching during decoding steps, our technique pre-computes matches statically based on per-token decoding logits. This streamlined process reduces computational complexity and facilitates easy deployment at scale. In comparison to related work such as Outlines and SynCode which also utilize finite-state automata (FSA) but with different strategies like manual indexing operations or lexer token unrolling, our approach offers a more generalized and user-friendly framework with support for wildcard matching enhancements. Additionally, our method demonstrates efficiency in handling grammars compared to systems like Synchromesh or Guidance which may sacrifice speed for flexibility. Looking ahead, our approach opens up various applications due to its clean design and efficiency. For instance, it can be applied effectively in generating JSON expressions with precise structure and content alignment. Overall, our innovative use of automata theory in language model decoding presents a promising avenue for enhancing string generation accuracy in diverse formal language contexts while maintaining computational efficiency at scale.