# Prefix Sharing Is a Sorting Problem

arXiv: https://arxiv.org/abs/2609.13692 · HTML: https://mlsanity.com/paper/2609.13692/

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

## Placed in

- Efficient LLM inference and serving / [KV cache optimization](https://mlsanity.com/inference/kv-cache-optimization/)

## Builds on (most cited first, 12 of 12)

- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models](https://mlsanity.com/paper/2104.08663/) (2021)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [Prompt Cache: Modular Attention Reuse for Low-Latency Inference](https://mlsanity.com/paper/2311.04934/) (2023)
- [CacheBlend: Fast Large Language Model Serving for RAG with Cached Knowledge Fusion](https://mlsanity.com/paper/2405.16444/) (2024)
- [A cost function for similarity-based hierarchical clustering](https://mlsanity.com/paper/1510.05043/) (2015)
- [Cache-Craft: Managing Chunk-Caches for Efficient Retrieval-Augmented Generation](https://mlsanity.com/paper/2502.15734/) (2025)
- [Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics](https://mlsanity.com/paper/1609.09548/) (2016)
- [PCR: A Prefetch-Enhanced Cache Reuse System for Low-Latency RAG Serving](https://mlsanity.com/paper/2603.23049/) (2026)
- [NP-Completeness for the Space-Optimality of Double-Array Tries](https://mlsanity.com/paper/2403.04951/) (2024)
- [CacheWeaver: Cache-Aware Evidence Ordering for Efficient Grounded RAG Inference](https://mlsanity.com/paper/2606.19667/) (2026)

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