TriForce: Lossless Acceleration of Long Sequence Generation with Hierarchical Speculative Decoding

• URL: http://arxiv.org/abs/2404.11912v3
• Date: Sun, 4 Aug 2024 00:58:04 GMT
• Title: TriForce: Lossless Acceleration of Long Sequence Generation with Hierarchical Speculative Decoding
• Abstract summary: Key-value (KV) cache has emerged as a bottleneck for efficient long-sequence support. TriForce is a hierarchical speculative decoding system that is scalable for long sequence generation. TriForce's robustness is highlighted by its consistently outstanding performance across various temperatures.
• Score: 43.28712253351293
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: With large language models (LLMs) widely deployed in long content generation recently, there has emerged an increasing demand for efficient long-sequence inference support. However, key-value (KV) cache, which is stored to avoid re-computation, has emerged as a critical bottleneck by growing linearly in size with the sequence length. Due to the auto-regressive nature of LLMs, the entire KV cache will be loaded for every generated token, resulting in low utilization of computational cores and high latency. While various compression methods for KV cache have been proposed to alleviate this issue, they suffer from degradation in generation quality. We introduce TriForce, a hierarchical speculative decoding system that is scalable for long sequence generation. This approach leverages the original model weights and dynamic sparse KV cache via retrieval as a draft model, which serves as an intermediate layer in the hierarchy and is further speculated by a smaller model to reduce its drafting latency. TriForce not only facilitates impressive speedups for Llama2-7B-128K, achieving up to 2.31$\times$ on an A100 GPU but also showcases scalability in handling even longer contexts. For the offloading setting on two RTX 4090 GPUs, TriForce achieves 0.108s/token$\unicode{x2014}$only half as slow as the auto-regressive baseline on an A100, which attains 7.78$\times$ on our optimized offloading system. Additionally, TriForce performs 4.86$\times$ than DeepSpeed-Zero-Inference on a single RTX 4090 GPU. TriForce's robustness is highlighted by its consistently outstanding performance across various temperatures. The code is available at https://github.com/Infini-AI-Lab/TriForce.

Related papers

• Accelerating GPU Inference of Large Language Models with Moderately Unstructured Sparse Weight Matrices [18.428868416628017]
  This paper proposes an efficient inference method for large language models (LLMs) with moderate sparsity.<n>It achieves up to 1.64x-level speedup over SpInfer and up to 1.41x end-to-end speedups over FlashLLM.
  arXiv  Detail & Related papers  (2026-06-13T13:38:27Z)
• ChunkFT: Byte-Streamed Optimization for Memory-Efficient Full Fine-Tuning [58.54940026861599]
  textscChunkFT is a memory-efficient fine-tuning framework.<n>textscChunkFT enables gradient computation for arbitrary sub-tensors without modifying the network architecture.<n>textscChunkFT consistently outperforms existing memory-efficient baselines.
  arXiv  Detail & Related papers  (2026-05-20T13:44:44Z)
• Joint Encoding of KV-Cache Blocks for Scalable LLM Serving [3.3230675313521716]
  Existing KV-cache compression methods rely on rigids, disrupt tensor layouts, or require specialized compute.<n>We propose joint encoding of KV-cache blocks, which fuses similar blocks across requests and input chunks into shared representations.<n>This alleviates the KV-cache memory bottleneck, supporting high-concurrency serving without specialized hardware.
  arXiv  Detail & Related papers  (2026-01-06T14:50:58Z)
• Memory-Efficient Acceleration of Block Low-Rank Foundation Models on Resource Constrained GPUs [11.45717904490388]
  Recent advances in transformer-based foundation models have made them the default choice for many tasks.<n>Their rapidly growing size makes fitting a full model on a single GPU increasingly difficult and their computational cost prohibitive.<n>Block low-rank (BLR) compression techniques address this challenge by learning compact representations of weight matrices.
  arXiv  Detail & Related papers  (2025-12-24T00:41:13Z)
• LaCache: Ladder-Shaped KV Caching for Efficient Long-Context Modeling of Large Language Models [52.56008278458534]
  LaCache is a training-free method for efficient and accurate generative inference of Large Language Models.<n>LaCache enables LLMs to address both of the critical challenges in long-range modeling: robust long-range capabilities and continuous generation without running out-of-memory.
  arXiv  Detail & Related papers  (2025-07-14T19:09:57Z)
• TailorKV: A Hybrid Framework for Long-Context Inference via Tailored KV Cache Optimization [21.229296254354878]
  Key-Value cache in generative large language models (LLMs) introduces substantial memory overhead.<n>Existing works mitigate this burden by offloading or compressing the KV cache.<n>We propose a hybrid compression method, TailorKV, which seamlessly integrates quantization and offloading.
  arXiv  Detail & Related papers  (2025-05-26T07:00:04Z)
• 70% Size, 100% Accuracy: Lossless LLM Compression for Efficient GPU Inference via Dynamic-Length Float [71.43026659686679]
  Large Language Models (LLMs) have grown rapidly in size, creating challenges for efficient deployment on resource-constrained hardware. We introduce Dynamic-Length Float (DFloat11), a compression framework that reduces LLM size by 30% while preserving outputs that are bit-for-bit identical to the original model.
  arXiv  Detail & Related papers  (2025-04-15T22:38:38Z)
• BitDecoding: Unlocking Tensor Cores for Long-Context LLMs Decoding with Low-Bit KV Cache [5.499460434066963]
  BitDecoding is a framework that unlocks Cores for efficient decoding with low-bit KV cache. It achieves up to 7.5x speedup on A100, 4.8x on A100, and 8.9x on H100, compared to FP16 FlashDecoding-v2. It also outperforms the state-of-the-art low-bit KV cache implementation (QServe) by up to 4.3x.
  arXiv  Detail & Related papers  (2025-03-24T15:22:41Z)
• Position-Aware Depth Decay Decoding ($D^3$): Boosting Large Language Model Inference Efficiency [26.173523821684306]
  A token-position aware layer skipping framework is proposed to save 1.5x times operations efficiently while maintaining performance. Experiments on large language models with $7 sim 70$ billion parameters show that $D3$ can achieve an average 1.5x speedup compared with the full-inference pipeline.
  arXiv  Detail & Related papers  (2025-03-11T15:15:54Z)
• QuantCache: Adaptive Importance-Guided Quantization with Hierarchical Latent and Layer Caching for Video Generation [84.91431271257437]
  Diffusion Transformers (DiTs) have emerged as a dominant architecture in video generation. DiTs come with significant drawbacks, including increased computational and memory costs. We propose QuantCache, a novel training-free inference acceleration framework.
  arXiv  Detail & Related papers  (2025-03-09T10:31:51Z)
• QuantSpec: Self-Speculative Decoding with Hierarchical Quantized KV Cache [67.84112700032007]
  Large Language Models (LLMs) are increasingly being deployed on edge devices for long-context settings. In these scenarios, the Key-Value ( KV) cache is the primary bottleneck in terms of both GPU memory and latency. We propose a novel self-speculative decoding framework, QuantSpec, where the draft model shares the architecture of the target model but employs a hierarchical 4-bit quantized KV cache and 4-bit quantized weights for acceleration.
  arXiv  Detail & Related papers  (2025-02-05T20:43:48Z)
• ShadowKV: KV Cache in Shadows for High-Throughput Long-Context LLM Inference [25.638980944695728]
  ShadowKV is an efficient long-context large language models (LLMs) inference system. It stores the low-rank key cache and offloads the value cache to reduce the memory footprint for larger batch sizes and longer sequences. It can support up to 6$times$ larger batch sizes and boost throughput by up to 3.04$times$ on an A100 GPU.
  arXiv  Detail & Related papers  (2024-10-28T19:08:12Z)
• Fast Feedforward 3D Gaussian Splatting Compression [55.149325473447384]
  3D Gaussian Splatting (FCGS) is an optimization-free model that can compress 3DGS representations rapidly in a single feed-forward pass. FCGS achieves a compression ratio of over 20X while maintaining fidelity, surpassing most per-scene SOTA optimization-based methods.
  arXiv  Detail & Related papers  (2024-10-10T15:13:08Z)
• SwiftKV: Fast Prefill-Optimized Inference with Knowledge-Preserving Model Transformation [32.62031120968721]
  Swift KV is a model transformation and distillation procedure designed to reduce the time and cost of processing prompt tokens. It reduces the compute requirement of prefill by 50% and the memory requirement of the KV cache by 62.5%. It can achieve a staggering 560 TFlops/ GPU of normalized inference throughput, which translates to 16K tokens/s for Llama-3.1-70B in 16-bit precision.
  arXiv  Detail & Related papers  (2024-10-04T22:45:26Z)
• MagicDec: Breaking the Latency-Throughput Tradeoff for Long Context Generation with Speculative Decoding [11.030853173032199]
  Large Language Models (LLMs) have become more prevalent in long-context applications. Speculative decoding (SD) is a widely used technique to reduce latency without sacrificing performance. We show that surprisingly SD can achieve speedup even for a high throughput inference regime for moderate to long sequences.
  arXiv  Detail & Related papers  (2024-08-20T17:57:31Z)
• ThinK: Thinner Key Cache by Query-Driven Pruning [63.13363917871414]
  Large Language Models (LLMs) have revolutionized the field of natural language processing, achieving unprecedented performance across a variety of applications.<n>This paper focuses on the long-context scenario, addressing the inefficiencies in KV cache memory consumption during inference.<n>We propose ThinK, a novel query-dependent KV cache pruning method designed to minimize attention weight loss while selectively pruning the least significant channels.
  arXiv  Detail & Related papers  (2024-07-30T17:59:08Z)
• vTensor: Flexible Virtual Tensor Management for Efficient LLM Serving [53.972175896814505]
  Large Language Models (LLMs) are widely used across various domains, processing millions of daily requests. Large Language Models (LLMs) are widely used across various domains, processing millions of daily requests.
  arXiv  Detail & Related papers  (2024-07-22T14:37:58Z)
• MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention [36.49445805074941]
  MInference (Milliontokens Inference) is a sparse calculation method designed to accelerate pre-filling of long-sequence processing. We demonstrate that MInference effectively reduces inference latency by up to 10x for pre-filling on an A100, while maintaining accuracy.
  arXiv  Detail & Related papers  (2024-07-02T17:59:56Z)
• Hardware-Aware Parallel Prompt Decoding for Memory-Efficient Acceleration of LLM Inference [19.167604927651073]
  Auto-regressive decoding of Large Language Models (LLMs) results in significant overheads in their hardware performance. 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. 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)
• HiRE: High Recall Approximate Top-$k$ Estimation for Efficient LLM Inference [68.59839755875252]
  HiRE comprises of two novel components: (i) a compression scheme to cheaply predict top-$k$ rows/columns with high recall, followed by full computation restricted to the predicted subset, and (ii) DA-TOP-$k$: an efficient multi-device approximate top-$k$ operator. We demonstrate that on a one billion parameter model, HiRE applied to both the softmax as well as feedforward layers, achieves almost matching pretraining and downstream accuracy, and speeds up inference latency by $1.47times$ on a single TPUv5e device.
  arXiv  Detail & Related papers  (2024-02-14T18:04:36Z)
• DISTFLASHATTN: Distributed Memory-efficient Attention for Long-context LLMs Training [82.06732962485754]
  FlashAttention effectively reduces the quadratic peak memory usage to linear in training transformer-based large language models (LLMs) on a single GPU. We introduce DISTFLASHATTN, a memory-efficient attention mechanism optimized for long-context LLMs training. It achieves 1.67x and 1.26 - 1.88x speedup compared to recent Ring Attention and DeepSpeed-Ulysses.
  arXiv  Detail & Related papers  (2023-10-05T03:47:57Z)
• H$_2$O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models [110.06476624089679]
  We introduce a novel approach for implementing the KV cache which significantly reduces its memory footprint. Our approach is based on the observation that a small portion of tokens contributes most of the value when computing attention scores. We propose Heavy Hitter (H$$O), a KV cache eviction policy that dynamically retains a balance of recent and H$$ tokens.
  arXiv  Detail & Related papers  (2023-06-24T20:11:14Z)
• Learning sparse auto-encoders for green AI image coding [5.967279020820772]
  In this paper, we address the problem of lossy image compression using a CAE with a small memory footprint and low computational power usage. We propose a constrained approach and a new structured sparse learning method. Experimental results show that the $ell_1,1$ constraint provides the best structured proximal sparsity, resulting in a high reduction of memory and computational cost.
  arXiv  Detail & Related papers  (2022-09-09T06:31: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.