Accelerating Constrained Decoding with Token Space Compression

• URL: http://arxiv.org/abs/2605.29986v1
• Date: Thu, 28 May 2026 14:22:20 GMT
• Title: Accelerating Constrained Decoding with Token Space Compression
• Abstract summary: CFGzip is an offline technique for compressing the token search space.<n>We report latency reduction of up to two orders of magnitude when CFGzip is used with a SoTA grammar engine.
• Score: 57.637871234402944
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: To guarantee that an LLM's outputs conform to a specified structure, context-free grammar (CFG) decoding engines force the selection of next tokens that produce strings that conform to a given CFG. While current CFG-constrained decoding engines are highly optimized, the inherent costs arising from the massive per-step search space -- i.e. the entire token vocabulary -- result in intractably high overhead for more complex CFGs: precisely the situation where CFG engines are most useful. In this paper, we introduce CFGzip, an offline technique for compressing the token search space, which massively reduces CFG engine overhead. In experiments, we report latency reduction of up to two orders of magnitude when CFGzip is used with a SoTA grammar engine, yielding an up to 7.5x speedup in total constrained generation time: with CFGzip, constrained decoding is now feasible at scale for complex CFGs.

Related papers

• STAC: Selective Spatiotemporal Aggregation and Compression for Video Reasoning Segmentation [60.597357847359255]
  Video segmentation demands pixel-accurate object tracking across hundreds of frames under complex natural language queries.<n>Existing methods address this through token compression, yet typically operate on features lacking temporal context.<n>State-space models resolve this constraint, as their linear recurrence selectively conditions each token on temporal context at $mathcalO(T)$ cost compression to reduce.
  arXiv  Detail & Related papers  (2026-07-03T03:28:25Z)
• End-to-End Context Compression at Scale [81.70601323130997]
  Long-context language model inference is bottlenecked by memory, as the KV cache grows with context length.<n>Recent techniques to compress the KV cache fall short: they either degrade model quality substantially or require considerable time and compute to compress a single long prompt.<n>Existing approaches are not competitive with KV cache compression on the accuracy-efficiency frontier.
  arXiv  Detail & Related papers  (2026-06-08T15:43:16Z)
• 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)
• Compressing Sequences in the Latent Embedding Space: $K$-Token Merging for Large Language Models [35.95256971588258]
  Large Language Models incur significant computational and memory costs when processing long prompts.<n>We propose K-Token Merging, a latent-space compression framework that merges each contiguous block of K token embeddings into a single embedding.<n>Experiments show that K-Token Merging achieves up to 75% input length reduction with minimal performance degradation.
  arXiv  Detail & Related papers  (2026-04-16T15:32:45Z)
• Multi-Vector Index Compression in Any Modality [73.7330345057813]
  Late interaction has emerged as a dominant paradigm for information retrieval in text, images, visual documents, and videos.<n>We introduce four approaches for index compression: sequence resizing, memory tokens, hierarchical pooling, and a novel attention-guided clustering (AGC)<n>AGC uses an attention-guided mechanism to identify the most semantically salient regions of a document as cluster centroids and to weight token aggregation.
  arXiv  Detail & Related papers  (2026-02-24T18:57:33Z)
• DeltaKV: Residual-Based KV Cache Compression via Long-Range Similarity [50.52392445266824]
  We propose a residual-based KV cache compression framework motivated by long-range inter-token similarity and highly shared latent components in KV representations.<n>Instead of discarding tokens, DeltaKV encodes semantic residuals relative to retrieved historical references, preserving fidelity while substantially reducing storage.<n>Experiments show that DeltaKV reduces KV cache memory to 29% of the original while maintaining near-lossless accuracy on LongBench, SCBench, and AIME.
  arXiv  Detail & Related papers  (2026-02-08T15:14:36Z)
• UniGist: Towards General and Hardware-aligned Sequence-level Long Context Compression [86.33995240043936]
  UniGist is a sequence-level long-context compression framework for large language models.<n>It efficiently preserves context information by replacing raw tokens with special compression tokens (gists) in a fine-grained manner.<n>Our scheme also supports flexible inference by allowing the actual removal of compressed tokens, resulting in real-time memory savings.
  arXiv  Detail & Related papers  (2025-09-19T08:47:37Z)
• Lossless Compression for LLM Tensor Incremental Snapshots [0.0]
  We build an effective compression solution, known as Language Model (LMC)<n>We show that a 16-core parallel implementation of LMC can attain compression and decompression throughput of 2.78 GiB/s and 3.76 GiB/s respectively.<n>This increase in performance ultimately reduces the resources needed and provides more time to copy the data to the storage system before the next epoch thus allowing for higher-frequency checkpoints.
  arXiv  Detail & Related papers  (2025-05-14T21:24:14Z)
• CODEPROMPTZIP: Code-specific Prompt Compression for Retrieval-Augmented Generation in Coding Tasks with LMs [6.936336826531964]
  Retrieval-Augmented Generation (RAG) enhances coding tasks by incorporating retrieved code examples into prompts.<n>Existing prompt compression techniques focus on natural language, lacking tailored solutions for code.<n>We propose CodePromptZip, a framework that compresses code examples before integrating into RAG.
  arXiv  Detail & Related papers  (2025-02-19T23:15:23Z)
• Revisiting Discriminator in GAN Compression: A Generator-discriminator Cooperative Compression Scheme [65.5405625485559]
  GAN compression aims to reduce tremendous computational overhead and memory usages when deploying GANs on resource-constrained edge devices. In this work, we revisit the role of discriminator in GAN compression and design a novel generator-discriminator cooperative compression scheme for GAN compression, termed GCC.
  arXiv  Detail & Related papers  (2021-10-27T13:54:55Z)

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.