HotPrefix: Hotness-Aware KV Cache Scheduling for Efficient Prefix Sharing in LLM Inference Systems

Transferring KV caches from GPU memory to host memory results in substantial transmission overhead.

“First, transferring KV caches from GPU memory to host memory results in substantial transmission overhead [48].”

• cites [48] 48. Shamane Siriwardhana, Rivindu Weerasekera, Elliott Wen, Tharindu Kaluarachchi, Rajib Rana, and Suranga Nanayakkara. 2023. Improving the domain adaptation of retrieval augmented generation (RAG) models for open domain question answering. Transactions of the Association for Computational Linguistics (TACL) 11 (2023), 1-17. sourceCould not verify

  Section 3.3 discusses the GPU time needed to re-encode passages and the CPU time needed to re-index them; Section 5.2 likewise discusses those computational costs. Searches for KV caches, GPU-to-host transfers, and communication overhead found no passage addressing the claimed transmission overhead. (LLM, conf=0.76)

  Experimental — accuracy not yet measured

Traditional external memory storage strategies for prefix KV caches often suffer high I/O overhead and frequent cache misses.

“This limitation necessitates the use of external memory storage strategies, which often suffer from high I/O overhead and frequent cache misses with traditional approaches.”

• cites [24] 24. Chao Jin, Zili Zhang, Xuanlin Jiang, Fangyue Liu, Xin Liu, Xuanzhe Liu, and Xin Jin. 2024. RAGCache: Efficient Knowledge Caching for Retrieval-Augmented Generation. In arXiv preprint arXiv:2404.12457. sourcePartly supported

  The Introduction (page unavailable in our copy) says limited GPU memory motivates offloading KV caches and that CPU-to-GPU transfers create a PCIe bottleneck, supporting the I/O-overhead portion. It does not establish frequent cache misses or specifically discuss prefix KV caches in this context. (LLM, conf=0.86)

  Experimental — accuracy not yet measured
• cites [26] 26. Theodore Johnson, Dennis Shasha, et al. 1994. 2Q: a low overhead high performance bu er management replacement algorithm. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 439-450. sourcePartly supported

  The Introduction says that fetching KV caches from disk is constrained by low I/O bandwidth and significantly increases time to first token. It describes what happens when no cache is found, but does not say that traditional external-storage approaches suffer frequent cache misses. (LLM, conf=0.85)

  Experimental — accuracy not yet measured
• cites [48] 48. Shamane Siriwardhana, Rivindu Weerasekera, Elliott Wen, Tharindu Kaluarachchi, Rajib Rana, and Suranga Nanayakkara. 2023. Improving the domain adaptation of retrieval augmented generation (RAG) models for open domain question answering. Transactions of the Association for Computational Linguistics (TACL) 11 (2023), 1-17. sourceCould not verify

  Sections 3.2 and 3.3 discuss an external knowledge base and the computational cost of re-encoding and re-indexing it. Searching our copy for prefix KV caches, I/O overhead, and cache misses found no passage addressing those storage strategies or their claimed drawbacks. (LLM, conf=0.75)

  Experimental — accuracy not yet measured

Current prefix sharing methods do not account for the dynamic nature of user requests, where reuse probabilities of prefixes can vary significantly.

“Current methods do not account for the dynamic nature of user requests, where reuse probabilities of prefixes can vary significantly.”

• cites [25] 25. Shuowei Jin, Xueshen Liu, Qingzhao Zhang, and Z Morley Mao. 2024. Compute or load kv cache? why not both?. In arXiv preprint arXiv:2410.03065. sourceCould not verify

  The Introduction discusses reuse of tokens across users and conversations, and §5.7 examines a burst of incoming requests. Neither passage says that prefix-reuse probabilities vary or that current methods fail to account for such variation. Searches for reuse probability, hit rate, and changing request patterns found no passage addressing that point. (LLM, conf=0.74)

  Experimental — accuracy not yet measured

Existing methods often fail to effectively manage GPU memory, resulting in frequent eviction of high-hotness caches in favor of low-hotness ones.

“Existing methods [30,72] often fail to effectively manage GPU memory, resulting in frequent eviction of high-hotness caches in favor of low-hotness ones.”

• cites [30] 30. Wonbeom Lee, Jungi Lee, Junghwan Seo, and Jaewoong Sim. 2024. InfiniGen: Efficient generative inference of large language models with dynamic KV cache management. In proceedings of USENIX Symposium on Operating Systems Design and Implementation (SOSP). 155-172. sourcePartly supported

  The Introduction (page not provided) says existing LLM-serving systems waste GPU memory through fragmentation and cannot share KV-cache memory effectively. Section 4.5 discusses evicting KV-cache blocks when GPU memory runs out, but does not say existing methods frequently evict high-hotness caches in favor of low-hotness ones. (LLM, conf=0.87)

  Experimental — accuracy not yet measured
• cites [72] sourcePartly supported

  The Introduction describes inefficient memory use and missed KV-cache reuse in existing systems. Section 3 says GPU memory fills quickly and describes eviction policies, but it does not say existing methods frequently evict high-hotness caches in favor of low-hotness ones. (LLM, conf=0.83)

  Experimental — accuracy not yet measured

Many prompts in LLM inference share common prefixes.

“Since many prompts share common prefixes, prefix sharing has been proposed to reuse shared prefix KV caches during inference.”

• Also stated in: § 1 Introduction · plain

  “A key issue is the redundant storage of shared prefixes, such as system instructions [28,39], reusable templates [57,63], or RAG retrieved documents [9].”

• cites [30] 30. Wonbeom Lee, Jungi Lee, Junghwan Seo, and Jaewoong Sim. 2024. InfiniGen: Efficient generative inference of large language models with dynamic KV cache management. In proceedings of USENIX Symposium on Operating Systems Design and Implementation (SOSP). 155-172. sourceSupported
• cites [66] 66. Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. 2019. Hellaswag: Can a machine really finish your sentence?. In arXiv preprint arXiv:1905.07830. sourceSupported
• cites [72] sourceSupported

Limited GPU memory capacity poses a significant challenge for caching large-scale prefixes.

“Insufficient GPU Memory: While GPUs excel in computation, their limited memory capacity poses a significant challenge for caching large-scale prefixes [13,48].”

• cites [13] 13. Bin Fan, Dave G Andersen, Michael Kaminsky, and Michael D Mitzenmacher. 2014. Cuckoo filter: Practically better than bloom. In Proceedings of the ACM International on Conference on emerging Networking Experiments and Technologies (CoNEXT). 75-88. sourceNot checked — no full text of the source
• cites [48] 48. Shamane Siriwardhana, Rivindu Weerasekera, Elliott Wen, Tharindu Kaluarachchi, Rajib Rana, and Suranga Nanayakkara. 2023. Improving the domain adaptation of retrieval augmented generation (RAG) models for open domain question answering. Transactions of the Association for Computational Linguistics (TACL) 11 (2023), 1-17. sourceCould not verify

  Section 3.3 discusses GPU time for re-encoding a large knowledge base, and Section 5.2 discusses the computational cost of that work. Neither passage addresses GPU memory limits or caching large-scale prefixes; searches for those terms found no supporting passage in our copy. Page numbers were not available. (LLM, conf=0.76)

  Experimental — accuracy not yet measured

The cuckoo filter is a compact data structure capable of storing information for tens of thousands of nodes while requiring only a few kilobytes of memory.

“First, the cuckoo filter is a compact data structure capable of storing information for tens of thousands of nodes while requiring only a few kilobytes of memory [14].”

• cites [14] 14. Yuan Feng, Hyeran Jeon, Filip Blagojevic, Cyril Guyot, Qing Li, and Dong Li. 2023. AttMEMO: Accelerating Transformers with Memoization on Big Memory Systems. In arXiv preprint arXiv:2301.09262. sourceCould not verify

  Our copy’s §5.3 describes a Faiss/HNSW index and reports search time for 100K vectors, but it does not discuss cuckoo filters or their memory requirements. Searches for “cuckoo filter” and for the claimed capacity and memory size found no supporting passage. (LLM, conf=0.76)

  Experimental — accuracy not yet measured

In long-context applications such as legal analysis, healthcare, and education, documents from a common pool are often reused across prompts.

“Additionally, in long-context applications such as legal analysis [10], healthcare [50], and education [47], documents from a common pool are often reused across prompts.”

• cites [10] 10. Shichen Dong, Wen Cheng, Jiayu Qin, and Wei Wang. 2024. QAQ: Quality Adaptive Quantization for LLM KV Cache. In arXiv preprint arXiv:2403.04643. sourceCould not verify

  The Introduction and §2.1 discuss reusing cached key–value computations while generating tokens within a sequence. They do not address whether documents from a common pool are reused across prompts in legal analysis, healthcare, or education; searches for shared documents and cross-prompt reuse found no supporting passage. Page numbers were not available in our copy. (LLM, conf=0.74)

  Experimental — accuracy not yet measured
• cites [50] 50. Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann, Yi Tay, Hyung Won Chung, Aakanksha Chowdhery, Quoc V Le, Ed H Chi, Denny Zhou, , and Jason Wei. 2022. Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them. In arXiv preprint arXiv:2210.09261. sourceCould not verify

  The Experimental Setup (p. 4) describes few-shot examples used in benchmark prompts, not documents reused across prompts in educational applications. Searches for education and shared long-context documents found no passage in our copy addressing that claim. (LLM, conf=0.77)

  Experimental — accuracy not yet measured
• cites [47] 47. Ying Sheng, Lianmin Zheng, Binhang Yuan, Zhuohan Li, Max Ryabinin, Beidi Chen, Percy Liang, Christopher Ré, Ion Stoica, and Ce Zhang. 2023. Flexgen: High-throughput generative inference of large language models with a single gpu. In Proceedings of International Conference on Machine Learning (ICML). 31094-31116. sourceCould not verify

  The Introduction (p. 1) discusses mathematics-education tasks, and Table 3 (p. 4) lists sources used for MathBERT’s training corpus. Neither those passages nor searches for document reuse across prompts address whether educational applications repeatedly draw documents from a common pool. (LLM, conf=0.76)

  Experimental — accuracy not yet measured

GPT-3 requires approximately 4.5 MB of KV cache per token.

“For example, GPT-3 requires approximately 4.5 MB of KV cache per token [17].”

• Also stated in: § Decoding Stage: · plain

  “GPT-3 generates a KV cache of approximately 4.5MB per token [17]”

• cites [17] 17. Suyu Ge, Yunan Zhang, Liyuan Liu, Minjia Zhang, Jiawei Han, and Jianfeng Gao. 2023. Model tells you what to discard: Adaptive kv cache compression for llms. In arXiv preprint arXiv:2310.01801. sourceCould not verify

  The Introduction and Section 3.1 explain that KV-cache memory grows as tokens are generated, but neither gives a per-token figure for GPT-3. Searches for “GPT-3 requires approximately 4.5 MB” and “4.5 MB GPT-3 cache token” found no passage supporting the claimed amount. Page numbers were not available in the indexed copy. (LLM, conf=0.74)

  Experimental — accuracy not yet measured

A significant portion of input prefixes in LLM inference are reusable.

“Opportunities for Reusing KV Caches: A significant portion of input prefixes in LLM inference are reusable [66], presenting an opportunity to reduce redundant computation through KV cache reuse.”

• cites [66] 66. Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. 2019. Hellaswag: Can a machine really finish your sentence?. In arXiv preprint arXiv:1905.07830. sourceSupported

SGLang uses a simple LRU eviction strategy that struggles to adapt to dynamic user requests.

“Additionally, SGLang employs a simple LRU eviction strategy, which struggles to adapt to dynamic user requests.”

• cites [72] sourcePartly supported

  Section 3 says SGLang uses a simple LRU eviction policy, supporting the first part of the claim. It does not say that this policy struggles with dynamic user requests; instead, the section describes the radix tree’s response to varied incoming requests and says cache-aware scheduling improves cache reuse. (LLM, conf=0.90)

  Experimental — accuracy not yet measured

SGLang's exclusive reliance on GPU memory restricts its scalability.

“However, its reliance solely on GPU memory limits scalability.”

• cites [72] sourcePartly supported

  Section 3 says GPU memory fills quickly with the KV cache, requiring LRU eviction, and Section 8 proposes extending RadixAttention across DRAM and disk. This supports a GPU-memory constraint on the current cache design, but the paper does not say that SGLang relies solely on GPU memory or explicitly conclude that this limits its overall scalability. (LLM, conf=0.82)

  Experimental — accuracy not yet measured

Operating system caching systems such as Linux page cache and ZFS ARC are built for uniform cache-line sizes and cannot handle the varying computational costs of different-length KV cache misses in LLMs.

“Operating system caching systems, like Linux page cache [38] and ZFS ARC [40], are optimized for uniform cache-line sizes, failing to address the variable computational costs of different-length KV cache misses in LLMs.”

• cites [38] 38. Pan Lu, Baolin Peng, Hao Cheng, Michel Galley, Kai-Wei Chang, Ying Nian Wu, Song-Chun Zhu, and Jianfeng Gao. 2023. Chameleon: Plug-and-play compositional reasoning with large language models. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS). 43447-43478.Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites [40] 40. Yuhong Mo, Hao Qin, Yushan Dong, Ziyi Zhu, and Zhenglin Li. 2024. Large language model (llm) ai text generation detection based on transformer deep learning algorithm. In arXiv preprint arXiv:2405.06652. sourceCould not verify

  The Introduction describes detecting AI-generated text, and the Method describes a transformer-based text classifier. Searches for Linux page cache, ZFS ARC, KV-cache misses, and variable recomputation costs found no passage addressing the caching claim. (LLM, conf=0.76)

  Experimental — accuracy not yet measured

SGLang's original experiments benefited from unshuffled datasets, which let its radix tree maximize prefix reuse.

“Notably, SGLang's original experiments [72] benefited from unshuffled datasets, which allowed its radix tree structure to maximize prefix reuse.”

• cites [72] sourcePartly supported

  Section 6.2 reports prefix-cache reuse across the original benchmarks, and Section 3 explains how RadixAttention uses a radix tree and cache-aware scheduling to improve reuse. But the paper does not say the experimental datasets were unshuffled or that their unshuffled order caused the reported reuse; searches for “unshuffled” and dataset-order terms found no such statement. The indexed passages provide no page numbers. (LLM, conf=0.85)

  Experimental — accuracy not yet measured

Shuffled workloads expose SGLang's limitations in adapting to dynamic and less predictable prefix reuse scenarios.

“However, shuffled workloads, which better represent real-world user access patterns, expose its limitations in adapting to dynamic and less predictable prefix reuse scenarios.”

• cites [72] sourcePartly supported

  Section 3, “Efficient KV Cache Reuse with RadixAttention” (page unavailable), says switching frequently between unrelated requests can cause cache thrashing and a low hit rate, supporting the concern that request order matters. It also describes cache-aware scheduling to mitigate that problem. The paper does not report that shuffled workloads expose a limitation of SGLang itself or establish that they better represent real-world access patterns. (LLM, conf=0.83)

  Experimental — accuracy not yet measured

• AssumptionRests on an assumption: Shuffled workloads better represent real-world user access patterns.

When SGLang runs the MMLU benchmark and simply evicts redundant KV caches from GPU to CPU with Llama-2 13B and batch size 8, total inference latency is 2138 seconds and offload time is 1200 seconds.

“For example, when SGLang runs MMLU benchmark and simply evicts redundant KV caches from GPU to CPU with Llama-2 13B model and batch size 8, the total inference latency is 2138 seconds and the offload time is 1200 seconds in our experiments, which is prohibitively expensive and makes this approach impractical for production deployment.”

HotPrefix improves inference latency by 1.02 to 1.34 times over 2Q.

“HotPrefix achieves the lowest inference latency, with a 1.11-1.37×,1.07-1.89×,1.13-1.63×,and 1.02-1.34×improvement over LRU, LFU, FIFO, and 2Q respectively.”

HotPrefix introduces offload time overhead of 24.8s on BBH dataset.

“Table 1 shows that the HotPrefix method introduces offload time overheads of 25.66s, 24.8s, 68.28s, and 27.03s on the MMLU, BBH, CEVA, and Hellaswag datasets respectively.”

HotPrefix improves GPU cache hit ratio by 1.17-2.38× over SGLang-LRU.

“HotPrefix achieves highest hit ratio across different tasks, with a 1.17-2.38×improvement over SGLang-LRU, 1.16-2.28×improvement over SGLang-LFU, 1.19-2.56×improvement over SGLang-FIFO, 1.17-2.51×improvement over SGLang-2Q and 1.11-3.27×improvement over vLLM.”

On an A6000 with LLaMA-3 8B, HotPrefix improves inference latency by 1.30 to 1.68 times over other methods.

“Compared with other methods, Hotprefix achieves 1.06-1.53×,1.08-1.24×,1.10-1.28×and 1.18-1.40×cache hit ratio improvement and 1.17-1.60×,1.16-2.25×,1.30-1.68×and 1.58-2.27×inference latency performance improvement on RTX 3090, A30, A6000 and A100 respectively.”

The combined E+A+P configuration improves cache hit ratio by 1.08 times over A+P.

“First, the combined”

With selective admission enabled, HotPrefix's cache hit ratio on Hellaswag is 5% lower than when admission is disabled.

“As shown in Figure 13(a), compared to disabling the admission policy, HotPrefix with the admission policy reduces the cache hit ratio by only 0.2% on MMLU and 10% on CEVAL and 5% on Hellaswag, but reduces 10-65× offload time.”

Hotness Promotion has the lowest GPU-CPU offload time.

“And the offload time between GPU and CPU of Hotness Promotion is also the lowest.”

HotPrefix improves inference latency by 1.07 to 1.89 times over LFU.

“HotPrefix achieves the lowest inference latency, with a 1.11-1.37×,1.07-1.89×,1.13-1.63×,and 1.02-1.34×improvement over LRU, LFU, FIFO, and 2Q respectively.”

HotPrefix achieves the highest GPU cache hit ratio across the MMLU, Hellaswag, BBH, and CEVAL workloads compared to SGLang variants and vLLM.

“HotPrefix achieves highest hit ratio across different tasks, with a 1.17-2.38×improvement over SGLang-LRU, 1.16-2.28×improvement over SGLang-LFU, 1.19-2.56×improvement over SGLang-FIFO, 1.17-2.51×improvement over SGLang-2Q and 1.11-3.27×improvement over vLLM.”

With selective admission enabled, HotPrefix's cache hit ratio on CEVAL is 10% lower than when admission is disabled.

“As shown in Figure 13(a), compared to disabling the admission policy, HotPrefix with the admission policy reduces the cache hit ratio by only 0.2% on MMLU and 10% on CEVAL and 5% on Hellaswag, but reduces 10-65× offload time.”

HotPrefix improves GPU cache hit ratio by 1.17-2.51× over SGLang-2Q.

“HotPrefix achieves highest hit ratio across different tasks, with a 1.17-2.38×improvement over SGLang-LRU, 1.16-2.28×improvement over SGLang-LFU, 1.19-2.56×improvement over SGLang-FIFO, 1.17-2.51×improvement over SGLang-2Q and 1.11-3.27×improvement over vLLM.”

HotPrefix improves GPU cache hit ratio by 1.19-2.56× over SGLang-FIFO.

“HotPrefix achieves highest hit ratio across different tasks, with a 1.17-2.38×improvement over SGLang-LRU, 1.16-2.28×improvement over SGLang-LFU, 1.19-2.56×improvement over SGLang-FIFO, 1.17-2.51×improvement over SGLang-2Q and 1.11-3.27×improvement over vLLM.”

On an A6000 with LLaMA-3 8B, HotPrefix improves cache hit ratio by 1.10 to 1.28 times over other methods.

“Compared with other methods, Hotprefix achieves 1.06-1.53×,1.08-1.24×,1.10-1.28×and 1.18-1.40×cache hit ratio improvement and 1.17-1.60×,1.16-2.25×,1.30-1.68×and 1.58-2.27×inference latency performance improvement on RTX 3090, A30, A6000 and A100 respectively.”

The highest improvement in latency is observed on the CEVAL dataset.

“The highest improvement is observed on the CEVAL dataset, as it features more diverse workloads and longer request lengths.”

With the LLaMA-2 13B model on A6000s, HotPrefix's overall inference latency falls linearly as the number of GPUs used for data parallelism rises.

“As the number of GPUs used for data parallelism increases, the overall inference latency of HotPrefix decreases linearly, demonstrating its scalability in multi-GPU data parallel.”

Hotness Promotion improves cache hit ratio by 1.13 to 2.57 times over recency promotion.

“As shown in Figure 16(a), Hotness Promotion achieves the highest cache hit ratio, with a 1.13-2.57×,1.01-1.14×,and 1.05-2.09×improvement over recency, frequency, and depth promotion respectively.”

On Gemma 9B model, HotPrefix achieves 1.58-1.91× improvement over vLLM.

“We also run the evaluation on Gemma 9B model, achieving similar inference latency performance and throughput improvement, with 1.45-1.64×over SGLang-LRU and 1.58-1.91×than vLLM.”

Hotness Promotion improves cache hit ratio by 1.05 to 2.09 times over depth promotion.

“As shown in Figure 16(a), Hotness Promotion achieves the highest cache hit ratio, with a 1.13-2.57×,1.01-1.14×,and 1.05-2.09×improvement over recency, frequency, and depth promotion respectively.”

On an RTX 3090 with the LLaMA-3 8B model, HotPrefix improves cache hit ratio by 1.06 to 1.53 times compared with other methods.

“Compared with other methods, Hotprefix achieves 1.06-1.53×,1.08-1.24×,1.10-1.28×and 1.18-1.40×cache hit ratio improvement and 1.17-1.60×,1.16-2.25×,1.30-1.68×and 1.58-2.27×inference latency performance improvement on RTX 3090, A30, A6000 and A100 respectively.”

HotPrefix improves GPU cache hit ratio by 1.16-2.28× over SGLang-LFU.

“HotPrefix achieves highest hit ratio across different tasks, with a 1.17-2.38×improvement over SGLang-LRU, 1.16-2.28×improvement over SGLang-LFU, 1.19-2.56×improvement over SGLang-FIFO, 1.17-2.51×improvement over SGLang-2Q and 1.11-3.27×improvement over vLLM.”

On an A100 with LLaMA-3 8B, HotPrefix improves cache hit ratio by 1.18 to 1.40 times over other methods.

“Compared with other methods, Hotprefix achieves 1.06-1.53×,1.08-1.24×,1.10-1.28×and 1.18-1.40×cache hit ratio improvement and 1.17-1.60×,1.16-2.25×,1.30-1.68×and 1.58-2.27×inference latency performance improvement on RTX 3090, A30, A6000 and A100 respectively.”

On an RTX 3090 with LLaMA-3 8B, HotPrefix improves inference latency by 1.17 to 1.60 times over other methods.

“Compared with other methods, Hotprefix achieves 1.06-1.53×,1.08-1.24×,1.10-1.28×and 1.18-1.40×cache hit ratio improvement and 1.17-1.60×,1.16-2.25×,1.30-1.68×and 1.58-2.27×inference latency performance improvement on RTX 3090, A30, A6000 and A100 respectively.”

Hotness Promotion improves inference latency by 1.09 to 1.88 times over depth promotion.

“Figure 16(b) demonstrates that Hotness Promotion achieves lowest inference latency, with a 1.17-2.22×,1.04-1.30×,and 1.09-1.88×improvement over recency, frequency, and depth promotion respectively.”

On an A30 with LLaMA-3 8B, HotPrefix improves cache hit ratio by 1.08 to 1.24 times over other methods.

“Compared with other methods, Hotprefix achieves 1.06-1.53×,1.08-1.24×,1.10-1.28×and 1.18-1.40×cache hit ratio improvement and 1.17-1.60×,1.16-2.25×,1.30-1.68×and 1.58-2.27×inference latency performance improvement on RTX 3090, A30, A6000 and A100 respectively.”

HotPrefix improves GPU cache hit ratio by 1.11-3.27× over vLLM.

“HotPrefix achieves highest hit ratio across different tasks, with a 1.17-2.38×improvement over SGLang-LRU, 1.16-2.28×improvement over SGLang-LFU, 1.19-2.56×improvement over SGLang-FIFO, 1.17-2.51×improvement over SGLang-2Q and 1.11-3.27×improvement over vLLM.”

Under tensor parallelism across four A6000 GPUs with the Qwen-2 72B model, HotPrefix attains the highest cache hit ratio among the compared systems.

“Under this configuration, HotPrefix also achieves the highest cache hit ratio and improves end-to-end latency that is 1.57-2.42×over SGLang and 1.60-2.61×over vLLM.”

The highest cache hit ratio improvement is observed on the CEVAL dataset.

“The highest improvement is observed on the CEVAL dataset due to its diverse and complex access patterns, which vLLM and SGLang's simple cache management strategies struggle to handle effectively.”

HotPrefix introduces offload time overhead of 27.03s on Hellaswag dataset.

“Table 1 shows that the HotPrefix method introduces offload time overheads of 25.66s, 24.8s, 68.28s, and 27.03s on the MMLU, BBH, CEVA, and Hellaswag datasets respectively.”

HotPrefix improves inference latency by 1.13 to 1.63 times over FIFO.

“HotPrefix achieves the lowest inference latency, with a 1.11-1.37×,1.07-1.89×,1.13-1.63×,and 1.02-1.34×improvement over LRU, LFU, FIFO, and 2Q respectively.”

Hotness Promotion improves inference latency by 1.04 to 1.30 times over frequency promotion.

“Figure 16(b) demonstrates that Hotness Promotion achieves lowest inference latency, with a 1.17-2.22×,1.04-1.30×,and 1.09-1.88×improvement over recency, frequency, and depth promotion respectively.”

On an A30 with LLaMA-3 8B, HotPrefix improves inference latency by 1.16 to 2.25 times over other methods.

“Compared with other methods, Hotprefix achieves 1.06-1.53×,1.08-1.24×,1.10-1.28×and 1.18-1.40×cache hit ratio improvement and 1.17-1.60×,1.16-2.25×,1.30-1.68×and 1.58-2.27×inference latency performance improvement on RTX 3090, A30, A6000 and A100 respectively.”

With selective admission enabled, HotPrefix's cache hit ratio on MMLU is only 0.2% lower than when admission is disabled.

“As shown in Figure 13(a), compared to disabling the admission policy, HotPrefix with the admission policy reduces the cache hit ratio by only 0.2% on MMLU and 10% on CEVAL and 5% on Hellaswag, but reduces 10-65× offload time.”

HotPrefix improves inference latency by 1.11 to 1.37 times over LRU.

“HotPrefix achieves the lowest inference latency, with a 1.11-1.37×,1.07-1.89×,1.13-1.63×,and 1.02-1.34×improvement over LRU, LFU, FIFO, and 2Q respectively.”

HotPrefix with selective admission achieves 1.28 to 3.54 times lower inference latency than without selective admission.

“Finally, HotPrefix achieves lower inference latency than without selective admission, with a 1.28-3.54×improvement.”

In the same four-A6000 Qwen-2 72B tensor-parallel setup, HotPrefix lowers end-to-end latency by a factor of 1.57 to 2.42 relative to SGLang.

“Under this configuration, HotPrefix also achieves the highest cache hit ratio and improves end-to-end latency that is 1.57-2.42×over SGLang and 1.60-2.61×over vLLM.”

Hotness Promotion improves cache hit ratio by 1.01 to 1.14 times over frequency promotion.

“As shown in Figure 16(a), Hotness Promotion achieves the highest cache hit ratio, with a 1.13-2.57×,1.01-1.14×,and 1.05-2.09×improvement over recency, frequency, and depth promotion respectively.”

On an A100 with LLaMA-3 8B, HotPrefix improves inference latency by 1.58 to 2.27 times over other methods.

“Compared with other methods, Hotprefix achieves 1.06-1.53×,1.08-1.24×,1.10-1.28×and 1.18-1.40×cache hit ratio improvement and 1.17-1.60×,1.16-2.25×,1.30-1.68×and 1.58-2.27×inference latency performance improvement on RTX 3090, A30, A6000 and A100 respectively.”

With selective admission enabled, HotPrefix reduces offload time by 10 to 65 times compared with disabling admission.

“As shown in Figure 13(a), compared to disabling the admission policy, HotPrefix with the admission policy reduces the cache hit ratio by only 0.2% on MMLU and 10% on CEVAL and 5% on Hellaswag, but reduces 10-65× offload time.”

HotPrefix introduces offload time overhead of 25.66s on MMLU dataset.

“Table 1 shows that the HotPrefix method introduces offload time overheads of 25.66s, 24.8s, 68.28s, and 27.03s on the MMLU, BBH, CEVA, and Hellaswag datasets respectively.”

In that setup, HotPrefix lowers end-to-end latency by a factor of 1.60 to 2.61 relative to vLLM.

“Under this configuration, HotPrefix also achieves the highest cache hit ratio and improves end-to-end latency that is 1.57-2.42×over SGLang and 1.60-2.61×over vLLM.”

Hotness Promotion improves inference latency by 1.17 to 2.22 times over recency promotion.

“Figure 16(b) demonstrates that Hotness Promotion achieves lowest inference latency, with a 1.17-2.22×,1.04-1.30×,and 1.09-1.88×improvement over recency, frequency, and depth promotion respectively.”

HotPrefix delivers up to a 2 times improvement in throughput compared with SGLang.

“Similarly, compared to SGLang, HotPrefix delivers up to a 2× reduction in latency and improvement in throughput.”

HotPrefix achieves up to a 2.25 times increase in throughput compared with vLLM with prefix sharing enabled.

“Extensive experimental results demonstrate that HotPrefix significantly enhances LLM inference efficiency, achieving up to a 2.25× reduction in inference latency and increase in throughput compared to vLLM with prefix sharing enabled.”

HotPrefix delivers up to a 2 times reduction in latency compared with SGLang.

“Similarly, compared to SGLang, HotPrefix delivers up to a 2× reduction in latency and improvement in throughput.”

HotPrefix achieves up to a 2.25 times reduction in inference latency compared with vLLM with prefix sharing enabled.

“Extensive experimental results demonstrate that HotPrefix significantly enhances LLM inference efficiency, achieving up to a 2.25× reduction in inference latency and increase in throughput compared to vLLM with prefix sharing enabled.”

HotPrefix avoids relying on traditional cache replacement strategies such as LRU, which could lead to higher cache misses and additional I/O for data transfer between host and GPU memory.

“In this case, HotPrefix avoids relying on traditional cache replacement strategies such as LRU, which could lead to higher cache misses and additional I/O for data transfer between host and GPU memory.”

Dynamic Hotness Tracking records and updates the hotness of prefix tree nodes during KV cache reads and writes, providing precise hotness information for cache management decisions in a low-overhead manner.

“This mechanism records and updates the hotness of prefix tree nodes during KV cache reads and writes, providing precise hotness information for cache management decisions in a low-overhead manner ( § 3.2).”

The key insight behind HotPrefix is that storing high-hotness prefix KV caches in GPU memory, because they are more likely to be reused, reduces the need for prefill computations.

“The key insight behind HotPrefix is to utilize the high bandwidth of GPU memory to store high-hotness prefix KV caches, which are more likely to be reused in the future, thus reducing the need for prefill computations.”

With a context length of 1024 and batch size of 16, the KV cache demand exceeds 73 GB.

“With a context length of 1024 and batch size of 16, the KV cache demand exceeds 73 GB.”

Relying on simple GPU-host collaboration can reduce overall efficiency rather than improve it, especially in scenarios that demand high throughput or low latency.

“Consequently, relying on simple GPU-host collaboration can reduce overall efficiency rather than improve it, especially in scenarios that demand high throughput or low latency performance.”

By selectively offloading only high-hotness KV caches to host memory, HotPrefix minimizes the adverse impact of offloading time on inference latency.

“By selectively offloading only high-hotness KV caches to host memory, HotPrefix minimizes the adverse impact of offloading time on inference latency.”

The design achieves overlap between GPU computation and memory transfers due to the absence of prefix sharing during decoding phase.

“This design achieves overlap between GPU computation and memory transfers due to the absence of prefix sharing during decoding phase.”

• AssumptionRests on an assumption: The decoding process typically generates unique content, which is unlikely to reuse prefix KV caches.

HotPrefix adapts to diverse access patterns by dynamically tracking hotness of KV cache entries and selectively retaining or offloading them based on reuse potential.

“In contrast, HotPrefix adapts to these characteristics by dynamically tracking the hotness of KV cache entries and selectively retaining or offloading them based on their reuse potential.”

The latency gain from selective admission comes from blocking the offload of KV caches unlikely to be reused into host memory, which cuts CPU-GPU offload time.

“This improvement stems from its ability to prevent the offloading of KV caches that are unlikely to be reused into host memory, greatly reducing the offload time between CPU and GPU memory.”

By periodically adjusting clock values, HotPrefix effectively differentiates recently accessed nodes from less relevant ones.

“By periodically adjusting the clock values, HotPrefix effectively differentiates recently accessed nodes from less relevant ones.”

The high improvement on CEVAL is because it features more diverse workloads and longer request lengths.

“The highest improvement is observed on the CEVAL dataset, as it features more diverse workloads and longer request lengths.”

vLLM uses a coarse-grained prefix-sharing approach, where prefixes that do not align with predefined block sizes cannot be fully utilized.

“And vLLM uses a coarse-grained prefix-sharing approach, where prefixes that do not align with predefined block sizes cannot be fully utilized.”

HotPrefix achieves a significantly higher prefix KV cache hit ratio on CEVAL due to its superior ability to adapt to dynamic nature of user requests.

“HotPrefix, with its superior ability to adapt to the dynamic nature of user requests, achieves a significantly higher prefix KV cache hit ratio on this dataset.”

During the decode phase, HotPrefix asynchronously reloads high-hotness KV caches from host memory into GPU memory, thereby enhancing prefix cache reuse.

“Additionally, during the decode phase, HotPrefix asynchronously reloads high-hotness KV caches from host memory into GPU memory, thereby enhancing prefix cache reuse.”

The reduction in inference latency and throughput achieved by HotPrefix primarily results from its ability to significantly increase the cache hit ratio for prefix KV caches.

“Specifically, the reduction in inference latency and throughput achieved by HotPrefix primarily results from its ability to significantly increase the cache hit ratio for prefix KV caches.”

Insertion failures in the cuckoo filter are highly unlikely.

“However, such insertion failures are highly unlikely for two reasons.”

• AssumptionRests on an assumption: Host memory provides sufficient space to accommodate all cuckoo filter entries.

HotPrefix attains the highest cache hit ratio through its hotness-aware eviction policy.

“Second, HotPrefix achieves the highest cache hit ratio with the help of Hotness-aware Eviction Policy.”

SGLang employs a simple LRU eviction strategy, which often results in premature eviction of high-hotness KV cache nodes when workloads are shuffled.

“SGLang employs a simple LRU eviction strategy, which often results in the premature eviction of high-hotness KV cache nodes when workloads are shuffled.”

HotPrefix may sometimes reject KV caches that could be reused later, leading to a slightly lower cache hit ratio.

“Although HotPrefix may occasionally reject certain KV caches that could be reused in the future, causing a little lower cache hit ratio, the overall advantages of Selective Admission Policy outweigh the disadvantages.”

Indiscriminate offloading would result in host memory being flooded with low-value KV caches, further increasing the burden of managing these caches.

“Such indiscriminate offloading would also result in host memory being flooded with low-value KV caches, further increasing the burden of managing these caches.”

The discrepancy in cache hit ratio arises from limitations in SGLang and vLLM cache management strategies, which are unable to retain high-hotness KV caches in GPU memory effectively.

“Specifically, the discrepancy arises from the limitations in the cache management strategies of SGLang and vLLM, which are unable to retain high-hotness KV caches in GPU memory effectively.”

The high improvement on CEVAL is due to its diverse and complex access patterns, which vLLM and SGLang's simple cache management strategies struggle to handle effectively.

“The highest improvement is observed on the CEVAL dataset due to its diverse and complex access patterns, which vLLM and SGLang's simple cache management strategies struggle to handle effectively.”

The hotness promotion process does not increase GPU memory usage, as the promotion plan guarantees that the total memory footprint remains constant.

“The hotness promotion process does not increase GPU memory usage, as the promotion plan guarantees that the total memory footprint remains constant.”

HotPrefix addresses these issues by employing a hotness-aware eviction strategy that prioritizes removal of low-hotness KV caches.

“HotPrefix addresses these issues by employing a hotness-aware eviction strategy that prioritizes the removal of low-hotness KV caches.”

• AssumptionRests on an assumption: Ancestor nodes in the prefix tree are inherently hotter than their descendant nodes.