Trie Automata for Constrained Decoding over Large Finite Sets

• URL: http://arxiv.org/abs/2608.12574v1
• Date: Wed, 12 Aug 2026 20:38:51 GMT
• Title: Trie Automata for Constrained Decoding over Large Finite Sets
• Abstract summary: We introduce the trie automaton, a specialized mechanism that exploits finite-set structure.<n>The trie achieves 7X faster per-step valid-token computation.<n>It maintains sub-100ms compilation up to K = 10,000 and flat per-step cost regardless of set size.
• Score: 4.37891903761924
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large language models increasingly need to generate structured outputs that conform to predefined schemas, with one common constraint being selection from a finite set of valid strings. Current constrained decoding systems handle this through general-purpose grammar compilation, which becomes prohibitively slow as the number of valid values grows into the thousands, a cardinality wall. We introduce the trie automaton, a specialized mechanism that exploits finite-set structure (shared prefixes, bounded depth, known cardinality) via Aho-Corasick multi-pattern matching to precompute per-node token masks. The trie achieves 7X faster per-step valid-token computation (0.65 us vs. 5.8 us) compared to XGrammar, one of the primary backends in vLLM and SGLang, and 2--6.5X faster compilation at K >= 300. Because precomputed masks enable a stateless serving path that bypasses the guided decoding pipeline, this advantage compounds in batch serving: end-to-end vLLM throughput reaches 219 req/s vs. XGrammar's 7.5 req/s at batch size 256 (29X). The 29X combines the algorithmic speedup with integration-path savings that only precomputed masks can unlock. Across seven tokenizer families (32K--262K vocabulary), the trie maintains sub-100ms compilation up to K = 10,000 and flat per-step cost regardless of set size, while guaranteeing 100% output validity.

Related papers

• Transformer Accelerator (TFA): A Macro-Op INT8 Hardware Chip for Transformer Inference and Machine Translation [0.3882135185458233]
  Transformer Accelerator (TFA) is a synthesizable, parameterizable INT8 memory-to-memory engine for transformer inference.<n>TFA implements matrix multiplication, softmax, RMSNorm, elementwise, and copy/gather operations through eight 512-bit macro-op descriptors.<n>The RTL combines an output-stationary multiply-accumulate array with ping-pong buffers that overlap DMA and compute, bit-exact reciprocal-square-root and divide units, key-value-cache and embedding addressing, and an abort-safe zero-padding write engine.
  arXiv  Detail & Related papers  (2026-08-06T06:59:25Z)
• GRID: Grammar-Railed Decoding for Enterprise SQL Generation [0.0]
  We present GRID (Grammar-Railed Decoding), a grammar-constrained decoding engine.<n>It uses advanced LALR(1) itself as a viable oracle.<n>Four guarantees (soundness, completeness, termination, and near-constant per-token cost) are stated with explicit preconditions.
  arXiv  Detail & Related papers  (2026-07-11T19:25:23Z)
• Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata [57.27430779838529]
  We present an exact and tractable algorithm for sampling from the constrained mean-field posterior under any constraint expressible as a finite automaton.<n>The approach guarantees constraint satisfaction by construction, supports both greedy and sampling-based decoding, and is compatible with parallel and block-wise decoding.<n> Empirical evaluations on Dream-7B and LLaDA-8 show substantial accuracy gains across various tasks.
  arXiv  Detail & Related papers  (2026-07-08T05:48:57Z)
• XFP: Quality-Targeted Adaptive Codebook Quantization with Sparse Outlier Separation for LLM Inference [0.0]
  XFP determines codebook size, outlier budget, and packing per layer automatically.<n>XFP reaches 138 tok/s single-stream decode on workstation hardware.<n>For models that do not fit in the target memory envelope, we present the H-Process.
  arXiv  Detail & Related papers  (2026-05-14T13:52:31Z)
• DMax: Aggressive Parallel Decoding for dLLMs [77.24184219948337]
  We present DMax, a new paradigm for efficient diffusion language models (dLLMs)<n>It mitigates error accumulation in parallel decoding, enabling aggressive decoding while preserving generation quality.<n>At the core of our approach is On-Policy Uniform Training, a novel training strategy that efficiently unifies masked and uniform dLLMs.
  arXiv  Detail & Related papers  (2026-04-09T14:35:42Z)
• Frequency-Ordered Tokenization for Better Text Compression [0.0]
  Method tokenizes text with Byte Pair.<n> encodes the result with variable-length integers before passing it to any standard compressor.<n>On enwik8 (100 MB Wikipedia), this yields improvements of 7.08 percentage points (pp) for zlib, 1.69 pp for LZMA, and 0.76 pp for zstd.
  arXiv  Detail & Related papers  (2026-02-26T12:53:48Z)
• REAR: Rethinking Visual Autoregressive Models via Generator-Tokenizer Consistency Regularization [130.46612643194973]
  reAR is a simple training strategy introducing a token-wise regularization objective.<n>On ImageNet, it reduces gFID from 3.02 to 1.86 and improves IS to 316.9 using a standardization-based tokenizer.<n>When applied to advanced tokenizers, it achieves a gFID of 1.42 with only 177M parameters, matching the performance with larger state-of-the-art diffusion models (675M)
  arXiv  Detail & Related papers  (2025-10-06T02:48:13Z)
• dParallel: Learnable Parallel Decoding for dLLMs [77.24184219948337]
  Diffusion large language models (dLLMs) offer parallel token prediction and lower inference latency.<n>Existing open-source models still require nearly token-length decoding steps to ensure performance.<n>We introduce dParallel, a simple and effective method that unlocks the inherent parallelism of dLLMs for fast sampling.
  arXiv  Detail & Related papers  (2025-09-30T16:32:52Z)
• A Simple Linear Patch Revives Layer-Pruned Large Language Models [58.056251480151104]
  Layer pruning has emerged as a widely used technique for compressing large language models (LLMs)<n>textscLinearPatch fuses two operations into one matrix multiply at the pruning interface.<n>The patch can be further refined with 5K unlabeled samples via memory-efficient offline distillation, pushing the retention to 95.16% within only 30 minutes on a single GPU.
  arXiv  Detail & Related papers  (2025-05-30T15:06:08Z)
• Hardware-Aware Parallel Prompt Decoding for Memory-Efficient Acceleration of LLM Inference [23.633481089469836]
  Auto-regressive decoding of Large Language Models (LLMs) results in significant overheads in their hardware performance.<n>We propose a novel parallel prompt decoding that requires only $0.0002$% trainable parameters, enabling efficient training on a single A100-40GB GPU in just 16 hours.<n>Our approach demonstrates up to 2.49$times$ speedup and maintains a minimal memory overhead of just $0.0004$%.
  arXiv  Detail & Related papers  (2024-05-28T22:19:30Z)
• Prepacking: A Simple Method for Fast Prefilling and Increased Throughput in Large Language Models [48.592730159983276]
  Prefilling is the computation of the key-value cache for input tokens in the prompt prior to autoregressive generation. For longer input prompt lengths, prefilling incurs a significant overhead on decoding time. We propose Prepacking, a simple yet effective method to optimize prefilling computation.
  arXiv  Detail & Related papers  (2024-04-15T07:49:10Z)
• Hydragen: High-Throughput LLM Inference with Shared Prefixes [39.622276190997205]
  Hydragen is a hardware-aware exact implementation of attention with shared prefixes. Our method can improve end-to-end CodeLlama-13b throughput by up to 32x against competitive baselines.
  arXiv  Detail & Related papers  (2024-02-07T18:53:01Z)
• Vcc: Scaling Transformers to 128K Tokens or More by Prioritizing Important Tokens [65.4435926060951]
  We propose to significantly improve the efficiency of Transformers for ultra long sequences, by compressing the sequence into a much smaller representation at each layer. Our algorithm is not only efficient (achieving more than $3times$ efficiency gain compared to baselines on 4K and 16K lengths) but also offers competitive/better performance on a large number of tasks.
  arXiv  Detail & Related papers  (2023-05-07T10:32:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.