Prefix Sharing Is a Sorting Problem
cs.DS · cs.CL
Quick verdict
This CS-theory paper proves prefix-cache layout is a hierarchy choice with 17–36% prefill savings on BEIR; theory self-verified, evaluation is token-only.
Summary
The paper studies how LLM serving stacks that reuse KV cache by exact prefix match should order the interchangeable pieces — retrieved passages, tool definitions, few-shot exemplars — of an assembled prompt. Its main result is a structure theorem: the minimum prefix-trie cost equals a minimum over binary hierarchies on the requests of weighted canonical-decomposition sizes, so choosing per-request chunk orders is equivalent to choosing one clustering of requests. This yields an O(3^m) exact algorithm and several structural findings: with at most two chunks per request the problem is minimum vertex cover and a global order is optimal; the smallest three-chunk counterexample is unique (cost 8 versus 9); and on a leave-one-out request family a global order pays Θ(n²) where the optimum — the merge-sort recursion — is Θ(n log n). Agglomerative clustering by common intersection is a tight ½-approximation for the achievable savings. On BM25 traces over three BEIR corpora (NFCorpus, SciFact, FiQA) the layout cuts prefill by 17–36% against production relevance ordering, widening with retrieval depth, and 13–23% survives pinning the top passages; DFS serving order lets a one-request cache match the unbounded-cache optimum. Limitations: token counts rather than latency, answer quality priced but not measured, and evaluation confined to BM25 on small BEIR corpora.
Review complete
Assessment at a glance
3
risk flags identified
● high 0
● medium 2
● low 1
4 strengths · 4 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- The minimum prefix-trie cost of laying out requests equals a minimum over binary hierarchies on the request population of the weighted canonical-decomposition sizes (Theorem 1), so choosing chunk orders is choosing one clustering of requests.
- A single global chunk order is optimal exactly when every request has at most two chunks — where the problem is minimum vertex cover — and the unique minimal three-chunk counterexample costs 8 versus 9 (Theorem 4).
- On the leave-one-out request family, global orders pay Θ(n²) while the optimum — the merge-sort recursion, i.e. minimum external path length — is Θ(n log n), an unbounded Θ(n/log n) gap (Theorem 5).
- Agglomerative clustering by common intersection is a tight ½-approximation for the achievable savings (Theorem 6) and lands within 0.05% of the exact optimum on sampled NFCorpus/SciFact request groups.
- On BM25 traces over three BEIR corpora the hierarchy layout cuts prefill by 17–36% versus production relevance ordering (13–23% surviving top-passage pinning), and DFS serving order lets a one-request cache attain the unbounded-cache optimum exactly (Theorem 7).
Strengths
Clean structure theorem that eliminates the decision variables
Theorem 1 (§3) proves OPTfree equals a min over binary request hierarchies of weighted canonical-decomposition sizes, via a laminar-family argument both directions, and immediately yields an O(3^m) exact solver (§3.1) that re-verified every exact number (solving m=16 in under 2s vs brute force dying at m=7).
Unusual honesty in the separation and algorithm results
§4.2 proves global orders optimal iff |Ri|≤2 with a verified unique minimal 3-chunk counterexample (8 vs 9); §6.3 gives a ½-approximation whose per-threshold inequality was machine-checked on 3,000 random instances with zero violations, plus an annealed worst-case search never passing 1.83.
Evaluation tracks the theory's prediction and discards contradicting prior evidence
Two honest limitations stated up front (§10)
Weaknesses
Narrow empirical scope
Quality risk priced, never measured
Coordination gap for online deployment
No guarantee on the cost objective itself
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper formulates MPT: choose, for each request assembled from a weighted chunk universe, a permutation of its chunks so that total prefix-trie cost — identical to prefill FLOPs and, under a full-trie cache, KV memory — is minimized, contrasting the free-permutation optimum (OPTfree) with the single global chunk order every deployed stack uses (OPTglob). Central claims: (1) Theorem 1: OPTfree equals a min over binary request hierarchies of the weighted canonical-decomposition sizes t_x(H); (2) global orders are optimal exactly when |Ri|≤2, where the problem is minimum vertex cover (Prop. 2), with a unique minimal three-chunk counterexample at cost 8 vs 9 (Theorem 4); (3) on the leave-one-out family the gap is Θ(n/log n) (Theorem 5, verified against OEIS A001855); (4) agglomerative clustering by common intersection is a tight ½-approximation for savings (Theorem 6); (5) empirically 17–36% prefill reduction on BM25 BEIR traces plus a DFS schedule attaining the unbounded-cache optimum with a one-request cache (Theorem 7). The claimed scope is honest: a token-count proxy, three small corpora, quality priced rather than measured.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 4 strengths & 4 weaknesses, analyzed in detail
- 3 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is the main result of 'Prefix Sharing Is a Sorting Problem'?
It proves that when LLM prompts are assembled from reusable pieces, the minimum KV-cache/prefill cost is achieved not by picking one global chunk order but by clustering the requests into a binary hierarchy and reading the per-request orders off that tree. Along the way it shows global orders are optimal only for two-chunk requests, that a leave-one-out example has a Θ(n/log n) gap, and that a simple agglomerative clustering is a tight ½-approximation for the achievable savings.
How much prefill can better RAG passage ordering save?
On BM25 retrieval traces over three BEIR corpora (NFCorpus, SciFact, FiQA) at retrieval depths k=5–16, the paper's hierarchy-based layout cuts prefill tokens by 17–36% versus concatenating passages in relevance-rank order, the typical production choice; 13–23% survives even if the top 1–3 most relevant passages are pinned in place. These are token-count savings, not measured latency gains.
Does the proposed method need a huge cache or changes to the model?
No model change is needed — only the order in which the serving stack concatenates the retrieved pieces, which the model treats as equivalent. The paper additionally shows that if the scheduler serves requests in depth-first order of the layout trie, a cache holding a single request's context achieves exactly the cost of an unbounded cache, so cache capacity and reorder window act as substitutes.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.