PrefixPlace: Provable Prefix Key-Value Placement for Large Language Model Serving under Heterogeneous Compute and Transfer Costs

PrefixPlace: Provable Prefix Key–Value Placement for Large Language Model Serving under Heterogeneous Compute and Transfer Costs Zhiyu Wang and 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. Index Terms—Large Language Model serving, Prefix caching, Combinatorial optimization, Approximation algorithms.

I. I NTRODUCTION Prefix reuse avoids repeated prefill when Large Language Model (LLM) requests share system prompts, retrieved documents, few-shot templates, or conversation histories. Modern inference engines reuse the corresponding Key–Value (KV) attention state [1], [2], [3], and recent designs also move KV state across workers or storage tiers [4], [5], [6], [7]. These mechanisms provide reuse and transfer primitives, but leave a separate planning question: which reusable prefixes should remain resident at each worker? This placement decision cannot be reduced to cache hit rate. On a local miss, a worker may either recompute the missing KV state from the token transcript or fetch a compatible replica. Their relative cost changes with accelerator speed, prefix depth, KV footprint, and effective KV goodput. Figure 1 isolates this effect using the same Qwen2.5-3B-Instruct model, 16-bit Floating-Point (FP16) representation, prompts, and software stack on three Graphics Processing Units (GPUs). Under

Materialization time (ms)

arXiv:2608.01655v1 [cs.DC] 3 Aug 2026

Quantum Cloud Computing and Distributed Systems (qCLOUDS) Lab School of Computing and Information Systems The University of Melbourne, Australia {zhiyu.wang4, rbuyya}@unimelb.edu.au

300

200

T4

A100

L4

Fetch @ 1.5 Gb/s

100

0

250

2000

4000

6000

Existing prefix (tokens)

Fig. 1. Measured time to materialize a 512-token missing chunk of Qwen2.53B in 16-bit Floating-Point (FP16) after an existing prefix. The dashed line is the fetch time implied by the measured 18.9-MB KV footprint and 1.5-Gb/s effective KV goodput. T4 favors fetching, L4 crosses near 3.8K tokens, and A100 favors recomputation over the measured range.

a common effective KV goodput of 1.5 Gb/s, fetching the measured 18.9-MB KV state for a 512-token chunk takes about 100.7 ms. Recomputation is already slower on T4, crosses the transfer cost near 3.8K existing tokens on L4, and remains faster throughout the measured A100 range. Thus, the same model and transfer condition can require opposite decisions solely because requester hardware changes. To address this problem, we develop PrefixPlace, an epochlevel planner that assigns each worker a resident prefix target from an observed prefix tree, demand matrix, memory budget, and profiled materialization costs. A feasible target is prefixcomplete: retaining a chunk also retains every cacheable ancestor on its prefix path. Coordination is needed because one resident replica can reduce miss cost for multiple requesters, but only where fetching beats recomputation; when transfer cost depends on the source, replica identity also affects value. Local-popularity policies can therefore over-replicate shared prefixes, whereas deduplication alone ignores requester heterogeneity and sourcedependent transfer. PrefixPlace accepts arbitrary epoch-level compute and transfer profiles rather than a parametric latency law; every local copy then contributes modular value, the first replica contributes weighted coverage, and source-dependent

costs generalize this to a monotone facility-location objective. In both cases, one worker’s exact marginal value is additive across tree nodes, enabling a shared rooted-tree oracle with provable guarantees. Our contributions are threefold. Cost-aware prefix placement model. We formulate epoch-level placement of prefix-complete KV targets under arbitrary profiled compute and transfer costs. We derive an exact modular-plus-coverage decomposition for requester-side transfer costs and a source-dependent facility-location formulation, precisely characterizing the shared value created by the first replica of each chunk. • Algorithms with guarantees. For a prefix tree with n placement chunks and a worker capacity of k chunks, we give an O(nk) exact single-worker Dynamic Programming (DP) algorithm. We prove that coordinated placement is strongly NP-hard and develop WorkerGreedy, a fixed-order 1/2-approximation for both objectives. PrefixPlace combines this guaranteed initialization with coordinate refinement and order-diverse starts to improve solution quality while preserving the bound. • Profile-driven evaluation. Measurements on T4, L4, and A100 GPUs across Qwen2.5 models from 3B to 32B expose hardware- and goodput-dependent fetch/recompute regimes. PrefixPlace averages 99.84% of exact optimum over 432 requester-side and 99.62% over 45 sourcedependent instances, and Retrieval-Augmented Generation (RAG) replay, WikiQA exact-demand, topology, demand-shift, and Central Processing Unit (CPU) scaling studies evaluate practical advantage and replanning cost.

•

The rest of the paper is organized as follows. Sections II–V present the problem setting, optimization model, algorithms, and performance evaluation respectively; Section VI reviews related work and Section VII concludes with future directions. II. P ROBLEM S ETTING A. Prefix KV as a placement object A transformer prefix determines the KV tensors reusable by every continuation of the same token sequence. Modern engines expose this reuse through block-structured prefix caches [1], [2], while recent designs stream, offload, or share KV state [5], [6], [4], [8]. PrefixPlace groups contiguous engine blocks into placement chunks, each treated as one placement and materialization unit. Grouping preserves exactprefix semantics, amortizes fixed operation overhead, and limits optimizer state. For each worker, the planner selects a prefix-complete resident target: a parent-closed set in which selecting a chunk also selects every cacheable ancestor. A target may contain multiple branches, but each selected chunk lies on a complete locally resident prefix path. A request’s materialization cost is the sum of the incremental costs of its required chunks; PrefixPlace consumes the profiled lookup values directly and does not assume a linear depth-cost relationship.

B. Compute and transfer cost model Let wm (b) be the profiled cost for worker m to materialize placement chunk b locally, conditioned on its preceding prefix, and let fm (b) be the effective cost to fetch that chunk from an eligible peer. For a chunk of Zb bytes and effective KV goodput rm , fm (b) = Zb /rm . (1) The planner may instead consume a directly measured fetchcost table, including stable copy, protocol, and round-trip components. When holder identity matters, fm←h (b) denotes the cost for requester m to fetch b from holder h. Remote reuse is beneficial to requester m exactly when wm (b) > fm (b). We call a measured depth where the preferred action changes a fetch/recompute crossover; the optimization neither requires one to exist nor assumes monotone costs, and hardware, model scale, prefix depth, and network path can each flip the preferred action for the same logical chunk. C. Planning epoch and compatibility PrefixPlace optimizes one planning epoch from aggregate prefix-tree demand, worker budgets, compatible resident states, and effective compute/transfer profiles. Routing operates outside the optimizer and determines the epoch demand matrix; Section IV describes when refreshed inputs trigger replanning. Candidate holders are filtered for compatible model weights and revision, KV precision, positional encoding, and parallelism layout. The planner exports one prefix-complete target per worker to the exact-prefix cache layer. III. O PTIMIZATION M ODEL AND S TRUCTURAL D ECOMPOSITION A. Prefix tree, demand, and feasibility Let T = (V, E) be a rooted prefix tree with n = |V | equalsized cacheable placement chunks; an optional no-cost dummy root represents the empty prefix and does not consume budget. Each node extends the exact prefix represented by its parent. Worker m ∈ M = {1, . . . , M } has budget km and selects a resident set Tm ⊆ V . We call Tm prefix-complete when it is parent-closed: selecting a node also selects every cacheable ancestor. A target may contain multiple branches, but every selected node lies on a complete locally resident prefix path. Workers optimized together satisfy the compatibility filters of Section II, so km maps directly to a byte budget. Let Λm (b) ≥ 0 be the aggregate epoch demand for requests routed to worker m that require chunk b. A request contributes demand to every placement chunk on its prefix path. When Λ is measured in requests per epoch and w, f in milliseconds, the objective below is milliseconds saved per epoch; normalized demand weights induce the same optimizer. The local recomputation cost is wm (b) ≥ 0. We first consider a sourceindependent, requester-specific fetch cost fm (b) ≥ 0, which may vary by requester and chunk; Section III-C then admits arbitrary source-dependent costs. Once resident locally, a chunk incurs zero materialization cost for that requester. If only a peer stores it, the requester

chooses the cheaper of recomputation and fetch, paying min{wm (b), fm (b)}; with no resident copy, it pays wm (b). Thus, a remote replica creates value only for requesters whose transfer cost is below recomputation.

If Hb (T ) = {h : b ∈ Th } is the holder set induced by placement T , then the exact saving is Fpair (T ) =

Use an all-recompute placement as the baseline. Define the local value am (b) = Λm (b) min{wm (b), fm (b)},

(2)

and the aggregate remote-coverage value M X

Λm (b) [wm (b) − fm (b)]+ ,

(3)

(6)

Proposition 1 (Source-dependent marginal oracle). Fpair is nonnegative, monotone, and submodular. Moreover, after fixing the current placements of all workers other than h, its exact marginal placement problem is a parent-closed tree selection with additive node profits X (−h) ph (b) = Λm (b)[qm←h (b) − vm (b)]+ , (7) m

where [x]+ = max{x, 0}. The local term measures what worker m gains from storing b even when another copy exists. The coverage term measures the shared saving created by the first resident copy. This separation is exact, not an approximation. Lemma 1 (Modular-plus-coverage decomposition). For any feasible placement T = (T1 , . . . , TM ), total materializationcost savings are exactly F (T ) =

h∈Hb (T )

where the maximum over an empty set is zero.

m=1

M X X

Λm (b) max qm←h (b),

b∈V m=1

B. Savings decomposition

∆(b) =

M XX

am (b) +

m=1 b∈Tm

X

∆(b).

(4)

b∈∪m Tm

Consequently F : 2E → R+ is nonnegative, monotone, and submodular over the ground set E = {(m, b) : m ∈ M, b ∈ V } of worker–chunk placement elements. Proof. Fix requester m and chunk b. If no worker stores b, the saving is zero. If a peer but not m stores it, the saving is [wm (b) − fm (b)]+ . If m stores it, the saving is wm (b) = min{wm (b), fm (b)} + [wm (b) − fm (b)]+ . Multiplying by Λm (b), summing over requesters, and observing that the second summand is earned once iff b is covered gives (4). The first term is modular and the second is weighted coverage, hence monotone submodular. The decomposition reduces arbitrary compute and transfer profiles to two interpretable values. If every requester prefers recomputation, ∆(b) = 0 and coordination creates no remotereuse value for chunk b. Otherwise, the first replica contributes exactly ∆(b) beyond the holder’s local benefit. Hence ∆ identifies where coordination can matter, while budgets and parent closure determine which opportunities are feasible.

(−h) where vm (b) is requester m’s best saving on b among the

current holders other than h. Proof. For each (m, b), the term in (6) is the maximum of fixed nonnegative weights over selected holders, which is monotone submodular. Their nonnegative weighted sum is therefore monotone submodular. Adding holder h improves (−h) (m, b) by exactly [qm←h (b) − vm (b)]+ ; summing over requesters gives (7), and summing these independent chunk marginals over a candidate subtree gives its exact gain. Source dependence changes the marginal node weights but not the per-worker tree problem. The rooted-tree oracle and the approximation/refinement framework therefore apply to both objectives. Setting fm←h (b) = fm (b) for every h ̸= m recovers (4). The placement problem is therefore max

T1 ,...,TM

s.t.

F (T ) |Tm | ≤ km ,

(8) Tm parent-closed, ∀m,

with Fpair replacing F for source-dependent costs. Compute and transfer behavior enter through profiled node costs; no ordering, convexity, or parametric latency law is required. Lookup tables, interpolation, and analytical profiles therefore lead to the same combinatorial problem and the same guarantees. IV. A LGORITHMS AND P LANNER O PERATION Figure 2 summarizes how PrefixPlace turns epoch inputs into per-worker targets. This section develops each stage in turn.

C. Source-dependent transfer costs

A. Exact single-worker oracle

Requester-side costs treat eligible holders as equivalent, while transfer costs may also depend on the source. Let fm←h (b) be the cost for requester m to fetch chunk b from holder h, and define the saving offered by holder h as ( wm (b), h = m, qm←h (b) = (5) [wm (b) − fm←h (b)]+ , h ̸= m.

The shared algorithmic primitive is a maximum-profit parent-closed subtree for one worker. Let each node have profit p(b) and let the budget be k. Number nodes in preorder b1 , . . . , bn , and let next(i) be the first position after the subtree rooted at bi . Define D[i, j] as the maximum profit obtainable from positions i, . . . , n using at most j additional chunks, under the invariant that the nodes selected before position i

Fig. 2. PrefixPlace architecture. Each epoch, the observed prefix tree, per-worker demand matrix Λm (b), memory budgets km , and GPU-profiled compute/transfer costs wm (b), fm←h (b) feed a three-stage planner: exact savings decomposition into local value, coverage, and source-aware marginals (Lemma 1, Prop. 1); WorkerGreedy initialization with the exact O(nk) rooted-tree oracle and a fixed-order 1/2-approximation (Theorems 1 and 3); and monotone coordinate refinement over order-diverse starts that preserves the 1/2 bound. One prefix-complete target per worker is exported to the exact-prefix cache layer; demand or routing shifts trigger replanning under the amortization rule (§IV-D).

are parent-closed and contain every ancestor of bi . For i ≤ n and j ≥ 1, D[i, j] = max{D[next(i), j], p(bi ) + D[i + 1, j − 1]} . (9) The boundary conditions are D[n + 1, j] = 0 for all j and D[i, 0] = 0 for all i. The first branch skips bi and therefore its entire subtree; the second includes bi , so preorder position i + 1 is eligible. Subtree endpoints, and hence every next(i), are precomputed in O(n) time. Theorem 1 (Exact rooted-tree oracle). For a rooted tree with n placement chunks and budget k, the maximum-profit parentclosed placement is computed exactly in O(nk) time and O(nk) memory. Proof. In preorder, the subtree rooted at bi occupies the contiguous interval {bi , . . . , bnext(i)−1 }. Consider an eligible state (i, j) in which the previously selected nodes are parent-closed and contain every ancestor of bi . Every feasible continuation makes one of two decisions. If it omits bi , parent closure also excludes every descendant of bi , so the next state is (next(i), j). If next(i) ≤ n, every ancestor of bnext(i) is also an ancestor of bi and is therefore already selected. If the continuation includes bi , it earns p(bi ) and proceeds to (i + 1, j − 1). When bi+1 is a descendant of bi , all of its ancestors are either ancestors of bi or bi itself and are therefore selected; when bi is a leaf, i + 1 = next(i) and the preceding argument applies. Thus, both successor states preserve eligibility, and the two cases are exhaustive, establishing (9) by backward induction. Hence D[1, k] is optimal. A preorder traversal computes all subtree endpoints in O(n) time. The table contains O(nk) states with O(1) work per state, and backtracking visits at most n states. The resulting dynamic program avoids generic child-bychild tree-knapsack convolution and is linear in tree size for each budget unit. B. Joint placement: hardness and approximation Coordinated placement couples workers through shared coverage value. The resulting hardness is intrinsic rather than an artifact of heterogeneous hardware or transfer costs.

Theorem 2 (Strong NP-hardness). Maximizing (4) over parent-closed placements with per-worker budgets is strongly NP-hard, even when all workers share the same depthdependent recomputation and fetch costs and all holder workers have the same positive budget. Proof.PReduce from 3-Partition. Given integers s1 , . . . , s3q with i si = qB and B/4 < si < B/2, construct a spider with an always-present dummy root and one leg of si cacheable chunks for each item. Create q holder workers of budget B and one requester worker of budget zero. All workers have the same costs: a depth-d chunk has recomputation cost w(d) = 2d and fetch cost f = 1. Only the requester has demand. Put one request at the tip of leg i with rate λi = 1/si ; hence every chunk on that leg has demand λi at the requester. If the union of holder placements covers the first xi ≤ si chunks of leg i, its saving is λi

xi xi X x2 1 X (w(d) − f ) = (2d − 1) = i ≤ xi , si si d=1

d=1

with equality P only for xi ∈ {0, si }. Therefore total saving is at most i xi ≤ qB, the aggregate holder capacity. Reaching qB requires every covered leg to be complete, every item leg to be covered, no duplicated chunk, and every holder budget to be full. Because a placement is parent-closed, covering the tip of a leg forces one holder to store that entire leg. Thus value qB is attainable iff the item lengths can be assigned to the q holders with load exactly B each. The 3-Partition bounds then force exactly three items per holder. Conversely, any valid 3-partition gives such a placement and attains qB. The construction uses only polynomially encoded integers/rationals and preserves the strong NP-hardness of 3-Partition [9]. The decomposition nevertheless preserves exact per-worker optimization. For a fixed worker order, let U be the chunks already covered by earlier workers. Worker m then sees the exact marginal profit pU / U }∆(b). m (b) = am (b) + 1{b ∈

(10)

The best feasible placement for m is therefore exactly Theorem 1 with profits pU m.

Theorem 3 (WorkerGreedy). Sequentially optimizing each worker’s exact marginal contribution in any order fixed before the run produces a feasible placement T G with G(T G ) ≥ 1 ∗ 2 G(T ), where G is either F in (4) or the source-dependent Fpair in (6). Proof. View each placement element as a worker–chunk pair. Let Si be the union of the first i greedy worker placements in the fixed order, and let Oi denote the placement assigned to worker i in an optimal joint solution T ∗ . Write Ri = SM ∪ O1 ∪ · · · ∪ Oi , with R0 = SM . Monotonicity gives G(T ∗ ) ≤ G(RM ). Moreover, Si−1 ⊆ Ri−1 , so diminishing returns yields G(Ri ) − G(Ri−1 ) ≤ G(Si−1 ∪ Oi ) − G(Si−1 ). Summing over i gives G(T ∗ ) ≤ G(SM ) +

X  G(Si−1 ∪ Oi ) − G(Si−1 ) . i

When worker i is processed, Oi is feasible for its exact marginal oracle. The corresponding term is therefore at most G(Si ) − G(Si−1 ). These greedy marginals telescope to G(SM ), and hence G(T ∗ ) ≤ 2G(SM ) = 2G(T G ). Configuration methods based on Linear Programming (LP) give stronger worst-case factors for the requester-side separable special case [10]. PrefixPlace contributes a direct rooted-tree-oracle framework that applies unchanged to both requester-side coverage and source-dependent facility-location marginals, while avoiding a global configuration LP and rounding stage. C. PrefixPlace: guaranteed coordination and refinement PrefixPlace strengthens the guaranteed WorkerGreedy solution through coordinate refinement: it removes one worker at a time, recomputes that worker’s exact node marginals against all other placements, reruns the same DP using (10) or (7), and accepts only strictly improving replacements (tolerance ε in floating point). Because the feasible state space is finite, refinement terminates at a coordinate-wise local optimum; monotone improvement preserves the starting 1/2 guarantee. To reduce order sensitivity, PrefixPlace refines multiple WorkerGreedy starts and returns the best candidate. For M ≤ 5, it evaluates every order; otherwise, it uses the standalone-score order, its reverse, and six fixed pseudorandom permutations. For the requester-side objective, it also includes Independent, Popularity, and LocalDedup candidates, ensuring that the returned placement is never worse than these alternatives under the same objective. Given node marginals, one requester-side greedy pass or one P refinement sweep costs O(n m km ). For source-dependent costs, maintaining the largest and second-largest current holder values for each requester–chunk pair computes all leave-oneworker-out marginals in O(M 2 n) per sweep. These are perpass bounds; the evaluated instances converge in two to three sweeps.

Algorithm 1 P REFIX P LACE with the exact rooted-tree oracle. Require: Tree T ; budgets {km }; demand {Λm }; profiled costs; tolerance ε Ensure: Prefix-complete placements T = (T1 , . . . , TM ) 1: procedure ROOTED DP(p, k) 2: Number nodes b1 , . . . , bn in preorder and compute next(i) 3: Set D[n + 1, j] ← 0 for 0 ≤ j ≤ k 4: Set D[i, 0] ← 0 for 1 ≤ i ≤ n 5: for i = n, n − 1, . . . , 1 do 6: for j = 1, 2, . . . , k do 7: s ← D[next(i), j] {skip bi and its subtree} 8: t ← p(bi ) + D[i + 1, j − 1] {take bi } 9: D[i, j] ← max{s, t} and record the maximizing branch 10: end for 11: end for 12: Backtrack from D[1, k] to recover the parent-closed set 13: return the recovered set 14: procedure P REFIX P LACE(T , {km }, {Λm }, costs) 15: Build am , ∆ by (2)–(3), or qm←h by (5) 16: Π ← all worker orders if M ≤ 5 17: if M > 5 then 18: Π ← standalone-score order, its reverse, and six fixed pseudorandom permutations 19: end if 20: C ← ∅ 21: for each fixed order π ∈ Π do 22: Tm ← ∅ for every worker m 23: for each worker h in order π do 24: if requester-side costs then S 25: U ← ℓ̸=h Tℓ 26: ph (b) ← ah (b) + 1{b ∈ / U }∆(b) for all b 27: else (−h) 28: vm (b) ← maxℓ̸=h:b∈Tℓ qm←ℓ (b) P (−h) 29: ph (b) ← (b)]+ m Λm (b)[qm←h (b) − vm 30: end if 31: Th ← ROOTED DP(ph , kh ) 32: end for 33: repeat 34: improved ← FALSE 35: for each worker h in order π do 36: Thold ← Th ; gold ← G(T ); Th ← ∅ 37: if requester-side costs then S 38: U ← ℓ̸=h Tℓ 39: ph (b) ← ah (b) + 1{b ∈ / U }∆(b) for all b 40: else (−h) 41: Recompute vm (b) from the current holders P (−h) 42: ph (b) ← (b)]+ m Λm (b)[qm←h (b) − vm 43: end if ′ 44: Th ← ROOTED DP(ph , kh ) 45: if G(T−h , Th′ ) > gold + ε then 46: Th ← Th′ ; improved ← TRUE 47: else 48: Th ← Thold 49: end if 50: end for 51: until improved = FALSE 52: C ← C ∪ {copy(T )} 53: end for 54: Add Independent, Popularity, and LocalDedup placements to C when requester-side

55: return arg maxX∈C G(X)

D. Planner operation and epoch updates Algorithm 1 turns each epoch’s tree, demand, budgets, and cost profiles into one prefix-complete target per worker. The planner maps measured profiles to wm (b) and either fm (b) or fm←h (b), constructs exact node marginals, evaluates the guaranteed and refined candidates, and exports the best target set to the cache layer. Its state is limited to the prefix tree, demand arrays, worker budgets, and requester-side or pairwise cost tables. When routing or popularity changes, the planner evaluates both the incumbent and a reoptimized target under refreshed demand. It adopts the new target only when the predicted horizon saving exceeds the one-time cost of materializing newly assigned chunks. Section V evaluates this amortization

rule together with solver runtime. V. P ERFORMANCE E VALUATION The evaluation follows the paper’s claim chain through five Research Questions (RQs): (RQ1) do measured costs require worker-specific decisions; (RQ2) how close is PrefixPlace to exact and relaxed optima; (RQ3) when does coordination create value; (RQ4) do the structural predictions persist across workloads, source-dependent costs, and input perturbations; and (RQ5) can PrefixPlace replan efficiently under demand shifts? A. Experimental methodology a) Measured compute and KV profiles: We profile unquantized FP16 Qwen2.5 models with identical prompts and software settings. The cross-hardware study runs 3B on T4, L4, and A100; 7B on L4 and A100; and 14B and 32B on A100. Each context length uses five prompts, three warmups, and seven timed repetitions; incremental measurements use three prompts and five repetitions per prefix–segment pair. Compute Unified Device Architecture (CUDA) synchronization brackets every timed region, and all repetitions are retained. The stack is CUDA 12.8, PyTorch 2.8.0+cu128, and Transformers 4.55.2. Table I summarizes the completed context ranges, measured KV footprints, and repetition stability. Unless otherwise stated, the main experiments use 512-token placement chunks and the corresponding measured incremental curves, with linear interpolation between sampled depths. Effective KV goodputs from 0.75 to 5 Gb/s span the measured fetch/recompute boundaries; RQ4 evaluates 1024token chunks as a granularity sensitivity check. b) Parameterized and public prefix structures: Two reproducible families vary sharing, locality, skew, and depth independently. The RAG-shaped workload has a shared system prefix, 40 document branches of 4–6 chunks, and 10 query leaves per document, with Zipf(0.9) document and Zipf(0.6) query popularity. A shared-request fraction ρ distributes that fraction of each document’s requests uniformly across workers; the remainder stays at a random home worker. The multiturn workload has 120 session chains of 3–15 chunks with Zipf(0.8) popularity and the same attachment model. Unless varied, each worker can store 10% of tree nodes. We also derive a public retrieval tree from all English WikiQA [11] entries (29,258 candidate rows, 3,047 questions, 2,811 document titles), which a deterministic lexical-token estimator partitions into 9,917 128-unit placement chunks; under the measured 3B FP16 KV footprint, an equal 1-GiB budget holds 227 chunks per worker. Offline placements use the exact aggregate demand of the full corpus. To evaluate the order-sensitive vLLM Automatic Prefix Caching (vLLM-APC) baseline under that same demand, each trial forms a complete 18,282-request multiset containing every worker–question pair exactly once; independent random permutations warm and evaluate the cache. A ±25% lexical-token-scale sweep tests sensitivity to the token mapping.

c) Unified benchmark with exact optima: We evaluate 432 three-worker instances and solve every instance to exact Mixed-Integer Linear Programming (MILP) optimality. The first 216-instance factorial block uses a reduced RAG-shaped tree designed for exact solution (30 document branches of two to four chunks, three question leaves each; 175–189 chunks), crossing eight workload seeds, three request-sharing levels, three transfer-goodput settings, and three worker configurations (mixed T4/L4/A100, three L4, or three A100; 8 × 3 × 3 × 3 = 216). The second block (22 branches of two to nine chunks, three leaves each; 183 chunks; mixed T4/L4/A100) crosses three levels of popularity-to-depth mismatch, two demand-skew levels, two budgets, three sharing levels, two goodput settings, and three seeds (3×2×2×3×2×3 = 216). At stronger mismatch levels, popular documents are assigned more often to shallower branches, making demand alone less predictive of the materialization cost saved by placement. All exact quality statistics below are computed over the pooled 432-instance benchmark.

d) Comparators and reporting metric: We compare PrefixPlace with four baselines. vLLM-APC [1], [12] replays vLLM’s per-worker block-level Least Recently Used (LRU) prefix cache on the routed request stream. Independent runs the exact rooted-tree oracle per worker on local demand weighted by recomputation cost, ignoring cross-worker reuse value; Popularity uses local demand alone; LocalDedup additionally discounts chunks already covered by earlier workers but not the requester-wide value created by the first copy. The requester-side placement comparator is the largest-F result among Independent, Popularity, and LocalDedup; sourcedependent experiments use the strongest of mean-rate, meantransfer-cost, best-source-cost, and Independent variants. For the RAG request-stream replay, a 30,000-request epoch warms APC and profiles the planners, and an independent 30,000request epoch evaluates all methods across five workload × five arrival-order seeds. For WikiQA, the offline methods use exact aggregate demand, while vLLM-APC uses 25 independent warm/evaluation permutation pairs of the complete worker–question request multiset. Saving over all-recompute is the profiled recomputation cost avoided by local hits or planned local/remote reuse. Because all cost inputs are measured on the profiled GPUs, the reported objective is denominated in milliseconds of avoided recomputation and transfer per epoch, and gains translate directly to materialization-time reductions on the corresponding hardware. For PrefixPlace placement P and comparator B, gain(P, B) = 100[G(P ) − G(B)]/G(B), where G is F or Fpair . Comparisons against exact MILP solutions and tree-aware LP bounds separately assess absolute solution quality.

e) Exact solvers and demand transitions: The unified requester-side benchmark uses a MILP with binary placement xm,b and coverage yb ; workload-scale checkpoints use its LP

TABLE I M EASURED GPU– MODEL PROFILES . T HE MEDIAN C OEFFICIENT OF VARIATION (CV) SUMMARIZES REPEATED FULL - PREFILL MEASUREMENTS . Context (tokens)

KV bytes/token

Median CV

128–7168 128–8192 128–8192 128–8192 128–8192 128–8192 128–4096

36,864 36,864 57,344 36,864 57,344 196,608 262,144

0.51% 0.42% 0.35% 0.27% 0.25% 0.17% 0.16%

T4-3B L4-3B L4-7B A100-3B A100-7B A100-14B A100-32B

X

am (b)xm,b +

m,b

s.t.

X

X

∆(b)yb

xm,b ≤ xm,par(b) ,

(11)

X

0 ≤ xm,b , yb ≤ 1.

b

yb ≤

xm,b ,

0.75 0.50 0.25

0.70

0.80

0.90

0.95

1.00

Savings / exact optimum

b

xm,b ≤ km ,

PrefixPlace

Popularity

0.00 0.60

relaxation: max

LocalDedup

Independent

1.00

Empirical CDF

Profile

vLLM-APC

m

SciPy 1.17.0 and HiGHS 1.8.0 solve both formulations. The source-dependent MILP P adds assignment variables zm,h,b with zm,h,b ≤ xh,b and h zm,h,b ≤ 1, exactly linearizing (6). For replanning, 100 transitions span both parameterized workloads, five seeds, 1.0/1.5-Gb/s goodput, six mixed-GPU workers, and 10% budgets. We shift 25/50/100% of routing mass or perturb popularity with log-normal σ = 0.5/1.0. Break-even requests equal the profiled one-time cost of newly assigned chunks divided by per-request objective gain. B. RQ1: do measured profiles require worker-specific decisions? Table I first establishes the coverage and stability of the measured profiles; median CV is at most 0.51% for every GPU–model pair. Figure 1 then holds model, representation, prompts, and effective KV goodput fixed and shows the decision consequence: T4, L4, and A100 fall into fetchdominated, crossover, and recompute-dominated regimes. For Qwen2.5-7B, the measured 512-token recomputation curve is approximately 170.2 + 0.0100p ms on L4 and 48.1 + 0.0050p ms on A100, where p is existing-prefix length. At 3 Gb/s, the same 29.4-MB chunk favors fetching on L4 but crosses near 6.1K tokens on A100. For A100-32B, the 134.2-MB chunk crosses near 2.7K tokens at 5 Gb/s. Thus, hardware identity changes the preferred miss action even when the model and network condition are held fixed. C. RQ2: how close is PrefixPlace to optimum? a) Exact optimum: Figure 3 scores vLLM-APC and the principal offline methods under the exact MILP objective on the unified 432-instance benchmark, with 175–189 chunks per instance. Per instance, five independent 30,000-request streams warm vLLM-APC; each frozen cache state, restricted to its usable prefix-complete blocks, is scored under the same objective. Averaged over the five orders, vLLM-APC reaches 78.63% of optimum with a 65.62% minimum. PrefixPlace averages 99.84% and never falls below 98.02%. These results

Fig. 3. Empirical Cumulative Distribution Function (CDF) of objective ratios to the exact MILP optimum across the unified 432-instance benchmark, with 175–189 chunks per instance. vLLM-APC freezes each replayed cache state and is evaluated under the same objective. TABLE II C UMULATIVE COMPONENT ABLATION ON THE UNIFIED 432- INSTANCE EXACT BENCHMARK . Variant One-pass WorkerGreedy + coordinate refinement + order-diverse starts + comparator safeguards

Mean/Opt. Min/Opt. 98.15% 98.93% 99.84% 99.84%

82.33% 85.76% 97.55% 98.02%

Exact 174/432 196/432 246/432 246/432

demonstrate that PrefixPlace remains consistently near-optimal across the unified benchmark. b) Component ablation: Table II isolates how complete PrefixPlace reaches this quality: WorkerGreedy averages 98.15% of optimum; coordinate refinement improves 124 instances (mean 98.93%, minimum 82.33% to 85.76%); orderdiverse starts improve another 161 (mean 99.84%, minimum 97.55%); and the comparator safeguards lift the minimum to 98.02%. The global minimum at every stage lies in the popularity-to-depth-mismatch block, the difficult tail of the benchmark, which refinement, order diversity, and safeguards repair while keeping every instance within 1.98% of the exact optimum. c) Broader exact and relaxed benchmarks: Table III consolidates this result with source-dependent exact instances and workload-scale LP bounds. Across 45 source-dependent MILP instances, PrefixPlace averages 99.62% of optimum and never falls below 97.90%. The 40 tree-aware LP checkpoints (three T4, three L4, three A100, or mixed T4/L4/A100 workers; two sharing levels; five seeds; 4 × 2 × 5 = 40) yield 99.66% of the LP upper bound on average, never below 98.71%, with the 10-checkpoint mixed-GPU subset at 99.55% and never below 99.07%. Because the LP relaxation retains capacity and parent closure and upper-bounds the integral optimum, each LP ratio is a valid lower bound on PrefixPlace’s ratio to it. D. RQ3: when does coordination create value? Figure 4(a) fixes full request sharing and the default 10% worker budget, then sweeps effective KV goodput in the mixed T4/L4/A100 RAG-shaped workload. Every point is a five-seed mean with a 95% confidence interval. PrefixPlace improves over the strongest evaluated placement baseline throughout the measured range: gain rises from 1.1% at 0.75 Gb/s to 6.2% at 1.5 Gb/s and remains 8.1–8.9% from 2 to 5 Gb/s. The peak

TABLE III S OLUTION QUALITY AGAINST EXACT OPTIMA AND LP UPPER BOUNDS . Setting Requester-side exact (432) Source-dependent exact (45) Tree-aware LP (40) Mixed-GPU LP subset (10)

Mean ratio Minimum ratio 99.84% 99.62% 99.66% 99.55%

98.02% 97.90% 98.71% 99.07%

Fig. 4. Value unlocked by coordination over the strongest evaluated placement baseline. (a) Full-sharing effective-KV-goodput sweep at a 10% worker budget. (b) Gain as per-worker budget varies under full sharing and 1.5-Gb/s effective KV goodput. Error bars show 95% confidence intervals; numeric labels report mean gain.

mean is 8.9% at 3 Gb/s, and the maximum over the complete 600-setting RAG sweep is 10.0%. Figure 4(b) isolates capacity. Mean gains are 7.34%, 6.24%, 3.10%, and 1.24% at 5%, 10%, 20%, and 30% budgets, respectively. Scarce capacity makes redundant replicas more expensive, so coordination helps most precisely where placement choices are consequential; the candidate safeguard retains the strongest evaluated alternative under the same objective. E. RQ4: do the structural predictions persist across workloads and costs? a) RAG request replay: Figure 5(a) reports PrefixPlace’s paired relative gain over each comparator on the RAG request replay. Across 25 paired runs, PrefixPlace improves saving by 40.29% over vLLM-APC, 8.59% over both Independent and Popularity (unrounded 8.588% and 8.595%, reflecting their nearly identical saving), and 6.30% over LocalDedup, and every paired run favors PrefixPlace. b) WikiQA exact-demand evaluation: Figure 5(b) uses the exact aggregate demand of the full WikiQA workload. PrefixPlace improves saving by 40.41% over vLLM-APC, 17.43% over Independent, 17.72% over Popularity, and 5.31% over LocalDedup. For vLLM-APC, the 40.41% mean is computed over 25 independent order pairs and has a 95% confidence interval of ±0.10 percentage points; each replay preserves the same complete worker–question demand used by the offline methods. The gain over the strongest offline baseline remains 4.99–6.69% under a ±25% lexical-token-scale sweep. c) Source-dependent transfer costs: Figure 6 evaluates whether holder identity changes placement value at sharedrequest fractions ρ ∈ {0.75, 1.0}. Two groups each contain one T4, L4, and A100 worker, with 10-Gb/s within-group goodput and 1–3-Gb/s between-group goodput; source-aware PrefixPlace uses the full fm←h table against the strongest source-oblivious variant under true costs. At 1 Gb/s between groups, mean gain is 5.8% for ρ = 0.75 and 7.4% for ρ = 1.0 (maximum 8.1% over all 30 settings); at 3 Gb/s, gains remain 2.0% and 1.8%, so source identity matters beyond requesteronly summaries.

Source-aware gain (%)

Fig. 5. PrefixPlace’s relative gain over each comparator. (a) RAG request replay: means and 95% confidence intervals over 25 paired 30,000profile/30,000-evaluation runs. (b) WikiQA exact-demand evaluation: offline bars use the full aggregate demand; the APC bar averages 25 independent warm/evaluation permutations of the complete worker–question request multiset, preserving that same demand. 8

ρ = 0.75

7

ρ = 1.0

6 5 4 3 2 1.0

1.5

3.0

Between-group KV goodput (Gb/s)

Fig. 6. Source-aware gain over the strongest evaluated source-oblivious variant at ρ = 0.75 and ρ = 1.0 as between-group effective KV goodput varies (mean ±1.96 standard errors across five seeds).

d) Robustness analysis: Table IV evaluates placements computed from perturbed inputs under the unperturbed calibrated objective, perturbing each profiled or demand value independently as b c = c exp(ϵ), ϵ ∼ N (0, σ 2 ). Even at σ = 0.30, the fifth percentile retains at least 98.74% of calibrated-placement saving. e) Sensitivity analysis: Table V varies workload structure, demand skew, worker order, placement granularity, and request-stream horizon: the multi-turn workload retains measurable coordination value, increasing Zipf concentration reduces new coverage opportunities, coordinate refinement nearly removes order sensitivity, doubling the chunk size preserves the coordination pattern, and the advantage over vLLM-APC persists across replay horizons of 3,000 to 30,000 requests. F. RQ5: can PrefixPlace replan efficiently under demand shifts? a) Placement updates: Table VI reports reoptimization gains and Break-Even (BE) requests. Reoptimization improves 95 of 100 transitions, with the amortization rule retaining the incumbent in five mild 25% routing shifts; across beneficial updates, median and 90th-percentile BE are 769 and 2,346 requests, 96.8% break even within 5,000 and all within 10,000, and complete routing shifts yield 23.74% median gain with a 251-request median BE. b) Solver runtime: Figure 7 measures CPU time of the coordinate-refined solver as tree size and worker count increase, with per-worker budgets given in the caption. On an EPYC 9V74 CPU, the n = 10,000, k = 128 configuration

TABLE VII O PTIMIZATION SCOPE OF REPRESENTATIVE KV- REUSE METHODS . Work

Primary decision

KV object / scope

Distinction from PrefixPlace

vLLM [1]/ SGLang [2] Preble [13]

Local cache organization and execution

Exact-prefix blocks / radix tree

Request-to-worker assignment

Prefix locality in existing worker caches

Mooncake [6]/ IMPRESS [7]/ CacheGen [5] RAGCache [14]/ HotPrefix [15]/ UniCache [16] CacheBlend [17] SemCache [18]

Transfer, storage, and tier management

Streamed, disaggregated, or multi-tier prefix KV

Provide worker-local exact-prefix reuse; vLLM-APC is our replayed baseline. PrefixPlace plans coordinated cross-worker targets. Optimizes routing; PrefixPlace plans prefix-complete placement from an epoch demand matrix. Provide transfer mechanisms and costs; PrefixPlace selects coordinated placement targets.

Hierarchy scheduling or eviction

RAG knowledge trees or worker-local prefix caches

Optimize eviction or hierarchy decisions rather than coordinated prefix-complete placement.

Request-local fused KV state Semantic-aware cache sharing

Recomputes within a request rather than coordinating exact-prefix placement. Coordinates semantic sharing rather than prefix-complete exact-prefix placement.

PrefixPlace

Prefix-complete target per worker

Non-prefix retrieved RAG chunks Multi-user inference with Low-Rank Adaptation (LoRA) at the edge Exact-prefix placement chunks

Perturbation Profile noise σ = 0.20 Profile noise σ = 0.30 Demand noise σ = 0.30

Mean retained

Fifth percentile

99.70% 99.34% 99.36%

99.23% 98.75% 98.74%

TABLE V S ENSITIVITY ANALYSIS ACROSS WORKLOAD AND ALGORITHM SETTINGS . Variation

Result

Multi-turn structure Zipf exponent 0.5 → 1.5 100 worker orders 1024-token chunks RAG replay horizon, 3,000–30,000 requests

45 settings: 1.83% mean and 4.93% maximum gain Mean gain decreases from 13.53% to 2.27% Refinement adds 4.12%; CV falls from 0.98% to 0.09% 27 settings: 3.00% mean and 11.01% maximum gain vs. APC: 38.91–40.54%; vs. best offline: 4.50–6.26%

takes 0.41, 1.12, and 2.35 s for 4, 8, and 16 workers, and the largest configuration (n = 50,000, M = 16, k = 128) completes in 12.29 s; refinement converges in two to three sweeps. VI. R ELATED W ORK Table VII positions PrefixPlace against representative KVreuse decisions, including local reuse, transfer and tiering, hierarchy or eviction, and request routing. Prefix reuse, transfer, and eviction. vLLM [1] provides hash-based Automatic Prefix Caching with block-level LRU eviction [12], SGLang [2] radix-tree exact-prefix reuse, and PromptCache [3] modular attention reuse. CachedAttention [4], CacheGen [5], Mooncake [6], and IMPRESS [7] optimize KV movement across device, network, or storage paths; RAGCache [14], HotPrefix [15], UniCache [16], and workload characterization [19] study hierarchy or eviction; CacheBlend [17] reuses non-prefix RAG chunks, DroidSpeak [8] shares state across model variants, and SemCache [18] coordinates semantic sharing for Low-Rank Adaptation (LoRA)-based edge inference. Routing and cooperative placement. Preble [13] routes requests toward existing prefix locality; PrefixPlace treats the routing-induced demand matrix as input and plans prefixcomplete placement. Classical paging [20] and Landlord-style file caching [21] assume placement-independent object costs, while FemtoCaching [22] captures cooperative placement. The present problem couples a rooted-tree feasible set at

TABLE VI R EOPTIMIZATION UNDER REFRESHED DEMAND . G AIN AND BE STATISTICS ARE COMPUTED OVER BENEFICIAL UPDATES ; P90 DENOTES THE 90 TH PERCENTILE . Demand change

Improves

Popularity σ = 0.5 Popularity σ = 1.0 Routing 25% Routing 50% Routing 100%

Refined solve time (s)

TABLE IV ROBUSTNESS ANALYSIS UNDER PROFILE AND DEMAND PERTURBATIONS .

Optimizes coordinated placement under profiled compute and transfer costs.

Gain Median BE P90 BE

20/20 0.87% 20/20 3.84% 15/20 0.61% 20/20 3.46% 20/20 23.74%

1,202 482 1,637 909 251

2,442 854 7,473 1,113 390

4 workers 8 workers 16 workers

101

100

10−1 103

104 Prefix-tree nodes

Fig. 7. CPU time of the coordinate-refined solver (log scale) as tree size n and worker count M increase. Each worker receives k = min(128, max(16, ⌊n/20⌋)) chunks; the n = 50,000, M = 16, k = 128 case completes in 12.29 s.

each worker with requester-specific recomputation and transfer value. Optimization tools. Tree knapsack [23] and submodular maximization [24] provide related techniques. Maximum separable assignment [10] supplies stronger configuration-LP guarantees for the requester-side separable special case. PrefixPlace instead develops one direct rooted-tree-oracle algorithm for both requester-side coverage and source-dependent facility-location marginals; monotone refinement then produces near-optimal solutions at the evaluated scales. VII. C ONCLUSIONS AND F UTURE W ORK Reusable prefix KV states create a cost-aware placement problem beyond hit-rate policies, which PrefixPlace addresses with modular-plus-coverage and facility-location formulations, an exact O(nk) rooted-tree oracle, a coordinated 1/2-approximation, and monotone refinement. Across 432 requester-side and 45 source-dependent instances solved to exact MILP optimality, it attains 99.84% and 99.62% of

optimum on average, never below 98.02% and 97.90%, respectively, and improves materialization-cost saving by 40.3% over vLLM-APC and 6.3% over the best offline baseline on RAG replays, with consistent gains on WikiQA, sourceaware topologies, and demand shifts. A 50,000-node, 16worker placement solves in 12.3 s on one CPU, and beneficial updates break even within a median of 769 requests. Future work includes co-optimizing request routing with placement and extending the epoch-level model to online placement with regret guarantees. R EFERENCES [1] W. Kwon, Z. Li, S. Zhuang, Y. Sheng, L. Zheng, C. H. Yu, J. E. Gonzalez, H. Zhang, and I. Stoica, “Efficient memory management for large language model serving with PagedAttention,” in Proc. ACM Symposium on Operating Systems Principles (SOSP), 2023, pp. 611– 626. [2] L. Zheng, L. Yin, Z. Xie, C. Sun, J. Huang, C. H. Yu, S. Cao, C. Kozyrakis, I. Stoica, J. E. Gonzalez, C. Barrett, and Y. Sheng, “SGLang: Efficient execution of structured language model programs,” in Proc. Conference on Neural Information Processing Systems (NeurIPS), 2024, pp. 62 557–62 583. [3] I. Gim, G. Chen, S.-s. Lee, N. Sarda, A. Khandelwal, and L. Zhong, “Prompt cache: Modular attention reuse for low-latency inference,” in Proc. Conference on Machine Learning and Systems (MLSys), 2024, pp. 325–338. [4] B. Gao, Z. He, P. Sharma, Q. Kang, D. Jevdjic, J. Deng, X. Yang, Z. Yu, and P. Zuo, “Cost-efficient large language model serving for multiturn conversations with CachedAttention,” in Proc. USENIX Annual Technical Conference (USENIX ATC), 2024, pp. 111–126. [5] Y. Liu, H. Li, Y. Cheng, S. Ray, Y. Huang, Q. Zhang, K. Du, J. Yao, S. Lu, G. Ananthanarayanan, M. Maire, H. Hoffmann, A. Holtzman, and J. Jiang, “CacheGen: KV cache compression and streaming for fast large language model serving,” in Proc. ACM SIGCOMM Conference (SIGCOMM), 2024, pp. 38–56. [6] R. Qin, Z. Li, W. He, J. Cui, F. Ren, M. Zhang, Y. Wu, W. Zheng, and X. Xu, “Mooncake: Trading more storage for less computation: A KVCache-centric architecture for serving LLM chatbot,” in Proc. USENIX Conference on File and Storage Technologies (FAST), 2025, pp. 155–170. [7] W. Chen, S. He, H. Qu, R. Zhang, S. Yang, P. Chen, Y. Zheng, B. Huai, and G. Chen, “IMPRESS: An importance-informed multi-tier prefix KV storage system for large language model inference,” in Proc. USENIX Conference on File and Storage Technologies (FAST), 2025, pp. 187– 201. [8] Y. Liu, Y. Huang, J. Yao, S. Feng, Z. Gu, K. Du, H. Li, Y. Cheng, J. Jiang, S. Lu, M. Musuvathi, and E. Choukse, “DroidSpeak: KV cache sharing across fine-tuned model variants,” in Proc. USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2026, pp. 319–338. [9] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco, CA: W. H. Freeman and Company, 1979. [10] L. Fleischer, M. X. Goemans, V. S. Mirrokni, and M. Sviridenko, “Tight approximation algorithms for maximum separable assignment problems,” Mathematics of Operations Research, vol. 36, no. 3, pp. 416– 431, 2011. [11] Y. Yang, W.-t. Yih, and C. Meek, “WikiQA: A challenge dataset for open-domain question answering,” in Proc. Conference on Empirical Methods in Natural Language Processing (EMNLP), 2015, pp. 2013– 2018. [12] vLLM Project, “Automatic prefix caching: Design and eviction policy,” vLLM Documentation, version 0.21.0, 2026, accessed July 2026. [Online]. Available: https://docs.vllm.ai/en/v0.21.0/design/prefix caching/ [13] V. Srivatsa, Z. He, R. Abhyankar, D. Li, and Y. Zhang, “Preble: Efficient distributed prompt scheduling for LLM serving,” in Proc. International Conference on Learning Representations (ICLR), 2025. [14] C. Jin, Z. Zhang, X. Jiang, F. Liu, S. Liu, X. Liu, and X. Jin, “RAGCache: Efficient knowledge caching for retrieval-augmented generation,” ACM Transactions on Computer Systems, vol. 44, no. 1, pp. 1–27, 2026.

[15] Y. Li, R. Gu, C. Huan, Z. Wang, R. Yao, C. Tian, and G. Chen, “HotPrefix: Hotness-aware KV cache scheduling for efficient prefix sharing in LLM inference systems,” Proceedings of the ACM on Management of Data, vol. 3, no. 4, pp. 250:1–250:27, 2025. [16] B. Ouyang, Y. Qiao, and J. Xing, “UniCache: Unifying prefix cache eviction for heterogeneous LLM serving workloads,” Proceedings of the ACM on Measurement and Analysis of Computing Systems, vol. 10, no. 2, pp. 54:1–54:27, 2026. [17] J. Yao, H. Li, Y. Liu, S. Ray, Y. Cheng, Q. Zhang, K. Du, S. Lu, and J. Jiang, “CacheBlend: Fast large language model serving for RAG with cached knowledge fusion,” in Proc. ACM European Conference on Computer Systems (EuroSys), 2025, pp. 94–109. [18] T. Ren, Y. Yao, Z. Hu, and J. Niu, “SemCache: Semantic-aware cache sharing for efficient multi-user LoRA-adapted LLM inference at the edge,” in Proc. IEEE International Conference on Computer Communications (INFOCOM), 2026, pp. 1–10. [19] J. Wang, J. Han, X. Wei, S. Shen, D. Zhang, C. Fang, R. Chen, W. Yu, and H. Chen, “KVCache cache in the wild: Characterizing and optimizing KVCache cache at a large cloud provider,” in Proc. USENIX Annual Technical Conference (USENIX ATC), 2025, pp. 465–482. [20] D. D. Sleator and R. E. Tarjan, “Amortized efficiency of list update and paging rules,” Communications of the ACM, vol. 28, no. 2, pp. 202–208, 1985. [21] N. E. Young, “On-line file caching,” Algorithmica, vol. 33, no. 3, pp. 371–383, 2002. [22] K. Shanmugam, N. Golrezaei, A. G. Dimakis, A. F. Molisch, and G. Caire, “FemtoCaching: Wireless content delivery through distributed caching helpers,” IEEE Transactions on Information Theory, vol. 59, no. 12, pp. 8402–8413, 2013. [23] D. S. Johnson and K. A. Niemi, “On knapsacks, partitions, and a new dynamic programming technique for trees,” Mathematics of Operations Research, vol. 8, no. 1, pp. 1–14, 1983. [24] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, “An analysis of approximations for maximizing submodular set functions, part i,” Mathematical Programming, vol. 14, pp. 265–294, 1978.

Related documents

• Toppling the Hierarchy in Byte-level Language Modeling#819909
• Modelling language using large language models#130643
• COMPARATIVE ANALYSIS OF LARGE LANGUAGE MODELS FOR AUTOMATED COMMIT MESSAGE GENERATION#266769
• Reference-Grounded Data Curation for Instruction-Following Thai-English Machine Translation#1129391
• Nested Byte-Level Vocabularies Are Cheap to Deploy and Expensive to Share: A Pre-Registered Negative Result#784905