Preserving Admission Responsibility in Multi-Tenant Large Language Model Prefix Caches
2026-08-03 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster Computing
AI summaryⓘ
The authors address a problem in managing shared GPU memory when running multiple large language models (LLMs) that cache important data called Key-Value (KV) blocks. They identify a mismatch they call the admission-responsibility gap, where current methods don't properly handle who should be responsible for managing and evicting cached data. To fix this, they propose PrefixShield, a system that tracks responsibility across requests and controls reuse and eviction based on predicted 'debt'. Their experiments show that PrefixShield improves cache hit rates significantly compared to existing policies, while still allowing fair sharing of resources.
GPU memoryLarge Language Models (LLM)Key-Value blockscache hit ratioeviction policyadmission-responsibility gapPrefixShieldpersistent statevLLMreuse promotion
Authors
Zhiyu Wang, Rajkumar Buyya
Abstract
Shared prefix caching turns Graphics Processing Unit (GPU) memory into persistent state shared across Large Language Model (LLM) tenants. A group that materializes new Key-Value (KV) blocks can force another to lose reusable state, yet request-time schedulers account for transient service, replacement policies primarily rank object value, and static partitioning strands idle capacity. We call this mismatch the admission-responsibility gap. To close it, we propose PrefixShield, which meters newly materialized full KV blocks, carries responsibility across requests, gates reuse promotion while debt remains, and uses projected debt to select the group supplying eviction candidates. We implement PrefixShield in vLLM. In paired runs under one-touch pollution, PrefixShield improves victim cache hit ratio by 9.39 percentage points over the Least Recently Used (LRU) policy and 8.64 points over S3-FIFO, restoring the victim from 4.92% to 84.87% at 4096-block scale, and gains 2.00 points over S3-FIFO under two-pass replay. It preserves benign ShareGPT behavior and work-conserving access to idle capacity. Delayed replay yields a 35.16-point advantage while debt remains. These results show that object-value signals rank what to retain, while persistent responsibility determines which group bears reclamation pressure.