A benchmark measuring the per-token latency overhead of constrained decoding for structured output generation in LLM serving.
Compares three strategies under a controlled synthetic setup:
- Free decoding — no constraints
- Token healing — post-process repair after free decode
- FSM guided decoding — per-token logit masking via finite-state machine
For full architecture, methodology, and design decisions, see design.md.
Almost every production LLM serving system enforces structured outputs: JSON mode, function call arguments, schema validation. The mechanism is logit masking at each decode step.
The cost of that masking is not obvious. This project measures it precisely and breaks it down into components.
For each combination of schema type, string length, and model confidence:
- per-token latency for each decoding strategy
- slowdown of FSM masking vs free baseline
- component breakdown of FSM step cost
- valid JSON output rate per strategy
- one-time FSM build cost, cold vs warm
Mean latency per decode step:
free: 0.234 ms healing: 0.232 ms (0.99x — effectively free) fsm: 0.459 ms (1.96x slowdown)
FSM step breakdown:
model logits: 14.9% mask build: 36.8% mask apply: 47.4% state update: 0.2%
One-time FSM build:
cold build: 33.0 ms mean warm build: 22.0 ms mean
Valid JSON output rate:
free: 0.933 healing: 0.929 fsm: 0.784
Token healing is effectively free during decode. It adds near-zero per-token cost but cannot enforce structural validity online.
FSM guided decoding adds roughly 2x per-token overhead. This is consistent across schema types, string lengths, and oracle confidence levels.
The dominant cost is mask construction and application, not grammar state tracking. Mask build and mask apply account for over 84% of FSM step time. Grammar state update accounts for only 0.2%.
The overhead is deterministic with respect to model confidence. Changing confidence from 0.6 to 0.95 does not change FSM slowdown. The masking cost is structural, not model-dependent.
Cold-start FSM build includes runtime warmup effects. Warm builds in long-running serving workers are faster. For serving, the warm build cost is the operationally relevant number.
guided-decoding-bench/ ├── src/ │ ├── init.py │ ├── config.py │ ├── vocab.py │ ├── schemas.py │ ├── oracle_model.py │ ├── fsm.py │ ├── free_decode.py │ ├── healing.py │ ├── guided_decode.py │ ├── benchmark.py │ ├── metrics.py │ └── analysis.py ├── results/ ├── plots/ ├── LICENSE ├── design.md ├── README.md ├── requirements.txt └── run.py
python3 -m venv venv source venv/bin/activate pip install -r requirements.txt python run.py
Outputs:
results/sweep_results.csv results/summary.txt plots/slowdown_vs_schema.png plots/slowdown_vs_confidence.png plots/fsm_component_breakdown.png plots/valid_rate.png plots/slowdown_vs_string_len.png
This benchmark isolates the overhead of constrained decoding in a controlled synthetic setup. It does not model:
- real transformer forward pass cost
- BPE tokenizer integration
- multi-token prefix trees
- batch masking across concurrent requests
- full CFG or Earley parser strategies
The results should be read as an isolation benchmark for masking overhead, not as a complete production serving benchmark.
MIT License. See LICENSE for details.
Joao Felipe De Souza 2026