KVPrior: On the Suprising Effectiveness of Marginalizing KVCaches over Prefixes

Counts differ because each database indexes a different set of publications. We treat OpenAlex as the canonical count; Google Scholar is not shown (no API, and crawling it violates its ToS).

To avoid costly prefills, non-prefix KVCache methods try to reuse individually prefilled KV caches in non-prefix positions. To recover the accuracy degradation, existing methods either perform inference-time recomputation or amortize its cost with model fine-tuning or link-token training, with little theoretical explanation for why they work. We propose KVPrior, a surprisingly simple \emph{recomputation-free}, \emph{training-free} method to obtain prefix-independent KVCache. Assuming the independence between retrieved documents, it samples a random set of prefixes from the training set, prefill the caches, and averages the context-dependent noise out. This surprisingly simple method nearly recovers the full prefill accuracy and surpassed existing approaches in tasks where the document independence assumptions hold (Biography and Needle-in-the-Haystack). In multi-hop-reasoning datasets where documents depend on each other, we observed weaker yet non-negligible improvements, and combination with existing approaches achieved the state of the art performance.