Why choosing among 10,000 values slows an LLM down — and how to fix it
Sh0ny
15 августа 20262 min read
In short
A new trie automaton speeds up constrained decoding for large finite sets, but the main gain does not come from the algorithm alone. I look at why the reported 29× in vLLM cannot be treated as pure token-computation speedup.
When an LLM has to pick a value from a list known in advance, the problem often lies not in the model but in checking each next token. For large lists ordinary grammar compilation runs into a "cardinality wall": the more admissible strings there are, the more expensive it becomes to service the constraint.
A trie automaton tackles the task not as a general grammar but as a special automaton for a finite set of strings. Common prefixes form a trie, and the admissible tokens for each node are turned into masks in advance. Thanks to that, checking the next step takes 0.65 µs against 5.8 µs for XGrammar — roughly seven times faster.
But the most interesting result is not in that figure. Precomputed masks make it possible to bypass the guided decoding pipeline and use the stateless serving path. So in batch processing it is not only the computation of admissible tokens that speeds up: vLLM's overall throughput at batch size 256 reaches 219 req/s against 7.5 req/s for XGrammar, meaning the reported 29× is made up of the algorithmic gain plus the saving on the integration path.
For practical use this means something simple: if answers are chosen from a large but fixed reference list, a general-purpose constrained decoding mechanism may be excessive. The authors report compilation in under 100 ms for sets of up to 10,000 values and an unchanging per-step cost as the set grows; the correctness of the output is guaranteed at 100%.
The limitation is fundamental too: this is a specialised solution precisely for finite sets with a known structure — common prefixes, bounded depth and a size known in advance. The results are given in comparison with XGrammar and depend on the batched-serving scenario: the 29× cannot be transferred automatically to any generation, any grammar or any batch size. The testing covers seven tokenizer families with vocabulary sizes from 32K to 262K, but the source itself is only a description of the work, with no detail on other load scenarios.
If your models choose from large reference lists, what limits the system more today: the speed of checking admissible tokens, or the architecture through which that check is wired into serving? Source: cs.AI updates on arXiv.org