Optimal chunk order reduces computation in large language model serving
Prefix Sharing Is a Sorting Problem
Data Structures and AlgorithmsComputation and Language
Summary
Large language model systems reuse previous computations when a new prompt starts with the same pieces as before. How these pieces are ordered affects how much work can be saved. The authors show that simply using one fixed order isn’t best except in very simple cases, and they map the problem to sorting and tree structures. Their approach can reduce unnecessary computation by reorganizing the pieces intelligently, leading to more efficient responses in practice.
What this means in practice
- •For machine learning engineers: Optimize prompt assembly order to reduce computational load and speed up serving large language model queries by reusing more cached computation.
- •For search system developers: Improve document retrieval layouts to minimize prefill time in retrieval-augmented generation pipelines by using hierarchical chunk ordering.
Authors
Rong He
Abstract
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.