llguidance

llguidance provides bindings and integrations across several environments:

Language Bindings

• Rust: Available via the parser directory.
• C and C++: Header available at parser/llguidance.h.
• Python: Available via the llguidance_py package (see python/llguidance/_lib.pyi for type hints).

Major Integrations

• OpenAI: Powers Structured Output (JSON Schema only).
• llama.cpp: Available via -DLLAMA_LLGUIDANCE=ON in cmake or via the Guidance Python package.
• vLLM: Integrated in recent versions.
• SGLang: Use --grammar-backend llguidance. When passing Lark grammars, prefix them with %llguidance {} (similar to llama.cpp).
• Chromium: Used for JSON Schema enforcement in window.ai.
• Other: Guidance (Python), LLGTRT (TensorRT-LLM), mistral.rs, and onnxruntime-genai.

llguidance is a library for constrained decoding (structured outputs) for Large Language Models (LLMs). It enforces arbitrary context-free grammars on LLM outputs with high performance (approximately 50μs of CPU time per token for a 128k tokenizer) and negligible startup costs.

Supported Grammar Formats

• JSON schemas: A large subset is supported.
• Regular expressions.
• Context-free grammars: Uses a variation of the Lark format, which can include embedded JSON schemas and regular expressions.
• llguidance format: An internal JSON-based format (being deprecated in favor of the Lark-like format).

Core Mechanism

Given a context-free grammar, a tokenizer, and a prefix of tokens, llguidance computes a token mask—a set of valid tokens from the tokenizer that can follow the current prefix while remaining compliant with the grammar. It achieves this by traversing a prefix tree (trie) using an Earley-based parser and a lexer based on regular expression derivatives.

Greedy Grammars are designed to handle programming language syntax by using standard lexer rules. They are defined using the greedy_grammar(grammar, skip=whitespace_regex) function and can be invoked from within a lazy grammar using gen(grammar=...).

Key characteristics of Greedy Grammars:

• Longest Match: Unlike lazy grammars, the greedy lexer takes the longest match for every lexeme (standard lexer behavior).
• Skipping: It automatically skips over any content that matches the provided skip regex (e.g., whitespace).
• Isolation: From the perspective of the outer (lazy) parser, a greedy_grammar() construct is treated as a single token, meaning the lexers do not interact.
• Lexeme Construction: Lexemes in greedy grammars are constructed from regex() nodes and string literals (note that gen() nodes are not allowed inside the greedy grammar definition).

def identifier():
  return regex(r'[a-zA-Z_][a-zA-Z0-9_]*')

def sql_program():
  return select([
    "SELECT" + identifier() + "FROM" + identifier() + 
    optional("WHERE" + identifier() + "=" + ...),
    ...
  ])

# Define the greedy grammar with whitespace skipping
def sql():
  return greedy_grammar(sql_program(), skip=r'\s*')

# Use the greedy grammar inside a lazy grammar
def my_program():
  return f"""
Query to list all animals
```sql
{gen(grammar=sql(), suffix="```")}
"""

In llguidance, Lazy Grammars are produced when using gen() without a stop= parameter. These grammars use a lexer (or scanner) that treats literal strings and regular expressions inside gen() calls as lexemes (terminals).

Key characteristics of Lazy Grammars:

• Shortest Match: The lazy lexer takes the shortest match for every lexeme available in a given parser state.
• Contextual Lexemes: Lexemes are only enabled in specific rows where the Earley parser allows them, making them inherently contextual.
• Regex Requirement: All regexes used for lexemes must never match an empty string.
• Performance Tip: To ensure high performance, use gen(regex=...) instead of using single-character strings or functions like zero_or_more(" ").

# Example of a lazy grammar structure
"Name: " + gen(regex=r'[A-Z][a-z]+', stop='\n') + "\n" + 
select([
  "Married? " + gen(regex=r'Yes|No'),
  "Age: " + gen(regex=r'\d+', stop='\n')
]) + "\n"

By default, llguidance treats sequences that look like special tokens (e.g., <|eot_id|>) as regular bytes. If you want these sequences to be treated as actual special tokens during tokenization, you must prefix the byte sequence with the marker byte 0xFF (255), defined as TokTrie::SPECIAL_TOKEN_MARKER.

Implementation Details

• Why 0xFF?: The byte 0xFF is not a valid UTF-8 byte, ensuring it does not occur in standard text inputs.
• Rust Users: You cannot include 0xFF in a &str; you must work with &[u8].
• Python Users: Be careful with encoding. Use b"\xFF" to represent the marker byte. Note that "\xFF".encode("utf-8") results in the two-byte sequence b"\xC3\xBF", which is not the correct marker.
• When to use: You generally only need to manage these marker bytes when manually constructing the token array for a TokTrie constructor.

# Correct way to represent the marker byte in Python
marker = b"\xFF"

# Incorrect way (this encodes the character, resulting in two bytes)
# incorrect = "\xFF".encode("utf-8") # b'\xc3\xbf'

The traversal algorithm computes the set of allowed tokens by traversing the trie in DFS order. The results are stored in a logits array where entries with a value of 0.0 indicate an allowed token.

Traversal Logic

1. DFS Order: The tree is laid out in memory in DFS order to allow for efficient iteration without explicit recursion.
2. Byte Validation: As the algorithm traverses, it checks if a byte is allowed (byte_allowed(n.byte)). If allowed, it pushes the byte to a stack and marks the corresponding token_id in the logits array as 0.0.
3. Stack Management: The algorithm uses pop_bytes() to manage the stack of bytes. This is used to backtrack to parent nodes when a branch is completed or when a node is skipped.
4. Performance Optimization: The implementation avoids recursion by using a loop and uses bit operations for pop_bytes to ensure the branch is branchless, minimizing mispredictions.

// Example of the logic used to mark allowed tokens
let mut logits = vec![-100.0; VOCAB_SIZE + 1];

// Simplified traversal logic
fn traverse(mut p: usize, nodes: &[TrieNode], logits: &mut [f32]) {
    // ... traversal logic that sets logits[n.token_id] = 0.0;
}