Structured Output from LLMs: Grammars, Regex, and State Machines
0:00 Introduction: LLMs can transform natural language into structured formats like JSON for various applications, but challenges arise in ensuring consistent formatting and avoiding extraneous information.
1:06 OpenAI API Example: OpenAI's API supports structured output generation using Pydantic and Zod schemas for type validation, increasing format consistency. However, current support is limited to basic features, excluding regex and custom validators.
3:02 Outlines Library Example: The open-source Outlines library enables structured output with any LLM, converting schemas to regex for matching. It also allows for direct regex-based output generation.
4:57 Finite State Machines and Regex: Regular expressions are linked to finite state machines (FSMs), which are used to validate output against defined patterns. Each regex has a corresponding FSM.
5:58 Regex Matching with LLMs: LLMs can generate regex-compliant outputs by tracking the current state in the FSM during token generation, filtering invalid tokens, and sampling from valid ones. Pre-computing valid tokens for each state enhances efficiency.
8:41 Context-Free Grammars: For complex nested structures, context-free grammars (CFGs) and pushdown automata (PDA) are necessary, offering greater expressiveness than regular languages.
9:40 Incremental Parsing of CFGs: Incremental parsing checks the validity of generated prefixes against the CFG at each step, but it's computationally expensive due to per-token checks.
11:22 Pushdown Automata: PDAs provide a faster approach to CFG-based generation, similar to FSMs but with a stack for tracking nested structures. This allows pre-computation of valid tokens for state-stack combinations.
12:18 Token-Terminal Mismatch Problem: Combining CFGs with LLMs introduces a mismatch between grammar terminals and LLM tokens, as tokenization boundaries don't align with grammar elements.
14:26 Vocabulary-Aligned Subgrammars & State Machine Composition: Recent research addresses the mismatch problem through vocabulary-aligned subgrammars (tracking both scanner and parser positions) and state machine composition (combining PDA and tokenizer FSMs).
16:06 Format Restriction and LLM Performance: Overly strict format restrictions can negatively impact LLM accuracy. A less restrictive approach to formatting is recommended for better performance.