DéjàVu: KV-cache Streaming for Fast, Fault-tolerant Generative LLM Serving

Foteini Strati, Sara Mcallister, Amar Phanishayee, Jakub Tarnawski, Ana Klimovic

TL;DR

DéjàVu is a novel, fault-tolerant LLM serving system that optimizes distributed inference by treating the Key-Value (KV) cache as a dynamic stream. By disaggregating prompt and token processing, swapping microbatches between GPU and CPU, and replicating state across nodes, DéjàVu doubles serving throughput and slashes failure recovery overheads.

What Problem Does This Paper Address?

Generative Large Language Models (LLMs) are notoriously expensive to serve. Because they generate text token-by-token, they rely on a KV cache to store prior computations and avoid redundant work. This makes LLM serving highly stateful and introduces three massive system bottlenecks:

  1. Pipeline Bubbles (Bimodal Latency): LLM inference has two distinct phases: prompt processing (compute-bound, highly variable latency) and token generation (memory-bandwidth bound, near-constant latency). Mixing these in a standard pipeline parallel setup leaves GPUs idling in massive "pipeline bubbles."
  2. GPU Memory Overprovisioning: Existing frameworks allocate GPU memory for all microbatches upfront. Since a pipeline stage only processes one microbatch at a time, most of this preallocated KV cache memory sits idle.
  3. Fragile Fault Tolerance: Large models require hundreds of gigabytes of memory, forcing deployments across multiple GPUs and nodes where hardware failures are common. When a node fails, the stateful KV cache is lost, forcing the system to restart the request entirely from scratch.
Figure 2. Prompt processing and average per-token generation time on A100 GPUs, using FasterTransformer (with batch size 8 and prompt size 1000). Y-axis is in log scale.

Methods

The authors introduce DéjàVu, powered by a low-level streaming library called DéjàVuLib. The system implements three core techniques to address the aforementioned challenges:

  • Prompt-Token Disaggregation: DéjàVu separates the infrastructure into dedicated prompt processing workers (P-workers) and token generation workers (T-workers). A resource allocation planner mathematically optimizes the split of machines to maximize throughput based on model configurations.
  • Microbatch Swapping: Instead of keeping all KV caches on the GPU, DéjàVu stores them in CPU memory and streams them to the GPU only when the respective microbatch is about to be processed (swap in), streaming the updates back to the CPU immediately after (swap out).
  • State Replication for Fault Tolerance: To survive node failures without restarting from scratch, each worker asynchronously replicates its KV cache to its neighbor in an $N$-stage ring topology (Worker $x$ streams to Worker $x+1$).

To make streaming viable over limited-bandwidth interfaces like PCIe, DéjàVuLib introduces low-level optimizations: buffered copies to aggregate small, non-contiguous token updates into a single contiguous chunk, and layer-by-layer pipelining to overlap cache streaming with active GPU computation.

Figure 5. Full D´ej`aVu system diagram. When disaggregation is enabled, the workers do either only prompt processing (P-worker) or token generation (T-worker). The blue arrows stand for prompt- token cache exchange, the red arrows for cache replication, and the orange arrows for cache swapping.

Datasets

The system was evaluated using real-world workload characteristics by sampling token generation lengths from the LMSys-chat-1m dataset.

Evaluations were performed using HuggingFace versions of popular open models adapted for FasterTransformer, including:

  • GPT2 (1.5B)
  • OPT (13B, 30B, 66B)
  • BLOOM (176B)

Key Insights and Ideas

  • The KV Cache is a Stream, Not a Static Block: Traditionally, the KV cache is treated as a static allocation in GPU memory. DéjàVu's core insight is that by treating the KV cache as a fluid data stream, you can decouple compute from memory constraints.
  • Hiding Latency via Pipelining: Cache streaming doesn't have to stall execution. Because LLM layers are processed sequentially, prompt caches can be streamed layer-by-layer, effectively hiding the transfer overhead behind the computation of subsequent layers.
  • Replication is Cheaper than Recomputation: In stateful systems, losing data means redoing compute. Asynchronous ring replication introduces negligible overhead during steady-state execution but saves massive amounts of redundant computation during a failure.

Key Results

  • Throughput Gains: Without failures, DéjàVu improves end-to-end LLM serving throughput by up to 2× compared to a FasterTransformer baseline for massive models like OPT-66B and BLOOM-176B.
  • Memory Efficiency: Microbatch swapping allows the system to accommodate larger batch sizes on the same hardware, boosting throughput by up to 1.8×.
  • Low-Level Speedups: DéjàVuLib's buffered copying optimization achieves a 95× performance improvement over naive, non-contiguous memory transfers.
  • Resilience: In the event of a hardware failure, DéjàVu reduces microbatch latency by 1.54× and delivers a 1.16× shorter overall runtime compared to non-fault-tolerant baselines by resuming directly from the latest replicated token step.
Figure 4. Effect on cumulative latency of an inference request when a failure occurs in today’s systems, on a GPT2-1.5B model

Limitations and Future Work

While microbatch swapping significantly frees up GPU memory, it is heavily bound by PCIe bandwidth. If the sequence length or batch size becomes exceptionally large, the time required to swap the KV cache back into the GPU can exceed the token generation time, degrading performance.

Additionally, the authors note that they are currently working on integrating iteration-level scheduling into DéjàVu to further refine how requests are dynamically batched and interleaved.

Summary updated

Abstract

Distributed LLM serving is costly and often underutilizes hardware accelerators due to three key challenges: bubbles in pipeline-parallel deployments caused by the bimodal latency of prompt and token processing, GPU memory overprovisioning, and long recovery times in case of failures. In this paper, we propose DéjàVu, a system to address all these challenges using a versatile and efficient KV cache streaming library (DéjàVuLib). Using DéjàVuLib, we propose and implement efficient prompt-token disaggregation to reduce pipeline bubbles, microbatch swapping for efficient GPU memory management, and state replication for fault-tolerance. We highlight the efficacy of these solutions on a range of large models across cloud deployments.
BibTeX
@inproceedings{strati2024dejavu,
  author = {Foteini Strati and Sara Mcallister and Amar Phanishayee and Jakub Tarnawski and Ana Klimovic},
  title = {{DéjàVu: KV-cache Streaming for Fast, Fault-tolerant Generative LLM Serving}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=AbGbGZFYOD},
}
Figure