# Efficient Guided Generation for LLMs

**Authors:** Brandon T. Willard, Rémi Louf  
**arXiv:** [2307.09702](https://arxiv.org/abs/2307.09702)  
**Date:** 2023-07-19  
**Summary page:** https://www.summarizepaper.com/en/paper/2307.09702v1/

## Key points

- Authors present an efficient approach to guiding language model text generation using regular expressions and context-free grammars
- Method adds minimal overhead to token sequence generation process, making guided generation practical
- Implementation available in open-source Python library Outlines
- Finite State Machine (FSM) approach can be expanded to Context-Free Grammars (CFGs) and LALR(1) parsers for efficient guided generation based on popular data formats and programming languages such as JSON, Python, and SQL
- Language Model (LM) token sampling and guided generation processes explained, highlighting the importance of sequences ending with a special <EOS> token
- Algorithm 1 presented as a basic LM token sampling method that iteratively samples new tokens until <EOS> is generated
- Different methods for generating samples from this distribution discussed, including greedy decoding

## Summary

, , , , 

In this article, the authors present an efficient approach to guiding language model text generation using regular expressions and context-free grammars. The method described adds minimal overhead to the token sequence generation process, making guided generation practical. The implementation of this approach is available in the open-source Python library Outlines. Furthermore, the authors discuss how their Finite State Machine (FSM) approach can be expanded to Context-Free Grammars (CFGs) and LALR(1) parsers for efficient guided generation based on popular data formats and programming languages such as JSON, Python, and SQL. The article also delves into Language Model (LM) token sampling and guided generation processes. It explains how tokens are sampled from a LM-generated random variable with trained parameters, where the vocabulary of the LM consists of strings from a fixed alphabet. The authors highlight the importance of sequences that end with a special <EOS> token in the LM setting. Additionally, Algorithm 1 is presented as a basic LLM token sampling method that iteratively samples new tokens until the <EOS> token is generated. The article discusses different methods for generating samples from this distribution, including greedy decoding. Overall, this comprehensive article provides insights into efficient guided text generation using regular expressions and context-free grammars within language models. It offers practical implementations and algorithms for enhancing text generation processes while minimizing overhead.