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.

Importance of tail latency.

Tail 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.

Fidelity of the stochastic conversation model.

To the best of our knowledge, WildChat is the only publicly available dataset that includes real timestamps. Our analysis of this dataset shows

• new-conversation arrivals are close to Poisson process;
• the probability of a conversation continuing decreases as the time to last turn increases;
• 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.

We will add these empirical results in the revised paper. Our 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.

Crucially, 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.

Hardware settings.

We 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.

Evicted KV cache blocks.

We 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.

Worse medium latency.

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 a more favorable tradeoff for user experience. In 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.

ShareGPT results.

We 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.

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.

Inference speed impact.

Prior 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.

Cache hit rate impact.

A 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).

Scope of evaluation.

Our 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).

Poisson distribution assumption.

Our 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.

Static Q parameter.

We 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.

Table 6: T-LRU (dynamic Q) vs T-LRU (static Q) TTFT Improvement (%), Sample Size = 30

Table 7: T-LRU (dynamic Q) vs T-LRU (static Q) TTFT Improvement (%), Sample Size = 50

From 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. In 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.

TTFT proxy.

We choose the number of uncached blocks as a proxy for two reasons.

1. 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.
2. 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.

Limited innovation.

We 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.

T-LRU is request size-aware and explicitly aligns KV cache capacity with a tail-latency objective. To 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.

Fairness concerns.

Our 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.

Estimating Q in practice.

In 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.

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.

NeurIPS, 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.

For 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.

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.

Clarification on prefix caching.

We 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.

Combination with other serving optimization.

We 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. We 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.

Table 5: TTFT Latency Improvement with Batching and Chunked-Prefill (%)

With 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.

Typo “mixed bathing”.

Fixed, thank you for spotting it!

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.

Lack of illustrative figures.

Thanks 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.

Trade-off with non-tail latency.

Below 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.

Table 1: Mean TTFT Latency (seconds)

Table 2: Max TTFT Latency (seconds)

Table 3: T-LRU vs LRU - TTFT Latency Improvement (%)

Table 4: T-LRU vs Thre-LRU - TTFT Latency Improvement (%)

Here 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.

We 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.

Dataset statistics.

We provided distributions of turns and tokens of ShareGPT and WildChat datasets in the appendix (Figure 4). Below we list the statistics:

• Average number of turns in a conversation: 3.51 (ShareGPT) and 2.54 (WildChat)
• Average number of user tokens: 94.46±626.39 (ShareGPT) and 295.58±1609.18 (WildChat)
• Average number of Chatbot tokens: 348.45±269.93 (ShareGPT) and 441.34±410.91 (WildChat)
• Number of languages: 41(ShareGPT) and 68 (WildChat)

Here 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.

Discussion on limitations.

Thanks for the suggestions. We will add the following discussions in the revised paper, which are also raised by other reviewers.

• 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.
• 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”.

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.

Related work.

All titles are given in full because links are not allowed in the rebuttal.

• 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.

• Caching work with variable-size objects: prompt 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. Content 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). In 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:

  • 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);
  • 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);
  • 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);
  • bit model (cost(p) = size(p)): “Page replacement with multi-size pages and applications to web caching” (Irani 1996);
  • general model: “Page Replacement for General Caching Problems” (Albers et al., 1999); “Randomized competitive algorithms for generalized caching” (Bansal et al., 2008).

  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.

• 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.

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 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.

Algorithm 1 loop condition.

Thanks for pointing this out. We have edited this to avoid infinite looping.

Improve technical discussion.

We appreciate the suggestions. We will add the following high-level intuitions before diving into the model and proofs:

To model multi-turn conversations, we need to specify:

1. when does a new conversation start?
2. when will a conversation speak again?
3. how many tokens does the prompt/response have?
4. when will a conversation end?

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. 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.