Vectorizing the Trie: Efficient Constrained Decoding for LLM-based Generative Retrieval on Accelerators

• URL: http://arxiv.org/abs/2602.22647v1
• Date: Thu, 26 Feb 2026 06:00:56 GMT
• Title: Vectorizing the Trie: Efficient Constrained Decoding for LLM-based Generative Retrieval on Accelerators
• Abstract summary: STATIC is an efficient and scalable constrained decoding technique for generative retrieval on hardware accelerators.<n>We deploy STATIC on a large-scale industrial video recommendation platform serving billions of users.
• Score: 7.020725160596732
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Generative retrieval has emerged as a powerful paradigm for LLM-based recommendation. However, industrial recommender systems often benefit from restricting the output space to a constrained subset of items based on business logic (e.g. enforcing content freshness or product category), which standard autoregressive decoding cannot natively support. Moreover, existing constrained decoding methods that make use of prefix trees (Tries) incur severe latency penalties on hardware accelerators (TPUs/GPUs). In this work, we introduce STATIC (Sparse Transition Matrix-Accelerated Trie Index for Constrained Decoding), an efficient and scalable constrained decoding technique designed specifically for high-throughput LLM-based generative retrieval on TPUs/GPUs. By flattening the prefix tree into a static Compressed Sparse Row (CSR) matrix, we transform irregular tree traversals into fully vectorized sparse matrix operations, unlocking massive efficiency gains on hardware accelerators. We deploy STATIC on a large-scale industrial video recommendation platform serving billions of users. STATIC produces significant product metric impact with minimal latency overhead (0.033 ms per step and 0.25% of inference time), achieving a 948x speedup over a CPU trie implementation and a 47-1033x speedup over a hardware-accelerated binary-search baseline. Furthermore, the runtime overhead of STATIC remains extremely low across a wide range of practical configurations. To the best of our knowledge, STATIC enables the first production-scale deployment of strictly constrained generative retrieval. In addition, evaluation on academic benchmarks demonstrates that STATIC can considerably improve cold-start performance for generative retrieval. Our code is available at https://github.com/youtube/static-constraint-decoding.

Related papers

• FluxBin: Flexible LUT-based Ultra-low-bit LLM Inference by Algorithm-Kernel Synergy [32.21687694159134]
  FluxBin is an algorithm that synerizes binary quantization with a highly optimized kernel.<n>FluxBin achieves up to $5.92times speedup and $10.19times energy savings.<n>This effectively enables the deployment of 70B-scale models on one single A100 bases with a $4times memory reduction.
  arXiv  Detail & Related papers  (2026-08-16T08:01:06Z)
• No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval [51.43543998583709]
  Single-stage Sparse Retrieval (SSR) is a paradigm shift that replaces expensive clustering with efficient sparse coding.<n>It reduces indexing time by 15x compared to ColBERTv2, halves retrieval latency, and simultaneously improves retrieval performance.
  arXiv  Detail & Related papers  (2026-05-28T15:53:34Z)
• SMART: When is it Actually Worth Expanding a Speculative Tree? [26.986851887229054]
  Tree-based speculative decoding accelerates autoregressive generation by verifying a branching tree draft tokens in a single targetmodel forward pass.<n>Existing methods prioritize maximizing token-level likelihood of the number of accepted tokens while ignoring a critical efficiency paradox''<n>We propose SMART, a system-aware marginal analysis framework for runtime tree construction.
  arXiv  Detail & Related papers  (2026-04-09T13:17:56Z)
• Eliminating Multi-GPU Performance Taxes: A Systems Approach to Efficient Distributed LLMs [61.953548065938385]
  We introduce the ''Three Taxes'' (Bulk Synchronous, Inter- Kernel Data Locality, and Kernel Launch Overhead) as an analytical framework.<n>We propose moving beyond the rigid BSP model to address key inefficiencies in distributed GPU execution.<n>We observe a 10-20% speedup in end-to-end latency over BSP-based approaches.
  arXiv  Detail & Related papers  (2025-11-04T01:15:44Z)
• Fast and Compact Tsetlin Machine Inference on CPUs Using Instruction-Level Optimization [0.4499833362998488]
  The Tsetlin Machine (TM) offers high-speed inference on resource-constrained devices such as CPUs.<n>We propose an efficient software implementation of the TM by leveraging instruction-level bitwise operations.<n>We introduce an early exit mechanism, which exploits the TM's AND-based clause evaluation to avoid unnecessary computations.
  arXiv  Detail & Related papers  (2025-10-17T13:44:20Z)
• TeLLMe v2: An Efficient End-to-End Ternary LLM Prefill and Decode Accelerator with Table-Lookup Matmul on Edge FPGAs [9.646882213709814]
  TeLLMe is a table-lookup-based ternary LLM accelerator for low-power edge FPGAs.<n>It supports both prefill and autoregressive decoding using 1.58-bit weights and 8-bit activations.<n>Under a 5W power budget, TeLLMe delivers up to 25tokens/s decoding throughput.
  arXiv  Detail & Related papers  (2025-10-03T05:37:51Z)
• Learn from the Past: Fast Sparse Indexing for Large Language Model Decoding [7.142158555793151]
  Large language models (LLMs) continue to support increasingly longer contexts.<n>Memory demand for key-value caches during decoding grows rapidly.<n>Sparse attention mechanisms alleviate this issue by computing attention weights only for selected key-value pairs.<n>Existing methods often treat each decoding step as an independent process.<n>We propose LFPS, an acceleration method that dynamically constructs sparse indexing candidates based on historical attention patterns.
  arXiv  Detail & Related papers  (2025-05-30T02:35:59Z)
• FastCar: Cache Attentive Replay for Fast Auto-Regressive Video Generation on the Edge [60.000984252907195]
  Auto-regressive (AR) models have recently shown promise in visual generation tasks due to their superior sampling efficiency.<n>Video generation requires a substantially larger number of tokens to produce coherent temporal frames, resulting in significant overhead during the decoding phase.<n>We propose the textbfFastCar framework to accelerate the decode phase for the AR video generation by exploring the temporal redundancy.
  arXiv  Detail & Related papers  (2025-05-17T05:00:39Z)
• EoRA: Fine-tuning-free Compensation for Compressed LLM with Eigenspace Low-Rank Approximation [84.70637613266835]
  EoRA is a fine-tuning-free method that augments compressed Large Language Models with low-rank matrices.<n>EoRA consistently outperforms prior training-free low rank methods in recovering the accuracy of compressed LLMs.
  arXiv  Detail & Related papers  (2024-10-28T17:59:03Z)
• Search for Efficient Large Language Models [52.98684997131108]
  Large Language Models (LLMs) have long held sway in the realms of artificial intelligence research. Weight pruning, quantization, and distillation have been embraced to compress LLMs, targeting memory reduction and inference acceleration. Most model compression techniques concentrate on weight optimization, overlooking the exploration of optimal architectures.
  arXiv  Detail & Related papers  (2024-09-25T21:32:12Z)
• MobiZO: Enabling Efficient LLM Fine-Tuning at the Edge via Inference Engines [28.18421624702502]
  We introduce MobiZO, a resource-efficient fine-tuning framework for Large Language Models (LLMs) specifically designed for edge devices.<n>We show that MobiZO achieves substantial runtime speedups and memory savings while improving fine-tuning accuracy.<n> Experiments demonstrate that MobiZO achieves substantial runtime speedups and memory savings while improving fine-tuning accuracy.
  arXiv  Detail & Related papers  (2024-09-23T20:14:09Z)
• 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)
• Shallow Cross-Encoders for Low-Latency Retrieval [69.06104373460597]
  Cross-Encoders based on large transformer models (such as BERT or T5) are computationally expensive and allow for scoring only a small number of documents within a reasonably small latency window. We show that weaker shallow transformer models (i.e., transformers with a limited number of layers) actually perform better than full-scale models when constrained to these practical low-latency settings.
  arXiv  Detail & Related papers  (2024-03-29T15:07:21Z)
• Practical Conformer: Optimizing size, speed and flops of Conformer for on-Device and cloud ASR [67.63332492134332]
  We design an optimized conformer that is small enough to meet on-device restrictions and has fast inference on TPUs. Our proposed encoder can double as a strong standalone encoder in on device, and as the first part of a high-performance ASR pipeline.
  arXiv  Detail & Related papers  (2023-03-31T23:30:48Z)
• Sparse Periodic Systolic Dataflow for Lowering Latency and Power Dissipation of Convolutional Neural Network Accelerators [3.043665249713003]
  This paper introduces the sparse periodic systolic (SPS) dataflow, which advances the state-of-the-art hardware accelerator for supporting lightweight neural networks. By exploiting the regularity of PPS, our sparsity-aware compiler optimally reorders the weights and uses a simple indexing unit in hardware to create matches between the weights and activations.
  arXiv  Detail & Related papers  (2022-06-30T19:16:46Z)

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.