mlsanityData to 14 Oct 2026

Prefix Sharing Is a Sorting Problem

arXiv 2609.13692 ↗First posted 12 Sep 2026cs.DS cs.CLcited by 0

On the map: Efficient LLM inference and serving → KV cache optimization

Abstract (arXiv)

LLM serving reuses KV cache by exact prefix match, so when a prompt is assembled from a set of reusable pieces -- retrieved passages, tool definitions, few-shot exemplars -- the order chosen for those pieces determines how much computation can be shared. Every deployed system fixes that order by a single global convention. We prove this is optimal only when requests contain at most two pieces, and asymptotically wrong in general. Our main result is a structure theorem: the minimum prefix-trie cost equals min_H sum_x w(x) t_x(H) over binary hierarchies H on the requests, where t_x(H) is the canonical decomposition size of the set of requests needing chunk x. Choosing chunk orders is therefore equivalent to choosing one hierarchy over requests. The identity yields an O(3^m) exact algorithm, identifies the two-chunk case as minimum vertex cover, and shows that on the leave-one-out family the optimum is the minimum external path length of a binary tree -- the merge-sort recursion -- so a global order pays Theta(n^2) against a true cost of Theta(n log n). Agglomerative clustering by common intersection is a tight 1/2-approximation for the achievable saving. On BM25 retrieval traces over three BEIR corpora the resulting layout reduces prefill by 17-36% against production RAG ordering, and the margin widens with retrieval depth as the theory predicts. Serving requests in the hierarchy's DFS order finally lets a cache holding one request's context attain the unbounded-cache optimum exactly, so cache capacity and reorder window act as substitutes.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving. Builds on 12 of its 23 references that are in the map. First posted on arXiv 12 Sep 2026.

Builds on

12 of 23 references.

Closest ancestors · 4

Same direction, newest first

  1. 2026PCR: A Prefetch-Enhanced Cache Reuse System for Low-Latency RAG Serving24 Mar
  2. 2025Cache-Craft: Managing Chunk-Caches for Efficient Retrieval-Augmented Generation5 Feb
  3. 2024CacheBlend: Fast Large Language Model Serving for RAG with Cached Knowledge Fusion26 May
  4. 2023Efficient Memory Management for Large Language Model Serving with PagedAttention12 Sep

Other references · 8

  1. 2023Lost in the Middle: How Language Models Use Long Contextscited by 3,455
  2. 2021BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Modelscited by 1,252
  3. 2023SGLang: Efficient Execution of Structured Language Model Programscited by 1,141
  4. 2023Prompt Cache: Modular Attention Reuse for Low-Latency Inferencecited by 268
  5. 2015A cost function for similarity-based hierarchical clusteringcited by 63
  6. 2016Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metricscited by 26
  7. 2024NP-Completeness for the Space-Optimality of Double-Array Triescited by 1
  8. 2026CacheWeaver: Cache-Aware Evidence Ordering for Efficient Grounded RAG Inferencecited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Sparse Prefix Caching for Hybrid and Recurrent LLM Serving
  2. 2026When Fancy Eviction Fails: Rethinking Cache Replacement For LLM Prefix Reuse
  3. 2026Cache-Aware Prompt Compression:A Two-Tier Cost Model for LLM API Caching
  4. 2025TokenLake: A Unified Segment-level Prefix Cache Pool for Fine-grained Elastic Long-Context LLM Serving
  5. 2026Not All Tokens Are Worth Caching: Learning Semantic-Aware Eviction for LLM Prefix Caches
  6. 2026PrefixWall: Mitigating Prefix Caching Side Channels in Shared LLM Systems
  7. 2025MEPIC: Memory Efficient Position Independent Caching for LLM Serving
  8. 2025LLM Serving Optimization with Variable Prefill and Decode Lengths