Aker: Density-Aware Approximate Caching for Vector Search (Extended Version)

Aker: Density-Aware Approximate Caching for Vector Search Extended Version Sukjoon Oh∗

Minki Kang

Dohyun Kim

Baotong Lu†

KAIST sjoon@kaist.ac.kr

KAIST minki.kang@kaist.ac.kr

KAIST ehgus421210@kaist.ac.kr

Microsoft Research baotonglu@microsoft.com

Jing Liu

Qianxi Zhang

Qi Chen

Youjip Won†

Microsoft Research jingliu3@microsoft.com

Microsoft Research qiazh@microsoft.com

Microsoft Research cheqi@microsoft.com

KAIST ywon@kaist.ac.kr

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 expensive disk searches. However, existing approaches suffer from two key limitations. First, their approximate hit predicates fail to simultaneously achieve high throughput and high accuracy, as they do not adapt to the varying local neighbor density in highdimensional spaces. Second, they lack an effective refresh mechanism to maintain cache correctness under 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, where each cache entry maintains its own threshold that is dynamically adjusted based on observed 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 for ANNS caches that applies deletions eagerly and insertions lazily. Under this model, Aker implements a low-overhead refresh mechanism that bounds cache staleness and preserves high 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. PVLDB Reference Format: Sukjoon Oh, Minki Kang, Dohyun Kim, Baotong Lu, Jing Liu, Qianxi Zhang, Qi Chen, and Youjip Won. Aker: Density-Aware Approximate Caching for Vector Search . PVLDB, 19(10): XXX-XXX, 2026. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/sjoon-oh/aker. ∗ Work partially performed during the internship at Microsoft Research. † Corresponding authors: Baotong Lu and Youjip Won.

This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing info@vldb.org. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 19, No. 10 ISSN 2150-8097. doi:XX.XX/XXX.XX

Query

Query

ABSTRACT

ANN Index

Pages

ANN Index

Hit Cluster

Dataset Update

Search Results

Miss

Cache

Hit

Update

v1 v2 v3 v4 Top-k

Dataset

Graph

v1 v2 v3 v4 Top-k

Cache

(a) Traversal-centric

(b) Result-centric

Figure 1: Two categories of caching strategies for ANNS.

1

INTRODUCTION

Vector search has become a foundational component in modern data-intensive applications, spanning web search engines [11, 22], recommendation systems [25, 37, 39, 41, 58], scientific discovery [16], and retrieval-augmented generation (RAG) [14, 18, 38]. These workloads rely on approximate nearest neighbor search (ANNS) to efficiently probe million- to billion-scale vector collections and retrieve relevant results under sub-second latency constraints. At the core of ANNS is the vector index, which organizes high-dimensional vectors according to their proximity, enabling efficient query processing while preserving high search accuracy. As data volumes continue to grow, modern vector stores place both vectors and indexes on disk at low cost [1, 3, 9, 21, 22, 32, 56, 60]. However, disk-resident storage makes I/O the dominant performance bottleneck during vector search. We observe that this bottleneck primarily stems from the inherent read amplification in ANNS: to satisfy accuracy requirements, a query typically accesses orders of magnitude more data than is ultimately returned. Specifically, the query first traverses a disk-resident index – organized as clusters [22, 26, 60] or graphs [32, 44] – during which candidates are fetched from disk into memory for distance computation, and then re-ranks the visited candidates to produce the top-𝑘. Achieving higher accuracy targets requires more aggressively expanding the search scope during index traversal, which substantially increases disk I/O and further exacerbates read amplification [63]. To mitigate this bottleneck, prior work has improved ANNS performance through algorithmic optimizations [22, 32, 60, 63] or emerging hardware [31, 46, 53, 54]. Complementary to these efforts, this paper investigates a practical result-centric cache for disk-based ANNS, with the goal of reusing past query results in DRAM to improve end-to-end query performance.

Figure 1 summarizes two caching strategies for ANNS: traversalcentric caching and result-centric caching. Traversal-centric caches [9, 32, 46, 62] retain intermediate data accessed during index traversal in memory, such as pages, clusters, or graph neighbors. By reusing the cached index structures and vectors, this approach reduces disk I/O during query processing. However, sustaining high performance typically requires a large cache budget, as ANNS traversal often incurs a high memory footprint due to excessive vector accesses. In contrast, result-centric caches [23, 27, 45, 47, 49] store only the past query vectors and their top-𝑘 results. To serve an incoming query, the system evaluates its similarity to cached queries and returns the corresponding top-𝑘 results when the similarity exceeds a predefined threshold. As this strategy does not require strict query equivalence, it constitutes an approximate cache relying on semantic similarity between queries. By avoiding the storage of intermediate traversal data, result-centric caching significantly reduces memory consumption. Moreover, cache hits can entirely bypass expensive ANN index traversals, yielding substantial performance gains. As a result, result-centric caching represents a promising direction for improving ANNS efficiency. However, the broader hit predicate makes cache hits no longer accuracy-safe, introducing two challenges that limit existing designs in practice. Dilemma between cache efficiency and accuracy. Since resultcentric caching relies on query similarity, it faces a trade-off between cache efficiency and accuracy. A loose similarity threshold increases cache hit ratios and thus improves system efficiency, but may match insufficiently similar queries, degrading accuracy. Conversely, a tight threshold preserves accuracy but may lead to low cache hit ratios by missing potential reuse opportunities. Furthermore, vector distributions in the high-dimensional space are often highly skewed: some regions are dense, while others are sparse. This heterogeneity renders the one-size-fits-all similarity thresholds adopted by prior work [18, 23, 27, 30, 45, 49] ineffective in balancing efficiency and accuracy across varying local vector densities. Heavyweight cache refresh. Modern vector databases continuously receive update operations [51, 60], requiring cached results to be refreshed to avoid staleness and maintain correctness. Otherwise, caches may miss newly inserted vectors or return deleted items. However, supporting cache refresh is expensive: it either requires scanning all cached entries to determine whether their results should be updated or aggressively invalidating cached entries, which forces costly ANNS executions in the underlying database. Consequently, existing result-centric caching approaches [18, 30] choose to permit stale entries at the expense of ANN accuracy or degrade cache efficiency under frequent updates. This paper presents Aker, an approximate cache that makes similarity-based reuse practical for disk-based vector searches by balancing accuracy and efficiency while supporting lightweight cache refresh. Aker is built on two core ideas. First, Aker introduces a density-aware caching strategy which maintains an individual similarity threshold for each cached query. Specifically, Aker adapts the threshold based on the local data distribution: it tightens the threshold for queries located in dense regions to preserve accuracy, while relaxing it in sparse regions to improve cache utilization. Moreover, the similarity threshold is dynamically adjusted at runtime, with accuracy treated as a first-class optimization objective.

Second, Aker introduces del-consistency, a practical consistency model between the cache and the underlying vector database. Delconsistency enforces immediate invalidation of deleted items to prevent stale results from being returned, while allowing the visibility of insertions to be deferred for update efficiency, which aligns well with the approximate nature of ANNS. We implement Aker through carefully designed caching structures that achieve high memory efficiency and fast cache-side searches. To reduce metadata overhead for queries sharing identical top-𝑘 results, Aker organizes cached queries into representative entries and lightweight alias entries. Only representative entries store the top-𝑘 results, while alias entries are linked to their corresponding representatives. To support efficient lookup for similar queries, Aker maintains a query filter which builds an embedded ANN index over cached queries, enabling the retrieval of similar queries without brute-force scans. Finally, Aker implements delconsistency via a lightweight refresh pipeline. We execute deletions in the cache by removing deleted vectors from cached results and repairing affected top-𝑘 lists using a small pool of top-(𝑘 + Δ) candidates, avoiding costly ANNS traversal in the underlying database. In contrast, insertion visibility is safely deferred by tracking an accuracy degradation risk for each cached query, triggering top-𝑘 recomputation only when the estimated risk exceeds a threshold. We make three contributions. First, we identify two fundamental limitations of existing approximate caches for ANNS and highlight the design challenges. Second, we propose Aker, an approximate caching system that combines density-aware similarity thresholds to balance accuracy and efficiency with del-consistency to efficiently support cache refresh under continuous updates. Finally, we implement Aker with memory-efficient caching structures that support fast lookups and lightweight refresh pipelines. By integrating Aker into the popular PostgreSQL pgvector extension [1–3, 9], we verify the effectiveness of Aker through endto-end evaluations. Across both web search and RAG workloads, Aker improves accuracy by up to 64 percentage points over prior state-of-the-art approximate caches. Moreover, compared to pgvector’s default shared buffer (i.e., traversal-centric caching), Aker reduces read amplification by up to 0.4× and increases throughput by up to 3.2× while using only 0.6× of the memory.

2 BACKGROUND 2.1 Vector Search and Index Vector search is widely used in modern data-intensive applications such as web search [11, 22] and retrieval-augmented generation [14, 18, 38]. In these systems, each data item is represented as a vector in a high-dimensional space. Given a query vector 𝑞, the system retrieves the top-𝑘 most similar vectors according to a similarity metric1 such as Euclidean, cosine, or inner product [9, 18, 22, 26]. Finding nearest neighbors via a brute-force scan yields exact results but incurs prohibitively high computational cost, especially at large scale. Consequently, modern vector stores adopt approximate nearest neighbor search (ANNS) to trade result accuracy for high search efficiency [9, 18, 22, 26, 32, 60]. ANNS systems rely on vector indexes that organize vectors based on proximity for efficient 1We use similarity and distance interchangeably in this paper. Higher similarity be-

tween vectors indicates smaller distance in the vector space.

retrieval of target vectors. Existing ANN indexes can be broadly categorized into two classes: cluster-based [9, 22, 26, 60] and graphbased [32, 44, 46, 51, 53, 56]. Cluster-based indexes group similar vectors using clustering algorithms such as 𝑘-means [22, 26, 60], with each cluster represented by a centroid. At query time, the system probes a small subset of clusters whose centroids are closest to the query vector. In contrast, graph-based indexes (e.g., HNSW [44]) construct a proximity graph in which each vector is connected to its nearest neighbors. Queries are processed via greedy graph traversal starting from one or more entry points, progressively moving toward closer vectors while pruning unrelated regions of the graph. The accuracy of ANNS is commonly evaluated using 𝑟𝑒𝑐𝑎𝑙𝑙@𝑘 = |𝑅𝑎 ∩𝑅𝑒 | , where 𝑅𝑎 denotes the set of 𝑘 searched vectors and 𝑅𝑒 𝑘 denotes the ground-truth top-𝑘 results. In practice, ANN indexes expose a trade-off between search accuracy and efficiency metrics such as throughput (QPS) and latency [22, 26, 32, 44, 60, 63]. Owing to their cost-effectiveness and competitive performance, disk-based ANNS solutions are widely adopted in vector databases [4, 7, 9, 10, 55] and have been deployed in major cloud services [1, 3].

2.2

Caching Strategy for Vector Search

To reduce I/O costs, disk-based ANNS systems employ DRAM to cache frequently accessed data [9, 22, 32, 46, 56, 60]. As illustrated in Figure 1, existing caching mechanisms for ANNS can be broadly categorized into two types – traversal-centric caching and resultcentric caching – based on the type of data being cached. Traversal-centric caches store index structures and vectors accessed during ANNS traversal. For instance, in cluster-based ANN indexes, the cache typically contains centroids and accessed clusters, whereas in graph-based indexes it stores frequently visited neighbors. Some approaches adopt static caching strategies [32], which place vectors near the entry points directly in DRAM, without cache replacement between disk and memory. Other systems, such as PostgreSQL pgvector [9], leverage the traditional database buffer pool to dynamically cache the hot data. Traversal-centric caching is effective when the dataset or index structures are small enough to fit in memory, or when sufficient DRAM is available to cache a substantial fraction of the traversal-related data. In contrast, result-centric caches aim to reduce memory consumption by storing only previously issued query vectors along with their final top-𝑘 results. When processing an incoming query, the system computes its similarity to cached queries and directly returns the corresponding top-𝑘 results if the queries match exactly or if their similarity meets a predefined threshold. Since the value of 𝑘 is typically fixed by the application and queries are often skewed, result-centric caching has proven effective in practice and been adopted in various applications [19, 29, 30].

2.3

Approximate Cache

Beyond serving equal-match queries, result-centric caches for ANNS provide a unique opportunity to reuse search results across queries that are semantically similar [52]. This opportunity arises from a fundamental property of modern embedding models: vectors that are close in the embedding space typically correspond to semantically similar texts or images. Consequently, even when two query vectors are not identical but sufficiently close, their top-𝑘 nearest neighbors in the database often exhibit high overlap.

This observation enables result-centric caches to operate as an approximate cache, in which the result returned from the cache may differ from that produced by the underlying ANNS engine. In such a cache, query similarity serves as the cache-hit predicate. Let 𝑞 denote a cached query and 𝐴 its associated top-𝑘 results. When a new query 𝑞 ′ arrives, the cache returns 𝐴 if the distance between 𝑞 and 𝑞 ′ , denoted by 𝑑 (𝑞, 𝑞 ′ ), falls below a predefined threshold 𝜏. The choice of 𝜏 is therefore critical, as it directly governs the trade-off between result accuracy and cache efficiency (hit ratios). We present two representative approximate cache designs: Proximity [18] and Potluck [30]. Proximity [18] is an approximate cache designed for RAG systems, where each cache entry stores a query vector along with its top-𝑘 search results. Cache hits are determined using a fixed similarity threshold 𝜏, which is configured at system initialization and remains unchanged during runtime. While this design is simple and easy to deploy, the static threshold makes it difficult to balance accuracy and efficiency under varying query workloads and data distributions. Potluck [30] is an approximate cache originally proposed to share computation results across mobile applications, but it is general enough to apply to ANNS workloads. Unlike Proximity, Potluck dynamically adjusts the similarity threshold during runtime to improve cache effectiveness. To this end, Potluck introduces a dropout mechanism to estimate the accuracy of cached results. When a query hits the cache, Potluck probabilistically triggers an intentional cache miss and executes the query against the underlying ANNS engine. The returned result is then compared with the cached result. If the two results match, indicating high cache accuracy, 𝜏 is increased to improve the cache hit ratio for future queries; otherwise, it is decreased to reduce approximation error.

3 MOTIVATION AND CHALLENGES 3.1 Read Amplification in ANNS We observe that the I/O bottleneck in disk-based ANNS primarily stems from excessive vector accesses during index traversal, particularly when high recall is required. To quantify this effect, we define read amplification 𝜌 as the ratio between the total size of vectors accessed during index traversal, denoted by 𝐶, and the size of the top-𝑘 results read from disk, denoted by 𝑅: 𝜌 ≜ 𝐶𝑅 . For traditional indexes over scalar data types, such as LSM-trees, read amplification is effectively bounded on the order of a few tens (e.g., 20–35×) due to simplified traversal paths [20, 36, 42, 48, 64]. In contrast, disk-resident ANNS exhibits substantially higher read amplification, as vector queries often need to access a large number of neighboring vectors to avoid missing potential candidates. To study this behavior, we measure the read amplification of two representative disk-based ANNS systems – PostgreSQL pgvector [9] and SPANN [22] – using the BIGANN [5] and SPACEV [11] datasets. We cover two vector indexes supported in pgvector: the graphbased HNSW and the cluster-based IVF. During query processing, pgvector relies on PostgreSQL’s shared buffer pool to load index structures and vector data from disk and cache frequently accessed pages. Therefore, the shared buffer pool effectively functions as a traversal-centric cache. SPANN [22] is a cluster-based system that adopts a static caching strategy, where cluster centroids are retained in memory while all posting lists reside on disk.

3

ρ (x10 )

3

10 8 6 4 2 0

pg-HNSW pg-IVFFlat SPANN

2 1 0 0

0.2 0.4 0.6 0.8

1

0

0.2

Recall@10

0.4

0.6

0.8

1

Recall@10

(a) Dataset: BIGANN [5]

(b) Dataset: SPACEV [11]

Frequency (103)

Figure 2: Read amplification (𝜌) of disk-based ANNS systems under different recalls. The amplification becomes extremely severe at high recall requirements (e.g., 0.8-0.9). Median 13.40

1.5 1.0 0.5 0.0 0

5

10

15

Distance

(a) Dataset: BIGANN

Median 6.91

2.0 1.5 1.0 0.5 0.0

20

0

2

4

6

8

10

Distance

(b) Dataset: SPACEV

Figure 3: Distribution of ground-truth top-1 distances to the queries. Large distance implies even the nearest neighbor is far away; thus the query lies in a sparser region. Figure 2 reports the read amplification of different indexes under varying recall requirements. Even at a low recall of 0.5, pgvector’s HNSW (pg-HNSW) and IVFFlat (pg-IVFFlat) already exhibit significant read amplification, reaching 70× and 155× across both datasets. Read amplification worsens as the recall requirement increases. To improve recall from 0.5 to 0.8, pg-HNSW incurs at least 7.4× and 9.5× higher disk I/Os on the two datasets, while pg-IVFFlat requires 14.7× and 24.6× more, respectively. SPANN shows a comparable trend, suffering from similarly severe read amplification. Therefore, meeting application-level recall targets (e.g., 0.8–0.9) can result in read amplification on the order of 102 –103 ×. The root cause is that achieving high recall necessitates accessing a much larger number of candidate vectors to avoid missing true nearest neighbors. For instance, on the SPACEV dataset, to return top-10 results occupying 4 KB, pgvector reads an average of 29.7 MB of data per query to achieve 𝑟𝑒𝑐𝑎𝑙𝑙 = 0.9. This mismatch highlights the inefficiency of disk accesses at high recall. While in-memory ANNS solutions eliminate disk I/O by keeping all data in DRAM, they scale poorly to large datasets due to prohibitive memory costs [26, 32, 46]. As an alternative, caching query results in memory offers an attractive design point: upon a cache hit, the system can bypass index traversal entirely, thereby substantially reducing read amplification and end-to-end query latency.

3.2

A Single Global Threshold for All Queries

Prior approximate caches rely on a single similarity threshold to determine whether an incoming query can become a cache hit. The similarity threshold 𝜏 is either globally fixed, or periodically adjusted. However, the single global 𝜏 struggles to simultaneously achieve high cache efficiency and accuracy. This limitation stems from the inherent non-uniformity of vector spaces: the local vector

density – the number of vectors within a given radius 𝑟 – can vary substantially across different regions [27]. A global threshold implicitly assumes that a single reuse radius is suitable for all queries and enforces a trade-off. Specifically, a larger 𝜏 improves cache hit ratios by treating more queries as hits, but risks returning incorrect neighbors in dense regions; conversely, a smaller 𝜏 preserves accuracy while causing unnecessary cache misses in sparse regions. To quantify this effect, we empirically examine density variance using the BIGANN and SPACEV datasets.2 Because selecting a meaningful radius 𝑟 is non-trivial, we approximate local density using the distance from each query to its closest ground-truth neighbor. For a query 𝑞, this distance is the radius of the smallest hypersphere centered at 𝑞 that contains at least one data point. Accordingly, smaller distances indicate denser regions of the vector space, while larger distances correspond to sparser regions. As shown in Figure 3, the top-1 distances range from 2.7 to 16.7 on BIGANN and from 4.2 to 10.0 on SPACEV, indicating substantial variation in local density. A single threshold thus cannot adapt to diverse query characteristics. In Section 5.2, we empirically verify that no single threshold can simultaneously balance recall and cache hit rate. This observation motivates our design of a density-aware similarity threshold, which maintains per-query thresholds and hit conditions and dynamically adjusts each threshold at runtime.

3.3

Absence of Cache Refresh Scheme

When the underlying ANN indexes evolve due to insertions and deletions, the cache must reflect these changes to prevent staleness. Existing approximate caching schemes typically assume a static dataset and therefore lack explicit cache refresh mechanisms. However, real-world workloads may continuously process insert and delete operations to maintain dynamic vector collections [40, 57, 60]. In those workloads, if a vector closer to a query 𝑞 is newly inserted, its cached top-𝑘 results must be updated to preserve search quality. Similarly, when one or more vectors in the cached top-𝑘 are deleted, the cache must be refreshed to reflect the changes. Refreshing cached results in approximate caches is non-trivial. Consider a query 𝑞 whose cached top-3 results are 𝑣 𝑎 , 𝑣𝑏 , 𝑣𝑐 with distances 0.13, 0.24, and 0.31, respectively. If a new vector 𝑣𝑑 is inserted with distance 0.19 to 𝑞, the correct top-3 becomes 𝑣 𝑎 , 𝑣𝑑 , 𝑣𝑏 . Updating the cache accordingly, however, can incur substantial overhead. Specifically, the system must first determine which cached queries are affected by the insertion, which requires scanning all cached queries and computing their similarity to the newly inserted vector. Deletions introduce analogous challenges: the system must identify cache entries whose top-𝑘 results include deleted vectors. Moreover, deletions invalidate cached queries because they reduce the number of available results below 𝑘. This requires the system to re-execute ANNS in the underlying database to reconstruct the top-𝑘. To efficiently maintain cache consistency under dynamic updates, we propose a result-level consistency model, termed del-consistency. Based on this model, we further design a lightweight cache refresh mechanism that incurs low maintenance overhead while effectively bounding recall degradation. 2 For simplicity and clarity of presentation, we use Euclidean distance throughout the

paper, where smaller values indicate higher similarity between vectors. Our design can be naturally extended to other distance metrics, such as cosine distance.

SEARCH(v)

DELETE(v)

Return

Neighbor Object (NO)

Lookup Update Refresh

RQ

{0.14, 2.15, -0.21, ...}

NRL

p0 p1

next

... pk

RQ

NO1

Result Data

NOn

TQ

Neighbor obj. reference list

minD

Log entry (LE) list

maxD

LE0

LE1

NO0

...

prev

LEn

LC

RQ prev next

Insert Log

Cache Entry

(a) Architecture

Neighbor Object

Neighbor Obj. Pool

...

Client

INSERT(v)

Log Elem.

(b) Cache entry structure

Figure 4: Aker overview.

4 AKER 4.1 Overview We present Aker, an approximate result cache for disk-based ANNS systems. Aker combines density-aware reuse control with lightweight refresh to support similarity-based result caching under dynamic updates. Aker provides the mechanisms required to make approximate caching practical inside a vector search engine. Conventional caches are equivalence-based. An exact key match is sufficient to locate cached data. Approximate caching enables broader reuse opportunities but introduces challenges that conventional caches do not encounter: which cached query is similar enough to reuse, how safe reuse is for that specific query, and how cached results should remain meaningful under updates. These requirements require additional components beyond a conventional cache. First, Aker adds a query filter, a small embedded ANN index over cached queries, with a low-cost management scheme because approximate reuse opportunities are hard to find through exactkey lookup alone. Second, Aker adds fine-grained reuse control through an entry-specific threshold and its safety rule to adapt to the local neighborhood density. Third, Aker adds a representative/alias cache entry structure and shared result management, because semantically similar queries may reuse the same top-𝑘 result set and therefore require different metadata organization for space efficiency. Finally, Aker adds del-consistency implemented through risk-triggered fast and slow refresh mechanisms, because approximate cached results must remain useful under updates without forcing expensive re-traversal on the hit path. Figure 4a illustrates key components of Aker. For searches, Aker probes the cache and returns a cache entry on a hit; otherwise, it queries the vector database. For inserts and deletes, Aker refreshes cached results to reflect updates in the base data. Vector search. Aker handles search requests with equality hits and approximate hits. It first searches the query lookup table, a hash table that maps a hashed query vector to a cache entry. Each cache entry stores the query vector and its top-𝑘 results. Aker first searches for an identical query in the query lookup table. When a match is found, the cache entry is returned. Otherwise, Aker takes an approximate search path by querying a query filter. The query filter is a small ANN index built over the query vectors of the cache entries. Its size depends on the number of cache entries. The query filter serves two roles: (1) retrieving a cache entry whose query is similar to an incoming query without a brute-force scan,

Table 1: Summary of key designs in Aker. Description

Section

Representative/ alias cache entry

Representative entries hold results; alias entries point to the representative entries.

4.2, 4.4

Query filter

Embedded index of cache entries that finds similar cache entry candidates.

4.1, 4.4, 4.7

Threshold 𝜏𝑞

Reuse radius for a cached query 𝑞; enlarged and shrunk dynamically from hit types.

4.2, 4.3, 4.4

Refresh

Del-consistency combines immediate deletion with fast/slow refresh via risk tracking.

4.1, 4.6

Active/Standby filter

Two-filter scheme that separates cache entry insertions from evictions.

4.7

and (2) locating cache entries that are likely to be affected by update requests. The cache entry is returned if an approximate hit condition is met; otherwise, the request becomes a miss. Vector insertion. When a client inserts a new vector into the vector database, Aker records the vector in an insert log. Aker then refreshes affected cache entries via two paths: a fast path and a slow path. The fast path uses the query filter to locate the cache entry whose query is closest to the inserted vector. It checks whether the new vector would enter that cache entry’s top-𝑘 results; if so, Aker updates the cached top-𝑘 accordingly. The slow path processes insert log records lazily in batches. Aker estimates the risk of recall degradation from lazy refreshes. When the risk exceeds a predefined threshold, it refreshes unchecked log entries. The two paths refresh the cache without a full scan of all cache entries. Vector deletion. Upon a vector deletion request, Aker first searches a neighbor lookup table to check whether the vector is present in the cache. Each neighbor object represents a cached result vector. If any of the vectors requested to be deleted reside in the cache, Aker immediately removes them and updates the neighbor lookup table. Cache entries that fail to keep a complete set of top-𝑘 are repaired during cache lookups by promoting reserved candidates.

4.2

Cache Entry Structure

Figure 4b shows the structure of a cache entry. The raw-query field RQ stores the query vector. The neighbor object reference list NRL stores references to the neighbor objects that store the query’s top-𝑘 results. The prev and next pointers link similar cache entries. The

per-query similarity threshold 𝜏𝑞 is stored in the TQ field. The maxD and minD fields keep the maximum and minimum distance between the query and its cached top-𝑘, respectively. Aker initializes TQ to minD/4, a conservative setting that biases early lookups toward preserving recall until Aker adapts TQ online. Each element of NRL points to a neighbor object in a neighbor object pool. Aker allows multiple cache entries to share neighbor object references to save the cache space. The cache size is controlled by capping the total number of neighbor objects. The neighbor lookup table is a hash table that maps each key vector to its corresponding neighbor object in the shared pool. Each neighbor object stores the raw vector and database-specific metadata (e.g., tuple identifiers in PostgreSQL). Because a neighbor object can be referenced by multiple cache entries, Aker uses a reference counter for each neighbor object for safe memory reclamation. When inserting a new cache entry, Aker checks whether each top-𝑘 vector already exists in the neighbor lookup table; if so, it reuses the existing neighbor object and increments its reference counter. Otherwise, it creates a new neighbor object and inserts it into the table. When a vector deletion is requested, Aker removes the corresponding neighbor object from the table. To avoid repeated approximate lookups for recurring queries, Aker uses entry linking. Specifically, when a query is served via an approximate hit, Aker registers a cache entry in the query lookup table. This newly inserted entry points to the cache entry that was previously served. When the same query vector arrives again, Aker directly returns the entry in 𝑂 (1) using the query lookup table, skipping both the query filter probe and the similarity check. Cache entries are classified into two types in Aker: representative and alias. A representative entry owns the NRL and is indexed in the query filter. Each element in the representative entry NRL points to a neighbor object. In contrast, an alias entry keeps an empty NRL. It links to a representative entry and is not indexed in the query filter. Cache entries are linked via prev/next pointers, forming a list whose head is the representative entry. A cache lookup returns a representative entry either directly or by following prev from an alias entry to the list head. By indexing only representative entries in the query filter, Aker can keep the query filter small (Section 4.7), while allowing repeated queries that were previously served via approximate hits to be answered via the query lookup table. The log checkpoint field LC references an insert log record. It tracks the progress of slow path refresh for a cache entry, i.e., how far the cache entry has processed insert log updates. When Aker invokes the slow path after vector insertions, it performs batched distance checks, scanning from LC (Section 4.6). Only representative entries maintain a valid LC, and alias entries set LC to null.

4.3

Per-Query Similarity Threshold

Aker maintains a per-query similarity threshold 𝜏𝑞 for each cached representative query 𝑞. The threshold 𝜏𝑞 controls the acceptance region for approximate reuse around 𝑞. When tuning 𝜏𝑞 , Aker prioritizes both low-overhead control and conservative safeguards. The most precise method is verification-based tuning. A cache can re-traverse the index and adjust the threshold based on the search discrepancy [30]. However, in disk-based vector search systems, invoking the underlying ANNS on cache hits reduces the benefit of caching. Therefore, Aker avoids direct feedback that requires

Query Lookup Table Not found

① Equality Match Q1 NRL p n ② Approx. Match Q2 null p n Q3 NRL p n

Query Filter

③ Approx. Match

N0

N1

N2

N3

N4

N5

N6

N7

N8

N9

Na

Nb

Neighbor Object Pool

Figure 5: Aker lookup. Aker probes query lookup table: on equality match (1) returns the entry; on alias hit (2) follows prev to the representative. Otherwise (3), probes query filter and returns a nearest cache entry; otherwise it is a miss. additional index traversals and instead uses a low-overhead signal already available in the cache: the hit type. An equality hit implies that the incoming query exactly matches a cached query, whereas an approximate hit implies that the incoming query does not match any cached query exactly but is still close enough to a cached query to reuse its result. In Aker, the two hit types play different roles in threshold control. An approximate hit is the primary warning signal that the current reuse radius may already be too permissive, because it serves one query using the cached result of another nearby query. Aker therefore shrinks 𝜏𝑞 after approximate hits. In contrast, an equality hit indicates that the current threshold has not introduced additional query-reuse error for that exact query. Aker therefore treats equality hits as a lowrisk signal for cautious increase in reuse opportunities. Concretely, Aker updates the per-query threshold TQ as follows: {︄ 𝜏𝑞,prev · 𝛼 𝐿 , (𝛼 𝐿 > 1), Equality-match 𝜏𝑞,next ← (1) 𝜏𝑞,prev · 𝛼𝑇 , (0 < 𝛼𝑇 < 1), Approximate-match Here, 𝜏𝑞 denotes the similarity threshold associated with a cached query 𝑞. 𝛼 𝐿 > 1 and 𝛼𝑇 ∈ (0, 1) are multiplicative factors for increasing and decreasing the threshold, respectively. To achieve better hit ratios, 𝜏𝑞 must be large. To achieve better search accuracy, 𝜏𝑞 must be small. Aker prioritizes search accuracy, thus using asymmetric update factors 𝛼 𝐿 = 1.1 and 𝛼𝑇 = 0.25 as its default values. To prevent 𝜏𝑞 from growing far beyond a reasonable distance, Aker limits the maximum 𝜏𝑞 by the distance between 𝑞 and its closest cached neighbor. Aker permits only mild growth after equality hits, and this growth is capped by the distance to the closest cached neighbor. Repeated equality hits thus do not drive unbounded threshold expansion. Each 𝜏𝑞 is updated on every cache hit.

4.4

Cache Lookup

Figure 5 and Algorithm 1 present a cache lookup workflow. Aker distinguishes two cache-hit types: equality match and approximate match. An equality match happens when an incoming query is identical to the cached query vector. In the case of an equality match, Aker first probes the query lookup table (line 2). If an identical query vector is found, the corresponding cache entry is returned. An approximate match occurs when the incoming query is not identical to the cached representative query but is sufficiently close. Aker supports two approximate match paths: (i) returning an alias entry via the query lookup table, or (ii) returning a representative entry via the query filter. First, the alias path handles queries that

Algorithm 1: Cache Lookup Input: query 𝑞 1 Procedure cacheRead(q): 2 𝑒 ← QueryLookupTable(𝑞) 3 if 𝑒 == NULL then 4 𝑒 ← QueryFilter(𝑞) 5 if distance(𝑞, 𝑒.𝑅𝑄) < 𝑒.𝑇𝑄 then 6 𝑒.𝑇 𝑄 ← updateTQ(𝑒.𝑇𝑄) 7 return 𝑒 8 return NULL // miss 9 while 𝑒.𝑝𝑟𝑒𝑣 is not NULL do 10 𝑒 ← 𝑒.𝑝𝑟𝑒𝑣 // Find representative entry 11 𝑒.𝑇 𝑄 ← updateTQ(𝑒.𝑇𝑄) 12 return 𝑒 have previously produced an approximate hit. Suppose an incoming query 𝑞 ′ approximately matches a cached query 𝑞 stored in a representative entry 𝑒. Aker creates an alias entry 𝑒 ′ for 𝑞 ′ and registers it in the query lookup table. The alias entry 𝑒 ′ stores a reverse pointer prev to its representative entry 𝑒. Upon a repeated request for the same vector 𝑞 ′ , Aker finds 𝑒 ′ from the query lookup table and follows prev to retrieve 𝑒 (line 10). This avoids rerunning the query filter search and distance comparison because 𝑞 ′ is already similar to the previously validated representative entry. If no alias entry is found in the query lookup table, Aker searches the query filter for a similar representative entry (line 4). Only representative entries are indexed in the query filter. Given a query 𝑞 ′ , the query filter returns the nearest representative entry 𝑒 whose cached query vector RQ is closest to 𝑞 ′ . Aker then computes the distance between 𝑞 ′ and RQ. If the distance is below the per-query similarity threshold TQ, it becomes an approximate hit.

4.5

Cache Update

To insert a new cache entry, Aker first generates neighbor objects for the retrieved top-𝑘 results and registers them in the neighbor lookup table. If an identical vector exists, Aker increments the reference counter of the existing neighbor object. Aker then creates a new representative entry and records the references in its NRL. The representative entry is registered in the query lookup table and indexed by the query filter. If the request is an approximate match, Aker creates an alias entry. Aker traverses the representative entry’s next pointers and links the alias entry at the tail. Finally, Aker inserts the alias entry into the query lookup table. Aker initializes the LC to the insert log tail. This is safe because the new representative entry is built over the latest database snapshot. In the slow refresh path, Aker scans the insert log starting from the cache entry’s LC to determine whether the vector should be included in the top-𝑘 set. A representative entry created on a cache miss at time 𝑡 is computed over the database snapshot at time 𝑡. Thus, the search result reflects all latest inserts up to the insert log tail at time 𝑡.

4.6

Cache Refresh

Del-consistency. We define consistency for ANNS caches as the result-level visibility agreement between the vectors in the underlying database and the vectors in the cache at time 𝑡 for a query 𝑞.

Let 𝑉𝑡 denote the set of live vectors in the database at time 𝑡, and let 𝑐𝑡 denote the cached top-𝑘 results of 𝑞 returned on a cache hit. Let 𝑠𝑡 denote the results of 𝑞 returned by executing the base ANNS on the database at time 𝑡. We propose a new consistency model called del-consistency. A cache is del-consistent at time 𝑡 for any query 𝑞 if it satisfies validity, while allowing relaxed visibility: P 1 (Validity). At any time 𝑡, cached results of 𝑞 contain only valid vectors, i.e., 𝑐𝑡 ⊆ 𝑉𝑡 and |𝑐𝑡 | = 𝑘. P 2 (Relaxed Visibility). At any time 𝑡, the cached results 𝑐𝑡 are not required to equal the ANNS results 𝑠𝑡 for the same query. Validity requires that deletion operations be reflected immediately in NRL. Otherwise, the cache could return vectors that no longer exist in the database. Relaxed visibility allows temporary staleness with respect to newly inserted vectors, which aligns well with ANNS as it returns approximate results. Aker enforces delconsistency that guarantees validity under deletions without requiring eager recomputation of the latest top-𝑘, which would impose high refresh cost on the hit path. Consider a cache that follows the del-consistency model. A cache entry for query 𝑞 is created at time 𝑡 0 . If a cached neighbor 𝑣 is deleted at 𝑡 1 (𝑡 1 > 𝑡 0 ), the cache removes 𝑣 immediately (P1). If a new vector 𝑢 is inserted at 𝑡 2 (𝑡 2 > 𝑡 0 ) and would appear in 𝑠𝑡2 , 𝑢 may remain invisible to 𝑞’s cache entry until the next refresh at 𝑡 3 (𝑡 3 > 𝑡 2 ). During this interval, the cache can still return a valid top-𝑘 (P2). Aker implements del-consistency by handling deletions immediately and insertions lazily, with a reserve parameter Δ. Deletions. Aker immediately removes deleted vectors from the neighbor object pool to satisfy validity (P1). However, after removals, a cache entry may no longer contain 𝑘 valid neighbors. In this case, the entry (cached query) must be invalidated. In Aker, a neighbor object can be referenced by multiple cache entries, thus a single vector deletion may invalidate multiple entries. To reduce cache entry invalidations, Aker stores the top-𝑘 results with an additional Δ-sized reserve in NRL. We choose Δ to be small and collect the reserve using the same search path as for the top-𝑘. ANNS algorithms typically maintain an internal candidate set that is larger than 𝑘 during search, even though they return only the top𝑘 results [18, 22, 43, 44]. Thus, Aker can save the (𝑘 + Δ) neighbors from the same traversal with negligible additional overhead. When a deletion invalidates a neighbor object, Aker removes it immediately and promotes the next closest reserved neighbor in NRL (P1, P2). If deletions break NRL such that the number of valid neighbor objects falls below 𝑘, Aker invalidates the corresponding cache entry. Insertions. When a new vector is inserted into the database, it is unknown which cache entries should include it in their NRL. A naive approach that scans every cached query and updates affected NRLs is expensive. To minimize overhead, Aker splits insertion handling into a fast path and a slow path (Algorithm 2). The fast path targets the cache entry that is most likely to be affected by the insertion (P2). Upon receiving an insert request, Aker appends the new vector to the insert log and queries the query filter (line 3) to retrieve the closest representative entry. Aker then compares the distance between the inserted vector and the entry’s RQ against the entry’s maxD (line 5). If the inserted vector is closer

Algorithm 2: Cache Refresh (Insertions) Input: new vector 𝑣 1 Log L; Batch size 𝐵; Risk 𝑅; Risk threshold 𝜏 risk ; 2 Procedure fastPath(𝑣): 3 𝑒 ← QueryFilter(𝑣) // fast path 4 if distance(𝑒, 𝑣) < 𝑒.maxD then 5 𝑒.𝑁 𝑅𝐿 ← updateNRL(𝑣) 6 𝑅 ← updateRisk(𝑒) 7 if 𝑅 ≥ 𝜏risk then 8 slowPath(𝐵) Procedure slowPath(𝐵): 𝑒𝑐 ← 𝑁 𝑒𝑥𝑡𝐸𝑛𝑡𝑟𝑦 // e_c: Cache entry 11 for 𝑒𝑙 = L [𝑒𝑐 .𝐿𝐶] to L [𝑒𝑐 .𝐿𝐶 + 𝐵] do 12 if distance(𝑒𝑙 .𝑅𝑄, 𝑒𝑐 .𝑅𝑄) < 𝑒𝑐 .maxD then 13 𝑒𝑐 .𝑁 𝑅𝐿 ← updateNRL(𝑒𝑙 ) // e_l: Log entry 14 𝑒𝑐 .𝐿𝐶 ← 𝑒𝑐 .𝐿𝐶 + 𝐵 15 𝑅 ← updateRisk(𝑒𝑐 )

SPACEV (dim=100)

SPACEV (dim=100)

TriviaQA (dim=768)

TriviaQA (dim=768)

9

10

than maxD, Aker evicts the farthest neighbor from NRL, inserts a reference to the new vector, and updates maxD accordingly. Because the fast path updates only one entry per insertion, other entries that should also include the new vector may remain stale. To propagate insertions beyond the fast path target, the slow path incrementally refreshes the remaining entries (line 8). On each cache lookup or insert log append, Aker selects one representative entry in a round-robin manner (line 10). For the selected entry, Aker scans the next batch of log records (default 16) starting from its LC. For each scan, Aker computes the distance between the inserted vector and RQ (line 12) and substitutes the inserted vector in the same manner as the fast path. Then, Aker advances LC to the most recently examined log position and recomputes the global risk R. During vector insertions and cache lookups, Aker triggers the slow path when R exceeds a predefined risk threshold. Aker maintains R as a conservative estimate of potential recall degradation under delayed insert propagation. R is derived from per-entry risk factors 𝑟 and the number of unchecked vectors in the insert log. For each representative entry 𝑒, 𝑟 (𝑒) estimates how likely an unseen inserted vector could enter 𝑒’s top-𝑘 by replacing a member of NRL. Aker uses the Δ reserve region in NRL as a proxy for how tight the top-𝑘 boundary is: since only the top-𝑘 results are returned, refreshing items at ranks 𝑘+1 to 𝑘+Δ can be delayed without changing the returned results (P2). 𝑟 (𝑒) =

𝑑𝑘 (𝑒) ∈ [0, 1], 𝑑𝑘+Δ (𝑒)

R =𝑟 ·

𝑈 𝑊

(2)

Here, 𝑑𝛼 (𝑒) denotes the distance between 𝑒’s query and the 𝛼th neighbor in 𝑒’s cached top-(𝑘+Δ) list. A value of 𝑟 (𝑒) close to 1 indicates a higher likelihood that an unseen insertion could substitute into the top-𝑘. By design, Aker over-estimates the risk by treating all unchecked insert log records as potentially harmful. 𝑟 is the average risk factor, 𝑈 is the average number of unchecked insert log records per cache entry, and 𝑊 is the total insert log size. R scales with both how tight the top-𝑘 boundaries are and how far entries lag behind the insert log. As R increases toward 1, the potential for recall degradation increases.

Figure 6: ANN index operation latency. We grow indexes to measure latency of top-1 lookup and incremental builds. We compare FAISS [26] HNSW (𝑚 = 4, 𝑒 𝑓 𝐶𝑜𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 = 8, 𝑒 𝑓 𝑆𝑒𝑎𝑟𝑐ℎ = 16), LSH (𝑛𝑏𝑖𝑡𝑠 matched to vector dimensionality), IVF with single build at 20K inserts (IVF-1; IVFFlat 𝑛𝑙𝑖𝑠𝑡𝑠 = 128, 𝑛𝑝𝑟𝑜𝑏𝑒 = 1), and with periodic rebuild at every 10K inserts (IVF-Re), and a brute-force scan (Full). Insert log. Aker reclaims insert log space when evicting a cache entry whose LC references the log head. Starting from the head, Aker advances the head and removes log records that are no longer referenced by the LC of any cache entry. This reclamation stops at the earliest log record that is referenced by at least one cache entry.

4.7

Eviction

Neighbor object pool. Aker evicts neighbor objects when a new cache entry requires allocating new neighbor objects but the pool has no free space. To free space, Aker selects a victim representative entry and reclaims the neighbor objects referenced by its NRL. We adopt FIFO because it has low overhead. Prior work suggests that under tight similarity thresholds, the accuracy impact of the eviction policy is minor [18]. Given a victim representative entry, Aker traverses its NRL and decrements the reference count of each neighbor object. If the reference count reaches zero, it is removed. Otherwise, the object remains alive because it is still referenced by other cache entries. If reclaiming a single victim entry does not provide enough free space, Aker evicts the next FIFO victim and continues until the space becomes sufficient. When evicting a representative entry, Aker also removes all linked alias entries. It follows the representative’s next pointers, removes each alias entry, and deletes the corresponding query lookup table records. After all aliases are removed, Aker deletes the victim representative entry and removes it from the query lookup table. Finally, Aker marks the representative entry as a tombstone in the query filter to prevent it from being returned by subsequent approximate lookups. Query filter. The query filter is the embedded ANN index over representative cached queries. To choose the best candidate for the query filter, we microbenchmark several index types [26] under an in-memory setting using two query sets (Section 5.1) as shown in Figure 6. The results show a clear trade-off between lookup and insertion latency across the index types. HNSW provides the lowest lookup latency even at higher dimensionality, but its insertion

New entry Q4 Q1

Q4

Q2 Q3

Q1 NRL Q2 NRL Q3 NRL

5.1

Freeze F2

Qb Qc

Q4 NRL Qa NRL Qb NRL Qc NRL

Q2 Q3

Q1 NRL Q2 NRL Q3 NRL

Standby(F1)

Qd NRL

Standby(F2)

Q4 NRL

Active(F2) Evicting Qb Qa Qd

Active(F3)

Q1 Q4

Figure 7: Query filter eviction. latency grows with the number of indexed elements. IVF shows low latency in insertion, but its lookup latency is higher than HNSW and grows more with the number of indexed elements. LSH is slowest in lookup and is less aligned with the distance metric used by the underlying ANNS. Because Aker targets read path optimization, we choose HNSW because it provides the lowest lookup latency. The adoption of HNSW for the query filter introduces two major challenges. First, to keep insertion overhead of the query filter low, Aker must bound the size of the index. Second, graph-based ANN indexes like HNSW make fine-grained deletions non-trivial because the removal may break the graph connectivity [26, 32, 60]. Prior systems often implement deletions via tombstones and periodic rebuilds [32, 60]. This approach has three limitations. First, searches may return deleted items before the next rebuild. Second, tombstoned elements inflate the index size and increase insertion latency. Finally, selecting the timing of index rebuilds becomes important, since rebuilding from scratch can amplify tail latency. To avoid per-entry deletions while bounding the size of the query filter, Aker implements a dual-index design where it decouples insertions from evictions and reclaims space by dropping an entire index at epoch boundaries. Aker maintains an active filter 𝐹𝐴 , standby filter 𝐹𝑆 , and a monotonically increasing epoch identifier. During an epoch, 𝐹𝐴 admits new representative entries, whereas 𝐹𝑆 admits no inserts and is used to isolate evictions. Aker advances the epoch when the number of evicted entries exceeds the number of live entries in the query filter. At an epoch transition, the filters swap roles, as shown in Figure 7. Under FIFO, the entries are evicted only from 𝐹𝑆 (F1), and the evicted entries are marked as tombstones. When the number of tombstones exceeds the number of live entries in the query filter, Aker halts inserts into 𝐹𝐴 (F2), seals it, and promotes it to become the next 𝐹𝑆 . Then, Aker creates an empty index as next 𝐹𝐴 (F3) and drops the previous 𝐹𝑆 (F1), thereby reclaiming space without per-entry deletions or clean rebuilds. During lookup, Aker queries both 𝐹𝐴 and 𝐹𝑆 and selects the closest candidate cache entry. Because evictions never occur in 𝐹𝐴 , any candidate returned from 𝐹𝐴 is valid. Consequently, Aker guarantees the return of valid cache entries, never returning tombstoned entries.

5

Experiment Setup

We integrate Aker into pgvector [9] HNSW (v0.8.0), a PostgreSQL [12] extension, as our primary ANNS system. pgvector provides a pagebased traversal-centric cache baseline via PostgreSQL shared buffer. We run all experiments on a server equipped with a four-socket Intel Xeon Platinum 8276 CPU, 512 GB RAM, and a 512 GB NVMe SSD, running Ubuntu 24.04. The client and PostgreSQL execute on the same machine. The client issues requests from a single thread. Unless otherwise stated, the default Aker uses (𝛼𝑇 , 𝛼 𝐿 ) = (0.25, 1.1), a query filter of m = 4, 𝑒 𝑓 𝐶𝑜𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 = 8, 𝑒 𝑓 𝑆𝑒𝑎𝑟𝑐ℎ = 16, and no deletion reserve (Δ = 0). Section 5.4 evaluates variants derived from the default configuration. PostgreSQL caches 8KB table and index pages in its shared buffer [12]. pgvector stores page-organized vectors and indexes as PostgreSQL tuples. These pages are also cached via the shared buffer, which cannot be disabled manually. To reduce the impact of buffers, we set the size to the minimum 128KB when evaluating approximate caches. pgvector can benefit from both shared buffers and OS cache [13]. Thus, we choose two settings for search workloads: a 16 GB memory-constrained deployment via container, and a host deployment where pgvector runs directly on the host. The memory-constrained deployment limits the OS caching support. We also evaluate whether Aker improves searches on a highly optimized disk-based index, DiskANN [32]. We add Aker as a frontend caching layer for DiskANN. DiskANN already manages its own memory-resident index, so Aker forwards a query to DiskANN only on a cache miss. The benchmark runs with a single thread. Datasets. We evaluate two application scenarios – web search and RAG – using SPACEV [11] and SPHERE [50] as summarized in Table 2. For RAG queries, we use TriviaQA [35]. For the search workload, we use 10M-scale datasets; for the refresh stress test, we use a 1M-scale dataset. We use a smaller scale in the refresh test to increase the likelihood that newly inserted vectors appear in the top𝑘, thereby stressing the refresh behavior. We build all indexes using Euclidean distance. For each workload, we set search parameters to achieve 0.9 recall at 𝑘=10 without approximate caches. Table 2: Build configurations and data sizes Dataset

SPACEV(10M)

SPHERE(10M)

SPACEV(1M)

Dimension

100

768

100

pgvector

m=16, efCon=128, Vector 4.6 GB, Index 7.4 GB

m=32, efCon=256, Vector 41.0 GB, Index 40.9 GB

m=16, efCon=64, Vector 477.9 MB, Index 781.8 MB

DiskANN

R=64, L=100, On-disk 3.5 GB, In-mem 1.1 GB

R=96, L=100, On-disk 39.0 GB, In-mem 5.1 GB

-

EVALUATION

We try to answer the following questions: • Does the per-cached query similarity threshold maintain stable accuracy across different request distributions compared to single-threshold methods? (Section 5.2) • Can Aker reduce read amplification compared to a traversalcentric cache? (Section 5.3) • Can Aker sustain high performance without degrading recall under cache refreshes? (Section 5.4)

Queries. We first examine the two released query sets: SPACEV and encoded TriviaQA. Figure 8 shows, for each query, the distance to its nearest neighbor in the released query set. The distribution characterizes inter-query relationships. The released queries show that zero distance is rare, indicating that most queries are distinct. Second, both dataset contain many queries with nearby neighbors. The released query sets contain semantic neighborhoods whose top-𝑘 results can overlap, making approximate reuse meaningful. However, real-world workloads are often skewed [6, 15, 18]. Public

SPACEV

TriviaQA

iaQA

PACEV

Figure 8: Nearest-neighbor (top-1) distance distribution in a query set. Smaller distances indicate that queries are more similar to one another. datasets provide query collections for measuring retrieval quality and are widely used in ANNS benchmarks [5, 8, 8, 11, 50]. For example, BIGANN [5] releases 10K benchmark query vectors, and SPACEV [11] provides query descriptors from Bing web searches. TriviaQA [35] comprises question-answer pairs collected from websites. These datasets are released as sampled query collections and therefore do not preserve request pattern information. Because real traces are unavailable, we synthesize a workload called simZipf that jointly models query similarity and request skew. We construct simZipf in two stages. First, for each base query, we build a similar-query group containing 50 queries. We take two different synthesis methods because each dataset exposes different forms of query information. For SPACEV, which provides only a query set 𝑄 of 29K vectors, we construct nearby queries directly in the vector space via linear interpolation. For each base vector 𝑞𝑖 ∈ 𝑄, we sample another vector 𝑝 ∈ 𝑄 and generate 𝑞𝑖′ = (1 − 𝜆)𝑞𝑖 + 𝜆𝑝, where 𝜆 is sampled uniformly from (0, 0.5). Repeating this procedure with 50 sampled choices of 𝑝 yields the similar-query group. For TriviaQA, which provides 10K raw natural-language questions, we generate 50 semantically similar questions using Mistral-7B [33]. Then, we encode the generated questions with the BGE-large encoder [59] to form the similar-query group. Next, we generate a skewed request sequence over the similar-query groups using a Zipfian distribution [15, 18, 24, 61]. We use YCSBC [6] to generate a 100K Zipfian key sequence (𝑘 1, 𝑘 2, . . . ), and map each similar-query group to the key with the same popularity rank. For each key access, we uniformly sample one query from the corresponding similar-query group. simZipf aims to simulate temporal locality while preserving semantic neighborhoods. We use three different skew settings ranging from low to high (Zipfian exponents: 0.30, 0.60, and 0.99) to simulate different combinations of semantic and temporal locality. Approximate caches rely on two locality dimensions: whether queries appear nearby in the vector space, and how strongly requests concentrate over the neighborhoods. To clarify these two dimensions, we analyze the simZipf traces using two complementary statistics: (1) nearest-neighbor distance distribution and (2) repeated-query distribution. The first captures whether the generated traces remain concentrated within semantic neighborhoods. The second captures how much of the locality stems from repeated identical queries compared to the semantically similar queries. Figure 9a shows that as the simZipf skew weakens, the generated traces spread toward larger nearest-neighbor distances. The two datasets exhibit different distance profiles. TriviaQA shows a bell-shaped distribution in mid-range distances (roughly 2 to 10). SPACEV shows a flatter profile (roughly 10 to 70) because its

(a) Generated nearest-neighbor distance distribution.

SPACEV

C=0.8

TriviaQA

C=0.7 C=0.4 C=0.2 C=0.2

(b) Equal-query distribution.

Figure 9: Similarity-popularity of simZipf queries. similar-query groups are generated directly in vector space. Despite these differences, both datasets exhibit the same qualitative trend: lower skew shifts more requests toward more distant semantic neighbors. This makes approximate reuse harder because fewer requests concentrate in very close neighborhoods, forcing reuse to rely on weaker semantic locality. In this sense, lower-skew traces are harsher for approximate caching, much as workloads with weaker temporal locality are harsher for conventional caches. We also analyze how often identical queries repeat in the generated traces. This analysis is necessary because if the workload were dominated by a very small number of repeated queries, a large fraction of the cache benefit could be attributed to equality matches. Figure 9b shows that stronger simZipf skew does not cause the traces to be dominated by repeated queries. The repeated-query distribution has a steeper cutoff and faster decay than would result from applying the same Zipfian skew directly to individual queries. Baselines. We compare Aker against Potluck and Proximity, which are the latest approximate caches. We also compare against PostgreSQL’s default traversal-centric cache, the shared buffer. For a fair comparison, we implement Proximity and Potluck within Aker by substituting only the threshold control module and keeping the rest of the system unchanged. All baselines share Aker’s neighbor object pool, NRL layout, and eviction policy. The differences reflect only the cache-hit rule. In both baselines, alias entries are disabled as they are Aker-specific optimizations. • Potluck+ [30]. We implement Potluck’s threshold-tuning mechanism. Following the Potluck algorithm, upon cache-entry insertion, we test set equivalence using the hashed vectors stored in NRL. At lookup time, Potluck performs dropout: with probability 𝑝, it forces a cache miss. We use Potluck’s default setting of 𝑝=0.10 and add a more aggressive setting of 𝑝=0.25. • Proximity+ [18]. We use a strict threshold for high recall. We measure all inter-query distances between the synthesized queries and use the 1st-percentile value as the fixed threshold.

SPACEV (Pool 1%)

SPACEV (Pool 5%)

TriviaQA (Pool 1%)

TriviaQA (Pool 5%)

AK

Figure 10: Recall. Aker (AK) maintains higher recall across skew levels than Potluck+ (PL) and Proximity+ (PRX).

5.2

SPACEV (Pool 1%)

SPACEV (Pool 5%)

TriviaQA (Pool 1%)

TriviaQA (Pool 5%)

PL10

PL25

PRX

AK

PL10

PL25

PRX

Figure 11: Hit ratios. Each stacked bar shows the total cache hit ratio. The yellow segment denotes equality hits, and the remaining segment denotes approximate hits.

Cache Accuracy

We evaluate all cache methods at 𝑘 = 10. This is a strict criterion, as each single missing ground truth neighbor reduces recall by 0.1. We target at least 0.8 recall for Aker, corresponding to fewer than one missed true neighbor per query. We set the neighbor object pool to store up to 1% and 5% of the dataset vectors. Aker shows consistent trends in recall and hit ratios across pgvector and DiskANN; thus we provide results for pgvector in Figure 10 and 11. Accuracy. Across varying skewness, Aker achieves up to 52.3 percentage points (pp) and 64.0 pp higher recall than the single similarity threshold methods on SPACEV and TriviaQA, respectively. In all settings, Aker misses fewer than one correct result on average and maintains recall above 0.80. The single similarity thresholds become overly permissive, producing more approximate hits. The low recall persists even when Proximity+ (PRX) uses a conservative setting of 1% inter-query distance, indicating that a strict constraint is insufficient to preserve accuracy. Potluck+ (PL) achieves higher recall than PRX by forcing pgvector searches. Higher 𝑝 leads to a higher recall. With 𝑝 = 0.1 (PL10), the maximum recall reaches 0.79 and 0.71 on each dataset, still missing more than one correct item. Higher recall is achieved by more frequently invoking the ANNS. Increasing 𝑝 to 0.25 (PL25) improves recall compared to PL10, but both still remain worse than Aker. Under low skew, query distributions become diverse. A single threshold fails to capture query-specific density. Thus, as skew decreases, the recall gap between Aker and other methods widens. Cache hit ratios. Figure 11 shows the hit ratios under varying skewness levels (𝑥-axis) and cache sizes. As skew increases, nearduplicate queries recur more frequently; all caches show increased total hit ratios. PRX achieves high hit ratios across all configurations, but mostly via approximate hits, which substantially reduce recall. PL also shows a higher approximate hit ratio than Aker. Although a larger 𝑝 triggers more ANNS, PL’s reliance on a single similarity threshold produces high approximate hits. In contrast, Aker adapts to workload skewness. As skew grows, Aker relies less on approximate hits. Aker shows higher recall because multiple thresholds allow approximate hits only when they are locally safe.

The uniform distribution further highlights the difference in the threshold control. As queries recur, equality hits dominate in Aker and the recall is preserved. In PL, the equality hits gradually loosen its global threshold and allows farther approximate matches. Sensitivity study. We empirically show how Aker preserves accuracy under different parameter choices. We sweep 𝛼𝑇 and 𝛼 𝐿 at 5% pool size on SPACEV and TriviaQA under simZipf 0.3, 0.6, and 0.99. The sweep shows two consistent trends. First, large 𝛼 𝐿 reduces recall and equality hit ratios. A larger 𝛼 𝐿 expands 𝜏𝑞 more aggressively, which makes later cache lookups more likely to be served by distant approximate hits. Second, large 𝛼𝑇 also reduces recall and equality hit ratios. Because 𝛼𝑇 controls contraction speed after approximate hits, a larger 𝛼𝑇 keeps 𝜏𝑞 loose for longer. As a result, more approximate hits are allowed. The sensitivity remains limited under low skew. Under simZipf 0.3, the workload shifts toward more diverse mid-range queries, reducing opportunities for safe reuse. Even in this setting, however, Aker prevents large recall loss across the parameter sweep. On SPACEV, recall changes only marginally across the tested parameter pairs. On TriviaQA, the recall spread is 4.8 percentage points (pp). However, the sensitivity becomes larger under high skew. For example, on TriviaQA, the recall spread increases from 4.8 pp at simZipf 0.3 to 9.2 pp at simZipf 0.99. Figure 13a and Figure 13b explain why the gap widens. As either 𝛼𝑇 or 𝛼 𝐿 increases, the share of equality hits decreases while the share of approximate hits increases. When a query is first served by an approximate hit, Aker creates an alias entry for that query and links it to the previously served entry. Subsequent repetitions of those equal queries are then served through the alias path. Looser parameter settings therefore admit more initial approximate hits, create more alias entries, and divert more future repetitions away from the equality hit path. Thus, the equality hit ratio falls even though more requests are being served from cache. The effect is clearest on TriviaQA with simZipf 0.99. At 𝛼 𝐿 = 1.10, increasing 𝛼𝑇 lowers the equality hit ratio from 34.2% to 23.1% while increasing the approximate hit ratio from 29.7% to 45.4%. At 𝛼𝑇 = 0.25, increasing 𝛼 𝐿 from 1.10 to 2.00 lowers the equality hit ratio from 31.9% to 29.4% and increases the approximate hit ratio from 32.2% to 35.6%.

simZipf 0.60

simZipf 0.99

TriviaQA

SPACEV

simZipf 0.30

Figure 12: Aker Sensitivity study: Recall. Each cell shows recall (%) for one parameter pair (𝛼𝑇 , 𝛼 𝐿 ). simZipf 0.60

simZipf 0.99

TriviaQA

SPACEV

simZipf 0.30

(a) Equality hit ratio. simZipf 0.60

simZipf 0.99

TriviaQA

SPACEV

simZipf 0.30

(b) Approximate hit ratio.

Figure 13: Aker Sensitivity study: Hit ratio. Each cell shows hit ratio (%) for one parameter pair (𝛼𝑇 , 𝛼 𝐿 ).

Across both figures, 𝛼𝑇 is the more influential parameter. Because 𝛼𝑇 directly controls how aggressively Aker contracts the threshold, increasing 𝛼𝑇 produces a larger shift toward approximate reuse and a larger recall drop than increasing 𝛼 𝐿 .

5.3

Cache Efficiency

Operational overhead. Figure 14 shows that Aker adds little overhead compared to pgvector processing latency. The average cache lookup latency remains below 0.1 ms. A cache miss adds less than 1 ms, from cache lookup and cache entry insertion combined.

Read amplification. We observe read amplification by measuring the average number of PostgreSQL 8 KB pages read per query from PostgreSQL logs. We compare Aker (AK) against pgvector’s traversal-centric cache, PostgreSQL shared buffer (PG). For Aker, we set the maximum neighbor object pool size to 1%, 2%, and 5%. For the shared buffer, we set the size from 128 MB to 8 GB. Figure 15 shows that Aker reduces read amplification, 𝜌, on both datasets. Under high skew (0.99), Aker reduces 𝜌 to 0.7× and 0.4× of pgvector on SPACEV and TriviaQA, while using only 0.4× and 0.5× of shared buffer memory, respectively. Under low skew (0.30),

TriviaQA (Host: 512GB)

SPACEV (Host: 16GB)

TriviaQA (Host: 16GB)

.30 .99

.30 .99

QPS

SPACEV (Host: 512GB)

Shared Buffer Size (MB), simZipf

(b) pgvector latency

Figure 14: Aker (lookup and cache entry insert) and pgvector latency. Each bar shows the average, and error bar shows 1stand 99th-percentile latencies.

QPS

(a) Aker latency

.30 .99

Req. Proc.

Pool Size

TriviaQA

SPACEV

TriviaQA

.30 Buf. Rd. .99

SPACEV

Aker still achieves 1.0× and 0.7× 𝜌 in both datasets while using 0.8× and 0.6× of pgvector’s memory. As ANNS requires large reads, each query can still read many pages when the working set exceeds the buffer. In Aker, page reads occur only on cache misses.

(a) QPS of pgvector. TriviaQA

SPACEV

Memory efficiency. Figure 17 shows NRL lengths and the query filter’s share of total memory in simZipf 0.99. An NRL length is the ratio of the number of neighbor objects to the number of cache entries. The NRL length below 𝑘 = 10 indicates neighbor objects are shared across entries. Compared to a naive design that allocates 𝑘 neighbor objects per entry, Aker reduces the number of TriviaQA

Figure 16: QPS. Figure 16a and Figure 16b follow the same approximation and plotting convention as in Figure 15. neighbor objects needed by 2.9-6.1×. Figure 17b shows that the number of cache entries brings minor overhead, with the query filter accounting for only 13.5-18.8% of total memory.

5.4

Figure 15: Read amplification. Numeric labels show the skewness. We omit simZipf 0.60 as it follows the same trend as simZipf 0.30. The memory use of the query filter is approximated as: (1) 𝑅 query vectors of cache entries (dimension 𝑑, float32) are 𝑅 · 𝑑 · 4 bytes, (2) maximum number of neighbors 𝑚 = 4, storing 𝑚 8-byte identifiers per entry are 𝑅 · 𝑚 · 8 bytes.

Cache Refresh

To invoke cache refresh, we first make the cache dirty, then run searches on the Aker-attached pgvector. Using a 1% neighbor object pool, we first warm up the cache by running simZipf 0.99. Next, we insert an additional 5% of vectors to fill the insert log from another split of SPACEV [60]. We then randomly invalidate neighbor objects to simulate deletions. We use deletion levels of 5%, 10% and 25%. Finally, the same search queries are re-executed. For Aker, we set Δ to 10 (AK-D10) and 30 (AK-D30), the risk threshold to 0.3, and the slow path batch size 𝐵 to 16. We compare against Potluck+ with probability 𝑝 = 0.10 (PL10). We include a norefresh ablation with Δ = 0, AK-RD, in which refresh mechanisms NRL Length

SPACEV

(b) QPS of DiskANN. The additional memory footprint of Aker over DiskANN remains small, reaching at most 26.4 MB on SPACEV and 275.6 MB on TriviaQA, which corresponds to 2.5% and 5.4% of DiskANN’s pinned in-memory index, respectively.

10 8 6 4 2 0 1% 5%

1% 5%

SPACEV

TriviaQA

(a) NRL length

Memory use (MB)

QPS. Figure 16a reports QPS under two pgvector deployment settings. On SPACEV, the 16 GB limit shows little difference in QPS as the data size fits the memory budget. On TriviaQA, in contrast, QPS decreases because the data is larger than the memory budget. In all settings, Aker achieves up to 2× and 3× QPS while using 0.8× and 0.6× the memory on SPACEV and TriviaQA, respectively. Despite DiskANN’s strong baseline efficiency, Aker provides improvements, with benefits varying across datasets and workload skew. On 100-dimensional SPACEV, DiskANN search is inexpensive, achieving an average query latency of 3.7 ms, with 70% spent on reads and 30% on index traversal. Under lower-skew workloads, the hit rate is not high enough to amortize Aker’s lookup cost shown in Figure 14. Thus, QPS improves only at simZipf 0.99. On 768-dimensional TriviaQA, DiskANN search is substantially more expensive: the average query latency rises to 21.1 ms, with 31% spent on reads and 67% on index traversal. Although this latency is lower than that of pgvector, the higher backend search cost makes bypassing the full search path more beneficial. Thus, Aker achieves up to 2.4× higher QPS across all skews on TriviaQA.

800 600

Cache entry NObj. Pool Query filter

400 200

18.8% 16.0%

16.1% 13.5%

0 1% 5%

1% 5%

SPACEV

TriviaQA

(b) Query filter overhead

Figure 17: Memory efficiency. Figure 17b shows the memory usage, following the same approximation of Figure 16a.

PL10 AK-RD

6

1 0.8 0.6 0.4 0.2 0

QPS

Recall@10

AK-D10 AK-D30

5

10

25

250 200 150 100 50 0

AK-D10 AK-D30

0

Deletion Rate (%)

PL10 AK-RD

5 10 15 20 25 30 Deletion rate (%)

(a) Recall

(b) QPS

Figure 18: Refresh stress-test under updates. The red line is the recall when no approximate cache is attached. Aker (AK) maintains high recall and QPS compared to Potluck+ (PL) and the refresh-disabled variant of Aker (RD).

Figure 19: Cache refresh overhead (AK-D10). are disabled in Aker. For PL10 and AK-RD, no refresh is performed. Under deletions, if a cache entry cannot maintain 𝑘 valid results, it is treated as a miss to avoid correctness violations (P1). Accuracy and QPS. AK-D10 and AK-D30 incur at most 2 pp recall drop across all deletion rates. AK-RD shows the highest recall because deletions invalidate many entries and trigger the ANNS more frequently. In Table 3, AK-RD shows a low cache hit ratio of 6.4% due to the large number of invalidated cache entries. In contrast, PL10 suffers from a large recall drop of 12.3 pp, even at low deletion rates. At a deletion rate of 5%, AK-D10 achieves the highest QPS, outperforming PL10 by 1.3× and AK-RD by 1.5×. Selection of Δ. Under a fixed pool budget, increasing Δ improves per-entry tolerance to deletions (more reserves per cached query), but each cache entry consumes more neighbor objects. Thus, the number of cache entries decreases. Table 3 illustrates the effect. AKD10 maintains 2× more cache entries with a higher hit ratio than AK-D30. Because AK-RD cannot recover cache entries, it shows the lowest hit ratio and QPS, even though it maintains 4× more cache entries than AK-D30. Overall, AK-D10 achieves the best deletion tolerance–recall balance, including the most aggressive stress level up to 25% deletions. This suggests that a small Δ is sufficient to tolerate the deletion pressure. Refresh overhead. Figure 19 reports the refresh latency in AK-D10 and compares it against the end-to-end search latency of pgvector. The log insert latency includes both the fast and slow paths. Overall, the refresh overhead remains small, never exceeding 0.25 ms. On average, Aker adds only 0.22 ms, which is about 4.4% of the 5 ms search latency. The results indicate that Aker introduces negligible refresh overhead relative to query processing. Table 3: Number of entries and hit ratio at 5% deletion rate. AK-D10

AK-D30

PL10

AK-RD

# of entries

625

315

1, 170

1, 284

Hit ratio

12.52%

9.71%

16.64%

6.39%

RELATED WORK

ANN index optimizations. These studies propose optimized ANN index designs that reduce disk I/O and memory costs. GoVector [65] proposes an index layout that places similar vectors on the adjacent disk pages to reduce I/O. DiskANN [32] and SPANN [22] propose a memory–disk hybrid index design to overcome extensive memory use. DiskANN proposes the Vanama algorithm and a hybrid storage layout that keeps quantized vectors in-memory and full-precision vectors on-disk. SPANN proposes a balanced clustering algorithm to reduce disk I/O overhead. SPFresh [60] extends SPANN to support incremental index builds while maintaining high accuracy under vector updates. CXL-ANNS [31] and SmartANNS [54] propose hardware-optimized index designs to accelerate index traversal. Approximate caches. These studies introduce approximate caching across diverse domains. Prior works have used approximate caches in systems for advertising [45], image retrieval [28], and scene understanding [49]. Potluck [30] proposed function-level caching to reduce cross-application computation. RAGCache [34] caches frequently referenced knowledge chunks to reduce end-to-end response time in RAG pipelines. GPTCache [17] and Proximity [18] leverage query similarity to reduce redundant document searches. These systems do not address query-specific reuse control or cache refreshes, which are the key designs of Aker.

7

CONCLUSION

We present Aker, an approximate cache for disk-based ANNS. Aker targets two challenges in approximate caching: maintaining high recall and throughput, and designing a low-cost cache refresh mechanism. First, Aker introduces per-query similarity thresholds that tailor hit decisions to each cached query based on observed hit behavior, preserving recall across varying neighborhood densities. Second, Aker proposes del-consistency, which applies deletions eagerly while handling insertions lazily via Δ reserves and risk scores that enable a low-overhead cache refresh pipeline. We integrate Aker into pgvector. Aker improves recall by up to 64 percentage points over prior solutions and increases QPS by up to 3.2× relative to PostgreSQL’s shared buffer, while using only 0.6× of the memory.

ACKNOWLEDGMENTS We thank the anonymous reviewers for their valuable comments and suggestions. This research was supported by the IITP-MSIT (Institute for Information & Communications Technology Planning & Evaluation, Ministry of Science and ICT) (RS-2024-00436680 and RS2024-00459026), Microsoft Research, and NRF (National Research Foundation of Korea) (RS-2025-00518369).

REFERENCES [1] [n.d.]. Amazon RDS for PostgreSQL. https://aws.amazon.com/rds/postgresql/. Accessed: 2025-06-13. [2] [n.d.]. Google Cloud Documentation: Generate and manage vector embeddings. https://docs.cloud.google.com/sql/docs/postgres/generate-managevector-embeddings. Accessed: 2025-06-13. [3] [n.d.]. pgvector in Azure Database - Flexible Server. https://learn.microsoft. com/en-us/azure/postgresql/flexible-server/how-to-use-pgvector. Accessed: 2025-06-13. [4] [n.d.]. Redis. https://redis.io. Accessed: 2025-06-13. [5] 2010. Datasets for Approximate Nearest Neighbor Search. http://corpus-texmex. irisa.fr. Accessed: 2025-06-13. [6] 2014. YCSB-C. https://github.com/basicthinker/YCSB-C. Accessed: 2025-06-13.

[7] 2020. Weaviate. https://weaviate.io. Accessed: 2025-06-13. [8] 2021. NeurIPS 2021 Competition Track. https://neurips.cc/Conferences/2021/ CompetitionTrack. Accessed: 2025-06-13. [9] 2021. pgvector. https://github.com/pgvector/pgvector. Accessed: 2025-06-13. [10] 2021. Qdrant. https://qdrant.tech. Accessed: 2025-06-13. [11] 2021. SPACEV1B: A Billion-scale Vector Dataset for Text Descriptors. https: //github.com/microsoft/SPTAG/tree/master/datasets/SPACEV1B. Accessed: 202506-13. [12] 2023. PostgreSQL Documentation. https://www.postgresql.org/docs/16/. Accessed: 2025-06-13. [13] 2025. PostgreSQL Documentation: Resource Consumption. https://www. postgresql.org/docs/current/runtime-config-resource.html. Accessed: 202506-13. [14] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. 2023. GPT-4 Technical Report. arXiv preprint arXiv:2303.08774 (2023). [15] Lada A Adamic and Bernardo A Huberman. 2002. Zipf’s Law and the Internet. Glottometrics 3, 1 (2002), 143–150. [16] Dávid Bajusz, Anita Rácz, and Károly Héberger. 2015. Why is Tanimoto index an appropriate choice for fingerprint-based similarity calculations? Journal of Cheminformatics 7, 1 (2015), 20. [17] Fu Bang. 2023. GPTCache: An Open-Source Semantic Cache for LLM Applications Enabling Faster Answers and Cost Savings. In Proc. of the 3rd Workshop for Natural Language Processing Open Source Software (NLP-OSS). 212–218. [18] Shai Bergman, Anne-Marie Kermarrec, Diana Petrescu, Rafael Pires, Mathis Randl, Martijn De Vos, and Ji Zhang. 2025. Leveraging Approximate Caching for Faster Retrieval-Augmented Generation. In Proc. of the 26th International Middleware Conference (MIDDLEWARE). 340–353. [19] B Barla Cambazoglu, Ismail Sengor Altingovde, Rifat Ozcan, and Özgür Ulusoy. 2012. Cache-Based Query Processing for Search Engines. ACM Transactions on the Web (TWEB) 6, 4 (2012), 1–24. [20] Zhichao Cao, Siying Dong, Sagar Vemuri, and David HC Du. 2020. Characterizing, Modeling, and Benchmarking RocksDB Key-Value Workloads at Facebook. In Proc. of 18th USENIX Conference on File and Storage Technologies (FAST). 209–223. [21] Cheng Chen, Chenzhe Jin, Yunan Zhang, Sasha Podolsky, Chun Wu, SzuPo Wang, Eric Hanson, Zhou Sun, Robert Walzer, and Jianguo Wang. 2024. SingleStore-V: An Integrated Vector Database System in SingleStore. Proc. of the VLDB Endowment 17, 12 (2024), 3772–3785. [22] Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. 2021. SPANN: Highly-efficient Billion-scale Approximate Nearest Neighborhood Search. Advances in Neural Information Processing Systems (NeurIPS) 34 (2021), 5199–5212. [23] Flavio Chierichetti, Ravi Kumar, and Sergei Vassilvitskii. 2009. Similarity Caching. In Proc. of the twenty-eighth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS). 127–136. [24] Brian F Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010. Benchmarking Cloud Serving Systems with YCSB. In Proc. of the 1st ACM symposium on Cloud Computing (SoCC). 143–154. [25] Paul Covington, Jay Adams, and Emre Sargin. 2016. Deep neural networks for YouTube recommendations. In Proc. of the 10th ACM Conference on Recommender Systems (RecSys). 191–198. [26] Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. 2026. The Faiss Library. IEEE Transactions on Big Data 12 (2026), 346–361. [27] Fabrizio Falchi, Claudio Lucchese, Salvatore Orlando, Raffaele Perego, and Fausto Rabitti. 2008. A Metric Cache for Similarity Search. In Proc. of the 2008 ACM workshop on Large-Scale Distributed Systems for Information Retrieval (LSDS-IR). 43–50. [28] Fabrizio Falchi, Claudio Lucchese, Salvatore Orlando, Raffaele Perego, and Fausto Rabitti. 2012. Similarity caching in large-scale image retrieval. Information Processing & Management 48, 5 (2012), 803–818. [29] Alessandro Finamore, James Roberts, Massimo Gallo, and Dario Rossi. 2022. Accelerating Deep Learning Classification with Error-controlled Approximate-key Caching. In Proc. of IEEE Conference on Computer Communications (INFOCOM). IEEE, 2118–2127. [30] Peizhen Guo and Wenjun Hu. 2018. Potluck: Cross-Application Approximate Deduplication for Computation-Intensive Mobile Applications. In Proc. of the 23rd International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). 271–284. [31] Junhyeok Jang, Hanjin Choi, Hanyeoreum Bae, Seungjun Lee, Miryeong Kwon, and Myoungsoo Jung. 2023. CXL-ANNS: Software-Hardware Collaborative Memory Disaggregation and Computation for Billion-Scale Approximate Nearest Neighbor Search. In Proc. of 2023 USENIX Annual Technical Conference (ATC). 585–600. [32] Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. Advances in Neural Information

Processing Systems (NeurIPS) 32 (2019). [33] Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. 2023. Mistral 7B. arXiv preprint arXiv:2310.06825 (2023). [34] Chao Jin, Zili Zhang, Xuanlin Jiang, Fangyue Liu, Shufan Liu, Xuanzhe Liu, and Xin Jin. 2025. RAGCache: Efficient Knowledge Caching for Retrieval-Augmented Generation. ACM Transactions on Computer Systems (TOCS) 44, 1 (2025), 1–27. [35] Mandar Joshi, Eunsol Choi, Daniel S Weld, and Luke Zettlemoyer. 2017. TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension. In Proc. of the 55th Annual Meeting of the Association for Computational Linguistics (ACL). 1601–1611. [36] Olzhas Kaiyrakhmet, Songyi Lee, Beomseok Nam, Sam H Noh, and Young-ri Choi. 2019. SLM-DB: Single-Level Key-Value Store with Persistent Memory. In Proc. of 17th USENIX Conference on File and Storage Technologies (FAST). 191–205. [37] Noam Koenigstein, Parikshit Ram, and Yuval Shavitt. 2012. Efficient retrieval of recommendations in a matrix factorization framework. In Proc. of the 21st ACM International Conference on Information and Knowledge Management (CIKM). 535–544. [38] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. 2020. Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks. Advances in Neural Information Processing Systems (NeurIPS) 33 (2020), 9459–9474. [39] Hui Li, Tsz Nam Chan, Man Lung Yiu, and Nikos Mamoulis. 2017. FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems. In Proc. of the 2017 ACM International Conference on Management of Data (SIGMOD). 835–850. [40] Jie Li, Haifeng Liu, Chuanghua Gui, Jianyu Chen, Zhenyuan Ni, Ning Wang, and Yuan Chen. 2018. The Design and Implementation of a Real Time Visual Search System on JD E-commerce Platform. In Proc. of the 19th International Middleware Conference Industry (MIDDLEWARE). 9–16. [41] Defu Lian, Haoyu Wang, Zheng Liu, Jianxun Lian, Enhong Chen, and Xing Xie. 2020. LightRec: A Memory and Search-Efficient Recommender System. In Proc. of The Web Conference 2020 (WWW). 695–705. [42] Xuchuan Luo, Pengfei Zuo, Jiacheng Shen, Jiazhen Gu, Xin Wang, Michael R Lyu, and Yangfan Zhou. 2023. SMART: A High-Performance Adaptive Radix Tree for Disaggregated Memory. In Proc. of 17th USENIX Symposium on Operating Systems Design and Implementation (OSDI). 553–571. [43] Craig Macdonald and Nicola Tonellotto. 2021. On Approximate Nearest Neighbour Selection for Multi-Stage Dense Retrieval. In Proc. of the 30th ACM International Conference on Information & Knowledge Management (CIKM). 3318–3322. [44] Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE transactions on Pattern Analysis and Machine Intelligence 42, 4 (2018), 824–836. [45] Sandeep Pandey, Andrei Broder, Flavio Chierichetti, Vanja Josifovski, Ravi Kumar, and Sergei Vassilvitskii. 2009. Nearest-Neighbor Caching for Content-Match Applications. In Proc. of the 18th International Conference on World Wide Web (WWW). 441–450. [46] Jie Ren, Minjia Zhang, and Dong Li. 2020. HM-ANN: Efficient Billion-Point Nearest Neighbor Search on Heterogeneous Memory. Advances in Neural Information Processing Systems (NeurIPS) 33 (2020), 10672–10684. [47] Tareq Si Salem, Giovanni Neglia, and Damiano Carra. 2022. Ascent Similarity Caching with Approximate Indexes. IEEE/ACM Transactions on Networking 31, 3 (2022), 1173–1186. [48] Subhadeep Sarkar, Dimitris Staratzis, Zichen Zhu, and Manos Athanassoulis. 2021. Constructing and Analyzing the LSM Compaction Design Space. Proc. of the VLDB Endowment 14, 11 (2021), 2216–2229. [49] Surya Selvam, Ravi K. Rajendran, Murugan Sankaradas, Anand Raghunathan, and Srimat T. Chakradhar. 2025. SimCache: Similarity Caching for Efficient VLM-based Scene Understanding. In Proc. of IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW). 3318–3327. [50] Michael Shen, Muhammad Umar, Kiwan Maeng, G Edward Suh, and Udit Gupta. 2025. Hermes: Algorithm-System Co-design for Efficient Retrieval-Augmented Generation At-Scale. In Proc. of the 52nd Annual International Symposium on Computer Architecture (ISCA). 958–973. [51] Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. 2021. FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search. arXiv preprint arXiv:2105.09613 (2021). [52] Jaime Teevan, Eytan Adar, Rosie Jones, and Michael AS Potts. 2007. Information re-retrieval: repeat queries in Yahoo’s logs. In Proc. of the 30th Annual International ACM SIGIR conference on Research and Development in Information Retrieval (SIGIR). 151–158. [53] Bing Tian, Haikun Liu, Zhuohui Duan, Xiaofei Liao, Hai Jin, and Yu Zhang. 2024. Scalable Billion-point Approximate Nearest Neighbor Search Using SmartSSDs. In Proc. of 2024 USENIX Annual Technical Conference (ATC). 1135–1150.

[54] Bing Tian, Haikun Liu, Yuhang Tang, Shihai Xiao, Zhuohui Duan, Xiaofei Liao, Hai Jin, Xuecang Zhang, Junhua Zhu, and Yu Zhang. 2025. Towards Highthroughput and Low-latency Billion-scale Vector Search via CPU/GPU Collaborative Filtering and Re-ranking. In Proc. of 23rd USENIX Conference on File and Storage Technologies (FAST). 171–185. [55] Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, et al. 2021. Milvus: A Purpose-Built Vector Data Management System. In Proc. of the 2021 International Conference on Management of Data (SIGMOD). 2614–2627. [56] Mengzhao Wang, Weizhi Xu, Xiaomeng Yi, Songlin Wu, Zhangyang Peng, Xiangyu Ke, Yunjun Gao, Xiaoliang Xu, Rentong Guo, and Charles Xie. 2024. Starling: An I/O-efficient Disk-Resident Graph Index Framework for HighDimensional Vector Similarity Search on Data Segment. Proc. of the ACM on Management of Data (PACMMOD) 2, 1 (2024), 1–27. [57] Chuangxian Wei, Bin Wu, Sheng Wang, Renjie Lou, Chaoqun Zhan, Feifei Li, and Yuanzhe Cai. 2020. AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data. Proc. of the VLDB Endowment 13, 12 (2020), 3152–3165. [58] Shitao Xiao, Zheng Liu, Weihao Han, Jianjin Zhang, Yingxia Shao, Defu Lian, Chaozhuo Li, Hao Sun, Denvy Deng, Liangjie Zhang, et al. 2022. Progressively Optimized Bi-Granular Document Representation for Scalable Embedding Based Retrieval. In Proc. of the ACM Web Conference 2022 (WWW). 286–296. [59] Shitao Xiao, Zheng Liu, Peitian Zhang, Niklas Muennighoff, Defu Lian, and JianYun Nie. 2024. C-Pack: Packed Resources for General Chinese Embeddings. In Proc. of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR). 641–649. [60] Yuming Xu, Hengyu Liang, Jin Li, Shuotao Xu, Qi Chen, Qianxi Zhang, Cheng Li, Ziyue Yang, Fan Yang, Yuqing Yang, et al. 2023. SPFresh: Incremental InPlace Update for Billion-Scale Vector Search. In Proc. of the ACM SIGOPS 29th Symposium on Operating Systems Principles (SOSP). 545–561. [61] Juncheng Yang, Yao Yue, and KV Rashmi. 2021. A Large-scale Analysis of Hundreds of In-memory Key-value Cache Clusters at Twitter. ACM Transactions on Storage (TOS) 17, 3 (2021), 1–35. [62] Wen Yang, Tao Li, Gai Fang, and Hong Wei. 2020. PASE: PostgreSQL Ultra-HighDimensional Approximate Nearest Neighbor Search Extension. In Proc. of the 2020 ACM SIGMOD International Conference on Management of Data (SIGMOD). 2241–2253. [63] Xizhe Yin, Chao Gao, Zhijia Zhao, and Rajiv Gupta. 2025. PANNS: Enhancing Graph-based Approximate Nearest Neighbor Search through Recency-aware Construction and Parameterized Search. In Proc. of the 30th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PPoPP). 369–381. [64] Qiang Zhang, Yongkun Li, Patrick PC Lee, Yinlong Xu, and Si Wu. 2022. DEPART: Replica Decoupling for Distributed Key-Value Storage. In Proc. of 20th USENIX Conference on File and Storage Technologies (FAST). 397–412. [65] Yijie Zhou, Shengyuan Lin, Shufeng Gong, Song Yu, Shuhao Fan, Yanfeng Zhang, and Ge Yu. 2025. GoVector: An I/O-Efficient Caching Strategy for HighDimensional Vector Nearest Neighbor Search. arXiv preprint arXiv:2508.15694 (2025).

Related documents

• Aker: Density-Aware Approximate Caching for Vector Search (Extended Version)#926604
• GateANN: I/O-Efficient Filtered Vector Search on SSDs#2717
• Onyx: Cost-Efficient Disk-Oblivious ANN Search#123957
• OnlineCache: Learning Dynamic Caching Policies with Error Correction for Efficient Diffusion Inference#422263
• Effectiveness and predictability of in-network storage cache for Scientific Workflows#1038674