Skip to content
Grammar-Constrained Decoding 75x Faster: Vocabulary Compression with Equivalence Classes

Grammar-Constrained Decoding 75x Faster: Vocabulary Compression with Equivalence Classes

Saarland University researchers present a vocabulary compression technique for grammar-constrained decoding that groups tokens into equivalence classes, reducing per-step grammar engine overhead from scanning the full vocabulary to updating only class representatives, achieving up to 75x speedup on complex grammars like Bython while preserving byte-identical output to uncompressed XGrammar2.

AI Frontier Lectures
AI Frontier Lectures
AI Frontier Lectures

The paper "Grammar-Constrained Decoding with Compressed Vocabularies" by Michael Sullivan and Alexander Koller from Saarland University was selected as a distinguished paper at EMNLP 2026. It addresses a key bottleneck in grammar-constrained decoding: at each generation step, the grammar engine must scan the entire vocabulary to determine which tokens are valid continuations. For complex grammars, this step becomes more expensive than the language model itself.

Problem: Full-Vocabulary Scanning at Every Step

Existing engines like XGrammar2 are fast, yet they still operate over the full vocabulary at each token. On programming-language grammars, this overhead slows generation by 2× to 9× when batch size is 1. The effect is most pronounced for Bython — a Python-like language with significant indentation — because Bython appears less frequently in pre-training data, so the model relies heavily on the grammar engine to produce valid code.

Solution: Equivalence-Class Compression

The authors propose a one-time pre-computation before inference. Tokens that are interchangeable under the grammar — i.e., swapping them never changes whether a partial sequence is grammatically valid — are merged into a single equivalence class. During decoding, the grammar engine only updates the representative of each class, then maps the resulting mask back to every token in that class. The language model continues to score the original vocabulary; the compressed mask is added to those scores before sampling. The output strings are byte-identical to those produced by uncompressed XGrammar2, so no separate accuracy evaluation is needed.

Experimental Setup

Hardware: single H100 GPU

Temperature: 0.2

Maximum generated tokens: 500

Random seeds: 5

Batch size: 8

Models: Llama-3B, Qwen-4B, GPT-20B

Grammars: JSON, XML, C++, Bython

Results: Up to 75× Speedup on the Hardest Grammar

The paper reports average generation times (including model inference) for the most challenging configuration — Bython, batch size 8:

Llama-3B: 44.51 s → 0.59 s (≈75× faster)

Qwen-4B: 97.07 s → 1.40 s (≈69× faster)

GPT-20B: 24-hour timeout → 1.89 s (vs. 1.50 s without any grammar)

For the other grammars (JSON, XML, C++), the speedup is smaller because the baseline engine is already fast on those simpler grammars. The bar charts in the paper show per-example overhead (ms) and per-token overhead (µs) for XGrammar2 (blue) versus the compressed version (red) across all four grammars and three models; the Bython group stands out with the highest baseline overhead and the largest absolute reduction.

Why It Works

The compression eliminates the per-step vocabulary scan. The number of equivalence classes is orders of magnitude smaller than the vocabulary size, so the grammar engine's work per step becomes negligible. Because the mapping from classes back to tokens is exact, the constrained distribution is mathematically identical to the uncompressed version, guaranteeing zero degradation in grammatical correctness.

Paper: https://aclanthology.org/2026.emnlp-main.749/

Diagram showing model, grammar engine, vocabulary, equivalence classes, and mask mapping
Diagram showing model, grammar engine, vocabulary, equivalence classes, and mask mapping
Bar charts comparing XGrammar2 vs compressed version on JSON, XML, C++, Bython across three models
Bar charts comparing XGrammar2 vs compressed version on JSON, XML, C++, Bython across three models

}

Code example

👀点击关注
AI前沿快速Follow
Original Source

Signed-in readers can open the original source through BestHub's protected redirect.

Sign in to view source
Republication Notice

This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactadmin@besthub.devand we will review it promptly.

LLM inferenceBythonEMNLP 2026constrained generationequivalence classesgrammar-constrained decodingvocabulary compressionXGrammar2
Reader feedback

How this landed with the community

Sign in to like

Rate this article

Was this worth your time?

Sign in to rate
Discussion

0 Comments

Thoughtful readers leave field notes, pushback, and hard-won operational detail here.