Tail-Optimized Caching for LLM Inference
Authors: Wenxin Zhang
Yueying Li
Ciamac C. Moallemi
Tianyi Peng
Venue: NeurIPS 2025 poster ()
Keywords: prompt caching
large language models
tail latency
KV‑cache eviction
Least‑Recently‑Used
Primary area: applications

Abstract: Prompt caching is critical for reducing latency and cost in LLM inference---OpenAI and Anthropic report up to 50–90\% cost savings through prompt reuse. Despite its widespread success, little is known about what constitutes an optimal prompt caching policy, particularly when optimizing tail latency—a metric of central importance to practitioners. The widely used Least Recently Used (LRU) policy can perform arbitrarily poor on this metric, as it is oblivious to the heterogeneity of conversation lengths. To address this gap, we propose Tail-Optimized LRU, a simple two-line modification that reallocates KV cache capacity to prioritize high-latency conversations by evicting cache entries that are unlikely to affect future turns. Though the implementation is simple, we prove its optimality under a natural stochastic model of conversation dynamics, providing the first theoretical justification for LRU in this setting---a result that may be of independent interest to the caching community. 
Experimentally, on real conversation data WildChat~\citep{zhao2024wildchat}, Tail-Optimized LRU achieves up to 27.5\% reduction in P90 tail Time to First Token latency and 23.9\% in P95 tail latency compared to LRU, along with up to 38.9\% decrease in SLO violations of 200ms. 
We believe this provides a practical and theoretically grounded option for practitioners seeking to optimize tail latency in real-world LLM deployments.

Tail-Optimized Caching for LLM Inference
Wenxin Zhang Columbia Business School #z2574@columbia.edd
Yueying Li Cornell University, Department of Computer Science y13469@cornel1..e
Ciamac C. Moallemi Columbia Business School ci amaacggbb. columbia. edu
Tianyi Peng
Columbia Business School
tp28450columbil wut.iia..c.ab......mmmoom.....el edu
Abstract
Prompt caching is critical for reducing latency and cost LLM inference-Opeet and Anthropic report up to 50-90% cost savings through prompt reuse. Despite its widespread success, little is known about what constitutes an optimal prompt caching policy, particularly when optimizing tail latency-a metric of central importance to practitioners. The widely used Least Recently Used (LRU) policy can perform arbitrarily poor on this metric, as it is oblivious to the heterogeneity of conversation lengths. To address this gap, we propose Tail-Optimized LRU, a simple two-line modification that reallocates KV cache capacity to prioritize high-latency conversations by evicting cache entries that are unlikely to affect future turns. Though the implementation is simple, we prove its optimality under a natural stochastic model of conversation dynamics, providing the first theoretical justification for LRU in this setting result that may be of independent interest to the caching community. Experimentally, on real conversation data WildChat (Zhao) et al. [2024). Tail-Optini Tail-Optimized LRU achieves up to 27.5% reduction in P90 tail Time to First Token latency and 23.9% in P95 tail latency compared to LRU, along with up 38.9% decrease in SLO violations of 200ms. We believe this provides practical and theoretically grounded option for practitioners seeking to optimize tail latency in real-world LLM deployments.
Introduction
Prompt Caching is Essential. AI capabilities have exploded in recent years, and so has the demand. By December 2024, ChatGPT handled 1 billion user messages every day with 300 million weekly
active users [OpenAl Newsroom 2024 To efficiently use scarce and costly GPU resources, prompt caching was proposed [Gim al.) 2024]: caches the KV cache of existing queries, allowing new query to skip some computation by reusing the KV cache it shares with existing queries [vLLM
Team 2025). Prompt caching can reduce prefill computation thus Time First Token (TTFT). This technique has been adopted by OpenAl and Anthropic, both reporting significant amount (50-90%) of latency and cost reductions [OpenAl] 2024, Anthropic [2024.. Despite the practical impact of prompt caching, little is known about how much existing caching policies-ss such as the Least Recently Used (LRU) policy- can be improved upon with respect to key metrics in LLM inference systems, which is the main motivation of this work.
Challenges of Optimizing Tail Latency. One of such key metries is tail latency. In real-time user-facing applications, companies care about high- response time, e.g., 95% of requests complete within 200 ms. In LLM conversation-bas based applications, users arrive request services through an alternating sequence of prompts and responses that we call turns. Each prompt, along with
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Arrival Sequence
of blocks
A:100
B:100
A:200
Conv A
Conv B
Cache Allocation Comparison: LRU vs T-LRU
Cached Blocks
LRU
T-LRU
LRU
T-LRU
LRU
T-LRU
100
LRU: Conv
IRU: Cone
I-LRU: Conv
100 A: 100
R-110
100
A: 100
T-LRU: Conv B
Capacity
25
A: 50
Timestep
Figure 1: Failure of LRU Tail Lateney. Consider example with two conversations (A and B) and a total of three turns (A has two turns; B has one). The top panel shows the total job size (conversation history plus user prompt) at each step. For simplicity, zero and that each user prompt consists of 100 blocks. The bottom panel shows the number cached blocks updated after each turn. The cache capacity is 100 blocks. We measure tail latency as the maximum processing time among the three requests (i.e., the 66.7% 96.7%-th percentile). Under LRU, all of conversation A's cache blocks evicted immediately after step 2, resulting in maximum of 200 uncached blocks at step 3. Therefore, the tail latency under LRU corresponds to the time required to process 200 blocks. contrast, if at step we partially evict A's cache so that both A and retain 50 cached tokens each, then regardless of whether the third request comes from A or B, the maximum number of uncached blocks is reduced to 150-an an improvement of 25%. This improvement is what our proposed policy, T-LRU, is designed to achieve.
assume the response length is
all previous conversation history, is treated job request. When the cache is full, the server must decide which KV cache blocks to evict, under four layers of uncertainty: 1) when new conversations arriving; 2) the number of future turns of existing conversations; 3) the size of future user prompt and model response; and 4) the arrival order of turns from concurrent conversations competing for cache space. Here, KV cache blocks are the atomic cacheable units of tokens, e.g., single block may consist of 128 tokens [OpenAI] 2024). These intertwined dynamics make tail latency optimization in L.M inference uniquely challenging.
Existing Approaches. Classic caching/paging policies mostly focus on maximizing cache hit rate, not tail latency. Among these, the LRU policy is perhaps the most representative, evicting the cache item that was accessed least recently. LRU has been widely adopted in LLM inference systems, including vLLM [Kwon et al., 2023). J, SGLang (Zheng al. 2024], and Mooncake [Qin et al. 2025 However, LRU does not account for the fact that different blocks within a request may have varying effects tail latency, thus leaving room for further optimization. See Figure for an illustrative example.
Our Approach: Tail-Optimized LRU (T-LRU). In this work, we focus optimizing the tail latency of TTFT (Time to First Token) through improved cache eviction policies. To this end, we introduce the metric Tail Excess Latency (TEL):
TEL
Σ max mTx(()) - Es, 0}.
(I)
where TTFT(i) denotes the Time to First Token for the i-th request, and & 2 a user-specific latency threshold (c.g.. & 200 ms). TEL captures the total TTFT exceeding the threshold, serving as a practical proxy for tail latency while treating each request independently. See Section for further diseussion of this objective.
Empirically, TTFT known be approximately linear in the number of uncached tokens i.e..
TTFT()) Rs a b(t).
(2)
'This approximation holds well when the uncached length not excessively long and the prefill of the request is not batched with others. We use this approximation for analytical purposes, while the actual TTFT is measured in experiments.

---

where a is a constant determined by the model and GPU configuration, and b(i) is the number of uncached blocks for request (see [Horton et al. 2024 and Figure B}. We use this approximation to motivate our policy design and simplify the analysis. By defining Ex/o, TEL. can be equivalently expressed as
TEL = E max(b(i) - E, 0}.
Our intuition is the following: for a conversation turn with conversation history length L and whose next prompt is expected add blocks, caching more than L Q & blocks for this turn cannot improve TEL. as the number of uncached blocks already lower than Ç. Any blocks beyond this TEL- safe budget can therefore be evicted "for free". See Figure for illustration of this idea. Motivated by this observation, we propose Tail-Optimized LRU (T-LRU), a simple modification of LRU. Upon cache overflow, T-LRU works in phases:
1. TEL-safe trimming: first evict blocks from conversations whose cache size exceeds the TEL-safe budget 1 Q -
2. LRU-as-usual: If space is still needed, evict blocks using LRU.
In Figure ! the performance of T-LRU with { 150 shown. In practice, the next-p eext-prompt length is unknown; T-LRU can use a constant Q such as the empirical average for estimating the length of the next-prompt Implementation requires only extra bookkeeping: mark TEL-safe blocks as "infinitely old," after which any existing LRU engine can evict them as usual.
# of uncached blocks
Turn
Turn
Turn
A3
A2
Q3
Q2
L1
Q1
L2
Time
Cached blocks at Turn
A three-turn conversation 41), (Q2, (Qa, As}} is shown, L; denotes conver- sation history (i.e., 7, Q + A1, L2 L Q2 A2). Bars indicate the number of uncached blocks each turn incurs; the red dashed line marks the latency threshold &. Tur 1: projected load for next request is L, + Q2 < E; no caching is needed. Tur 2: L2 Q3 ç, at least Lg + Q3 blocks must be cached (green), but caching more won't 't improve TEL further.
Figure 2:
Theoretical Optimality. On the theoretical front, we establish the following results;
1. Belady's 's algorithm [Belady 1966], which evicts the block whose next use is furthest in the future, is a clairvoyant caching strategy known to achieve the hindsight-optimal hit rate. We show that combining TEL-safe trimming with Belady's 's algorithm yields an policy being hindsight optimal for TEL (Theorem []. This result justifies the use of T-LRU, as LRU is widely used heuristic for Belady's algorithm.
2. In the caching literature, the settings under which LRU is online optimal are not well understood. To address this, introduce novel stochastic model for multi-turn conversa- tions that captures both uncertainty and temporal locality in LLM workloads. Within this framework, we prove that a generalized T-LRU is optimal (Theorem D. incorporating the optimality of classical LRU (for average latency) and T-LRU as special cases. To the best of
Furthermore, Q { can be combined and interpreted one tunable parameter that determines how many blocks at the end of the conversation history are considered safe evict.

---

our knowledge, this is the first result demonstrating the optimality of LRU under a natural, conversation-drive driven arrival model, and may be of broad interest the caching community.
Strong Practical Performance. Finally, we evaluate the performance of T-LRU and LRU on real multi-turn chat traces from ShareGPT [Contributors] 2025] and WildChat (Zhao et al.) 2024]. Our policy achieves up to a 23.9% reduction in P95 tail latency compared to LRU, and up to 38.9 38.9% decrease SLO violations relative to the strongest bascline. We also provide insights into selecting the latency threshold & (Section 5). These results highlight the practical advantages of T-LRU,
The rest of the paper organized as follows. We discuss related work in Section A In Section 2 we describe the problem setting and present the mandsight-optiman policy for TEL. Section ijitrrduuess the T-LRU policy and demonstrates that it never worse than LRU for optimizing TEL. In Section 4 we prove the optimality of T-LRU for class of stochastic models that capture conversational arrivals. S presents the experimental results. Finally, Section 6 discuss future directions.
Hindsight Optimal Policy
Deterministic Arrival Trace. To begin, we describe the prompt caching problem for LLM inference under a deterministic arrival trace to study the hindsight optimality, deferring the stochastic model to Section for online optimality. Consider discrete time horizon & .,2,.... T with N conversations over steps. For each conversation E [N], let T; S [T] denote the set of time steps when conversation issues request. Assume Ti is disjoint from each other. For each E Ti, let di. and ar,, denote the lengths of the user prompt and model response for that turn, respectively, measured in blocks; otherwise, qi Dj 0 for & Ty
Caching State. For E [N] and E [T]. let zi,t denote the number cached blocks for conversation i time t, before the request arrival. The caching state { must satisfy the following constraints.
First, the total number of cached blocks cannot exceed the cache capacity C7 at any time:
Σ M
Fiat S C,
VI [T]
(capacity constraint)
(4)
Second, for each conversation, the number of cached blocks cannot exceed the length of its conversa- tion history up to time t:
J1 S
Σ (g. + aiz),
vi [N], TE T<T
(5)
Third, the cache allocation for conversation can only increase when a request from that conversation arrives; otherwise, it can only decrease or stay the same:
J1,41 Fi,to
Vi E [N], t $ Ts t T (cache increases only arrival)
(6)
A caching policy must determine the caching state (x.,r) subject to these constraints. When a request arrives, the server can reuse any cached blocks in (Ir,e), while any evicted blocks must be
recomputed [3]
For simplicity, we assume optional caching: a request is not required to be added to the cache after serving. Extending to forced caching is straightforward (by replacing the inequality in constraint (5) with equality); we defer this discussion to Appendix D
Latency Objective: TEL. We aim to optimize the tail latency metric via the caching policy. Persentile-based tail latency notoriously difficult to optimize directly, so we introduce the Tail Excess Latency (TEL) metric as a tractable surrogate:
TEL Σ max (TTFT(((())) - Es, 0):
KE[N], 1ET
'In practice, evicted blocks may be retrieved from other storage layers (e.g., CPU DRAM or SSD). Here, we focus on single-layer cache and do not consider inter- layer transfers.

---

where TTFT(i, t) denotes the Time to First Token for the request at time t of conversation i and &. is a pre-defined threshold. TEL analogous to Conditional Value at Risk (CVaR), but with an explicit, user-specified threshold [Bäuerle and Ott 2011 Chow et al. 2015): it also resembles SLO attainment metries [Zhong et al. 2024]. with the distinction that THL penalizes larger violations proportionally more. Setting &. = 0 recovers the average-latency objective. While our theoretical analysis centers on TEL, our experiments report conventional metries (tail latency and SLO violation
rate) for straightforward comparison in future studies.
As discussed in 2 to simplify the analysis and guide policy design, we assume TTFT grows linearly
with the number of uncached blocks- an assumption empirically justified (see Figure 3) by the
dominance of feed-forward linear layers during inference (Kamath et al., 2025 Zhu al. 2024 Ye et al. 2025 Thus,
TEL a
E max CET:
Oi
B
Fi,t -
j=1
where = E,/ar, and Σj= (i.j Ej=1 Bij Fi,t is the number of blocks that need to be computed the request of conversation at time I (here, j== Ui E/=1
4i.j is the total number of blocks in the conversation history, and Ci,, corresponds to the new request prompt at time I.).
Latency vs Load
120
coched ead
Cached ead 200
tachal tuz 600
600
Latenry (ms))
oad
rached ned
cached ead 1200
60
cached oad 1400
rarhed nvd 1602
40-
250
500
100C
1250
1500
2750
Tokcnn Load
Figure 3: Experimental results demonstrate that TTFT increases approximately linearly with the number of uncached tokens. The plot shows TTFT latency as a function of the total prompt length (Token Load) and the size of the cached prefix (Cached Load). We conducted our experiments using Vicuna-7B with vLLM's prefix caching enabled on a Colab A100 GPU.
Hindsight Optimal Policy for TEL With both the decision timeline and objective clarified, we next ask: If the system knew the entire future arrival frace, what caching policy would minimize TEL? Understanding this maddsight-otiima benchmark unveils what's 's important to improve tail latency and thus guides our policy design. The hindsight optimal policy chooses cache variables { N: the number of cache blocks conversation i can reuse at the beginning of step t. and slack variables Mj, 2 ( to minimize TEL::
min Σ
Σ
44.
[EIN]
s.t.
5).
6
Uitt
9: +
ai.
Fie
E,,
Vi [N], te T, (slack variable)
Here uis describes the TEL objective as the uis equals (E)=1 9i. + Σ at Fi,1 E) in the optimal solution.
Theorem 1 Slindsight-Optingg Policy Structure). The hindsight-optimen policy that minimizes TEL restricts the number of KV-cache blocks allocated to each conversation within the TEL-safe budget, given by (Σ)= hi, + E/= thg - -5) If the total allocation exceeds the cache capacity, the policy evicts cache blocks from conversations whose next requests are expected arrive furthest in the future.
5

---

See Appendix B for detailed proof. Setting Ç = 0 recovers average latency minimization, and in this case, the theorem implies the surthest-in-future eviction strategy optimal recover the Belady optimal policy, which was shown to maximize cache hit rate in classical caching problems [Belady [966]. Therefore, the hindsight optimal policy for minimizing TEL. can characterized as threshold-capped version of the Belady policy. We call this policy Tail-Optimized Belady.
3 Tail-Optimized LRU
Inspired by the Tail-Optimized Belady policy (Theorem D we propose Tail-Optimized LRU, an online policy that also maps into the future and caches just enough to prevent conversations' next turns from affecting TEL. To adapt the hindsight optimal policy to online settings, we make two modifications: 1) replace the actual next-prompt length Q with an estimate Q: 2) use the least- recently-used eviction strategy rather than the furthest-in-futurr
Pscudocode is given in [ We believe Tail-Optimized LRU is a practical, low-friction upgrade for any LLM caching system that already relies on LRU: its no-worse-thar worse-than-LLRU guarantee (Theorem ??) eliminates adoption risk, while the lightweight modifications from standard LRU minimize adoption costs.
Algorithm 1: Tail-Optimized LRU Policy
Input: Number of conversations N, Timestamp of Last Turn {Ti). Number of cached blocks {Xi), conversation history lengths {Li,, arriving conversation 0, arriving conversation length l.
Parameters: Policy parameters: threshold &, next-turn length estimate {Ô.}
Output: Updated cache sizes {X+}
Lo f Lg Xp < Lg. To t Current Timestamp // Update system state for arriving conversation
Lienn] X; C' then foreach i E [N] do
if X; 2 L; + Q - & then
X X; -
// "Free Eviction" under TEL objective
if E X; < C then
return X
while EIE[N] X; C do
Find j = arg min eM
// Evict using LRU
X, + X, -1
return
Lightweight Integration with Existing Caching Systems. Implementing Tail-Optimized LRU in cache system based LRU only requires extra bookkeeping: mark blocks that can be evicted "for free" (i.e., blocks identified in the proactive trimming phase) as infinitely old. Then these blocks can be evicted seamlessly by any existing LRU engine in the usual way. This design is also compatible with paged KV cache technique which stores keys and values non-contiguous memory space.
4 Optimality of Tail-Optimizeed LRU in Stochastic Conversation Model
In this section, we prove the optimality of generalized Tail-Optimized LRU policy under stochasti- cally generated traces, which covers the optimality of T-LRU (Policy I
and LRU as special cases.
Stochastic Conversation Model. Classic caching models fail to capture the nature of LLM workload: unlike traditional cache systems where objects have static sizes and independent access patterns, LLM workloads consist of multi-turn conversations that dynamically start, evolve, and terminate over time; see related work in Section A To address this gap, build novel stochastic model that characterizes these unique features of LLM workloads.
To characterize multi-turn conversations, our model must address four fundamental questions: (1) when do new conversations start? (2) when will an active conversation generate next prompt? (3) how many tokens appear in prompts and responses? (4) when do conversations terminate? Real

---

traces from Zhao et al. [2024] reveals strong temporal locality in multi-turn conversations: the longer a user goes without sending their next prompt, the less likely they are ever return. This observation conversations are also least-likely fit-likkely-t-retumm has direct practical implication: least-recently-usee
Consequently, when cache capacity constraints force eviction decisions, prioritizing recently active conversations aligns with their probability of future requests. We capture this pattern by modeling the number active conversations as continuous- birth-death process. Specifically,
New conversations are "born" rate Aconv 0, and each active conversation "dies" rate J > 0. We index conversations by their arrival order, = 1,2,....
While active, conversation generates requests according to an independent Poisson process with rate X; >
At each turn, a random prompt length Q is drawn from a known (possibly conversation- specific) distribution; the length of model responses A follows an arbitrary distribution that the decision-makes does not need to know.
This design has an appealing property: conversations with exponential "death clocks" naturally implement the temporal locality observed empirically. The longer conversation stays quiet, the more likely it has terminated, making it safe candidate for cache eviction. Building on this insight, we develop T-LRU, a policy that maintains LRU ordering while prioritizing conversations whose next coo--tooffitttokenn (TTFT) latency threshold. In this section, prove that
request would breach generalized version of T-LRU that minimizes expected total eviction loss (TEL) is optimal under our stochastic conversation model.
For simplification, we assume that KV caches cannot be reused across different conversations. This assumption is also motivated by security and privacy concerns: e.g., vLLM implement cache isolation to prevent timing-based inference attacks
The decision-maker only observes the turns as they arrive, but departures are never observed. Thus the problem is modeled as partially observable Markov decision process (POMDP), where the optimal policy is defined for each possible belief state over the POMDP states. As the conversations arrive and depart independently, we can decompose the belief state be the individual expected turn rates of each conversation.
Belief Markov Decision Process.
Let (t) denote the expected turn-arrival rate is n. (t) A₁ The belief is updated using
belief at time t that conversation i is still active, then its
(t) = exp(-xi( last turn time)),
as each conversation lasts for an exponential amount of time with mean Jr.
Therefore, the system state at time L of the belief MDP is given by (A(1), L(t), X()), where (!) the total length (blocks) of conversation i time and (t) is the number of KV cache blocks from conversation all prior to the arrival at time f. The decision- maker chooses X', which blocks to cache after serving each request, to minimize the Tail Excess Lateney for M requests for arbitrary M E N. Appendix C details the finite-horizon Bellman equation.
Expected- Seoectdd-Tai-OOee TTal--Ottimiee LRU (ET-LRU), ET-LRU chooses the post-arrival cache allocation that minimizes the expected TEL at the next turn, using current beliefs of turn- turn-arrival rates. Formally,
Definition (Expected Tailed-Optin Optimized LRU). Let denote the index of the conversation arriving at time t with new prompt length Q and model response length A, X (tt)) denote the cache state before arrival, and x((+), L((+) denote the belief turn-arrival rates and conversation history lengths updated after service (>o(1t)= = Xo, (1t)tt = T.g(1)) +Q + A). ET-LRU chooses
x ETLAU E arg Σ -B(C,(tt)) + Y [)+1
(8)
s.1. Yo S Lo(t"), (optional caching)
(9)
Y < (t, Vi 0
(cannot conjure caches)
(10)
Σ Y. C. (capacity constraint)

---

where the expectation is taken over Qi the random user prompt length for conversation i at its next arrival.
The probability that conversation i generates the next request is proportional to its belief turn-arrival is the expected TEL contributed by conversation Here constraint ( implies that the decision-maker can cache at most the total conversation history
rates ):(t+), thus ((()))))(((+)++))))X))))
of conversation 0 just served; constraint (TO) says conversation's 's cache allocation can grow only whenn it arrives.
Theorem 2 (Optimality of Expected- Taad--aai---iiiiii LRU). Expected-Tail- Tail-Optinized LRU (Definition 7 is an optimal online caching policy for minimizing Tail Excess Latency under the stochastic conversation model above.
The proof is by induction on the number of turns and comparing the value-to-go functions under our policy and another policy that evicts differently. Here, the ceastrrceetly-uset time reflects the expected turn-arrival rate and thus can approximate furthest-in-future. Theorem has three implications:
LRU is optimal for average latency. Setting { = and assuming homogeneous turn- arrival rates across conversations, the objective in optimization problem 8 reduces to max Σ, cxp(-j(tt last turn time))Y, thus ET-LRU reduces to LRU. Therefore, Theorem 2 establishes the optimality of LRU for minimizing average latency under our stochas- tic arrival model. To the best of our knowledge, such a result had not previously been established.
Optimality of Tail-Optimized LRU: if the user prompt length is deterministic, Expected-Tait Optimized LRU is reduced to deterministic version as stated in Policy (with estimate Q replaced by deterministic Q). Theorem 2 thus establishes the optimality of fail-Optimized LRU in this model.
When Q 0 after the first turn and responses also have zero length, our model reduces to classic caching with unit page size. In this case, the optimal policy "evicts the block whose conversation is least likely to return", generalizing least-rccentl--used.
Therefore,
LRU serves as a common backbone across three classic caching regimes, providing theoretical justification for adopting LRU and Tail-Optimized LRU for LLM inference workload.
5 Experiments
5.1 Datasets and Metrics
We evaluate caching policies two conversational datasets: WildChat and ShareGPT (Figure 4 and Figure 5). For each dataset, we select conversations based on their arrival timestamps and extract the first 1000-2000 turns across these conversations. Specifically, we sample conversations in chronological order (by first-turn timestamp), split each conversation into individual turns, and simulate their arrivals following the observed timestamps in the trace.
We measure latency metrics (median, P90, P95, P99) and service-level objective (SLO) attainment under different caching policies. Our default experimental configuration uses Vicuna-7B served single A100 GPU via vLLM with tensor parallelism disabled (TP = 1) and without mixed batching. We present the results for WildChat below. Due space constraints, Results for ShareGPT, which exhibit qualitatively similar patterns, are provided in Appendix G
5.2 Tail Latency Reduction
We measure the tail latency reduction of our policy against LRU and Threshold LRU- only if the conversation length exceeds a fixed threshold, a configuration for LRU we observed in practice. We fix the input parameter for T-LRU, next- pext-proppt length Q to be the average prompt length (200 for WildChat, 150 for ShareGPT), and use 1024 as the threshold for Threshold-LA following the one used by A
httpe::/plattorr.oppoet https///ppp.pp..o//ooo///oo////a
8

---

Distribution of Number of Turns
Distribttio of Prompt Longths
Distribution of Response Langthe
Mean: 2.95
Moar: 142.4
Mean: 431.1
4000
Median:
Medien
Medien: 539
P95: 10.0
PS6: 807.0
2000
PBS: 1169.0
3000
Fregancc
1500
2000
1000
1000
500
15
12
10"
10"
10"
10'
12"
12"
Number of Tums per Converaatio (og soale)
Prongt ProngtLoagh Length pokkens log (cors)
Response Length (ookons log sooke)
Figure 4: Distributions of turns and tokens of WildChat (Zhao et al. 2024 datasets (sampled 10,000
conversations).
In Tables 2 we report the relative latency improvements of T-LRU over both LRU and Threshold- LRU across various cache capacities C' and tail-latency thresholds & We observe that T-LRU reduces P90 tail TTFT by up to 27.5% and p95 tail TTFT by up to 23.9% 3%9% compared to LRU, and achieves comparable improvements over Threshold-LRU.
Sensitivity latency threshold f.- The benefit of T-LRU peaks when latency threshold & is calibrated to match the target tail percentile of interest. For example, with capacity C = 1000 under LRU, medium, P90, P95, and P99 tail latencies are roughly 40 ms, 240 ms, 326 ms, and 505 ms. Setting & 200 ms yields the largest improvement in P90 tail latency; setting &. = 300 ms yields the largest improvement in P95 tail latency. A high value, e-g. E. 500 ms, relaxes protection for moderate tails and only provides protection for extreme tails up to 3% of increase in P99 tail latency
Operationally, the latency threshold &. can be tuned either based on fixed service level objective (e.g., target TTFT), or adaptively based on the observed tail latency of served turns. For example, the decision-maker can periodically update &, to match the desired tail latency TTFT observed over recent turns. Raising & makes TEL-safe trimming more aggressive, and could potentially increase average latency as the policy allows more turns to incur latency up to É., reflecting the classic trade-off' between average and tail performance.
Comparing Threshold-LRU and T-LRU. Threshold-LRU is a straightforward patch for LRU's blindness to conversation length. In industry systems such at OpenAl, prompt caching is enabled only when the rumning conversation history exceeds a fixed length. While simple to implement, this policy makes binary, all-or-nothing decision for each conversation: either cache the entire conversation history or cache nothing at all. In contrast, T-LRU makes adaptive, fine-grained caching decisions. Rather than caching entire conversations indiscriminately, T-LRU caches just enough tokens from each conversation to ensure its next request will not breach the latency threshold. This fundamental difference persists regardless of prompt length. Even with zero-length prompts, Threshold-LRU would apply its binary rule based on history length, while T-LRU would adaptively cache the amount that just right so not impacting the tail.
Table I: Relative latency improvement of T-LRU over LRU with various &,
50ms
100ms
150ms
E. 200ms
E. 500ms
Capacity
p90
p95
p90
p45
p90
p95
p90
p45
p90
p95
p99
1000
4.0%
0.0%
4.5%
1.0%
5.3%
1.5%
7.3%:
2.0%
114%
-1.3%
3.2%.
2000
1.2%
0.6%
3.4%
0.6%
5.1%
3.4%
9.2%
4.4%
.4.9%
-2.8%
3.3%
4000
1.7%
0.7%
4.1%
2.8%
10.5%
4.2%
13.3%
10.8%
-7.5%
-3.4%
3.4%
6000
5.0%
2.1%
10.6%
4.0%
16.0%
11.4%
-8.7%
-4.2%
3.4%
8000
2.2%
0.7%
10.5%
8.5%
23.0%
15.8%
8.8%
19.5%
-13.7%
-3.5%
1.4%
10000
3.6%
7.4%
20.0%
27.5%
20.1%
6.9%
23.9%
-13.3%
-3.5%
-0.0%
CC' 10, 000 corresponds to approximately 4.8 GB Vicuna-7B with Float16, see Appendix "We set { fa/c using simple linear fit between awaited prefill tokens and prefill time, which is easy to implement in practice.

---

Table 2: Relative latency improvement of T-LRU Threshold-LRU with various
& 50ms
&x 100ms
& 150ms
Ex 200ms
S.
500ms
Capacity
p90
p95
p90
p95
p90
p95
p90
p95
p90
p95
p99
1000
1.5%
0.0%
1.0%
1.0%
2.9%
1.5%
4.8%
2.0%
-400%
-1.3%
3.2%
2000
0.4%
0.6%
2.7%
0.6%
4.4%
3.4%
8.6%
4.4%
-5.7%
-2.8%
3.3%
4000
0.3%
0.0%
2.7%
2.1%
9.3%
3.5%
12.0%
10.2%
-9.0%
-4.2%
3.4%
6000
4.7%
1.2%
10.4%
3.1%
15.7%
10.6%
14.1%
14. 6%
-9.1%
-5.2%
3.4%
8.5%
22.2%
15.8%
7.8%
-14.9%
-3.5%
1.4%
10000
2.4%
6.1%
19.0%
14.6%
26.6%6
19.0%
5.7%
22.8%
-14.7%
-5.0%
-0.0%
5.3 SLO Violation Reduction
We measure the count of requests that service-level objective, another objective similar to TEL-thhe amouns latency beyond a threshold. Table repoort the improvement on SLO attainment ratio (relative drop in requests whose TTFT exceeds 200 ms). With the latency threshold &, set to 200 ms SLO, compared to LRU, T-LRU reduces between 8.8% (small cache capacity) and 40.7% (large cache capacity) of violations.
Sensitivity to latency threshold E.. When E, is much lower than the SLO (E. = or 100 ms), improvement is modest because both baselines already satisfy most requests; when is far higher (E. 500 ms). T-LRU focuses on larger tails and can allow for a few extra 200 ms violations.
These results echo the design goal: TEL. minimization penalizes how much request overshoots &.. yet the same trimming logic also cuts the number of SLO violations whenever ç, aligns or is slightly below the target latency budget.
Table 3: Relative improvement of T-LRU: % reduction in requests with latency > 200ms
Capacity
E, LRU.
E,
C,
LRU
Thre-LRt RU:
Thre-LRR
LRU.
Thre-I.RU
I.R17
Thre-I.R1J
L.RU
Thre-I.UU
1000
1.2%
-1.2%
4.1%
1.8%
6.3%
4.2%
8.8%
6.6%
-1.8%
-4.2%
2000
2.4%
1.2%
6.1%
4.9%
9.1%
8.0%
13.3%
12.3%
.488
.6.1%
4000
3.9%
1.3%
7.1%
4.7%
14.3%
12.0%
22.1%
20.0%
-12.3%
-15,3%
6000
2.0%
0.7%
12.2%
11.0%
20.9%
19.9%
30.4%
29.5%
-12.2%
-13.7%
-19.3%
-21.9%
10000
7.4%
4.6%
25.9%
23.7%
31.9%
29.8%
40.7%
38.9%
-19.3%
-22.9%
6 Future Directions and Conclusions
We propose Rail-Optimized LRU (T-LRU), a simple yet effective modification to the Least Recently Used caching policy that significantly improves tail latency in multi-ture conversational LLM serving. By adaptively caching just enough tokens to keep each conversation's 's next request below latency threshold-rather than making binary all-or-nothing caching decisions, T-LRU achieves substantial tail latency reductions (e.g., 20-30% improvement P95 TTFT) with modest impact on median performance.
T-LRU makes deliberate design choice: sacrifice tens of milliseconds the median to eliminate hundreds of milliseconds at the tail. This trade-off aligns well with strict SLO requirements in production systems, though exploring multi-objective policies that balance tail and median latency differently remains an interesting direction for future work.
exploring
Our focus is on single storage layer, but real systems increasingly adopt hierarchical memory architectures, Extending T-LRU to multi-tier KV caching systems-where evicted blocks migrate to slower storage (CPU memory, SSD) rather than being discarded-coull unlock further performance gains. Recent work [Qin et al. 2025) has begun exploring such architectures, and understanding opti- mal promotion/demotion policies across cache tiers represents an important open problem. Another compelling direction is joint optimization of caching and load balancing. Recent work (Srivatsa et al. 2024) has initiated exploration of how caching decisions interact with request routing distributed LLM serving. Analyzing these problems through queueing-theoretic lens and considering both cache locality and load distribution could systematically characterize fundamental trade-offs and guide practical system design.
10

---

References
Amey Agrawal, Nitin Kedia, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav Gulavani, Alexey Tumanov, and Ramachandran Ramjee. Taming (Throughput-Latenes tradcoff (LLM) inference with [Sarathi-Serve) In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24),
pages 117-134, 2024.
Authropic, Prompt caching, 2024. prompt- caching
Nicole Bäuerle and Jonathan Ott. Markov decision processes with average-value criteria. Mathematical Methods of Operations Research, 74:361-311 -39,, 2011.
Laszlo A. Belady. A study of replacement algorithms for a virtual-storage computer. IBM Systems journal, 5(2): 78-101, 1966.
Daniel S Berger, Ramesh K Sitaraman, and Mor Harchol-Balter. (AdaptSize): Orchestrating the hot object memory cache in a content delivery network. 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17), pages 483-498, 2017.
Daniel S Berger, Benjamin Berg, Timothy Zhu, Siddhartha Sen, and Mor Harchol-Balter. {RobinHood): Tail latency aware caching dynamic reallocation from {Cache-Rioe to (tache-Poor); In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18), pages 195-212, 2018.
BioNumbers Database. Average duration of single eye blink. BioNumbers Database, 2024. URL https
//bionumbers. hms, harvard. edu bionumber. aspz7id=100706 BNID 100706.
Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. cambridge university press. 2005.
Allan Borodin, Sandy Irani, Prabhakar Raghavan, and Baruch Schieber. Competitive paging with locality of reference. Journal of Computer and System Sciences, 50(2):244-255 1995.
Hao Che, Ye Tung, and Zhijun Wang. Hicrarchical web caching systems: Modeling, design and experimental results. IEEE journal on Selected Areas in Communications, 20(7):1305-13) 2002.
Jiayi Chen, Nihal Sharma, Tarannum Khan, Shu Liu, Brian Chang, Aditya Akella, Sanjay Shakkottai, and Ramesh Sitaraman. Darwin: Flexible learning- farning-based edn caching. Proceedings of the ACM SIGCOMM 2023 Conference, pages 981-999, 2023.
Yinlam Chow, Aviv Tamar, Shie Mannor, and Marco Pavone. Risk-sensitive and robust decision decision-making: a evar optimization approach. Advances neural information processing systems, 28, 2015.
Marek Chrobak and John Noga. Lru is better than fifo. Algorithmica,, 23:180-185. 1999.
Edward Grady Coffmaan and Peter J Denning. Operating systems theory, volume 973. prentice-Hall Englewood Cliffs, NJ, 1973.
ShareGPT Contributors, Sharegpt: A dataset of multi-turn chat interactions with large language models. httte::/hugginggacee http:///hhggggggaa...oco//aaaata http://///..ttttt//////////////.
2025.
Asit Dan and Don Towslcy. An approximate analysis of the Iru and fifo buffer replacement schemes. In Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, pages 143-152, 1990.
Amos Fiat, Richard M Karp. Michael Luby, Lyle A McGeoch, Daniel D Sleator, and Neal E Young. Competitive paging algorithms.. Journal of Algorithms, 12(4):685-699, 1991.
In Gim, Guojun Chen, Seung-seob Lee, Nikhil Sarda, Anurag Khandelwal. and Lin Zhong. Prompt cache: Modular attention reuse for low-latency inference. Proceedings of Machine Learning and Systems, 6:325-338, 2024.
Maxwell Horton, Qingqing Cao. Chenfan Sun, Yanzi Jin, Sachin Mehta, Mohammad Rastegari, and Moin Nabi. Kv prediction for improved time first token. arXiv preprint 11X0v22410.0839), 2024.
Raj Jain. Characteristics of destination address locality in computer networks: A comparison of caching schemes. Computer networks and ISDN systems, 18(4):243-255 2544, 1990.
Chao Jin, Zili Zhang, Xuanlin Jiang, Fangyue Liu, Xin Liu, Xuanzhe Liu, and Xin Jin. Ragcache: Efficient knowledge caching for retrieval- generation. arXiv preprint 124447 2024.
11

---

Yunho Jin, Chun-Feng Wu, David Brooks, and YeoY Wei. s²: Increasing gpu utilization during generative inference for higher throughput. Advances in Neural Information Processing Systems, 16:18015-18027, 2023.
Aditya K Kamath, Ramya Prabhu, Jayashree Mohan, Simon Peter, Ramachandran Ramjee, and Ashish Panwar. Pod-atten and-attention: Unlocking full prefill-decode overlap for faster IlM inference. In Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2, pages 897-912, 2025.
WC King. Analysis of paging algorithms. Proc. IFIP 1971 Congress, Ljubljana, pages 485-4944949 495-490. North- Holland, 1972.
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and lon Stoica, Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems Principles, pages 611-612226 1-626, 2023.
Emilio Leonardi and Giovanni Luca Torrisi. Least recently used caches under the shot noise model. 2015 JEEE Conference on Computer Communications (INFOCOM), pages 2281-2289. IEFF, 2015.
Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM (JACM), 68(4):1-25, 2021.
Naram Mhaisen, Abhishck Sinha, Georgios Paschos, and George losifidis. Optimistic no-regret algorithms for discrete caching. Proceedings of the ACM on Measurement and Analysis of Computing Syxtems, 6(3):1-28, 2022.
Michael Mitzenmacher and Rana Shahout. Queueing, predictions, and large language models: Challenges and open problems. Stochastic Systems, 15(3):195-22 2191 2025.
OpenAL. Prompt caching guide, 2024. prompt-caching Developer documentation.
URL
OpenAl Newsroom. 300m weekly chatgpt users and lb daily messages, December 2024. URL https 7/x.
http://wwwwooooeeerttaaaaa/e/eaa 19643733399218477444 Tweet.
Vidyadhar Phalke and Bhaskarpillai Gopinath. An inter-reference gap model for temporal locality in program behavior. ACM SIGMETRICS Performance Evaluation Review, 23(1):291 -300000 1995.
Ruoyu Qin, Zheming Li, Weiran He, Jialei Cui, Feng Ren, Mingxing Zhang, Yongwei Wu, Weimin Zheng, and Xinran Xu. Mooncake: Trading more storage for less computation a kveache- centric architecture for serving IIm chatbot. In 23rd USENIX Conference on File and Storage Technologies (FAST 25), pages 155 1700. USENIX Association, 2025.
Daniel D Sleator and Robert E Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202-208 1985.
Vikranth Srivatsa, Zijian He, Reyna Abhyankar, Dongming Li, and Yiying Zhang. Preble: Efficient distributed prompt scheduling for Ilm serving. 2024.
vLLM Team. Automatic prefix caching, 2025. URL https://docs vwlm. htw.maaa/eee/ttale/attttto// Project documentation.
prefix_ haipss/ccacinnn/ettlleeees
Zihao Ye, I Lequn Chen, Ruihang Lai, Wuwei Lin, Yineng Zhang, Stephanie Wang, Tianqi Chen, Baris Kasikei, Vinod Grover, Arvind Krishnamurthy, et al. Flashinfer: Efficient and customizable attention engine for llm 2025.
inference serving, arXiv preprint arXiv:2501.01
Wenting Zhao, Xiang Ren, Jack Hessel, Claire Cardie, Yejin Choi, and Yuntian Deng. Wildchat: Im chatgpt interaction logs the wild. arXiv preprint arXiv:2405.01477 2024.
Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Livia Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E Gonzalez, et al. Sglang: Efficient execution of structured language model programs. Advances in Neural Information Processing Systems, 37:62557-62583, 2024.
Yimmin Zhong, Shengyu Liu, Junda Chen, Jianbo Hu, Yibo Zhu, Xuanzhe Liu, Xin Jin, and Hao Zhang. (DistServe): Disaggregating prefill and decoding for goodput optiiized large language model serving. In 18th USENIX Symposium Operating Systems Design and Implementation (OSDI 24), pages 193-210, 2024.
Banghua Zhu, Ying Sheng. Lianmin Zheng, Clark Barrett, Michael I Jordan, and Jiantao Jiao. On optimal caching and model multiplexing for large model inference. arXiv preprint arXiv:2306. 230.000030000033,, 2023.
12

---

Kan Zhu, Yilong Zhao, Liangyu Zhao, Geféi Zuo, Yile Gu, Dedong Xie. Yufei Gao, Qinyu Xu, Tian Tang. Zihao Ye, al. Nanoflow: Towards optimal large language model serving throughput. arXiv preprint arXiv:2408. 12757. 2024.
Timothy Zhu, Daniel Berger, and Mor Harchol Balter. Sne meister. Admitting more tenants lateney slos. In Proceedings of the Seventh ACM Symposium on Cloud Computing, pages 374-387, 2016.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Justification: Our abstract and introduction list three core claims: new cache eviction rule, Tail-Optimized LRU; (ii) provable optimality under stochastic conver- sation model; and (iii) empirical tail-latency gains real LLM workloads. Each claim is backed by theorem or experiment.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In the last section, we discuss future directions that could relax our the single-tier cache assumption and single-server assumption.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess..
13

---

While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Complete proofs are in Appendix with cross-references and we provide intuition and proof sketch in the main paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We perform experiments public datasets and provide all codes in the submission.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
14

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We would submit and release the code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
Sublic/guides CooeeSubisssoonolliii
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed run reproduce the results. See the NeurlPS code and data submission guidelines (https
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide details of parameters used in the experiment for our policy, such as cache capacity and latency threshold.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
15

---

Justification:
Our experiments are used to simulate performances of proposed and baseline policies that deterministic on fixed job request traces, thus we do not have error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We used A100 GPU estimate the default latency function.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that http://///l/tttttssessieeeeellll
didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https:
Answer: [Yes]
Justification: We checked the NeurIPS Code of Ethics; no personal data disallowed content is involved
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
16

---

Question:
Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discussed the trade-off between tail latency versus average latency, with the former speaking to fairness.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (c.g.. dep.lymeln of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: Our work is about a caching policy, not a pretrained model or scraped dataset.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We have properly credited data used in the paper.
Guidelines:
17

---

The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new dataset or model checkpoint is introduced.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We did not perform any human-subject data collection.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsoureing nor research with human subjects.
18

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLM is used only for writing, editing and facilitating data analyses and experimenting.
Guidelines:
The answer NA means that the core method development in this research does involve LLMs as any important, original, or non non-standard components.
Please refer to our LLM policy http:///herripps.cc//oeeeeeereee for what should or should not be described.
19

---

Appendix
A
Related Work
Classic Caching and Paging. The caching problem has been extensively studied from a competitive analysis perspective, with binary cache hit/miss metrics. Foundational results include the hindsight- optimal Belady's algorithm [Belady] [966]. optimal deterministic online policies (Sleator and Tarjan 1985], and randomized algorithms Fiat et al. 1991]. Beyond worst-case competitive ratios, many works model structured request processes capture temporal locality observed in practice, includ-
ing access graph models [Borodin et al. 1995 Chrobak and Noga 1999.. independent reference
models [Coffman and Denning 1973 King, 1972 Dan and Towsley 1990, Che et al. 2002]. Shot
Noise models [Lennrddi and Torrisi 20155. LRU Stack and Working Set models [Jinn 1990] and
Inter-Reference Gap models [Phalke and Gopinath
1995]. For broader overviews, see Borodin and
El- Yaniv 2005); for caching with predictions, see
Lykouris and Vassilvitskii [021]. Mhaisen et al.
2022].
Alternative Metrics. Beyond binary hit/miss metrics, several systems optimize continuous objectives. Darwin Chen et al., 2023] balances hit rate and disk writes in CDN caching. RobinHood [Berger et al. 2018 and SNC-Meister [Zhu et al. [2016] target tail latency in web services and multi-tenan systems, respectively. AdaptSize [Berger et al. 2017) handles variable-size objects in content delivery networks. However, these works focus on traditional web caching rather than the unique characteristics of I.I. inference: multi-turn conversations with growing context windows and strict real-time latency requirements.
Prompt Caching for LLM Inference. Prompt caching reuses precomputed KV states from con- versation history to reduce prefill computation. Recent systems explore various aspects: prefix caching [Kwon al. 2023]. attention reuse [Gim al. 2024], RAG optimization [Jin et al., 2024), structured generation /Zheng et al. 2024], load balancing [Srivatsa et al. 2024]. hierarchical stor-
age [Qin al., 2025), and optimal model multiplexing [Zhu et al. 2002]. While these works demonstrate the value of prompt caching, they primarily optimize throughput or average latency
rather than tail latency.
Recent work on LLM serving has begun addressing tail latency through architectural innovations.
Sarathi-Serve (Agrawal et al. 2024 uses chunked prefill and stall-free scheduling, while Dist- Serve (Zhong et al.) 2024) disaggregates prefill and decoding for goodput optimization. These systems target tail latency but do not use caching the primary optimization lever.
Our work. To sum up, existing works have studied continuous metrics other than binary cache hit/miss and variable-size objects, but we are the first to prompt caching the primary lever to optimise TTFT tail latency, and the first to provide theoretical guarantees for tail-excess latency. Our work bridges the gap between classical caching theory, modern LLM serving systems, and tail latency optimization.
B Proof of Theorem [ Hindsight Optimal Policy for TEL
Proof. The proof has two steps: 1) show that optimizing the original TEL problem 7 equivalent to a new problem (TT) of maximizing the total number of reused cached blocks, subject to an additional "TEL-safe" capping constraint; 2) show that this new problem a classic offline caching problem whose optimal solution is to cap the KV cache size using TEL-safe budget and then evict using furthest-in innfuut-- policy.
Step one: Equivalence of Optimization Problems by
Fix feasible to 7 the optimal is given
Us
0z - F1, -
as otherwise we have u4, infeasible or can be improved. Thus we can focus cache decisions
20

---

We claim the optimal solution to the optimization problem 7 must satisfy the TEL-safe budget
Ji,t EE= Vis Ez=1 aig - -5) +
for every E [N], T. Suppose not, i.e., the optimal x²' {) for some E [N],6 Tr Then we have Eب= Bi + j== Unj -
to satisfies x'e, >
Σ 9bi + Σ and :/yy; - <,0,0,m <<0 0, =0. 0.
In this case, setting Vi,t Ej=1i Vi.j + Σラ anj - will not affect the value of w/, while releasing cache capacity that can be directed to other conversations, which contradicts the optimality of x'.
As the optimal solution must respect the sSfe budget, we can simplify the objective:
ΣΣ
u4e = ΣΣ
+
24,1 -
KE[N] AET.
REIN] TE
j=1
j=1
t-1
= Σ Σ
9h +
Σ
ai, - -20
Σ
qi.j +
az,j
Ditt
-
iE|M] TE.;
1=1
j=l
j=1
j=l
t-1
ΣΣ
9J
+ Σ
O. - - <<0 .0
EEN IET.
j=1
t-
t-1
E FE[N] SE
a.j - E2
Σ 9i
Oi - 5
E
Di.t
j=1
iE[M)CET
where the last equality holds as Ti for the requests with Σ Ri + ΣE= minimizing Eie[N] EiE,, Ua is equivalent to maximizing LIENN] ΣIET, Zi as the first term of the right-hand-side of the last equality above is constant.
ai { < 0. Thus
Therefore, rewrite
7 follows:
max KNEEN
Σ
Σ
Frit
(11)
iE
iE[N]
DET.
s.t.
6
1-1
F1,1 S
Gi
Oi,j - { +
Vi [M,teT:
(12)
j=1
Step two. We can interpret each block as a unit-size item that, once arrived, is requested again every subsequent turn of the same conversation (prefix reuse). At time E T,, the number of cache hits for that request of conversation equals exactly Ti,t Hence the objective of (I]) is the total number of cache hits over the horizon.
Because the cache content may change only at request times and all items have unit size, is paging instance with unit pages and clairvoyant knowledge, except that each request carries
per-request cap on the number of allowable hits, which we can enforce by immediately discarding any excess above upon the turn's completion.
In paging with unit pages, the offline optimal policy that maximizes total hits (equivalently minimizes misses) is Bélády's furthest-in futtur rule: whenever eviction is needed, evict the item whose next request is farthest in the future. Here, all blocks of conversation share the same next request time-the the next arrival of conversation i-so the rule specializes to: evict from the conversation whose next arrival is farthest in the future.
21

---

C Proof of Theorem 2
Proof. Given system state X, L,X,, X, let 0 denote the index of the conversation that is the h arrival with user prompt length Q and model response length A. The finite-horizon value-to-go function is
(Le + Q Xe -
number of uncached blocks above threshold
min XX 2r,
Vi+1(
VL, A)
x.
betief arrival state transition conversation length transition
with VM (-) O, where the feasible caching decision space is
(Y E Nddi((,0))
LO LLScO Xx,
with dim X, dim(X) x) + 1 (0 dim(X)), here dim X) denotes the dimension of vector X.
and the dimension expands when a new conversation arrives; ④ O) update the belief turn rate of conversation 0 Ås then discount belief turn rates of all conversations by exp(-μr7 v (L, Q+ updates the conversation length vector. Specifically, we increase the dimension of if necessary (i.e.. when 8 represents a new conversation), and add Q +
its 8th entry.
Let denote the index of the conversation that the 4tth arrival, with user prompt length Q and model response length A. Define the belief arrival rate vector X, the conversation length vector as L, and the cached token length vector as X, the cost-to-go function given by:
VA L. X, 0 Q.Q.4) (Lg + Q - Xe- - E)*
+
min (x ET,00Q0, [V++1 ( 0,T), V ((L,,,++ A), X,,Q'
with VM++1-) = 0. Let's rewrite + (A 0, (T 0), with
A(A, 0) updates the return rate vector upon the arrival of conversation 6. Specifically, this operator changes the belief arrival rate of conversation A
2 r) discount all return rates by exp(-pur).
The proof is by using induction and argue that if we choose a different caching state than X TLRU the cost will be higher. last arrival M, VM (X, L, X, Qo, As) (Lo + Qo Xe E)+ and any caching policy is optimal.
Suppose this holds for the 1tth + arrival. We proceed to show that the result holds for the h arrival. To simplify the notation, we define
(x, L. X)
Ao (Ve( X, 0, Qo, Ao)], Á r(A 0), VLL 0, Qo + Ao),
Then we need to prove
J& L. E S Jk (й, X')
To this, by definition of state transition, suppose the inter-arrival time is the discounted arrival rates are
À (x-exp(-ur) with Ào Xo-
From these expressions, we can conclude that regardless value of r. the return rates at next arrival maintain the same relative ordering as in A for conversations. Note that due to heterogeneous turn rates across conversations, conversation that arrived the hth arrival may not have the highest turn rate. Without loss of generality, let's assume
0 and let P, > + Σ, A,) denote the probability that conversation j returns at the next arrival, and (dim; = Xoonw/ (>ccov + Σ, Aa) denote the probability that new conversation starts at the next arrival.
We proceed to show this holds for any number of tokens evicted by treating each token eviction separately. Among all conversations that have arrived so far and have at least one cached token, list ascending order the ranking criterion score
their indices as i(1 (()),
A,P(L. Qi - X.),
22

---

Insert conversation & that just arrives into this ordered list according to its own score PQ 2 0)
Let X (1) denote the cache state that evicts a token from conversation i(1), and X (k) denote the cache state that evicts a token from conversation i(k) with &s >
JK+1 (1))
Σ
Qe +Q: xx(1)
-x)(( =)
vedim( (1))++
+ Pi(1) Aan
min x X100 J++2 (44)) ((),,, Qaay Aaa)). A.x))x((1)))
+ Pi(k) ARm
min x xu 1 i())), VLL, Qi(k) + Aua))) x(
Σ EQ.A.
min
J ((
(k())
Σ
O. IL,
+0; -x))) +1
(idim(((1))+))
+ P(( E. Qan.
min X11)ExXXX00)000000000000000 (4)) AQt)), x(())
+ Pi(M) (aua))
min JR+2 (T(, (LL) Qi(a)) + A(a)) x'))
x (10G
Σ EQ.A.
min X(A))XX((()LLL...-A-
Jk WLL (81)
(1(1))((k))
JR4 (A, L, Xk));
where the inequality holds as
by Definition [ (11) is the optimal solution while X(k) a feasible solution, and fū; are proportional to Ae thus
Σ [( + -
Σ
[Et Q x,()) +)+1
(edim(X(())
(edim(X(1))
and the expected cost incurred when a new conversation arrives (with probability Pd)m(((1)+2) Eol(Q - +]+ for both caching state, thus
Σ
Σ iEdimiX (1))41
dedim(X (1)++1
by induction hypothesis, the optimal X'(1)* and X')))* given by the optimization problem 8). Fix a user prompt length Qi and a model response length A; and we compare the to under (1) and X (k).
if conversation i(1) arrives next. then need to evict
token from X (1)
than from X(k). Suppose the extra token evicted from X (1) is from conversation (kk), then X'(1)" X'(k)* If not, then this means the extra token evicted is from another conversation with better ranking criterion, thus we have
J i(1)), (I)) Qi() + X'()")
2J4+2(T( (T() i(1)), (LL ((L Qam + ('k)))((k)")
by the induction hypothesis.
23

---

if conversation d(k) arrives next, then one need to evict one more token from X (k) than from X (1). In the optional caching model, the extra token evicted form X must be from conversation i(1) by the definition of the ranking of conversations, thus =11))=X'((
Jn (T(A, i())), (LL, Qu( + A(a)), A (k)))
= 2 (T (())) (L,, Qua) + A(x)); (k)")
if conversation other than i(1), i(k) arrives next, then X'())* and (1) need to evict the same number of tokens. If X'(k) evicts least one token from conversation i(k), then X' (1) = (k)). If not, then this means X X' evicts one token from another conversation with better ranking criterion, thus we have
JR+2 (T(A, i)), (LL i, x')))) Ju Je42 WLL, A.), (')))).
Therefore, by induction, the result holds for all 2 1.
Greedy Implementation. The optimization problem ( need not be solved explicitly as token-by-token greedy procedure suffices. At a high-levei, the policy ranks each token by arrival rates weighted by its counterfactual cost, i.c., the cost increase when we evict this token.
PPL: + Q; E X,) E[(L, + Q. E - (X; - 1)) - B[(L, + Qi - X.)*1
i... the difference in expected cost if we further evict one token when we have X; tokens in cache.
Algorithm 2: Expected-Tail--ptimee Tail-OOrimized LRU Policy
Input: Number of conversations N, cache sizes (X,), current lengths {Li). belief turn rates {Mr distribution of length of user prompt {Q:}. threshold ç. arriving conversation 6, arriving user prompt length Q arriving model response length A, tokens to evict n
Output: Updated cache sizes {X,} evicted +-
Lo +
// Update system state arriving conversation 0
Xa +- La
Ag + Xa
for each i E E do
Compute 1/ +- >-- P(I, + Q -2 X,)
Ranking criterion // Conversation with minimum value // Evict one token
while evicted
do
Find j = arg
1/
X, + X, 1
evicted f- evicted +1
Vy + A1 P(Ly + Q, - 2 X,)
Update ranking criterion
return )
In the implementation of the policy, one can use min-heap to process which token to evict using the ranking criterion. The computational complexity of the policy given by O(EE) + n log EE],, where [E] is number of conversations with non-zero cached tokens and is the number of tokens one needs to evict.
We show that policy 2 indeed returns a cache state that is an optimal solution to the optimization problem (8). Lemma 1. Policy returns optimal solution to the optimization problem
8
Proof. We prove by contradiction. Note that it is possible for the policy to return multiple optimal solutions, and it is also possible for the optimization problem (8) to have multiple optimal solutions. Suppose not, then the two of solutions do not intersect. Let X denote optimal solution. Then there must exist two conversations i, such that X; 2 and
X,P(L, + - X +1) A,P(L, A, - x2,i),
24

---

Then we can construct another solution X' such that X = X for k k i.j. =
x - 1. Then the difference between the objective values of X' and X is given by
OBJ(XX) OBJ(X*) A,EI(L, + +Q, - 8 +X7 (LL, + Q) - - - 1))*1
- (A,BI(L + -
+ - -5-x))+
= XyP(L, + A₂ - X,) - A,P(L Qi - - x1+1)
<0,
which contradicts the optimality of X
D Discussion on Forced Caching
Implementation of Tail-Optimized LRU. To implement forced caching, especially GPU level, the server needs to decide which block to evict as serving the turn. The server may not know the total number of cache blocks evict due the uncertainty in the model response length, nevertheless the server can repeatedly call our policy to evict more tokens if needed.
Hindsight optimal policy. To model forced caching, replace optional caching constraint 5 with
Bit+1
(q.. + on..). Vi E [N], E T, and < T,
(13)
ie., when turn arrives, the server is required to cache its whole conversation history including newly generated response. Theorem [ continues to hold under forced caching.
Expected-Taill Tail-Optimized LRU. To model forced caching, we replace feasible caching decision space under optional caching with
xx(X,0,10 (Y e Nddi(X.0) .)) EXsCYY- xx,
Theorem continues to hold under forced caching, i.e., Expected-Tail-Optimiine LRU remains to be optimal,
every future prompt (if it arrives) has a known, fixed length Q 2 O. Here this fixed length be heterogeneous across conversations and across turns. Crucially, the decision-maker still does not know if any given conversation will return; they only know that should it return, its next-turn question length will be Q. In this case, Expected-Tail- Tail-Optimmzedd LRU is reduced to a deterministic version as stated in policy I
conversations have homogeneous turn rates Aum
This peed-prompt-length assumption holds when prompts pre-specified. When 0 after the first turn and responses also have zero length, our model reduces to classic paging with unit page size.
E
Additional Figures
F
KV Cache Size Computation
We calculate the KV cache memory requirements for the Vicuna-7B model. For 10,000 tokens stored in Float16 precision, the total KV cache size is approximately 4.88 GB. With Float32 precision, this memory requirement doubles to approximately 9.77 GB.
F1
Model Configuration
The following parameters are from the Vicuna-7B-v13. model configuration
Hidden Size: 4096
http:///eeteaeeee.....o.o.ooeoo. json
25

---

Distribution of Number of Turns
Distribution of Prompt Lengths
Distribution of Response Langthe
2500
Mean: 7.91
Mear: 99.0
Mean: 663.2
Madiae:
Med
Medien: 569
PS5: 28.0
PS5: 300,0
PBS: 1701
2006
Freqatccy
Fregarnc
5000
1008
2000
1008
2000
12
10'
12"
10"
10"
10'
10'
16'
10"
Number of Tums per Converation (0g scaley
Prompt Length tokkens log soore)
Response Length tookans, log scole)
Figure 5: Distributions of turns and tokens of ShareGPT [Contributors 10,000 conversations).
2025 datasets (sampled
Number of Attention Heads: 32
Number of Hidden Layers: 32
Number of Key- Value Heads: 32
Head Size: 128 (Hidden Size + Number of Attention Heads)
Data Type: Float16 (2 bytes per value)
F22
Calculation
The KV cache size per token is computed as: KV cache per token (bytes) = x Layers KV Heads x Head Size x Data Type Size
= 2 x 32 x 32 x 128 x 2
524,288 bytes
where the leading factor of accounts for storing both Key (K) and Value (V) matrices. For 10,000 tokens, the total memory requirement is:
Total KV cache (bytes) = 10,000 x 524,288
552442,88,000 bytes
Converting to gigabytes:
5,242,880,000
KV cache size (GB)
10243
4.8828 GB
G Additional Experiment Results
G.1
Offline Baselines and T-LRU Variants with Future Knowledge.
Recent work on queueing systems has shown that machine learning predictions, such as predicted service times or job characteristics, can significantly improve scheduling and resource allocation decisions Mitzenmacher and Shahout [025]. In the context of LLM inference systems, various types of predictions (e.g., conversation continuation, prompt lengths) could also potentially enhance caching performance. This motivates natural question: which predictions are most valuable for caching, and how much improvement can each type unlock? To answer this, we design T-LRU variants with different levels of future knowledge, creating predictability spectrum that quantifies marginal benefit of each prediction type.
We evaluate three policies with increasing levels of future knowledge:
T-LRU (baseline): Uses the empirical average prompt length to predict future requests. No knowledge of conversation termination actual prompt lengths.
26

---

End-Aware T-LRU: Knows whether each conversation will continue (return) or terminate, but does not know future prompt lengths. This variant evicts all blocks from terminating conversations and follows standard T-LRU for continuing ones.
Length-Aware T-LRU; Knows both conversation continuations AND the exact length of the next user prompt. This variant uses exact prompt lengths for TEL-safe trimming and evicts all caches when conversations end.
Additionally, we include Tail-Optimized Belady, the hindsight-optimgs policy for TEL that knows the entire future arrival sequence. This serves as an upper bound on achievable performance.
the latency distributions (median, P90, P95, P99) under different eaching policies across varying cache capacities on the WildChat dataset.
We highlight two observations from Figure First, tail improvement is achieved with a modest cost to the median latency. T-LRU (blue squares) consistently beats LRU and Threshoid-LRU at the tail (around 300 ms). but its median latency is slightly higher (increased from 10ms to 40ms). The trade-off is expected and in fact intended. Median latency degradation is minimal and users will likely not notice: for context, the duration of blink is on average 100-400 milliseconds according to the Harvard Database of Useful Biological Numbers (BioNumbers Database 2024]. T-LRU deliberately trades off slightly higher median latency (a few milliseconds) to achieve larger tail latency reductions (tens to hundreds of milliseconds), which is more favorable for user experience.
Second, a single-bit forecast "will this conversation continue?" is a remarkably powerful signal. End-Aware T-LRU performs much better than T-LRU, while Length-Aware T-LRU gains only small additional edge from knowing the exact prompt length. In practice, predicting whether a single conversation will continue is much easier than forecasting exact prompt sizes, and vastly easier than predicting the full arrival sequences required by -ptimnpte Belady. Existing works like [Jin ctt al. 2023 propose models predict the length of model response with up to 98.61% prediction accuracy, underscoring the practical viability of deploying End-Aware policies.
Note that Tail-Optimized Belady is the optimal policy for our TEL objective for the &. chosen, thus it not necessarily the optimal policy for tail latency different levels. On the other hand, solving for the optimal policy for tail latency is computationally hard.
50th Tocert
201h Persentt
4:30
24:33
33
2x33
1000
080
Optivized Ro
Tst Optereeee LIU
Bnd Swore TUK
Leugt daiee TLMU
The L401
50th Faccer Lbc
93th Fanse
23th Parandi
20th Parsori
26387)
19-30
4x18
Orlel Capady (1)
Grtic Capate
Gofe Caparry
Cafh- Cath-Coerie Coperit XD
Tal optivired Beads
Tsl optiriedd LPU
Bnd swom TUK
Leugt daarc TLM)
Tha (9U)
Porcerlee
93th Fesae
2311 Prrcndi
20th PNrroveit
24w:39
4xT2"
4000
2009
4007
2200
3000
080
Goffic Ceparro
Figure 6: Latency results for various settings (threshold latency &. = 100, 200, 300 ms) from top to bottom panels.
27

---

G.2 Results on ShareGPT with Synthetic Timestamps
ShareGPT [Contributors) 2025 does not include timestamps each request, thus we generate them with the stochastic model described in Section + Specifically, for each conversation, we draw exponential inter-arrival times with rate Aconv I, then for each conversation, we generate inter-arrival times between each turn within conversation using Exponential distribution with rate
Atum 3. The average prompt length in ShareGPT is approximately 100 tokens (we thus set Q 100 in implementation), with an average of 3.5 turns per conversation.
Tables 5 show that Tail-Optimized LRU still beats both LRU and Threshold-LRU: it trims P90 by up to 10%, and P95 by up to 7%. The smaller improvement compared to the ones observed in WildChat (Tables stem from the stready-high base latencies under LRU (with capacity C = 1000 under LRU, medium, P90, P95, P99 tail latencies are roughly 209 ms, 1415 ms, 2447 ms, 3649 ms). thus percentage improvements shrink.
Table 4: Relative latency improvement of T-LRU over LRU with various &, (ShareGPT)
c,
E, 100ms
E,
f,
Capacity
p90
p95
p90
p95
p90
p95
p90
p95
p90
p95
1000
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.9%
0.6%
0.9%
0.9%
0.7%
2.3%
4000
0.6%
0.6%
0.7%
1.8%
2.0%
2.5%
2.5%
3.0%
4.2%
3.5%
0.7%
1.3%
2.1%
2.9%
4.9%
3.6%
8.1%
4.2%
10.0%
4.7%
8000
1.5%
0.9%
2.6%
1.8%
3.5%
2.5%
4.8%
3.6%
9.6%
5.0%
10000
0.9%
0.7%
3.6%
1.7%
4.3%
2.9%
5.1%
3.6%
9.0%
6.9%
Table 5: Relative latency improvement of T-LRU over Threshold-LRU with various & (ShareGPT)
E. = 50ms
c. 100ms
E.
200ms
&. 300ms
E. 500ms
Capacity
p95
p90
p95
p90
p95
p90
p90
p95
1000
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.9%
0.6%
0.9%
0.9%
2030
0.7%
0.0%
0.7%
0.2%
0.9%
1.5%
1.4%
2.0%
2.7%
2.3%
2.5%
6000
0.7%
0.8%
2.1%
2.4%
4.9%
3.1%
8.1%
3.7%
10.0%
4.2%
0.8%
2.0%
1.2%
2.9%
2.0%
4.1%
3.0%
9.0%
4.5%
10000
0.9%
0.6%
3.6%
1.6%
4.3%
2.8%
5.1%
3.5%
9.0%
6.8%
Using 200 ms SLO, T-LRU cuts the share of requests above the budget by 2-8% across capacities (Table Improvements again peak when &. is near the desired percentile; extremely high &, trades those mid-tail wins for heavier protection of the extreme tail, echoing the WildChat pattern.
Table 6: Relative improvement T--RRU reduction in requests with latency > 200ms (ShareGPT)
Capacity
E,
50ms
E, 100ms
E, 150ms
E,
200ms
E, 500ms
LRU
Thre-LRU
Thre-LRU
LRU
Thre-LRU
LRU
Thre-LRU
ThreLRU
1000
1.6%
2.3%
2000
1.1%
1.0%
1.9%
1.8%
2.6%
2.5%
3. 1%
3.0%
-8.6%
-8.7%
4000
1.8%
1.3%
3.9%
3.4%
4.7%
4.2%
4.8%
4.3%
-15.6%
-16.2%
6000
1.9%
1.1%
4.7%
3.9%
6.0%
5.2%
4.7%
3.9%
-26.2%
-27.2%
8000
1.2%
0.9%
4.3%
4.0%
4.9%
4.6%
2.9%
2.6%
-39.3%
-39.7%
2.2%
Lastly, in spite of the extra foresight, End-Aware T-LRU and Length- T-LRU show only marginal gains over T-LRU, and all three policies perform very closely to Tail-Optimized Belady, the optimal hindsight policy that minimizes the Tail Excess Latency. This is exactly what our stochastic model predicts: under Poisson arrivals, LRU's recency order is already near-perfect proxy for "furthest in the future", the rule the hindsight policy uses for eviction, so extra foresight offers diminishing returns.
28

---

Langth-daare Percendis
Facertia
135 110
14:15
24
26000
13"
35-
255 11
13
231
33:0
Cipindyy
Capadly
Carh Oppariy
Caprriy
TE-Oppimiine Deads
Tol-OptimioddD LTU
End-wwer TUHU
Length-dnsee TLBU
-P. DRU
Thrsshold LT
50th Facertle
92m1 Faccertle
1511 Parcendi
50th Percantle
14
24
13
225 10
13
10
x3x
32x
Carto
Carh
Cllf Caperiyy (11)
Tel-Optimied LSU
End-eeer TUBU
Length-Aasee TUNU
Thrashodd LT0
Facertle
Facerile
E311 Peraanii
60th Nerandile
13
13
23
50
2303
40:00
7303
4001
7002
1000
2003
Figure 7: Latency results for various settings (threshold latency 100, 200, 300 ms) from top to bottom panels (ShareGPT)
29


Reviews:
[{"review_id": "erLNdpNDU1", "reviewer": "Reviewer_u7Si", "summary": "Prompt caching is an important way to reduce TTFT by storing the KV cache of prior requests, but it’s generally impossible to cache all prior requests due to limited memory. This paper proposes a new eviction algorithm—Tail-Optimized LRU—for prompt caching, which minimizes “Tail Excess Latency” (e.g., total latency above some threshold, across all requests). It proves that this algorithm is optimal under a stochastic model of the incoming requests, and shows empirically that it effectively reduces the tail latency—p90, p95 TTFT— on different datasets of real conversation data (e.g., WildChat) by 27.5% and 23.9%, respectively, relative to LRU.", "questions": "- What existing caching literature has continuous metrics (like TTFT) as opposed to discrete metrics like cache hit vs miss? Also, what examples in the caching literature require varying amounts of storage for different elements of the cache? Has any prior work introduced tail-excess latency?\n- I believe the first while loop in Algorithm 1 should be \"while \\sum X_i > C and there exists i such that X_i >= L_i + Q_i^  - \\xi\". Is this correct?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The goal of minimizing “Tail Excess Latency” is well motivated, given that inference providers often want to reduce the percentage of requests that exceed some TTFT threshold (where the user experience starts degrading).\n- The proposed algorithm—”Tail-Optimized LRU”—is simple, easy to implement in existing LRU systems, and is a natural modification of the eviction algorithm that is (hindsight) optimal (i.e., has full knowledge of all future requests), to deal with the fact that in real settings, the exact lengths and arrival order of the future requests is not known. It is also shown to be optimal under a stochastic model of the arriving requests.\n- Empirically, the paper demonstrates convincingly that tail-optimized LRU reduces the p90 and p95 TTFT values, as well as the percent of requests with TTFT greater than a threshold.\n\nWeaknesses\n- The technical discussion could be made clearer, especially Section 4. Giving better introductions to the different sections, where the main ideas/intuitions/take-aways are explained clearly, would be quite helpful before diving into the low-level technical details, notation, and theoretical results.  \n\nNote: I do not actively work on caching algorithms, so my confidence is medium.", "was_revised": true, "final_justification": "I continue to believe this is a nice contribution to the prompt caching literature. Method is simple, and improves an important metric (amount of TTFT time above threshold). I will keep my score.", "rebuttal": "We thank the reviewer for thoughtful feedback and constructive suggestions. We are grateful that the reviewer found our work well motivated, and our policy simple, easy to implement and has strong empirical results. Below we address the concerns raised.\n\n## Related work.\nAll titles are given in full because links are not allowed in the rebuttal.\n* Continuous metrics: “Darwin: Flexible Learning-Based CDN Caching” (Chen et al., 2023) optimizes for both hit rate and disk writes, “RobinHood: Tail Latency-Aware Caching — Dynamically Reallocating Cache Resources from the Cache-Rich to the Cache-Poor” (Berger et al., 2018) and “SNC-Meister: Admitting More Tenants with Tail Latency SLOs” (Zhu et al., 2016) for tail latency.\n* Caching work with variable-size objects:\nprompt caching works certainly lie in this category: “Prompt cache: Modular attention reuse for low-latency inference” (Gim et al. 2023), “On Optimal Caching and Model Multiplexing for Large Model Inference” (Zhu et al., 2023), and “SGLang: Efficient Execution of Structured Language Model Programs” (Zheng et al. 2023). See more in our related work section in the paper.\nContent delivery networks also require varying amounts of storage for different elements of the cache: “AdaptSize: Orchestrating the Hot Object Memory Cache in a Content Delivery Network” (Berger et al., 2017).\nIn theoretical computer size literature, let cost(p) denotes the cost of a cache miss of object p and size(p) denotes the size of object p, there are four types of caching models:\n  + uniform model (cost(p) = size(p) = 1): “Competitive paging algorithms” (Fiat et al., 1991); “A study of replacement algorithms for a virtual-storage computer” (Belady 1966);\n  + cost mode (size(p) = 1): “A primal-dual randomized algorithm for weighted paging” (Bansal et al., 2012); “New results on server problems” (Chrobak et al., 1991);\n  + fault model (cost(p) = 1): “Caching is hard—even in the fault model” (Chrobak et al., 2012); “Practical bounds on optimal caching with variable object sizes” (Berger et al., 2018);\n  + bit model (cost(p) = size(p)): “Page replacement with multi-size pages and applications to web caching” (Irani 1996);\n  + general model: “Page Replacement for General Caching Problems” (Albers et al., 1999); “Randomized competitive algorithms for generalized caching” (Bansal et al., 2008).\n\n  In these works, the goal is to study the computational complexity of the offline caching and the competitive ratio of online policies. Fault model, bit model, and general model also have variable-size objects.\n* Tail-excess latency: To our knowledge, Tail excess latency is a novel metric, inspired by conditional value at risk and the (P90/P99) percentile tail latency. The closest paper, “Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve” (via chunked prefill and stall-free scheduling) and “DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving” target tail latency rather than our above threshold metric.\n\n\nTo sum up, existing works have studied continuous metrics other than binary cache hit/miss and variable-size objects, but *we are the first to use prompt caching as the primary lever to optimise TTFT tail latency, and the first to provide theoretical guarantees for tail-excess latency*. We will add the above discussion in the revised paper to clarify the gap our work fills.\n\n\n\n\n## Algorithm 1 loop condition.\nThanks for pointing this out. We have edited this to avoid infinite looping.\n\n\n\n\n## Improve technical discussion.\nWe appreciate the suggestions. We will add the following high-level intuitions before diving into the model and proofs:\n\n\n\n\n> To model multi-turn conversations, we need to specify:\n> 1. when does a new conversation start?\n> 2. when will a conversation speak again?\n> 3. how many tokens does the prompt/response have?\n> 4. when will a conversation end?\n\n\n\n\n> For 1), we assume new conversations “birth” as a Poisson process. For 2), we assume each conversation generates prompts following another Poisson process. For 3), we assume prompt length and answer length follows some fixed distribution. For 4), we give each conversation an exponential death clock: the longer it stays quiet, the less likely it is to come back. This matches what we observe empirically in WildChat traces.\n> Under our model, least-recently-used implies least-likely-to-return. When a conversation “dies”, one can throw away related cache trunks safely. Our policy T-LRU keeps the LRU ordering but prioritizes conversations whose next arrival will breach a TTFT latency threshold. In this section, we will show that a generalized version of T-LRU that minimizes expected TEL is optimal under our stochastic conversation model."}, {"review_id": "BCFX3yuVEE", "reviewer": "Reviewer_XCfR", "summary": "This paper proposes a KV caching policy for LLMs with a focus on optimizing tail latency. In particular, the authors introduce Tail-Optimized LRU, which prioritizes high-latency conversations and achieves optimal tail latency under a natural stochastic model of conversation dynamics. They present a novel stochastic model for multi-turn conversations to capture uncertainties and the temporal locality of LLM workloads. The authors empirically validate the effectiveness of the proposed method using real multi-turn chat traces, including ShareGPT and WildChat. Experimental results show that Tail-Optimized LRU reduces p95 tail latencies by up to 23.9% compared to the baseline LRU method.", "questions": "- Could you provide additional details about the datasets used (e.g., average token length, number of conversation turns, and topic coverage)?", "limitations": "- While the authors mention future directions in the conclusion, it would be beneficial to include a more detailed analysis of the current method's limitations.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths \n- The paper is theoretically sound. The authors prove the optimality of the proposed Tail-Optimized LRU under a reasonable stochastic conversational model.\n- Optimizing tail latency in LLM-based conversations is a novel and relevant problem.\n- The proposed method achieves substantial empirical reductions in tail latency cases. \n\nWeaknesses\n- The paper lacks illustrative figures that describe the proposed method and compare it to existing approaches. This makes it difficult to fully grasp the core mechanisms and workflow of the method.\n- The proposed method involves a performance trade-off: while the method improves tail latency, the method underperforms in non-tail cases compared to the baseline LRU. LLM serving systems often involve multiple users, concurrent queries, KV cache limitations, and constrained computational resources. In such scenarios, performance degradation in non-tail cases may impact overall system efficiency. It would be helpful if the authors provided evaluation results that reflect a more comprehensive view of performance, such as average or maximum latency per token across the entire dataset, irrespective of percentiles.", "was_revised": true, "final_justification": "This paper provides a solid theoretical analysis. However, the paper lacks illustrative figures that would help readers understand the proposed method and its key differences from prior work. For these reasons, I assign a \"weak accept\". I also note that I am unfamiliar with the paper's field and related works.", "rebuttal": "We thank the reviewer for thoughtful feedback and constructive suggestions. We appreciate that the reviewer found our work theoretically sound, and the problem we tackle is novel and relavent. Below we address the concerns raised.\n\n## Lack of illustrative figures.\nThanks for the suggestion. In our submitted paper, Figure 1 (a) illustrates what our policy caches for one conversation across turns and Figure 1 (b) illustrates the comparison with LRU using an example. We also state our policy explicitly in Algorithm 1. We appreciate that these figures may not have conveyed the low-level workflow clearly enough, and we will bridge this gap by adding diagrams to illustrate what blocks are cached/evicted.\n\n\n\n\n## Trade-off with non-tail latency.\nBelow we list the average and maximum TTFT latencies and the relative improvement of T-LRU over LRU and Thre-LRU. For Table 3 and 4, positive numbers mean the improvement (decreased latency); negative numbers mean increased latency.\n\n\n### Table 1: Mean TTFT Latency (seconds)\n| Capacity | ξ=50ms T-LRU | ξ=50ms LRU | ξ=50ms Thre-LRU | ξ=100ms T-LRU | ξ=100ms LRU | ξ=100ms Thre-LRU  | ξ=150ms T-LRU | ξ=150ms LRU | ξ=150ms Thre-LRU  | ξ=200ms T-LRU | ξ=200ms LRU | ξ=200ms Thre-LRU  | ξ=500ms T-LRU | ξ=500ms LRU | ξ=500ms Thre-LRU  |\n|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|\n| 1000 | 0.0853s | 0.0849s | 0.0852s | 0.0858s | 0.0849s | 0.0852s | 0.0862s | 0.0849s | 0.0852s | 0.0862s | 0.0849s | 0.0852s | 0.0872s | 0.0849s | 0.0852s |\n| 2000 | 0.0829s | 0.0821s | 0.0826s | 0.0839s | 0.0821s | 0.0826s | 0.0846s | 0.0821s | 0.0826s | 0.0847s | 0.0821s | 0.0826s | 0.0863s | 0.0821s | 0.0826s |\n| 4000 | 0.0788s | 0.0773s | 0.0782s | 0.0809s | 0.0773s | 0.0782s | 0.0816s | 0.0773s | 0.0782s | 0.0820s | 0.0773s | 0.0782s | 0.0845s | 0.0773s | 0.0782s |\n| 6000 | 0.0752s | 0.0730s | 0.0746s | 0.0777s | 0.0730s | 0.0746s | 0.0788s | 0.0730s | 0.0746s | 0.0795s | 0.0730s | 0.0746s | 0.0826s | 0.0730s | 0.0746s |\n| 8000 | 0.0720s | 0.0691s | 0.0712s | 0.0745s | 0.0691s | 0.0712s | 0.0756s | 0.0691s | 0.0712s | 0.0778s | 0.0691s | 0.0712s | 0.0810s | 0.0691s | 0.0712s |\n| 10000 | 0.0682s | 0.0652s | 0.0677s | 0.0712s | 0.0652s | 0.0677s | 0.0737s | 0.0652s | 0.0677s | 0.0755s | 0.0652s | 0.0677s | 0.0784s | 0.0652s | 0.0677s |\n\n\n\n\n\n\n\n\n### Table 2: Max TTFT Latency (seconds)\n| Capacity | ξ=50ms T-LRU | ξ=50ms LRU | ξ=50ms Thre-LRU | ξ=100ms T-LRU | ξ=100ms LRU | ξ=100ms Thre-LRU  | ξ=150ms T-LRU | ξ=150ms LRU | ξ=150ms Thre-LRU  | ξ=200ms T-LRU | ξ=200ms LRU | ξ=200ms Thre-LRU  | ξ=500ms T-LRU | ξ=500ms LRU | ξ=500ms Thre-LRU  |\n|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|\n| 1000 | 0.7070s | 0.7070s | 0.7070s | 0.7070s | 0.7070s | 0.7070s | 0.7070s | 0.7070s | 0.7070s | 0.7041s | 0.7070s | 0.7070s | 0.6449s | 0.7070s | 0.7070s |\n| 2000 | 0.7070s | 0.7070s | 0.7070s | 0.7070s | 0.7070s | 0.7070s | 0.7070s | 0.7070s | 0.7070s | 0.6885s | 0.7070s | 0.7070s | 0.6263s | 0.7070s | 0.7070s |\n| 4000 | 0.7070s | 0.7070s | 0.7070s | 0.7070s | 0.7070s | 0.7070s | 0.6885s | 0.7070s | 0.7070s | 0.6885s | 0.7070s | 0.7070s | 0.6263s | 0.7070s | 0.7070s |\n| 6000 | 0.7070s | 0.7070s | 0.7070s | 0.6885s | 0.7070s | 0.7070s | 0.6885s | 0.7070s | 0.7070s | 0.6885s | 0.7070s | 0.7070s | 0.6263s | 0.7070s | 0.7070s |\n| 8000 | 0.6885s | 0.7070s | 0.6885s | 0.6885s | 0.7070s | 0.6885s | 0.6885s | 0.7070s | 0.6885s | 0.6698s | 0.7070s | 0.6885s | 0.6263s | 0.7070s | 0.6885s |\n| 10000 | 0.6885s | 0.6885s | 0.6885s | 0.6885s | 0.6885s | 0.6885s | 0.6698s | 0.6885s | 0.6885s | 0.6698s | 0.6885s | 0.6885s | 0.6263s | 0.6885s | 0.6885s |\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n### Table 3: T-LRU vs LRU - TTFT Latency Improvement (%)\n\n\n\n\n| Capacity | ξ=50ms Mean | ξ=50ms Max | ξ=100ms Mean | ξ=100ms Max | ξ=150ms Mean | ξ=150ms Max | ξ=200ms Mean | ξ=200ms Max | ξ=500ms Mean | ξ=500ms Max |\n|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|\n| 1000 | -0.44% | 0.00% | -0.96% | 0.00% | -1.52% | 0.00% | -1.46% | 0.42% | -2.63% | 8.79% |\n| 2000 | -0.92% | 0.00% | -2.17% | 0.00% | -3.02% | 0.00% | -3.19% | 2.62% | -5.11% | 11.42% |\n| 4000 | -2.00% | 0.00% | -4.73% | 0.00% | -5.63% | 2.62% | -6.11% | 2.62% | -9.40% | 11.42% |\n| 6000 | -3.00% | 0.00% | -6.50% | 2.62% | -7.98% | 2.62% | -8.98% | 2.62% | -13.23% | 11.42% |\n| 8000 | -4.09% | 2.62% | -7.78% | 2.62% | -9.29% | 2.62% | -12.46% | 5.27% | -17.12% | 11.42% |\n| 10000 | -4.61% | 0.00% | -9.12% | 0.00% | -12.94% | 2.72% | -15.68% | 2.72% | -20.17% | 9.04% |\n\n\n\n\n\n\n\n\n### Table 4: T-LRU vs Thre-LRU - TTFT Latency Improvement (%)\n| Capacity | ξ=50ms Mean | ξ=50ms Max | ξ=100ms Mean | ξ=100ms Max | ξ=150ms Mean | ξ=150ms Max | ξ=200ms Mean | ξ=200ms Max | ξ=500ms Mean | ξ=500ms Max |\n|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|\n| 1000 | -0.12% | 0.00% | -0.64% | 0.00% | -1.20% | 0.00% | -1.14% | 0.42% | -2.31% | 8.79% |\n| 2000 | -0.39% | 0.00% | -1.63% | 0.00% | -2.48% | 0.00% | -2.65% | 2.62% | -4.55% | 11.42% |\n| 4000 | -0.77% | 0.00% | -3.47% | 0.00% | -4.36% | 2.62% | -4.83% | 2.62% | -8.08% | 11.42% |\n| 6000 | -0.70% | 0.00% | -4.13% | 2.62% | -5.57% | 2.62% | -6.55% | 2.62% | -10.71% | 11.42% |\n| 8000 | -1.02% | 0.00% | -4.60% | 0.00% | -6.07% | 0.00% | -9.14% | 2.72% | -13.67% | 9.04% |\n| 10000 | -0.75% | 0.00% | -5.09% | 0.00% | -8.76% | 2.72% | -11.41% | 2.72% | -15.73% | 9.04% |\n\n\nHere we are using the same experiment setup as in the submission: first 1,306 turns from WildChat with average user-prompt length Q = 200, using ​​Vicuna-7B on one Colab A100 GPU. \n\n\n\n\nWe observe in our experiments, T-LRU does slightly increase p50 latency and average latency, which is expected as we are trading-off worst-case experience (p95/p99) with the mean. However, the medium/average latency degradation (+1/+10 milliseconds) is minimal and users will likely not notice: for context, the duration of a blink is on average 100–400 milliseconds according to the Harvard Database of Useful Biological Numbers (BNID 100706). However, reducing p99 latency from 500 ms to 400 ms improves the user-experienced responsiveness. T-LRU deliberately trades off slightly higher median latency (a few milliseconds) to achieve larger tail latency reductions (tens to hundreds of milliseconds), which is more favorable for user experience.\n\n\n## Dataset statistics.\nWe provided distributions of turns and tokens of ShareGPT and WildChat datasets in the appendix (Figure 4). Below we list the statistics:\n* Average number of turns in a conversation: 3.51 (ShareGPT) and 2.54 (WildChat)\n* Average number of user tokens:  94.46±626.39 (ShareGPT) and 295.58±1609.18 (WildChat)\n* Average number of Chatbot tokens: 348.45±269.93 (ShareGPT) and 441.34±410.91 (WildChat)\n* Number of languages: 41(ShareGPT) and 68 (WildChat)\n\n\nHere the token statistics are computed based on the Llama-2 tokenizer. For WildChat English conversations, the topic includes assisting/creative writing, analysis/decision explanation, coding factual info, and math reason (\"WildChat: 1M ChatGPT Interaction Logs in the Wild\"). ShareGPT covers topics including technology, education, business, legal, relationship, literature, science, language (\" The Shifted and The Overlooked: A Task-oriented Investigation of User-GPT Interactions\"). We will add these statistics in the revised paper to provide more context.\n\n\n\n\n## Discussion on limitations.\nThanks for the suggestions. We will add the following discussions in the revised paper, which are also raised by other reviewers.\n* Tail-vs-median trade-off: T-LRU intentionally sacrifices a few milliseconds at the median to cut tens–hundreds of milliseconds at the tail. Practitioners might prefer a hybrid policy that blends the two objectives, which is interesting for future works.\n* Automatic threshold calibration: T-LRU relies on a user-chosen TTFT threshold, which penalizes latency above the threshold but does not directly translate to a service level objective. It would be practically-relevant to see how to tune this using live traffic for a given service level objective such as “95% of requests complete within 200 ms”."}, {"review_id": "yP8q98E4Oz", "reviewer": "Reviewer_9wiK", "summary": "The author modifies the Cache LRU algorithm in online serving systems like VLLM, introducing an LRU variant that explicitly optimizes for tail latency. The motivation appears well-justified, and the technical approach is both simple and effective. Experiments demonstrate that the proposed algorithm slightly increases median latency but significantly reduces tail latency, leading to improved SLO compliance.", "questions": "I have placed my questions in the above weaknesses part. I recommend that the authors, if possible, further evaluate the improvements brought by their method when combined with various practical serving optimizations, such as continuous batching and prefixed cache. While I understand that implementing these features can be challenging, doing so would strengthen the significance of the paper in real-world settings. Additionally, there is a typo in Section 5.1: “without mixed bathing” should be corrected to “without mixed batching.”", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strengths:\n\n1. The motivation of the paper is well-founded. This strategy of sacrificing median performance to optimize for worst-case scenarios is widely adopted in many fields.\n\n2. The method remains simple yet effective, and experiments show that it can significantly improve tail latency compared to standard LRU.\n\n\n# Weaknesses:\n\nI have some concerns regarding the experiments. It appears that the study does not account for several widely used optimizations present in state-of-the-art serving systems.  First, mixed or continuous batching was disabled in the experiments, which could significantly increase latency. I am unsure how the proposed algorithm would perform with continuous batching enabled in a realistic system. Second, under cache reuse settings, it is common practice to use prefixed caching. \n\nWhen evicting blocks with LRU, should blocks involved in prefixed caching be treated differently?\nMoreover, has the impact of this widely-adopted prefixed caching feature been considered in the experiments?\n\n# Overall：\nOverall, I believe this paper effectively optimizes tail latency by adopting the strategy of sacrificing median performance to improve worst-case scenarios. This solution is novel in my opinion, and it opens up a promising direction for future studies. Although the paper does not integrate some popular optimizations into its experimental setting—which somewhat limits the practical significance of the results for real-world deployment—I think this is acceptable in academic research. After all, similar issues are also present in the evaluations of other academic work. Therefore, I believe the strengths of this paper outweigh its weaknesses, and I am inclined to give a decision of Weak Accept. If the authors could further address the above limitations, I would be willing to raise my score.", "was_revised": true, "final_justification": "Although the benefits of the proposed method are reduced when combined with modern optimization techniques, it still yields positive results. Therefore, I will maintain my positive score.", "rebuttal": "We thank the reviewer for thoughtful feedback and constructive suggestions. We are grateful that the reviewer found our work well motivated, our policy simple and easy to implement, and our empirical results strong. Below we address the concerns raised.\n\n## Clarification on prefix caching.\nWe do assume the standard “prefix-reuse” plus “suffix-eviction” design adopted by vLLM and OpenAI. See Figure 1 (a) for illustration of our cache eviction policy. We used the umbrella term prompt caching in the submission, which may have obscured the point. In the revised paper, we will use “prefix caching” explicitly.\n\n\n## Combination with other serving optimization.\nWe really appreciate this suggestion. Optimization techniques such as mixed batching, chunked-prefill and other different parallelism strategies are orthogonal to the cache eviction, so we can integrate them with our policy T-LRU.\nWe tested these features using ​​Sarathi (budget size is 4096 tokens and a batch forms when probability 0.1), and set the Tail-excess latency ξ threshold as 200 ms. The table below reports the relative TTFT latency improvement of T-LRU with other optimization enabled over LRU. Positive numbers mean the improvement (decreased latency); negative numbers mean increased latency.\n\n\n### Table 5: TTFT Latency Improvement with Batching and Chunked-Prefill (%)\n| Capacity | **p90** |         | **p95** |         | **p99** |        |\n| ------------------ | ------- | ------- | ------- | ------- | ------- | ------ |\n|                    | LRU | Thre-LRU    | LRU | Thre-LRU    | LRU | Thre-LRU   |\n| 1 000              | 2.73 %  | 2.73 %  | 0.30 %  | 0.36 %  | 0.00 %  | 0.00 % |\n| 2 000              | 6.61 %  | 6.58 %  | 1.81 %  | 2.69 %  | 0.03 %  | 0.03 % |\n| 4 000              | 13.50 % | 12.52 % | 8.95 %  | 9.82 %  | 6.43 %  | 6.43 % |\n| 6 000              | 18.30 % | 15.34 % | 12.66 % | 12.50 % | 6.43 %  | 6.43 % |\n| 8 000              | 13.24 % | 11.92 % | 14.60 % | 15.17 % | 6.25 %  | 6.23 % |\n| 10 000             | 9.55 %  | 8.53 %  | 15.45 % | 12.38 % | 9.40 %  | 8.65 % |\n\n\nWith batching and chunked-preffil enabled, T-LRU consistently outperforms LRU and Thre-LRU, though the margin narrows compared with no-scheduler baseline (as reported in Table 1 and Table 2 in our submitted paper). These results confirm that our tail-optimized prompt caching policy remains beneficial and is fully compatible when advanced serving optimizations are enabled.\n\n\n## Typo “mixed bathing”.\nFixed, thank you for spotting it!"}, {"review_id": "FCNLc8L86e", "reviewer": "Reviewer_A6ow", "summary": "Summary: The paper introduces Tail-Optimized LRU, a caching strategy designed to minimize tail latency in large language model (LLM) inference. By reallocating KV cache capacity to prioritize high-latency conversations and evicting less impactful cache entries, the authors aim to address the limitations of traditional LRU policies, which are not optimized for heterogeneity in conversation lengths. The approach is theoretically grounded with proofs of optimality under certain conditions and empirically validated through experiments on real-world datasets. Significant reductions in P90 and P95 tail latencies, as well as SLO violations, are reported compared to standard LRU and Threshold-LRU policies.", "questions": "1. The estimated Q is static during the inference, but in engineering application, it may be fluctuating at different times. If we calculate the average length of the last N given questions and make Q dynamic, will the tail latency become smaller or not?\n2. Could Tail-Optimized LRU lead to a decrease in overall cache hit rate? Might it also reduce the system's overall throughput? It would be valuable to evaluate such potential negative impacts of Tail-Optimized LRU in the experiments, in order to better understand its trade-offs.", "limitations": "Not available", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1) The authors provide rigorous theoretical analysis and prove the optimality of their proposed policy under a natural stochastic model, adding depth to the understanding of caching strategies in LLM inference.\n2) The simplicity of the implementation, requiring only minor modifications to existing LRU systems, makes it an attractive option for practitioners looking to optimize their LLM deployments without extensive changes to infrastructure.\n﻿\nWeaknesses:\n\n\n1) Performance and Trade-off Concerns\n- Inference speed impact: T-LRU's cache removal strategy might negatively affect overall inference speed and system throughput\n- Cache hit rate reduction: optimizing for tail latency could decrease the overall cache hit rate\n- Lack of comprehensive evaluation: Missing experiments on full inference latency and potential negative impacts\n﻿\n2) Modeling Assumptions and Limitations\n- Poisson distribution assumption: The assumption that conversations die according to a Poisson distribution may not hold across different user habits and conversation types, limiting real-world applicability\n- Static Q parameter: The next-turn length estimate Q remains fixed during inference, while in practice it likely fluctuates over time. Dynamic adjustment based on recent conversation history might improve performance\n- Oversimplified TTFT proxy: Using the number of uncached blocks to approximate Time to First Token overlooks other real-world factors affecting latency\n﻿\n3) Innovation and Scope\n- Limited innovation: merely adding priority handling for tail excess without fundamentally addressing the root causes of tail latency\n- Fairness concerns: The method doesn't address fairness across users, potentially creating inequities in service quality\n- Practical implementation challenges: The accurate estimation of Q in real-world deployments is difficult", "was_revised": true, "final_justification": "While I appreciate the work's rigor and practical merits, my revised perspective still leans negative for NeurIPS. This research appears more aligned with AI systems and architecture focus—its core contributions lie in LLM inference optimization, caching strategies, and system-level performance tuning, which are more central to specialized venues in AI infrastructure.\n \nNeurIPS, despite including systems research, tends to prioritize ML theory, algorithmic innovations, or foundational model breakthroughs. The audience here likely has limited focus on the architectural details and engineering optimizations that form the heart of this work.\n \nFor broader impact and more targeted feedback, this paper would be better suited for conferences or journals specializing in AI systems (e.g., MLSys, ASPLOS) or architecture, where the community’s expertise and interest in such system-level optimizations are far more pronounced.", "rebuttal": "We thank the reviewer for thoughtful feedback and constructive suggestions. We are grateful that the reviewer appreciated our rigorous theoretical analysis, and that our policy is simple to implement in practice. Below we address the concerns raised.\n\n## Inference speed impact.\nPrior works have shown the decode phase is the primary bottleneck in inference serving (“LLM Inference Performance Engineering – Best Practices”, Databricks 2024; “Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve”). For example, “Mind the Memory Gap: Unveiling GPU Bottlenecks in Large-Batch LLM Inference” shows that prefill time remains below **5%** in total execution time each at large batch sizes 256. T-LRU policy only touches KV cache blocks and does not sit on the critical path of attention mechanism or matrix multiplication. We are working to implement our policy on vLLM and will report the results on inference speed in the revised paper.\n\n\n## Cache hit rate impact.\nA binary cache hit/miss metric is not informative when objects vary in sizes and can be cached partially. One can achieve 100% cache hit rate if we save one cache block for each conversation (assuming capacity allows), yet the TTFT will still be large. Our objective is thus the number of uncached blocks, effectively a size-weighted cache hit metric, and has a more direct and monotonic relationship with TTFT latency (see Figure 3 in the appendix submission).\n\n\n## Scope of evaluation.\nOur paper focuses on the tail latency of time to first token, and we consider decode latency or end-to-end latency as orthogonal optimization. With chunked prefill, decode and prefills are interleaved in one batch, improving the tail TTFT can also positively impact the tail end-to-end latency. In prefill/decoding-disaggregated engines, TTFT and decode latency are independent, so a tail TTFT improvement strictly lowers overall tail latency. We agree that a comprehensive evaluation of our policy is valuable, and we provide some preliminary experiment analyses here (Table 1-5 in this rebuttal).\n\n\n## Poisson distribution assumption.\nOur policy does not rely on the poisson distribution assumption and is guided by a general monotonicity intuition: higher latency requests deserve more cache. Our empirical results on WildChat dataset were done using real timestamps. Only theoretical optimality in Section 4 requires the Poisson assumption for analytic tractability, a common approach in the caching and queueing literature. In real conversational data, we do observe that the probability of conversation continuing decreases as the time to last request increases, i.e., monotone-decreasing hazard, which is what our model tries to capture.\n\n\n## Static Q parameter.\nWe agree that dynamic Q estimation may yield better performance and our framework gives user the flexibility to choose a rolling average or a learned predictor. The table below report the relative TTFT improvement of T-LRU with a dynamic Q over T-LRU with a static Q. Positive numbers mean the dynamic version lowers latency; negative numbers mean it increases latency. Sample size is the number of most recent requests used to compute the dynamic average user prompt length.\n\n\n### Table 6: T-LRU (dynamic Q) vs T-LRU (static Q) TTFT Improvement (%), Sample Size = 30\n| Capacity | **P90** |       | **P95** |       | **P99** |       |\n| --------- | ------- | ----- | ------- | ----- | ------- | ----- |\n|           | ξ=100ms    | ξ=150ms  | ξ=100ms    | ξ=150ms  | ξ=100ms    | ξ=150ms  |\n| 1000      | 0.59    | 0.49  | 0.00    | 0.22  | 0.00    | 0.00  |\n| 2000      | 0.00    | 0.29  | 0.71    | 0.01  | 0.00    | 0.00  |\n| 4000      | 1.05    | 0.23  | 0.00    | 0.58  | –0.70   | –2.75 |\n| 6000      | 0.89    | 0.15  | 0.98    | 0.29  | –2.75   | –4.85 |\n| 8000      | 1.27    | 0.34  | 1.11    | 0.00  | –4.94   | –3.37 |\n| 10 000    | 1.35    | –3.09 | 0.06    | –0.72 | –6.03   | –3.23 |\n\n\n### Table 7: T-LRU (dynamic Q) vs T-LRU (static Q) TTFT Improvement (%), Sample Size = 50\n| Capacity | **P90** |       | **P95** |       | **P99** |       |\n| --------- | ------- | ----- | ------- | ----- | ------- | ----- |\n|           | ξ=100ms    | ξ=150ms  | ξ=100ms    | ξ=150ms  | ξ=100ms    | ξ=150ms  |\n| 1000      | 0.59    | 0.49  | 0.00    | 0.22  | 0.00    | 0.00  |\n| 2000      | 0.00    | 0.00  | 0.71    | 0.01  | 0.00    | 0.00  |\n| 4000      | 0.81    | 0.03  | 0.00    | 0.58  | –0.70   | –2.75 |\n| 6000      | 0.94    | 0.11  | 0.98    | 0.29  | –2.75   | –4.85 |\n| 8000      | 1.39    | 1.03  | 1.56    | 0.00  | –6.24   | –3.37 |\n| 10 000    | 1.35    | –3.17 | 0.06    | –0.72 | –6.03   | –3.23 |\n\n\nFrom the experiments, we find small to moderate gains at P90/P95 but inconsistent effect at p99, and that window size matters modestly for WildChat data.\nIn practice, one can tune sample size to match the time scale of change in prompt lengths. A data-driven rule of thumb is to pick the sample size whose mean-squared prediction error for Q is lowest on recent history. We think dynamic Q is a very interesting future direction, and will add ths discussion in the revised paper.\n \n## TTFT proxy.\nWe choose the number of uncached blocks as a proxy for two reasons.\n1. Empirically such a linear approximation holds well when the uncached length is not excessively long and the prefill of the request is not batched (see Figure 3 in the appendix submission). Thus the proxy captures the dominant driver of TTFT while allowing us to do closed-form analyses. We want to emphasize that we report the actual TTFT in the experiments, and the proxy is used only in the theory.\n2. Focusing on the number of uncached blocks decouples the cache policy from other serving optimization. The number of uncached blocks signals how much work must be done, and the monotonic relationship between it and TTFT remains generally applicable regardless of what optimization stack is deployed. This allows the insights from our paper to remain valid.\n\n\n## Limited innovation.\nWe think the root causes of tail latency arises from heterogenous request sizes, contention for limited KV cache capacity, and stochasticity in arrivals and departures that cause queueing. One can certainly mitigate tail latency by either increasing capacity or decreasing demand, but does not eliminate the root causes.\n\n\nT-LRU is request size-aware and explicitly aligns KV cache capacity with a tail-latency objective.\nTo the best of our knowledge, we are the first paper that looks at optimizing tail latency via prompt caching (Sarathi-Serve used chunked-prefills and stall-free scheduling), and we also show the optimality of our policy in a novel stochastic multi-turn conversation model. *Simplicity of our policy is a feature* so that it can be dropped into existing systems that already default to LRU, and complements orthogonal techniques such as batching.\n\n\n## Fairness concerns.\nOur policy tries to equalize per-request latency by giving more cache memory to requests with potentially high TTFT latency, agnostic to which user this request is coming from. Therefore we promote fairness at the request level, which could also benefit user-level fairness (e.g., proportional or max-min fairness across tenants), and we leave this as an interesting future direction.\n\n\n## Estimating Q in practice.\nIn our paper, Q denotes the average user-prompt length, which is readily measurable from logs (e.g., Q is 295.58 across all conversations in WildChat dataset, and is 94.46 for ShareGPT). We also use the average length of a user prompt in our experiment."}, {"review_id": "x7NpKeekxW", "reviewer": "Reviewer_kqbN", "summary": "Prompt caching is an important issue for LLM service. Its effectiveness can reduce latency and improve user experience, and on the other hand can reduce costs for the service providers. The paper introduced a new metric, tail latency, to evaluate the quality of LLM service. To optimize the tail latency, a novel stochastic model for multi-turn conversations is introduced, characterizing the certainties and temporal locality of LLM workload, and a novel policy, Tail-Optimized LRU, is proposed to optimize the objective. Moreover, new policy’s dominance over LRU is also soundly proven. Several other theoretical results are also given. The experiments shows competitive and significant performance of the new policy over existing LRU on tail latency.", "questions": "Q1: You mention that your new metric, tail latency, is an important issue for LLM inference QoS. Do you have any reference or data to support its importance? You shall clarify the assertion, since it’s a brand-new metric to the community.\n\nQ2: How well does your stochastic model models the real-world characteristic? Do you have any reference or data to verify it?\n\nQ3: How many A100 do you used? Can your hardware settings simulate real-world clusters for LLM serving well? For example, inter-machine communication settings, network settings etc.\n\nQ4: How do you recover the evicted KV cache blocks? Are they stored in CPU memory, disk, or simply discarded? Recovering by loading from disk or recomputation can be a lot different.\n\nQ5: Your algorithm performs worse than LRU on 50% percentile. Will that be a problem? As the median quality seems to be worsened.\n\nQ6: ShareGPT results can be presented to the main text. I suspect you remove it to the appendix due to the page limit.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The major strengths of the paper are its topic significance and novelty of its stochastic modeling and policy.\n2. The topic of prompt KV caching is a significant issue for LLM serving systems. It’s strongly correlated to service quality and cost.\n3. This work is the first one in the community to model and analyze prompt caching to such extent, while proposing policy tailored for LLM service different from traditional OS caching/paging.\n\nWeakness:\n1. The importance of tail latency over median latency and hit rate is not clarified. Besides, the hardware settings require more specifications too.\n2. As tail latency is a new metric to the community, adequate references and data shall be given to support the metric, which is absence from the paper.\n3. The author only mentions its experiments run on A100, not mentioning GPU number, inter-machine communication settings, network settings and other settings that are crucial for reproduction and real-world usage.", "was_revised": true, "final_justification": "The concern about the latency metric and some evaluation results are clarified. I will maintain my score.", "rebuttal": "We thank the reviewer for thoughtful feedback and constructive suggestions. We are grateful that the reviewer appreciated the importance of the problem we try to tackle and the novelty of  our approach. Below we address the concerns raised.\n\n## Importance of tail latency.\nTail latency has been important for large-scale services: it is critical for a data center operator’s revenue, see “Understanding and Leveraging the Impact of Response Latency on User Behaviour in Web Search” (Xiao et al., TOIS 2017). “The Tail at Scale” (Dean & Barroso, 2013) shows that a tiny fraction of slow requests dominates user-perceived experience. These findings naturally transfer to interactive LLM applications, and modern LLM stacks have already internalized the need for optimizing tail latency: “Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve” targets p99 tail latency, and “DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving” focuses on both p90 TTFT latency and time-per-output-token latency. We will add the above references in the introduction to underline the importance of tail latency.\n\n\n## Fidelity of the stochastic conversation model.\nTo the best of our knowledge, WildChat is the only publicly available dataset that includes real timestamps. Our analysis of this dataset shows\n* new-conversation arrivals are close to Poisson process;\n* the probability of a conversation continuing decreases as the time to last turn increases;\n* inter-turn arrivals exhibit three regimes: uniform interval (B = -1), Poisson (B = 0), and bursty (B = 1), with Poisson regime dominating. Here B is the burstiness index computed as $(\\sigma - \\mu)/(\\sigma + \\mu)$, where $\\sigma$ denotes standard deviation of inter-arrival times and $\\mu$ denotes mean of inter-arrival times.\n\n\nWe will add these empirical results in the revised paper.\nOur formulation is the first stochastic model to capture both uncertainty and temporal locality in LLM workloads, which we believe will interest the broader modeling community.\n\n\nCrucially, the policy design itself does not rely on the stochastic conversation model, and is guided by a general monotonicity intuition: higher latency requests deserve more cache.\n\n\n## Hardware settings.\nWe used one A100 GPU on a Colab environment to simulate a typical single-node deployment. We agree that full-cluster results with inter-node communications would be valuable and plan to explore this in future work.\n\n\n## Evicted KV cache blocks.\nWe discarded evicted KV cache blocks. In Section 7 in the submitted paper, we pointed out that our focus is on a single storage layer, and exploring 314 hierarchical KV caching architectures such as in “Trading more storage for less computation—a kvcache-centric architecture for serving llm chatbot” (Qin et al., 2025) could provide insights into better managing multi-layer resources.\n\n\n## Worse medium latency.\nT-LRU deliberately trades off slightly higher median latency (a few milliseconds) to achieve larger tail latency reductions (tens to hundreds of milliseconds), which is a more favorable tradeoff for user experience.\nIn our experiments, T-LRU does slightly increase p50 latency, which is expected as we are trading-off worst-case experience (p95/p99) with the mean. However, the medium latency degradation (+10 milliseconds) is minimal and users will likely not notice: for context, the duration of a blink is on average 100–400 milliseconds according to the Harvard Database of Useful Biological Numbers (BNID 100706). However, reducing p99 latency from 500 ms to 400 ms improves the user-experienced responsiveness.\n\n\n## ShareGPT results.\nWe put the results on ShareGPT in the appendix due to 1) page limit and that 2) ShareGPT lacks arrival timestamps data, so we simulated the arrivals requests using our stochastic multi-turn conversation model, making it supportive rather than primary evidence."}]

Author rebuttal:

Meta-review: This paper proposes Tail-Optimized LRU (T-LRU), a novel caching policy for LLM inference, specifically designed to reduce tail latency. Prompt caching is crucial for reducing latency and cost in LLM inference, but existing policies like Least Recently Used (LRU) can perform poorly on tail latency due to the conversation length heterogeneity. The paper presents a theoretically sound and empirically effective solution to an important problem in LLM inference. The proposed Tail-Optimized LRU policy is a simple modification to existing LRU systems that significantly improves tail latency and SLO compliance. The introduction of Tail Excess Latency as a novel metric and the proof of optimality under a new stochastic conversation model demonstrate meaningful theoretical contributions, which are valuable for the NeurIPS community.

While some reviewers initially raised concerns about the clarity of technical discussions, experimental scope, and modeling assumptions, the authors provided thorough rebuttals. They clarified existing figures, provided extensive new experimental data, detailed dataset statistics, and explained their modeling choices and the practical implications of parameters like Q. The discussion of the median-vs-tail latency trade-off was also well-articulated and justified from a user experience perspective.

The concern about the paper's fit for NeurIPS, while acknowledged, is mitigated by the depth of theoretical analysis and the generalizable insights into caching policy design for modern interactive AI systems. The work bridges theoretical foundations with practical system optimization, making it an interesting contribution. The overall positive sentiment from the majority of reviewers, combined with the satisfactory author responses, leads to a recommendation of Accept.
Decision: Accept (poster)