Grammar-Forced Drafts
Relevant source files
The following files were used as context for generating this wiki page:
Grammar-Forced Drafts accelerate model inference by using a grammar as a source for speculative decoding. In workloads with constrained outputs, such as JSON or function calling, certain tokens become deterministic based on the grammar. The system identifies these spans—including brackets, quotes, key names, and separators—and proposes them as drafts with high acceptance probability.
Sources: c/grammar.h:3-11, README.md:162-166
The grammar serves only as a draft source and never as a sampling constraint. If the grammar is incorrect or out of sync, the engine rejects the drafts but produces identical output to an unconstrained run. This fail-soft design ensures that speed optimizations never corrupt the model's precision or semantics.
Sources: c/grammar.h:13-16, schema_gbnf.h:11-15
Architecture and Components
The system uses a Pushdown Automaton (PDA) that operates at the byte level to evaluate a subset of GBNF (Gerhard's Backus-Naur Form).
Data Structures
| Structure | Description |
|---|---|
Grammar | A collection of GBNF rules and the root entry point. |
GrCls | A bitmap representing a set of admissible bytes (0-255). |
GrState | The current state of the PDA walker, tracking multiple stacks for ambiguity. |
GrStack | A stack of frames representing the current position in the grammar. |
Sources: c/grammar.h:34-45
Speculative Flow
The following diagram illustrates how the grammar informs the draft process:
A draft is "forced" when only one byte is legally allowed by the grammar and the parse cannot terminate at that point.
Sources: c/grammar.h:26-30, c/grammar.h:312-315
GBNF Grammar Subset
The engine parses a specific subset of GBNF, which includes the following features:
- Literals: Strings enclosed in quotes (e.g.,
"{"). - Character Classes: Byte sets (e.g.,
[a-z0-9]) including negations ([^...]). - Repetition: Postfix operators
?(optional),*(zero or more), and+(one or more). - Alternates: Choice between paths using the
|operator. - Recursion: Support for nested rules, protected by a maximum depth to prevent infinite loops.
Sources: c/grammar.h:18-25
JSON Schema Compilation
The schema_gbnf.h header provides a compiler to transform JSON Schemas into GBNF text. This allows users to provide standard JSON Schemas instead of hand-writing GBNF.
Supported JSON Schema Features
- Objects: Properties in declared order. If
requiredis present, it must list every property to follow "strict" semantics. - Arrays: Item types with
minItems(0 or 1). - Primitives:
string,number,integer,boolean,null. - Constraints:
enumandconstfor strings and numbers.
Sources: schema_gbnf.h:17-33
The jws (JSON WhiteSpace) Rule
The compiler injects jws rules at every separator (commas, colons, brackets). This allows the grammar to tolerate arbitrary model-generated whitespace while remaining strict enough to force key names and structural literals.
Sources: schema_gbnf.h:92-105, schema_gbnf.h:177
Sources: schema_gbnf.h:134-171
API Integration
The openai_server.py gateway exposes grammar-forced drafts through the response_format parameter in completions and chat completions.
Configuration Options
| Parameter | Type | Description |
|---|---|---|
json_object | type | Uses a generic whitespace-tolerant JSON grammar. |
json_schema | type | Compiles the provided schema into a specific GBNF. |
gbnf | type | Custom colibri extension for raw GBNF strings. |
Sources: c/openai_server.py:488-518
When the gateway receives a response_format request, it translates the format into a GBNF string. This string is passed to the engine via the SUBMIT header.
# Generic JSON GBNF used for json_object type
GENERIC_JSON_GBNF = (
'root ::= jws jval jws\n'
'jval ::= jobj | jarr | jstr | jnum | "true" | "false" | "null"\n'
'jobj ::= "{" jws ( jstr jws ":" jws jval jws ( "," jws jstr jws ":" jws jval jws )* )? "}"\n'
...
)
Sources: c/openai_server.py:448-459
Conclusion
Grammar-Forced Drafts provide a mechanism for accelerating structured output by identifying deterministic byte sequences. By compiling JSON Schemas into GBNF and using a PDA walker to identify unique legal transitions, the system can generate multi-token spans that are verified in a single forward pass. This process remains safe due to its decoupling from actual sampling, acting only as a performance optimizer.
Sources: c/grammar.h:3-16, schema_gbnf.h:7-15