How fast can grammar-structured generation be?

🌈 Abstract

The article discusses the use of structured generation to improve the results obtained from large language models (LLMs). It focuses on ensuring that the costs of structured generation are low enough for widespread use, while also maintaining flexibility in the structure being imposed.

🙋 Q&A

[01] Introduction

1. What are the key goals and challenges discussed in the introduction?

• The article discusses the goal of ensuring that the costs of structured generation are low enough for widespread use, while also maintaining flexibility in the structure being imposed.
• It notes that performance and flexibility are often a tricky trade-off, and describes how the author has devised an extension of the regular language approach to context-free languages that carries theoretical performance and scaling guarantees similar to the regular language/regex case.

2. What are the key results demonstrated in the introduction?

• The author demonstrates an implementation of the context-free grammar-structured generation approach that adds negligible sub-millisecond average impact on generation.
• The author shows that this approach can produce output that follows a specified context-free grammar, while leaving enough room for the model to generate useful results.

[02] An Embedded SQL Grammar

1. What is the goal of the SQL grammar example?

• The goal is to generate SQL statements that return values from the "id" column of the "users" table, while following a specific context-free grammar.

2. How does the author implement the SQL grammar-structured generation?

• The author defines a formal context-free grammar that specifies the desired prompt text and a single fenced Markdown-style code block containing only valid SQL.
• The author creates a CFG Guide that follows the outlines API to sample according to this grammar.
• The author demonstrates that the generated output follows the specified grammar.

3. What are the performance results of the SQL grammar-structured generation?

• The author performs profiling and shows that the CFG-structured generation adds on average sub-millisecond latencies, and barely breaks a millisecond at maximum.

[03] C Grammar Comparisons

1. What is the goal of the C grammar comparison?

• The goal is to compare the performance of the author's CFG-structured generation approach to the grammar-structured generation in llama.cpp, using a more complex C grammar.

2. How does the author implement the C grammar-structured generation?

• The author uses a comprehensive C grammar adapted from a Yacc specification, which has 211 rules compared to the 21 rules in the C grammar provided by llama.cpp.
• The author applies the same settings to the author's CFG-structured generation approach using a c_logits_processor instance.

3. What are the performance results of the C grammar-structured generation?

• The author's CFG-structured generation approach introduces a latency of around 0.5 ms/token on average, while llama.cpp's grammar-structured generation adds approximately 101 ms/token to each sampling step.

4. How do the results compare between the two approaches?

• The author's CFG-structured generation approach significantly outperforms llama.cpp's grammar-structured generation, even with a much larger and more complex grammar.

[04] Going Forward

1. What are the key points about the author's approach going forward?

• The author's approach is able to structure generation according to non-trivial context-free grammars and very large vocabularies with only a negligible cost.
• The author's current implementation is unoptimized pure Python, and the author has numerous optimizations lined up that will bring down the latency significantly.
• The author also has natural extensions to non-deterministic context-free grammars, non-trivial lexer-level logic, and efficient semantic constraints.