PrefixPlace: Provable Prefix Key-Value Placement for Large Language Model Serving under Heterogeneous Compute and Transfer Costs
2026-08-03 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster Computing
AI summaryⓘ
The authors looked at improving how Large Language Models reuse parts of previous computations to save time and memory during inference. They created a planner called PrefixPlace that smartly decides where to store and access these parts based on costs like memory limits and data transfer times. Their method uses a mathematical approach to find near-optimal placements quickly, performing almost as well as the best possible solutions. Testing on different hardware and tasks showed PrefixPlace can save more costs and run efficiently even on large problems.
Prefix Key-Value reuseLarge Language Modelsinference optimizationmemory budgetfacility-location problemreplica placementRetrieval-Augmented Generationmaterialization costvLLM Automatic Prefix Cachingresource allocation
Authors
Zhiyu Wang, Rajkumar Buyya
Abstract
Prefix Key-Value (KV) reuse avoids repeated prefill in Large Language Model (LLM) inference, but local misses require recomputation or replica fetches. Their relative cost varies with hardware, prefix depth, KV goodput, and replica location, making hit-rate-based placement suboptimal. To address this issue, we propose an epoch-level planner, PrefixPlace, which assigns prefix-complete targets under memory budgets and profiled demand, compute, and transfer costs. The objective decomposes into local-copy value plus first-replica coverage, and source-dependent costs yield a monotone facility-location objective; each worker update is an additive rooted-tree problem solved exactly in O(nk) time for n chunks and capacity k, giving a fixed-order 1/2-approximation that coordinate refinement and order-diverse starts improve without weakening. T4, L4, and A100 measurements reveal distinct regimes. Across 432 instances with exact optima, PrefixPlace averages 99.84% of optimum and never falls below 98.02%. In Retrieval-Augmented Generation (RAG) replays, it improves materialization-cost saving by 40.3% over vLLM Automatic Prefix Caching (vLLM-APC) and 6.3% over the best offline baseline. On WikiQA, gains are 40.4% and 5.3%. Finally, PrefixPlace solves a 50,000-node, 16-worker placement in 12.3 s on one processor, enabling timely replanning.