KVPrior: On the Suprising Effectiveness of Marginalizing KVCaches over Prefixes

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 recomputation-free, 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 \lsota performance.