Research map / Large language models / Language, safety and interpretability
Earley-Driven Dynamic Pruning for Efficient Structured Decoding
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes ZapFormat, a dependency-graph-based dynamic pruning of Earley states plus a state cache, implemented in the Formatron constrained decoding engine, reporting up to ~2x throughput gains over XGrammar, Outlines, and lm-format-enforcer on JSON, JSON Schema, and GeoQuery tasks.
Problem
Constrained decoding with context-free grammars via Earley parsing accumulates dead or redundant parser states at every decoding step, which increases memory use and slows LLM structured generation.
Approach
Track dependencies among Earley items in a dependency graph and prune items not reachable from the last Earley set, combined with an Earley state cache, plus token mask caching, rejection prefixes and grammar transformation in one engine.
Key results
- Formatron reaches up to 12174.68 tokens/s on Gemma geoquery vs 616.66 for XGrammar, and 10639.87 vs 598.98 for Outlines-level baselines on Mistral JSON Schema throughput.
- Removing pruning drops throughput by roughly 30-50% for most models in the ablation (e.g., Gemma 3-run 10609 to 6981 tokens/s).
- Max memory usage drops only slightly with pruning (Llama3 1655.48 MB without pruning vs 1635.92 MB with).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Formatron instead of XGrammar | Gemma-2-9B · Geoquery | throughput (tokens/s): 616.66 -> 12174.68 | Helped |
| Use Formatron instead of XGrammar | Gemma-2-9B · JSON Grammar | throughput (tokens/s): 10245.04 -> 8668.69 | Hurt |
| Use Formatron instead of XGrammar | Mistral-7B · JSON Grammar | throughput (tokens/s): 15273.72 -> 12046.54 | Hurt |
| Add dynamic pruning (ablation) | Formatron · JSON Schema, 3 runs (Gemma-2-9B) | throughput (tokens/s): 6981.35 -> 10609.08 | Helped |
| Add dynamic pruning (ablation) | Formatron · JSON Schema, 3 runs (Llama-3-8B) | throughput (tokens/s): 6269.24 -> 10271.73 | Helped |
| Add dynamic pruning (ablation) | Formatron · JSON Schema, 3 runs (Mistral-7B) | throughput (tokens/s): 9727.00 -> 13522.77 | Helped |
| Add dynamic pruning (ablation) | Formatron · JSON Schema, 3 runs (Qwen2.5-7B) | throughput (tokens/s): 8635.20 -> 10537.26 | Helped |
| Add caching alongside pruning (ablation) | Formatron · JSON Schema, 3 runs (Gemma-2-9B) | throughput (tokens/s): 3595.48 -> 10609.08 | Helped |
| Add caching alongside pruning (ablation) | Formatron · JSON Schema, 3 runs (Llama-3-8B) | throughput (tokens/s): 3464.36 -> 10271.73 | Helped |
| Add caching alongside pruning (ablation) | Formatron · JSON Schema, 3 runs (Mistral-7B) | throughput (tokens/s): 8845.90 -> 13522.77 | Helped |
| Add caching alongside pruning (ablation) | Formatron · JSON Schema, 3 runs (Qwen2.5-7B) | throughput (tokens/s): 4189.57 -> 10537.26 | Helped |
| Add dynamic pruning (ablation) | Formatron · Constrained decoding (Llama-3-8B) | maximum memory usage (MB): 1655.48 -> 1635.92 | Helped |
Surprising findings
- XGrammar outperforms Formatron on some settings, e.g., Gemma json_grammar (10245 vs 8669 tokens/s) and Mistral json_grammar.
- End-to-end pipeline throughput gains are small; Formatron is close to XGrammar and unconstrained decoding in JSON/s, suggesting the parsing-stage speedup matters less end-to-end.
Limitations
- Accuracy evaluation is limited and Formatron is not best on all accuracy metrics; outputs differ across libraries due to unspecified whitespace handling.
- Reported throughput measured on a single RTX 3090 with a few models and tasks; claims of 2x are task-dependent.
Experimental setup
Datasets: Geoquery JSON Schema examples JSON grammar examples
Benchmarks: Geoquery JSON Schema generation JSON grammar generation
Metrics: throughput (tokens/s) maximum memory usage (MB) accuracy
Baselines: lm-format-enforcer Outlines XGrammar
Builds on: Earley algorithm XGrammar lm-format-enforcer Outlines
Closest papers by meaning
- Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads (ICML 2024 · similarity 0.87)
- Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata (NeurIPS 2026 · similarity 0.87)
- Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation (ICML 2024 · similarity 0.87)
- RAPID: Long-Context Inference with Retrieval-Augmented Speculative Decoding (ICML 2025 · similarity 0.87)
- Grammar-Aligned Decoding (NeurIPS 2024 · similarity 0.87)
- Probe Pruning: Accelerating LLMs through Dynamic Pruning via Model-Probing (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.