Exact Vector Caching Methods for Top-K ANN Search in Vector-Indexed Systems

Abstract

Vector-indexed systems provide the foundation for many modern machine learning features including semantic search and retrieval-augmented generation, where top-K approximate nearest neighbor (ANN) search is the standard for vector retrieval. While caching is a natural optimization, existing caching approaches are either approximate or limited to the top-1 case [7, 5, 4, 13, 12], leaving top-K exact caching unaddressed. This paper formalizes the exact caching problem for top-K ANN search and introduces two solutions we dub the Circular Inclusion Guarantee (CIG) and Half-Gap Guarantee (HGG) that certify which cached response vectors, if any, are among the true nearest-neighbors for a given query. We derive five caching algorithms from these guarantees, prove their correctness under metric distances, and extend them to cosine distance. We evaluate these algorithms across synthetically generated datasets isolating the effects of different workload characteristics such as inter-query distance, cache-to-test response set size (K/N) ratio, and cache size, as well as on SIFT-1M and ESCI. All algorithms achieve 100% accuracy under Euclidean and angular distances on synthetic data. We find hit rate is primarily decided by K/N ratio and inter-query distance in synthetic data, with hits observed in workload distributions satisfying both K/N > 1 and angular inter-query distance of < 3 degrees. Evaluation on SIFT-1M and ESCI yields zero hits, which data characterization suggests is primarily due to their inter-query distances lying outside of the ranges in which these algorithms produce hits under synthetic conditions. We also provide evidence of an inherent cache utilization ceiling for our algorithms arising from the conservativeness of the guarantees.