Aker: Density-Aware Approximate Caching for Vector Search

Abstract

Disk-based approximate nearest neighbor search (ANNS) incurs high I/O overhead due to frequent disk accesses during index traversal. Approximate caching, which reuses the results of past queries to serve future similar queries, offers a promising approach to bypass disk searches. However, existing approaches suffer from two limitations. First, their hit predicates fail to simultaneously achieve high throughput and high accuracy, as they do not adapt to the varying local neighbor density. Second, they lack an effective refresh mechanism to maintain cache correctness during vector updates. We present Aker, an approximate cache for disk-based ANNS. Aker addresses these limitations through two core design choices. First, we introduce a per-query similarity threshold that each cache entry dynamically adjusts based on cache hit patterns. This design enables Aker to adapt to neighborhood densities to preserve both efficiency and accuracy. Second, we propose del-consistency , a consistency model that applies deletions eagerly and insertions lazily. Under this model, Aker implements a low-overhead refresh mechanism that bounds cache staleness while preserving search accuracy. We integrate Aker into pgvector and evaluate it on representative workloads. Aker improves recall by up to 64 percentage points over prior solutions and increases QPS by up to 3.2×, while using 0.6× the memory of pgvector's shared buffers.