PaperlayerView exact revision on arXiv

Source-linked AI summary

Cost-Efficient Large Language Model Serving for Multi-turn Conversations with CachedAttention

Bin Gao, Zhuomin He, Puru Sharma, Qingxuan Kang, Djordje Jevdjic, Junbo Deng, Xingkun Yang, Zhou Yu, Pengfei Zuo

arXiv:2403.19708v3cs.CLcs.LG

TL;DR

Multi-turn LLM serving repeatedly recomputes historical KV caches, increasing serving costs. CachedAttention reuses those caches through hierarchical storage and coordinated access, placement, and truncation mechanisms. Experiments report lower TTFT, higher prompt-prefilling throughput, and lower end-to-end inference cost.

  • Problem

    Existing LLM serving engines repeatedly compute historical KV caches across multi-turn conversations, incurring high serving costs.

  • Method

    CachedAttention reuses historical KV caches through hierarchical storage, overlapped cache access, scheduler-aware placement, and positional-encoding-decoupled truncation.

  • Results

    Up to 87% lower TTFT, 7.8× higher prompt prefilling throughput, and 70% lower end-to-end inference cost are reported for multi-turn conversations.

  • Takeaways & Limitations

    CachedAttention reduces repetitive KV-cache computation while supporting cache storage and reuse across multi-turn conversations.

Abstract

from arXiv · show

Interacting with humans through multi-turn conversations is a fundamental feature of large language models (LLMs). However, existing LLM serving engines executing multi-turn conversations are inefficient due to the need to repeatedly compute the key-value (KV) caches of historical tokens, incurring high serving costs. To address the problem, this paper proposes CachedAttention, a new attention mechanism that enables reuse of KV caches across multi-turn conversations, significantly reducing the repetitive computation overheads. CachedAttention maintains a hierarchical KV caching system that leverages cost-effective memory/storage mediums to save KV caches for all requests. To reduce KV cache access overheads from slow mediums, CachedAttention employs layer-wise pre-loading and asynchronous saving schemes to overlap the KV cache access with the GPU computation. To ensure that the KV caches to be accessed are placed in the fastest hierarchy, CachedAttention employs scheduler-aware fetching and eviction schemes to consciously place the KV caches in different layers based on the hints from the inference job scheduler. To avoid the invalidation of the saved KV caches incurred by context window overflow, CachedAttention enables the saved KV caches to remain valid via decoupling the positional encoding and effectively truncating the KV caches. Extensive experimental results demonstrate that CachedAttention significantly decreases the time to the first token (TTFT) by up to 87%, improves the prompt prefilling throughput by up to 7.8$\times$ for multi-turn conversations, and reduces the end-to-end inference cost by up to 70%.

1 Introduction

CachedAttention addresses the high cost of multi-turn LLM serving by reusing historical KV caches instead of recomputing them. It combines hierarchical storage, overlapped cache access, scheduler-aware placement, and positional-encoding-decoupled truncation.

  • Motivation: 73% of ShareGPT conversations involve multiple turns, making efficient historical-context handling important for LLM serving.The dataset analysis identifies multi-turn interaction as a common workload.
  • Core approach: CachedAttention saves KV caches in AttentionStore when sessions become inactive and reloads them when sessions resume, avoiding repetitive computation.This replaces conventional cache discarding with reuse across ensuing turns.
  • System design: Layer-wise pre-loading, asynchronous saving, and scheduler-aware fetching and eviction overlap cache access with computation and place likely-needed caches in faster storage layers.The design addresses transfer overhead and uses scheduler hints to guide cache placement.
  • Core approach: Hierarchical KV-cache storage uses slower, larger-capacity host memory and disks because GPU HBM capacity is insufficient for continuously expanding conversations.Prior HBM-only retention can exhaust free HBM space quickly.
  • System design: Positional-encoding decoupling and KV-cache truncation preserve cache validity when conversations exceed the model context window.CachedAttention separates positional encoding during saving and restores it during loading.
  • Results: Up to 87% lower TTFT, 7.8× higher prompt prefilling throughput, and 70% lower end-to-end inference cost are reported for multi-turn conversations.The evaluation uses the real ShareGPT dataset.

2 Background and Motivation

Multi-turn inference repeatedly recomputes historical KV caches even though most input tokens may be historical, creating substantial cost and latency. The background motivates reusing those caches while addressing storage capacity, access overhead, placement, and context-window invalidation.

  • Generative LLM inference basics: Transformer inference has prefilling and decoding phases: prefilling processes the prompt and builds KV caches, while decoding generates output tokens sequentially.Prefilling time grows with input-token count, whereas decoding has relatively constant computation per iteration.
  • Multi-turn conversations: In multi-turn sessions, each new request depends on historical tokens from earlier questions and answers to maintain coherent context.The session is represented as a sequence of conversation turns with accumulated history.
  • Multi-turn conversations: 73% of ShareGPT conversations are multi-turn, and 30% contain more than 4K tokens, indicating frequent and potentially long-context workloads.ShareGPT contains more than 90K conversations.
  • Recomputation inefficiencies: Current serving engines discard prior KV caches after a turn, then regenerate historical caches in later turns as the session expands.Historical tokens can exceed 99% of the input in a new conversation, while repetitive computation occupies 99% of the time.
  • Design challenges: Reusing historical KV caches could reduce up to 99% of prefilling cost, but external cache access can block GPU computation.The KV-cache loading time is non-negligible compared with repetitive cache computation.
  • Design challenges: Scheduler-aware placement is needed because disks provide tens of TBs but less than 5 GB/s bandwidth, making randomly accessed caches slow to retrieve.The design challenge is to keep accessed caches in faster hierarchy levels.
  • Design challenges: Context-window truncation can invalidate saved caches because removing old tokens changes positional information; 47% and 30% of sessions exceed 2K and 4K tokens.This issue does not affect engines that recompute from the truncated prompt.

3 The CachedAttention Design

CachedAttention reuses historical KV caches across conversation turns and organizes them in AttentionStore. Its design combines overlapped cache access, hierarchical placement, and positional-encoding-decoupled truncation.

  • Overview: CachedAttention reuses historical KV caches from AttentionStore, prefilling only newly added conversation tokens instead of recomputing the full prompt.For Turn 3, the caches for q1, a1, q2, and a2 are reused while only q3 is prefilled.
  • Overview: AttentionStore is a hierarchical KV caching system with cache-access, placement, and truncation techniques for multi-turn inference.
  • Overview: CachedAttention overlaps KV-cache loading and saving with inference computation through layer-wise pre-loading and asynchronous saving schemes.
  • Overview: It uses host memory and disks as multi-tier storage, with scheduler-aware fetching and eviction to manage cache placement.
  • Overview: CachedAttention decouples positional encoding from saved KV caches and re-embeds it during loading, allowing truncation without invalidating caches.

3.2 Overlapped KV Cache Access

CachedAttention reduces KV-cache access overhead by overlapping cache transfers with GPU computation. Layer-wise pre-loading targets reads, while asynchronous saving overlaps write-back with inference.

  • 3.2.1 Layer-wise Pre-loading from Memory to HBMs: Layer-wise pre-loading loads subsequent layers’ KV caches while the GPU computes the current transformer layer.The corresponding cache is intended to be in the HBM execution buffer when self-attention begins for that layer.
  • 3.2.1 Layer-wise Pre-loading from Memory to HBMs: Pre-loading is imperfect when TloadLhist > Tpref Lnew, because KV-cache transmission exceeds the partial prefilling time.A larger customized pre-loading buffer can start earlier and overlap more layer-loading gaps.
  • 3.2.2 Asynchronous Saving from HBMs to Memory: Asynchronous saving overlaps KV-cache write-back with inference instead of placing all saving after a conversation round.The scheme uses different overlap mechanisms for prefilling and decoding because their KV-cache generation rates differ.
  • 3.2.2 Asynchronous Saving from HBMs to Memory: During prefilling, the write stream retains KV caches layer by layer, allowing produced caches to overlap with subsequent decoding computation.

3.3 Hierarchical KV Cache Placement

CachedAttention places KV caches across host memory and disks, using scheduler knowledge to fetch likely-needed caches early and evict less urgently needed ones.

  • 3.3.1 Scheduler-aware Fetching from Disks to Memory: CachedAttention uses host memory and disks as a hierarchical store, favoring host memory because it is faster than disks.The cited access speeds are tens of GB/s for DRAM versus several GB/s for SSDs.
  • 3.3.1 Scheduler-aware Fetching from Disks to Memory: Scheduler-aware fetching pre-fetches disk-resident KV caches for waiting jobs into host memory using the scheduler’s job queue.A look-ahead prefetching window checks waiting jobs and fetches a cache when it is not already in host memory.
  • 3.3.1 Scheduler-aware Fetching from Disks to Memory: A host-memory buffer supports fetching when memory is full, while threshold-triggered eviction preserves buffer availability.
  • 3.3.2 Scheduler-aware Eviction from Memory to Disks: Scheduler-aware eviction uses future access information from the job queue rather than relying only on historical strategies such as LRU or FIFO.A look-ahead eviction window exempts caches associated with upcoming jobs and prioritizes suitable tail entries for eviction.
  • 3.3.2 Scheduler-aware Eviction from Memory to Disks: When both host memory and disks require space, CachedAttention selects eviction candidates across the hierarchy to maintain cache hit rate.The example evicts Job 4 from host memory and Job 9 from the full disks.

3.4 Decoupled KV Cache Truncation

Context-window truncation changes token positions and can invalidate saved KV caches. CachedAttention preserves their validity by decoupling positional encoding and re-embedding new positions when loading.

  • 3.4 Decoupled KV Cache Truncation: When a 4K context overflows, conventional serving truncates the oldest 2K prompt tokens.
  • 3.4 Decoupled KV Cache Truncation: Truncation invalidates CachedAttention’s saved KV caches because removing tokens changes the positional information of remaining tokens.
  • 3.4 Decoupled KV Cache Truncation: CachedAttention stores KV caches without positional encodings and applies new positional encodings when loading truncated caches.The design works with relative positional encoding, which embeds positional information in query and key vectors.
  • 3.4 Decoupled KV Cache Truncation: CachedAttention can retrieve a truncated KV cache, such as KV [0:1536], load it into HBM, and then apply new positional encodings.
  • 3.4 Decoupled KV Cache Truncation: The system can also follow token discarding lists from KV-cache compression methods and deliver the resulting pruned cache for inference.

4.1 Experimental Setup

The evaluation uses multiple LLMs, GPU configurations, storage resources, and ShareGPT-derived multi-turn workloads, comparing CachedAttention with recomputation.

  • Testbeds: Experiments run on four NVIDIA A100 GPUs with 80GB HBM each, 128GB DRAM, and 10TB SSDs connected through PCIe Gen 4.
  • Models: The evaluated models include LLaMA-1 65B, LLaMA-2 13B and 70B, Falcon 40B, and Mistral-7B with a 32K context window.
  • Workloads: Workloads use 9K ShareGPT conversation sessions with Poisson-generated arrivals at λ = 1.0.
  • Baseline: CachedAttention is compared against recomputation, which discards inactive-session KV caches and recomputes them when sessions resume.

4.2 End-to-end Performance

CachedAttention improves end-to-end multi-turn serving by reusing historical KV caches, reducing TTFT, increasing prefilling throughput, lowering GPU time, and cutting inference cost relative to recomputation.

  • Workload: The workload contains about 52K conversation turns, evaluated after warming AttentionStore with the first 10K turns.
  • Cache hit rate: CachedAttention achieves cache hit rates of 86%, 71%, 89%, and 90% for LLaMA-13B, LLaMA-65B, LLaMA-70B, and Falcon-40B, respectively.
  • TTFT: 85%, 61%, 87%, and 86% TTFT reductions are achieved for LLaMA-13B, LLaMA-65B, LLaMA-70B, and Falcon-40B versus recomputation.
  • Prefilling throughput: 6.8×, 2.6×, 7.8×, and 7.2× prefilling-throughput speedups are achieved for LLaMA-13B, LLaMA-65B, LLaMA-70B, and Falcon-40B versus recomputation.Layer-wise pre-loading overlaps historical-cache loading with prefilling of newly input tokens.
  • GPU time: CachedAttention achieves GPU-time speedups of 4.0×, 1.9×, 3.3×, and 3.4× for LLaMA-13B, LLaMA-65B, LLaMA-70B, and Falcon-40B versus recomputation.The gains reflect reduced historical-token recomputation and reduced recomputation after context overflow.
  • Inference cost: Inference-cost savings are 70%, 43%, 66%, and 68% for LLaMA-13B, LLaMA-65B, LLaMA-70B, and Falcon-40B, respectively, versus recomputation.The savings primarily stem from reduced GPU time while using host memory and disks for inactive-session caches.

4.3 Ablation Studies

Ablations show that CachedAttention’s overlap, scheduler-aware placement, and positional-encoding decoupling improve access efficiency, cache retention, and model quality under context overflow.

  • Overlapped KV cache access: Layer-wise pre-loading reduces the impact of historical KV-cache loading by overlapping it with computation on newly input tokens.
  • Overlapped KV cache access: Asynchronous KV-cache saving overlaps saving with inference execution, reducing the overall execution overhead as prompt length increases.
  • Scheduler-aware fetching and eviction: With 128GB DRAM and 2TB SSD, CachedAttention outperforms LRU and FIFO in overall cache hit rate by 27% and 31%, respectively.
  • Scheduler-aware fetching and eviction: With 128GB DRAM and 10TB SSD, CachedAttention reaches an 86% hit rate versus 58% for LRU and 48% for FIFO, with GPU-time speedup up to 2.7×.
  • Context overflow: Context-overflow handling reduces hit rates by 17.6%, 41.5%, 18.1%, and 18.4% for LLaMA-13B, LLaMA-65B, LLaMA-70B, and Falcon-40B when positional encoding invalidates saved caches.
  • Decoupled positional encoding: CachedAttention maintains PPL comparable to token truncation, with a difference of < 0.02, while naive KV-cache truncation produces PPL > 103.
  • Decoupled positional encoding: CachedAttention and token truncation provide high comparable accuracy after context overflow on MMLU, LongEval, and PIQA.
  • Cache capacity: A cache-capacity ratio of RCC/CCpUT = 0.25 yields a 98% cache hit rate, compared with 51% at 0.1, and peak throughput coincides with peak hit rate.

5 Related Work

Related work reduces KV-cache overhead through compression, fragmentation control, prompt-prefix sharing, or limited-memory caching, whereas CachedAttention targets multi-turn conversations across slower storage hierarchies.

  • KV Cache Management: Quantization, compression, and fine-granularity non-continuous memory reduce KV-cache storage overhead or fragmentation, and are orthogonal to CachedAttention’s multi-turn focus.
  • KV Cache Management: LMDeploy caches multi-turn KV caches in HBM, while RadixAttention and ChunkAttention target tasks sharing prompt prefixes.
  • KV Cache Management: Pensieve uses GPU and CPU memory for multi-turn KV caches, whereas CachedAttention exploits slower, larger storage hierarchies and addresses offloading challenges.
  • Inference Parameter Offloading: FlexGen offloads model weights and KV caches to DRAM and disks for offline inference, while other systems offload model weights or inactive expert weights.

6 Conclusion

CachedAttention reuses KV caches across ensuing turns and adds schemes for efficient cache access, placement, and truncation. Experiments show substantial improvements in multi-turn serving efficiency and cost.

  • CachedAttention reuses KV caches for ensuing turns of the same conversation, reducing KV-cache recomputation overhead.
  • CachedAttention combines overlapped KV-cache access, hierarchical KV-cache placement, and positional-encoding-decoupled KV-cache truncation.
  • TTFT decreases by up to 87% for multi-turn conversations.
  • Prompt prefilling throughput improves by 7.8× for multi-turn conversations.
  • End-to-end inference cost decreases by up to 70%.
Loading 2403.19708v3…