arXiv CSopen access

GateANN: I/O-Efficient Filtered Vector Search on SSDs

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

operating systems, kernel, virtualization

GateANN: I/O-Eﬃcient Filtered Vector Search on SSDs Nakyung Lee∗, Soobin Cho∗ , Jiwoong Park, Gyuyeong Kim† Sungshin Women’s University

arXiv:2603.21466v2 [cs.OS] 26 Mar 2026

Abstract

A natural alternative is pre-ﬁltering that checks the ﬁlter before issuing I/O and skips non-matching nodes. However, the characteristic of graph search makes this diﬃcult, because a visited node is both a candidate result and a routing state whose neighbors guide the search. Skipping a nonmatching node can therefore disconnect important traversal paths, sharply reducing performance and recall. The core challenge is that non-matching nodes are useless as results, yet often essential for traversal. Prior work on ﬁltered search [3] addresses this challenge by building a ﬁlter-aware graph index. This improves I/O efﬁciency, but at the cost of ﬂexibility. They require expensive index rebuilds when the ﬁlter schema changes, and are typically limited to a ﬁxed class of predicates such as equality ﬁlters. They do not naturally support ad-hoc predicates such as subset conditions over multi-label metadata or range predicates over continuous attributes. As a result, existing SSDbased systems remain stuck between two undesirable choices: either waste SSD I/O with post-ﬁltering, or rebuild specialized indexes for restricted predicate types. In this context, we ask the following question: Can we achieve I/O eﬃciency for ﬁltered vector search on an unmodiﬁed graph index while supporting any ﬁlter predicates? To answer this question aﬃrmatively, this paper introduces GateANN, an I/O-eﬃcient SSD-based graph ANNS system for ﬁltered search. Our key insight is that traversing a node requires only two pieces of information: its neighbor list and an approximate distance estimate, neither of which requires the full-precision vector stored on the SSD. Based on this, GateANN decouples graph traversal from vector retrieval by keeping the neighbor list and approximate distances in memory, enabling pre-ﬁltering without harming graph connectivity. To realize this, GateANN introduces graph tunneling: for nodes that fail the ﬁlter, the search traverses through them using only in-memory routing metadata without issuing any SSD read. This adds moderate memory overhead (e.g., 6 GB for 100M vectors), which is tunable by adjusting the number of in-memory neighbors per node. We evaluate GateANN on datasets ranging from 10M to 1B vectors with both synthetic and real multi-label metadata [21]. Across these workloads, GateANN reduces SSD I/Os by up to 10× relative to post-ﬁlter baselines and improves throughput by up to 7.6× at 10% selectivity while maintaining comparable recall. As ﬁlters become more selective, the gains grow further. GateANN also closes the gap with in-memory search: it matches or surpasses in-memory Vamana in single-thread latency despite using SSD. In summary, this paper makes the following contributions:

We present GateANN, an I/O-eﬃcient SSD-based graph ANNS system that supports ﬁltered vector search on an unmodiﬁed graph index. Existing SSD-based systems either waste I/O by post-ﬁltering, or require expensive ﬁlter-aware index rebuilds. GateANN avoids both by decoupling graph traversal from vector retrieval. Our key insight is that traversing a node requires only its neighbor list and an approximate distance, neither of which needs the full-precision vector on SSD. Based on this, GateANN introduces graph tunneling. It checks each node’s ﬁlter predicate in memory before issuing I/O and routes through non-matching nodes entirely in memory, preserving graph connectivity without any SSD read for non-matching nodes. Our experimental results show that it reduces SSD reads by up to 10× and improves throughput by up to 7.6×.

Introduction

High-dimensional vectors have become a universal representation for unstructured data across diverse applications, from recommendation systems to retrieval-augmented generation (RAG) [6, 11, 15, 19, 31], driving demand for nearestneighbor search at scale. Since exact search is prohibitively expensive, approximate nearest neighbor search (ANNS) is preferred, and graph-based indexes are widely adopted for their superior latency–recall tradeoﬀ [9, 13, 15, 17]. Recently, SSD-based graph indexes (e.g., DiskANN [22], PipeANN [4]) have made large-scale vector search practical on a single commodity server. To scale beyond memory capacity, these systems store full-precision vectors and graph topology on NVMe SSDs, retaining only compressed vectors in memory for approximate distance computation. In practice, vector search queries rarely target the entire dataset. Instead, they often restrict results using metadata predicates such as document type, time range, access-control lists, or product category. Such ﬁltered search is common in production vector databases [8, 25]. Unfortunately, existing SSD-based graph indexes use post-ﬁltering: they fetch candidate nodes from SSD, compute exact distances, and discard nodes that do not satisfy the predicate. This wastes substantial work. For example, if only 10% of the dataset matches the ﬁlter, then 90% of SSD reads and exact-distance computations are spent on data that will never appear in the ﬁnal result. Under high load, this wasted work becomes the throughput bottleneck (§2.2). ∗ Equal contribution. † Corresponding author. Code https://github.com/GyuyeongKim/GateANN-public.

available

at 1

PipeANN

103

102

Post-filter Naive pre-filter

104

1 4 8

Threads

(a) Throughput scaling.

103 0.0

0.5

Recall@10

1.0

(b) Post-ﬁlter vs. naïve pre-ﬁlter.

Figure 1. Motivating experiments on BigANN-100M with 10% selectivity. (a) Post-ﬁltering systems plateau early because of wasted per-node work. (b) Naïve pre-ﬁltering destroys graph connectivity, degrading throughput and recall.

Background and Motivation

We begin by reviewing SSD-based graph ANNS (§2.1), then explain the I/O dilemma in ﬁltered vector search (§2.2). We next motivate the need for I/O-eﬃcient pre-ﬁltering on unmodiﬁed graph indexes (§2.3).

2.1

DiskANN

Throughput (QPS)

• We identify the fundamental tension in ﬁltered SSD-based graph search: post-ﬁltering wastes SSD I/O and computation, while naive pre-ﬁltering breaks graph connectivity and collapses recall (§2). • We present GateANN, which decouples graph traversal from vector retrieval through pre-I/O ﬁlter checking and graph tunneling, enabling I/O-eﬃcient ﬁltered search on an unmodiﬁed graph index (§3). • We evaluate GateANN on datasets from 10M to 1B vectors with synthetic and real metadata, showing up to 10× fewer SSD I/Os and up to 7.6× higher throughput than SSD-based post-ﬁlter baselines at comparable recall (§5).

2.2 The I/O Dilemma in Filtered Vector Search Filtered vector search is common. Production queries rarely search the entire dataset. Enterprise RAG restricts by document type and access control, legal search ﬁlters by jurisdiction and time range, and e-commerce search narrows by product category. Such metadata predicates are pervasive in practice [8, 18, 25, 33]. We deﬁne the selectivity 𝑠 of a ﬁlter as the fraction of the dataset that satisﬁes it. Selectivities in the 1–10% range are common in both benchmark and production settings [10, 16, 35]. Post-ﬁltering is general, but wastes SSD I/O. Existing SSD-based graph ANNS systems such as DiskANN and PipeANN handle ﬁlters by post-ﬁltering: they fetch every candidate node from SSD and only then check whether the node satisﬁes the predicate. This approach is general and indexagnostic, but it pays full per-node cost—SSD I/O, exact distance computation, and candidate management—regardless of whether the node matches the ﬁlter. This means that, for example, at selectivity 𝑠 = 0.1, 90% of SSD reads are wasted on fetching non-matching nodes that cannot appear in the ﬁnal result. This waste becomes costly under multi-threads. In Figure 1 (a), we can see that PipeANN outperforms DiskANN by overlapping I/O and computation across the number of threads. However, as concurrency increases, they converge on similar throughput because both ultimately spend most of their budget processing nodes that fail the ﬁlter. Naïve pre-ﬁltering saves I/O, but breaks graph search. A natural alternative is to push the predicate before I/O and skip nodes that fail the ﬁlter. However, this is fundamentally problematic for graph search: non-matching nodes are not only poor result candidates, but also routing states that connect the search to other regions of the graph. Skipping their expansion prevents the search from reaching their neighbors, even when those neighbors match the predicate. Because many paths between matching nodes pass through non-matching nodes, pre-ﬁltering fragments the graph over

SSD-Based Graph ANNS

Graph-based approximate nearest neighbor search (ANNS) organizes vectors as a proximity graph, where each vector is a node and edges connect approximate neighbors. Given a query, the search starts from an entry point and greedily traverses toward nodes that appear progressively closer to the query, returning the closest visited nodes as approximate nearest neighbors [4, 15, 22]. At the billion scale, storing full-precision vectors in memory is often infeasible on a commodity server [9, 23, 24, 28, 30]. For example, storing 128-dimensional ﬂoat32 vectors together with a degree-64 graph at a scale of one billion points requires approximately 768 GB of memory, far exceeding the memory capacity of a commodity server. This motivates SSD-based graph ANNS systems such as DiskANN [22] that place node records on NVMe SSDs while keeping only compressed vectors in memory using Product Quantization (PQ) for approximate distance estimation. In DiskANN, each node occupies a 4 KB-aligned record containing its full-precision vector and neighbor list. Search proceeds in rounds: the system selects a beam of promising candidates, issues SSD reads for them, waits for the batch to ﬁnish, and then continues. PipeANN [4] improves over this batch-and-wait design by using io_uring to pipeline reads asynchronously. Instead of waiting for an entire batch, it continuously submits reads, polls completions, and processes nodes while keeping many I/Os in ﬂight. This overlap substantially improves throughput. However, in both systems, graph traversal still incurs a random SSD read for every expanded node, and each read costs tens to hundreds of microseconds. As a result, pernode SSD I/O remains the dominant cost. 2

SSD

useless

!!"#$"

SSD

useful

unvisited match pre-built subgraph

SSD

E SSD

SSD

(a) Post-ﬁltering

! !"#$"

(b) Filter-aware index

MEM

E MEM

GateANN

memory for approximate distance computation. However, the neighbor list is tightly coupled with full-precision vectors in SSDs. Since neighbor lists are lightweight compared to the full vectors, they can be maintained entirely in memory at a fraction of the cost of full-precision vectors. Our approach. By leveraging the above insight, GateANN decouples graph traversal from vector retrieval by maintaining a compact neighbor list in memory. Before issuing any SSD I/O, GateANN checks each candidate node’s ﬁlter predicate against this in-memory metadata. Nodes that do not satisfy the predicate are traversed purely in memory, preserving graph connectivity without incurring a disk read. Nodes that do satisfy the predicate trigger an SSD fetch for exact distance computation. Because GateANN operates directly on the original graph rather than a rebuilt, ﬁlter-speciﬁc index, it supports arbitrary predicates without any index modiﬁcation. Trade-oﬀ. This design introduces a deliberate memory–I/O trade-oﬀ. Avoiding SSD reads for ﬁlter-failing nodes requires storing neighbor lists in memory. At billion scale, the additional memory footprint is about 63 GB at the default setting, and can be reduced to 34 GB with fewer neighbors or increased to 123 GB for better tunneling quality. This overhead is practical on commodity servers with 128–512 GB of memory, and is attractive because SSD access is more expensive than in-memory traversal. Moreover, the overhead is tunable. Operators can retain fewer neighbors per node to reduce memory usage, trading some tunneling quality for a smaller memory footprint while still outperforming postﬁltering baselines (§5.4.2). Comparison to existing works. Figure 2 and Table 1 summarize how GateANN diﬀers from prior approaches. Postﬁltering in Figure 2 (a) reads every traversed node from SSD and applies the predicate only afterward, so non-matching nodes still incur full I/O and distance computation. A ﬁlteraware index in Figure 2 (b) pre-builds label-speciﬁc subgraphs to conﬁne traversal to matching nodes, reducing wasted I/O but requiring an index rebuild whenever the label changes. GateANN in Figure 2 (c) checks the predicate before I/O on the original graph: matching nodes follow the normal SSD path, while non-matching nodes are traversed in memory. This preserves graph connectivity and eliminates SSD I/O for ﬁlter-failing nodes, without restricting the predicate or rebuilding the index.

Figure 2. Diﬀerent approaches for ﬁltered vector search. matching nodes into many small disconnected components, particularly at low selectivity. Figure 1(b) conﬁrms this. At the same throughput, naïve pre-ﬁltering achieves much lower recall than post-ﬁltering, and its maximum recall plateaus at ∼57% even at 2.7K QPS, compared to >99% for post-ﬁltering. Increasing the search list size 𝐿 cannot overcome this limitation since unreachable components remain invisible regardless of how many candidates the traversal explores. Filter-aware indexes improve eﬃciency, but sacriﬁce ﬂexibility. Prior work on ﬁltered search incorporates label information directly into the index structure. For example, Filtered-DiskANN (F-DiskANN )[3] augments the graph with label-aware connectivity and entry points, reducing unnecessary I/O. However, they require the label space to be known at build time. Supporting a new predicate or changing the taxonomy requires rebuilding the index, which can take days at the billion scale. They also cannot handle adhoc predicates such as subset predicates over multi-label metadata or range predicates over continuous attributes. 2.3

F-DiskANN [3]

Filter type Post-ﬁltering Filter-aware Index pre-ﬁltering √ I/O-eﬃcient × △ √ √ Any ﬁlter predicates × √ √ No index rebuild ×

PipeANN [4]

C D

SSD

Table 1. Comparison with existing works. △: partial (reduces but does not eliminate I/O for non-matching nodes).

tunneling

C D

MEM

!!"#$"

A SSD

non-match

Toward I/O-Eﬃcient Pre-ﬁltering

Rethinking why pre-ﬁltering seems impractical. Prior work has regarded pre-I/O ﬁlter checking as incompatible with graph search, because skipping a non-matching node appears to discard not only a bad result candidate but also a useful routing state. This leaves an all-or-nothing choice: either fetch every visited node from SSD and apply postﬁltering, or skip non-matching nodes and risk losing graph connectivity. The problem is not pre-ﬁltering itself, but the coupling between traversal and I/O in existing systems. Today, a node’s neighbor list is stored alongside its vector in a single disk sector; the only way to discover a node’s neighbors is to read that sector from SSD. This means that even determining the next traversal hop requires a disk I/O, regardless of whether the node matches the ﬁlter. Insight: the missing piece is already small. Graph traversal requires only two types of information per node: a neighbor list and an approximate distance estimate. Existing SSD-based systems already keep compressed vectors in 3

Figure 3. GateANN overview. A candidate is ﬁrst checked against the in-memory ﬁlter store. Filter-passing nodes follow the normal SSD path: an asynchronous read followed by exact distance computation. Filter-failing nodes are routed to the graph tunneling path: the neighbor store provides the adjacency list, PQ distances are computed in memory, and promising neighbors are inserted back into the candidate list. Both paths feed into the same sorted frontier.

GateANN Design

scales with metadata size: a single-label equality ﬁlter requires one byte per node (100 MB at 𝑁 =100M), while richer multi-label metadata requires more but remains a small fraction of the overall memory budget. GateANN places this check at the earliest point in the search pipeline, before both hot-node cache lookup and SSD submission. This placement is deliberate: a node that fails the ﬁlter should incur neither SSD I/O nor exact distance computation, so checking the predicate ﬁrst removes all unnecessary work on non-matching nodes, not just SSD reads. Neighbor store. The second component is the neighbor store, which replicates each node’s adjacency list from the on-disk graph into memory. Its purpose is to enable tunneling. When a node fails the ﬁlter, the search needs to access the node’s neighbors to continue traversal, but the neighbors are normally embedded in the node’s SSD record alongside the fullprecision vector. The neighbor store extracts just the adjacency information—a list of up to 𝑅max neighbor IDs per node—so that tunneling can proceed without any SSD read. Like the ﬁlter store, the neighbor store is built at load time from the existing on-disk index and does not modify it. Because each node in the Vamana graph stores neighbors in order of proximity, retaining the ﬁrst 𝑅max entries preserves the closest and most useful neighbors for routing. The structure supports 𝑂 (1) lookup by node ID, ensuring that tunneling adds negligible latency compared to the SSD read it replaces.

3.1 Overview Figure 3 shows the architecture of GateANN. The central design principle is to separate graph traversal from vector retrieval: whether a node’s full-precision vector is fetched from SSD should depend on whether the node can contribute to the query result, not on whether the node lies on the search path. GateANN realizes this by inserting a ﬁlter-aware dispatch stage into the asynchronous search pipeline. Each candidate is dispatched to one of two paths based on a lightweight in-memory predicate check. The two paths diﬀer only in how a node is processed—both feed candidates into the same sorted frontier, so the rest of the search algorithm is unaffected. This preserves the asynchronous I/O pipeline [4] intact while ensuring that every SSD read serves a node that can appear in the ﬁnal result. The following subsections describe each component in detail. 3.2 Key Components Filter store. The ﬁrst component is the ﬁlter store, a memoryresident structure that holds each node’s ﬁlter metadata and supports 𝑂 (1) predicate evaluation by node ID. The key design goal is to make every ﬁlter decision before any I/O, so that the system never pays the cost of an SSD read for a node that cannot contribute to the result. The ﬁlter store is intentionally decoupled from the graph index: it is loaded from a separate metadata ﬁle and can be replaced independently. This separation is what enables GateANN to support arbitrary predicates—equality, range, multi-label subset, or conjunctions thereof—without rebuilding the graph. Adding a new predicate type only requires providing the corresponding metadata; the graph index and the search algorithm remain unchanged. The memory cost

3.3 Graph Tunneling Why tunneling? When a candidate fails the ﬁlter, the search must still be able to move through it. Otherwise, the traversal would stop at the boundary of a ﬁltered-out region. GateANN addresses this by tunneling through the node in memory rather than fetching its vector from SSD. 4

Algorithm 1 GateANN search loop (simpliﬁed). Require: Query 𝑞, ﬁlter predicate 𝑓 , search list size 𝐿, result size 𝐾, I/O width 𝑊 1: C ← sorted candidate frontier, initialized with the entry point 2: Q ← ∅ ⊲ in-ﬂight SSD reads 3: while C has undispatched candidates or Q ≠ ∅ do 4: while |Q| < 𝑊 and C has an undispatched candidate do 5: 𝑐 ← best undispatched candidate in C 6: if ﬁlter_store[𝑐] satisﬁes 𝑓 then 7: Submit asynchronous read for 𝑐’s SSD record 8: Add 𝑐 to Q and mark 𝑐 as dispatched 9: else 10: nbrs ← neighbor_store[𝑐] 11: for each unvisited 𝑛 ∈ nbrs do 12: 𝑑𝑛 ← PQ_dist(𝑞, 𝑛) 13: if 𝑑𝑛 improves the frontier threshold then 14: Insert (𝑛, 𝑑𝑛 ) into C 15: end if 16: end for 17: Mark 𝑐 as visited and ﬁlter-failing 18: end if 19: end while 20: for each completed read 𝑟 returned by the SSD do 21: Compute the exact distance for 𝑟 22: Expand 𝑟 ’s neighbors from the returned SSD record 23: Insert promising neighbors into C 24: Remove 𝑟 from Q and mark 𝑟 as visited 25: end for 26: end while 27: return top-𝐾 ﬁlter-passing candidates from C

Figure 4. Graph tunneling example. ➊ Node 𝐵 passes the ﬁlter and follows the normal SSD path. ➋ Node 𝐶 is selected next but fails the ﬁlter check. ➌ GateANN reads 𝐶’s neighbors (𝑁 1 –𝑁 4 ) from the neighbor store in memory. ➍ PQ distances to the query are computed for each neighbor; neighbors below the frontier threshold (here 0.45) are kept (𝑁 1 , 𝑁 3 ) and the rest (𝑁 2 , 𝑁 4 ) are discarded. ➎ Promising neighbors are inserted into the candidate list, and 𝐶 is marked visited but ineligible for results. The key observation behind tunneling is that each node in a graph search serves two distinct roles: it is a result candidate that may appear in the ﬁnal top-𝐾, and a routing waypoint whose edges connect the search to other regions of the graph. Post-ﬁltering conﬂates these roles, since every visited node is fetched from SSD regardless of whether it contributes to the result. Tunneling separates them: a node that fails the ﬁlter can never be a result candidate, so it only needs to fulﬁll its waypoint role. Fulﬁlling the waypoint role requires only the node’s adjacency list and approximate (PQ) distances, both of which reside in memory. This separation is eﬀective because of a large cost asymmetry between the two paths. An SSD random read takes on the order of 100 𝜇s, while a neighbor store lookup and PQ distance computation complete in sub-microsecond time— roughly two orders of magnitude faster. Tunneling therefore replaces the most expensive per-node operation with one that is ∼100× cheaper, and the beneﬁt scales with the fraction of visited nodes that fail the ﬁlter. This also clariﬁes the diﬀerence from naïve pre-ﬁltering, which simply skips non-matching nodes without expanding their neighbors. Skipping breaks graph connectivity: if many consecutive nodes fail the ﬁlter, the search frontier becomes disconnected and recall collapses (as shown in §2). Tunneling avoids this by preserving neighbor expansion—it eliminates only the SSD read, not the graph traversal step. The search can therefore cross arbitrarily long non-matching regions through a sequence of cheap in-memory hops. Example. Figure 4 shows an example. The search has reached node 𝐴 from query 𝑄, and the candidate list is [𝐶, 𝐴, 𝐵, 𝐷]. Node 𝐵, the next unvisited candidate, passes the ﬁlter and follows the normal SSD path (➊). The search then selects

node 𝐶, which fails the ﬁlter (➋). Rather than issuing an SSD read, the system tunnels through 𝐶 entirely in memory: it reads 𝐶’s neighbors from the neighbor store (➌), scores them with PQ distances (➍), and inserts the promising ones into the candidate list (➎). The candidate list is updated to [𝑁 1 , 𝑁 3 , 𝐶, 𝐷], and the search continues from 𝑁 1 . Note that the net eﬀect is that 𝐶 served as a routing waypoint—connecting the search to new candidates 𝑁 1 and 𝑁 3 . Putting it together. Algorithm 1 summarizes the integrated search loop. The important structural property is that both paths, SSD retrieval and in-memory tunneling, feed candidates into the same sorted frontier. The rest of the search remains unchanged: the algorithm repeatedly selects promising frontier nodes, expands them, and returns the top-𝐾 ﬁlter-passing candidates. 3.4 Design Implications and Trade-oﬀs Approximate distances for tunneling. Graph tunneling uses PQ distances rather than exact distances from full vectors. This is acceptable because traversal only needs a good priority signal to decide which neighbors to explore next, not the precise ranking required for the ﬁnal result set. PQ distances are used solely to order frontier expansion; ﬁnal 5

Table 2. Memory overhead for 𝑁 -size datasets.

Table 3. Datasets used in evaluation.

Component

Formula

Size (100M)

Size (1B)

Filter store (single-label) Filter store (multi-label) Neighbor store (𝑅max = 16)

𝑁B varies 𝑁 · 17 · 4 B

100 MB ∼900 MB 6.3 GB

1 GB ∼9 GB 63 GB

PQ vectors (baseline)

𝑁 · 32 B

3.2 GB

32 GB

Dataset BigANN-100M DEEP-100M YFCC-10M BigANN-1B

results are always drawn from ﬁlter-passing nodes evaluated with exact distances. Two factors may aﬀect tunneling quality. First, tunneled nodes are prioritized with PQ distances rather than exact distances. Second, when 𝑅max < 𝑅, the in-memory adjacency contains only a subset of each node’s neighbors, potentially missing some routing paths. Both inﬂuence which routes the search explores ﬁrst, but neither changes the ﬁnalresult rule above. PQ errors also do not accumulate across hops in the way path-based approximation might suggest. Each candidate is rescored independently against the original query, and the frontier is globally resorted after every expansion. An approximation at one hop may alter the frontier ordering temporarily, but it does not propagate as a chained numerical error. When needed, the system can compensate by modestly increasing the search list size 𝐿, and we evaluate that trade-oﬀ in §5. Consecutive non-matching nodes. At low selectivity, a tunneled node often exposes neighbors that also fail the ﬁlter. GateANN handles this case naturally. If a neighbor later becomes the best frontier candidate and still fails the ﬁlter, the system tunnels through it as well. In this way, singlehop tunneling composes into multi-hop traversal without any special multi-hop operator. This design has two advantages. First, it avoids materializing all nodes within multiple hops of a ﬁltered region, which would grow the work exponentially. Second, it lets the frontier be re-ranked after every hop, preserving the best-ﬁrst character of the search. The algorithm therefore moves through long ﬁltered regions as a sequence of cheap in-memory expansions rather than a single large speculative expansion. Long non-matching stretches are a workload-dependent challenge. If ﬁlter predicates are strongly correlated with graph locality, the search may need to cross larger ﬁltered regions before reaching matching nodes, which can require a larger frontier or a larger 𝑅max to maintain recall. We explicitly investigate these cases in the evaluation rather than assuming label independence. Memory overhead. The additional memory cost is the neighbor store: MEMneighbor = 𝑁 × (1 + 𝑅max ) × 4 bytes,

Vectors

Dim

Type

Labels

100M 100M 10M 1B

128 96 192 128

uint8 ﬂoat uint8 uint8

synth., 10 classes synth., 10 classes real, ∼200K tags synth., 10 classes

representative sizes for 𝑁 = 100M and 1B. Combined with the PQ vectors already kept by the baseline and a modest ﬁlter store, the total memory footprint remains practical on commodity servers. GateANN treats 𝑅max as a runtime parameter, not an indexbuild parameter: the neighbor store is constructed at load time by scanning the on-disk graph and extracting the ﬁrst 𝑅max neighbors of each node, without modifying the index itself. Operators can therefore adjust 𝑅max freely across deployments or restarts without rebuilding the graph, unlike ﬁlter-aware indexes, which bake ﬁlter structure into the graph at build time. Larger values improve tunneling quality by exposing more candidate routes through non-matching regions, while smaller values reduce memory footprint and per-node in-memory work.

4 Implementation We implement GateANN in C++ by extending the PipeANN codebase [4]. The implementation adds two read-only metadata structures and modiﬁes the candidate dispatch path in PipeANN’s asynchronous search loop. Filter store. The ﬁlter store is allocated at index load time from a separate metadata ﬁle and is indexed by node ID. For single-label predicates, each entry stores a ﬁxed-width label. For multi-label predicates, each entry stores the metadata needed for in-memory predicate evaluation, loaded from a sparse matrix representation. The structure is read-only during search and shared across all query threads. Neighbor store. The neighbor store stores up to 𝑅max neighbors per node in a contiguous array with ﬁxed stride. It is built at load time by a sequential scan over the on-disk graph. We allocate it with mmap and MAP_POPULATE so that its pages are materialized before query processing begins. Like the ﬁlter store, the neighbor store is read-only and shared across query threads. Search loop integration. GateANN inserts the ﬁlter check before PipeANN’s SSD submission path. Candidates that satisfy the predicate follow the original path unchanged. Candidates that fail the predicate are expanded through the neighbor store using PipeANN’s existing PQ distance computation and candidate insertion routines. The I/O completion path, io_uring submission and completion logic, and PQ infrastructure are otherwise unchanged.

(1)

where 𝑁 is the number of nodes and 𝑅max is the number of in-memory neighbors retained per node. Table 2 shows 6

100

101

Latency (ms)

102

(a) BigANN-100M: Recall vs. Latency

1.0

104 103 0.7

0.8

0.9

Recall@10

0.9 0.8 0.7

1.0

Throughput (QPS)

0.8

105 Recall@10

GateANN

Throughput (QPS)

Recall@10

1.0

DiskANN PipeANN

100

101

Latency (ms)

(b) BigANN-100M: QPS vs. Recall

102

105 104 103 0.7

0.8

0.9

Recall@10

1.0

(d) DEEP-100M: QPS vs. Recall

Figure 5. Recall–latency (1 thread) and throughput–recall (32 threads) tradeoﬀ curves on 100M-scale datasets. GateANN consistently outperforms both PipeANN and DiskANN across the entire recall range.

Evaluation

thread (CPU-pinned via taskset) to isolate per-query search eﬃciency without inter-thread contention; throughput experiments use 32 threads to stress the I/O pipeline. Default selectivity is 10% unless stated otherwise.

5.1 Methodology Testbed. All experiments run on a single server with two Intel Xeon Silver 4514Y CPUs (Sapphire Rapids, 32 physical cores supporting 64 logical cores), 256 GB DDR5, and a Samsung PM9A3 2 TB NVMe SSD (Gen4). For §5.4.3, we additionally use a Samsung 9100 PRO 4 TB NVMe SSD (Gen5). The server runs Ubuntu 22.04 with Linux kernel 5.15. Datasets. Table 3 summarizes the used datasets. BigANN100M and DEEP-100M use synthetic, uniform 10-class labels, modeling the common category-based ﬁltering scenario. YFCC-10M [21] uses real multi-label metadata (∼200K tag vocabulary) with variable per-query selectivity. BigANN-1B validates scalability to billion-scale workloads. Compared systems. We compare ﬁve systems:

5.2 Main Results 5.2.1 Overall Performance Figure 5 shows the recall–latency and throughput–recall tradeoﬀ curves on BigANN-100M and DEEP-100M. Each point corresponds to a diﬀerent search list size 𝐿. Latency. On BigANN-100M, GateANN achieves ∼0.77 ms mean latency at 90% recall, which is 1.9× faster than PipeANN and 13.0× faster than DiskANN. The improvement is most pronounced at moderate recall targets (60–85%), where the majority of visited candidates fail the ﬁlter and are resolved entirely via in-memory tunneling. At high recall larger than 95%, GateANN remains faster than all baselines, though the gap narrows as the absolute number of ﬁlter-passing I/Os grows. On DEEP-100M, the trend holds with slightly larger absolute latencies due to DEEP’s ﬂoat32 vectors (384 bytes per vector vs. BigANN’s 128 bytes), which increase the CPU cost of each exact distance computation without aﬀecting GateANN’s I/O elimination. Throughput. GateANN achieves ∼16.0K QPS at 90% recall on BigANN-100M, compared to ∼2.1K for PipeANN, a 7.6× improvement. The throughput advantage exceeds the latency advantage because 32 threads share a ﬁxed CPU-side I/O processing budget: each SSD read triggers not only a disk access but also sector parsing, exact distance computation, and candidate management (§5.4.4). The I/O reduction in GateANN frees this budget, enabling throughput to scale with the number of threads rather than per-I/O overhead. The advantage persists across the recall. For example, at 95% recall, GateANN sustains a 6.9× throughput gap.

• DiskANN [22]: synchronous beam search (𝑊 =8). • PipeANN [4]: asynchronous pipelined search (𝑊 =32). • GateANN: asynchronous pipelined search with pre-I/O ﬁlter checking and graph tunneling (𝑊 =32, 𝑅max =32). • Vamana [22]: in-memory graph search (no SSD). • F-DiskANN [3]: ﬁlter-aware graph index with per-label medoids and hard candidate ﬁltering. DiskANN, PipeANN, and GateANN search the same standard Vamana graph index built with graph degree 𝑅=96 and build-time search list 𝐿build =128, with PQ compression (32 chunks). F-DiskANN uses a diﬀerent index built by FilteredVamana, a label-aware construction that embeds ﬁlter information into the graph structure. Note that 𝑊 has diﬀerent semantics across systems: in DiskANN it is the synchronous beam width (all 𝑊 reads must complete before the next round), while in PipeANN and GateANN it is the asynchronous pipeline depth (up to 𝑊 concurrent in-ﬂight I/Os). We follow each system’s recommended settings, as in the PipeANN paper [4]. §5.4.8 shows that GateANN’s throughput plateaus at 𝑊 ≥8, so the speciﬁc choice of 𝑊 =32 does not inﬂate our results. Metrics. We report Recall@10, throughput (QPS), mean latency, and mean SSD I/Os per query. The search list size 𝐿 is swept to trace Pareto curves. Latency experiments use 1 7

5.2.2 Scalability Figure 6 shows throughput from 1 to 32 threads at 𝐿=200. PipeANN plateaus at 8 threads (QPS at 8, 16, and 32 threads are virtually identical at ∼2.1K). DiskANN reaches ∼1.84K

PipeANN

Ga eANN

1.0

Recall@10

104

0.9

103 102

Throughput (QPS)

Throughpu (QPS)

DiskANN

104

DiskANN PipeANN GateANN

0.8

0.7

Number of hreads

Latency (ms)

103

100

(a) Recall vs. Latency (1 thread)

40 30 20

200 0

10.2×

200

400

Search list size L

(a) Mean I/Os per query vs. 𝐿.

10%

Selectivity

1.0

PipeANN GateANN

104 103

5.1×

102

20%

101 0.5

(b) I/O reduction vs. selectivity.

0.6

0.7

0.8

Recall@10

0.9

1.0

Figure 9. Throughput–recall tradeoﬀ curves on YFCC-10M with real multi-label ﬁlters (subset predicate).

Figure 7. I/O reduction on BigANN-100M. (a) GateANN issues far fewer I/Os than PipeANN. (b) The measured reduction closely follows the theoretical expectation of 1/𝑠.

the I/O reduction is a structural property of the ﬁlter mechanism, not an artifact of a particular 𝐿. Figure 7 (b) compares the measured reduction ratio against the expected 1/𝑠 at three selectivities: 20.5× at 5% (expected: 20×), 10.2× at 10% (expected: 10×), and 5.1× at 20% (expected: 5×). The close match validates that pre-I/O ﬁlter checking with graph tunneling achieves the optimal I/O count without sacriﬁcing graph connectivity.

QPS at 32 threads, an 18× ratio from 1 thread, but ultimately hitting the same ceiling. Both baselines converge despite PipeANN’s 6.7× single-thread advantage, because, at high concurrency, both saturate the same aggregate I/O processing budget of ∼430K IOPS. GateANN breaks through this ceiling by eliminating 90% of I/Os and the per-node overhead that accompanies each one. At 1 thread, GateANN achieves 1.60K QPS, 2.4× over PipeANN; at 32 threads, the gap widens to 9.8× as GateANN reaches 20.5K QPS. The gap widens because, within the saturated I/O budget, throughput is inversely proportional to I/Os per query: PipeANN issues ∼206 I/Os per query while GateANN issues only ∼20, and the resulting 9.8× gap closely matches the 10× I/O reduction ratio. 5.2.3

0.9

Recall@10

Figure 8. Billion-scale results on BigANN-1B. GateANN’s advantage holds at 10× the scale of the 100M experiments.

Measured E pected (1/s)

20.5×

0.8

(b) QPS vs. Recall (32 threads)

Throughput (QPS)

PipeANN GateANN

400

IO reduction ratio

Mean IOs per query

Figure 6. Throughput scaling from 1 to 32 threads on BigANN-100M, 𝐿=200.

0.7

5.2.4 Performance at Billion-Scale We evaluate on BigANN-1B. The 1B index is built with 𝑅=128, 𝐿build =200 to accommodate the larger graph. At this scale, 𝑅max =32 requires ∼123 GB of DRAM for the neighbor store; together with PQ codes (∼32 GB), the total ﬁts within the server’s 256 GB memory capacity. Figure 8 shows the recall–latency and throughput–recall tradeoﬀ curves. At 90% recall with 32 threads, GateANN achieves 9.7K QPS, outperforming PipeANN at 1.7K QPS by 5.7× and DiskANN at 1.4K QPS by 6.8×. This conﬁrms that GateANN’s pre-I/O ﬁlter checking and graph tunneling scale to billion-scale datasets without degradation.

I/O Reduction

We next measure how many SSD I/Os GateANN eliminates and whether the reduction matches expectations. At selectivity 𝑠, a fraction 𝑠 of visited nodes pass the ﬁlter and require SSD I/O; the remaining 1−𝑠 are intercepted by preI/O ﬁlter checking. Hence, the expected I/O reduction is 1/𝑠 compared to a post-ﬁlter baseline. Figure 7 (a) shows the mean I/Os per query as a function of 𝐿 on BigANN-100M. At 𝐿=100, PipeANN issues ∼108 I/Os per query, while GateANN issues only ∼11, a 10.2× reduction. The two curves are nearly parallel: as 𝐿 grows, both systems visit proportionally more nodes, but GateANN intercepts the same fraction (1−𝑠) at each step, conﬁrming that

5.2.5 Real-World Labels: YFCC-10M To test generality, we evaluate on YFCC-10M with real metadata tags from the BigANN benchmark [21]. Each vector has a variable number of tags from a vocabulary of ∼200K terms; a result is valid if the query’s tags are a subset of the result’s tags. This setting introduces variable per-query selectivity and more complex predicate evaluation. 8

100

Latency (ms)

101

(a) Recall vs. Latency (1 thread)

1.0

104 103 0.7

0.8

0.9

Recall@10

100

101

Latency (ms)

(b) QPS vs. Recall (32 threads)

105 104 103 0.7

102

(a) Recall vs. Latency (1 thread)

0.8

0.9

Recall@10

1.0

(b) QPS vs. Recall (32 threads)

Figure 11. Comparison with F-DiskANN. F-DiskANN uses a FilteredVamana index with label-aware edge routing and per-label medoid entry points.

Figure 9 shows the throughput–recall tradeoﬀ at 32 threads. GateANN dominates PipeANN across the entire overlapping recall range and extends signiﬁcantly beyond PipeANN’s reach. At moderate recall (∼35%), GateANN achieves 16.7× higher throughput, exceeding the 7.6× advantage on BigANN100M, because YFCC’s real tag distribution yields an average selectivity of ∼5%. The top tag covers 34% of vectors, but most queries require rare tags. At this selectivity, GateANN reduces I/Os by 18.5×, closely matching the expected 1/𝑠 ≈ 20× prediction. The advantage persists at higher recall: at 77% recall, GateANN sustains 14.1× throughput. PipeANN reaches ∼83% recall but only by pushing 𝐿 to 20K, issuing 20K I/Os per query and dropping to 22 QPS—a throughput ﬂoor that makes further recall gains impractical. GateANN, by contrast, continues to 91% recall by tunneling through non-matching nodes in memory, sustaining 14 QPS even at its highest recall point while PipeANN stalls at 83% with comparable throughput. These results conﬁrm that GateANN generalizes beyond synthetic single-label ﬁlters to real-world multi-label metadata with variable per-query selectivity.

PipeANN 5% Ga eANN 5%

PipeANN 10% Ga eANN 10%

PipeANN 20% Ga eANN 20%

0.90

1.00

Throughput (QPS)

105 104 103

0.80

0.85

Recall@10

0.95

Figure 12. QPS vs. Recall at 5%/10%/20% selectivity.

We evaluate using the oﬃcial DiskANN codebase on BigANN100M with 10-class labels. Figure 11 shows that F-DiskANN achieves high recall and reduces I/Os by ∼25% over DiskANN at 90% recall, conﬁrming genuine routing beneﬁt. However, the throughput improvement over DiskANN is modest—2.2K vs. 1.8K QPS at 32 threads—because at 10% selectivity each label covers 10M vectors, a subgraph large enough that postﬁltering is not catastrophic. At 90% recall, GateANN achieves 16.0K QPS, outperforming F-DiskANN’s 2.2K QPS by 7.3× in throughput. The same trend holds on DEEP-100M, where GateANN reaches 12.0K QPS versus F-DiskANN’s 883 QPS. The two approaches target diﬀerent layers: F-DiskANN improves the graph structure by ∼25% I/O reduction, whereas GateANN optimizes the search engine with 10× I/O reduction by eliminating reads for non-matching nodes.

Comparison with Alternative Approaches

5.3.1 In-Memory Search: Vamana We compare against Vamana [22], which loads the full graph and all full-precision vectors into memory (∼57 GB) and applies post-ﬁltering. Vamana computes exact distances for every visited node. Figure 10 (a) shows that GateANN achieves lower single-thread latency than Vamana at the same recall despite issuing SSD I/Os, because the CPU savings on non-matching nodes outweigh the I/O cost for matching ones. in Figure 10 (b) with 32 threads, Vamana’s throughput advantage becomes more apparent as in-memory computation scales freely with more threads while each SSD I/O carries ﬁxed per-operation overhead, yet GateANN still reaches within 1.3× of Vamana at 90% recall while using only ∼16 GB versus ∼57 GB, owing to pre-ﬁltering. 5.3.2

F-DiskANN GateANN

0.8

1.0

Figure 10. Comparison to Vamana (post-ﬁltering).

5.3

DiskANN PipeANN

Throughput (QPS)

0.8

105

Recall@10

PipeANN GateANN

Throughput (QPS)

Recall@10

1.0

Vamana DiskANN

5.4 Deep Analysis 5.4.1 Selectivity Sensitivity A key property of GateANN is that its beneﬁt scales with ﬁlter restrictiveness: lower selectivity yields greater I/O reduction. We evaluate this by varying selectivity across 5%, 10%, and 20% on BigANN-100M with 32 threads. Figure 12 shows the throughput–recall at each selectivity. Two phenomena emerge: GateANN’s throughput increases

Filter-Aware Index: F-DiskANN

F-DiskANN [3] builds a label-aware graph (FilteredVamana) that routes edges preferentially through same-label nodes. 9

Through ut (QPS)

20000

Rmax=32

15000

Pi eANN GateANN

Bet

Rmax=8

5000 0

Rmax=64

Rmax=16

10000

ter

Table 4. Performance on Gen4 vs. Gen5 SSDs (BigANN100M, Recall@10 ≥ 90%). The Gen5/Gen4 column shows how much each system beneﬁts from the faster SSD.

Rmax=48

DiskANN PipeANN GateANN

DRAM Overhead (GB)

Gen5/Gen4 (1 thread)

Gen5/Gen4 (32 threads)

1.53× 1.10× 0.99×

1.06× 1.00× 1.04×

(a) Throughput at 90% recall vs. DRAM overhead.

Rmax=16 (6GB) Rmax=32 (12GB)

Table 5. Per-query time breakdown at ∼86–90% recall (1 thread, BigANN-100M).

Rmax=48 (18GB) Rmax=64 (24GB)

Throughput (QPS)

PipeANN Rmax=8 (3GB)

104

Component

103 102 0.80

0.85

0.90

Recall@10

0.95

1.00

(b) Tradeoﬀ curves at diﬀerent 𝑅max .

% GateANN (𝜇s)

64 4.3 — — 1041 69.5 393 26.2

6 0.9 338 49.3 112 16.3 230 33.5

Total

1498 100

686 100

and GateANN sees no beneﬁt (0.99×) because its ∼25 I/Os per query leave the bottleneck entirely at CPU. At 32 threads, PipeANN shows zero beneﬁt from the faster SSD. This is the key result: if the SSD were the saturated resource, doubling its IOPS capacity would improve throughput proportionally. The zero gain proves that the binding constraint is CPU-side per-I/O overhead—the processing chain triggered by each read, as quantiﬁed in §5.4.4. DiskANN beneﬁts modestly (1.06×) because its synchronous batching has lower per-I/O CPU overhead, leaving some room for reduced device latency to help. GateANN is likewise SSD-independent (1.04×), but for a diﬀerent reason: it has already eliminated the wasted I/Os, so there are few remaining reads to beneﬁt from a faster device. The implication is that faster SSDs alone cannot solve the ﬁltered search problem; reducing the number of I/Os, not the speed of each, is the eﬀective lever.

Figure 13. Impact of maximum neighbors per node. as selectivity decreases (more tunneling, less I/O), while PipeANN’s throughput is roughly independent of selectivity since it reads every visited node regardless of ﬁlter match rate. At ∼90% recall, GateANN outperforms PipeANN by: 11.7× at 5%, 6.7× at 10%, 3.6× at 20%. The relationship conﬁrms that GateANN’s I/O reduction tracks 1/𝑠 and directly translates to throughput gains. 5.4.2 DRAM–Performance Tradeoﬀ To investigate the trade-oﬀ between the performance and memory usage, we sweep 𝑅max from 8 to 64 on BigANN100M. Figure 13 (a) shows throughput at 90% recall as a function of DRAM overhead. Even 𝑅max =8 at 3.4 GB delivers 2.2× higher throughput than PipeANN; throughput peaks at 𝑅max =48 with 19K QPS, 8.9× over PipeANN, and drops at 𝑅max =64, conﬁrming the diminishing-returns analysis in §3.4. Figure 13 (b) shows the full tradeoﬀ curves. All 𝑅max conﬁgurations outperform PipeANN across the entire recall range. 5.4.3

PipeANN (𝜇s)

SSD I/O (submit + poll) Tunneling (PQ + AdjIndex) Processing (exact dist.) Other (list mgmt., loop)

5.4.4 Time Breakdown

Impact of SSD Speed

A natural question is whether faster SSDs diminish the beneﬁt of GateANN. We compare the Gen4 PM9A3 and Gen5 Samsung 9100 PRO, which diﬀer by approximately 2× in random 4 KB read throughput. Table 4 reveals each system’s SSD sensitivity. At 1 thread, DiskANN beneﬁts the most (1.53×) because every query serially waits for I/O; PipeANN’s asynchronous pipeline already hides most device latency, limiting its gain to 1.10×; 10

Table 5 decomposes per-query latency at ∼86–90% recall (1 thread). In PipeANN, exact distance computation dominates (69.5%), while SSD I/O itself is only 4.3%—each I/O triggers an expensive processing chain that far exceeds the device access time. GateANN replaces this path with in-memory tunneling for non-matching nodes, shrinking processing by 9.3× from 1041 to 112 𝜇s and total latency by 2.2× from 1498 to 686 𝜇s. At 32 threads, the gap widens further. Because each I/O carries the full processing chain above—submission, polling, sector parsing, and distance computation—32 threads collectively exhaust their CPU budget at ∼430K aggregate IOPS, a CPU-side ceiling rather than an SSD limit (§5.4.3). Beyond this ceiling, throughput becomes inversely proportional to I/Os per query: PipeANN issues ∼206 I/Os (2.1K QPS) while

Latency (ms)

103

0.7

(a) Recall vs. Latency (1 thread)

0.8

0.9

Recall@10

(b) QPS vs. Recall (32 threads)

PipeANN α=1.0 Ga eANN α=1.0

Throughput (QPS)

105 104

0.8

0.9

Recall@10

1 thread 32 threads

5000

0.8

0.9

1.0

Recall@10

(b) QPS vs. Recall (32 threads)

0.75

W=4 W=8 W=16 W=32

0.50 0.25

8 16 32

Pipeline depth W

(a) QPS vs. 𝑊 at 93% recall.

1.0

200

400

Search list size L

(b) Recall is invariant to 𝑊 .

Figure 17. Pipeline depth (𝑊 ) sweep for GateANN on BigANN-100M. Recall is identical across all 𝑊 ; throughput plateaus at 𝑊 ≥8 (32 threads) and at 𝑊 ≥4 (1 thread).

Figure 15. Eﬀect of label–vector correlation. Labels are assigned via 𝑘-means: 𝛼=0 is random, 𝛼=1 assigns each node the label of its nearest cluster center.

at 𝛼=1 each node receives the label of its nearest cluster center. Selectivity remains 10% (10 classes) at all 𝛼. Figure 15 shows that spatial correlation aﬀects achievable recall. At 𝛼=0 (random), the ﬁltered 10-NN are scattered across the graph, capping recall at ∼88% because the unﬁltered graph cannot bridge long chains of non-matching nodes. At 𝛼=1 (clustered), matching nodes form compact regions and both systems reach >99%. GateANN outperforms PipeANN at every 𝛼, but the gap shrinks as correlation increases: at 𝛼=0, GateANN eliminates ∼90% of I/Os; at 𝛼=1, traversal naturally stays within the matching cluster, leaving fewer wasted I/Os to eliminate.

GateANN issues ∼20 (20.5K QPS), yielding a 9.8× gap that closely matches the 10× I/O reduction. 5.4.5 Skewed Label Distributions Real-world label distributions are typically skewed: a few labels are common while many are rare. We test robustness by replacing uniform labels with a Zipf distribution (𝛼=1.0, 10 classes), where the most common class covers 34% of vectors and the rarest covers only 3.4%. Queries are distributed uniformly across classes, creating a mix of high- and lowselectivity queries in each run. Figure 14 shows that GateANN maintains its advantage under skewed distributions. The mixed selectivities are favorable for GateANN: rare-class queries (3.4% selectivity) see even larger I/O reductions, while common-class queries (34%) still beneﬁt because two-thirds of candidates fail the ﬁlter. The overall throughput improvement of 8.5× over PipeANN reﬂects the selectivity-weighted average. 5.4.6

0.7

1.00 10000

103 0.7

Latency (ms)

Figure 16. Range predicate (L2-norm binning, 10 bins).

QPS at L=300

PipeANN α=0.5 Ga eANN α=0.5

(a) Recall vs. Latency (1 thread)

Figure 14. BigANN-100M with Zipf-distributed labels (𝛼=1.0, 10 classes). Selectivity ranges from 3.4% (rare) to 34.1% (common) across queries. PipeANN α=0.0 Ga eANN α=0.0

103

0.7

1.0

104

Throughput (QPS)

PipeANN GateANN

0.9

GateANN

Recall@10

0.8

DiskANN PipeANN

Recall@10

104

0.9

0.7

1.0

Throughput (QPS)

1.0

5.4.7 Range Predicates To validate that GateANN handles non-categorical predicates, we construct a range predicate by binning each vector’s L2 norm into 10 equal-frequency bins and selecting one bin per query (∼10% selectivity). This predicate is purely geometric and creates concentric-shell-like regions in the vector space. Figure 16 shows latency and throughput curves. At ∼89% recall with 32 threads, GateANN achieves 2.8K QPS, 6.5× higher than PipeANN’s 429 QPS; at 1 thread, GateANN reaches this recall at ∼2.8 ms vs. ∼2.6 ms for PipeANN, with DiskANN at ∼19 ms. All three systems plateau at ∼90% recall because norm-based bins create concentric shells whose boundaries cut across the graph structure, leaving the ﬁltered subgraph sparsely connected regardless of 𝐿. The result conﬁrms that

Spatial Label Correlation

The preceding experiments assign labels uniformly at random, but real-world metadata often correlates with the vector space To measure the impact of such correlation, we assign labels using 𝑘-means clustering (𝑘=10 on BigANN100M) with a mixing parameter 𝛼: at 𝛼=0 labels are random; 11

Recall@10

104

0.9 PipeANN (Post) PipeANN (Early) GateANN (Pre)

0.8 0.7

cheap (∼90 ns). In contrast, GateANN (Pre) reduces latency to 0.77 ms, a 2.0× improvement, by eliminating SSD reads. At 32 threads (Figure 18(b)), the pattern is even clearer. PipeANN (Early) reaches 2085 QPS, almost identical to PipeANN (Post) at 2098 QPS, whereas GateANN (Pre) achieves 16017 QPS, 7.6× higher. The reason is that removing distance computation without removing I/O does not address the bottleneck. As Table 5 shows, per-I/O cost at 32 threads is dominated by submission, polling, and sector parsing. Both PipeANN variants still issue ∼206 I/Os per query and hit the same ∼430K IOPS ceiling. Only GateANN eliminates the SSD reads themselves, conﬁrming that what to read matters far more than what to compute.

Throughput (QPS)

1.0

Latency (ms)

(a) Recall vs. Latency (1 thread)

103 0.7

0.8

0.9

Recall@10

1.0

(b) QPS vs. Recall (32 threads)

Figure 18. Ablation on BigANN-100M (𝑠=0.1). PipeANN (Early) checks the ﬁlter after each SSD read and skips exact distance computation for non-matching nodes; GateANN (Pre) additionally eliminates the SSD reads themselves.

6 Related Work SSD-based graph ANNS. DiskANN [22] introduced SSDresident graph search with synchronous beam search. Subsequent systems improve SSD eﬃciency through asynchronous I/O pipelines [4], locality-aware graph layout [27, 32], co-designed layout and async runtime [34], page-aligned node placement [12], and direct-insert updates [5]. SPANN [2] and OrchANN [7] adopt inverted-index designs but do not support metadata predicates. They retrieve every expanded node from SSD and typically handle ﬁlters through postﬁltering. GateANN avoids fetching ﬁlter-failing nodes by decoupling graph traversal from vector retrieval, complementary to any on-disk graph index. Filtered ANNS. Most prior work targets in-memory settings. NHQ [26] builds a composite proximity graph with a fused vector-attribute distance, UNG [1] encodes label-set containment in edges, JAG [29] incorporates attribute distances at construction and transforms query predicates into continuous ﬁlter distances at search time, and ACORN [18] uniformly densiﬁes HNSW edges so that predicate-induced subgraphs are navigable. Curator [10] complements graph indexes with partition-based subindexes for low-selectivity queries, and SIEVE [14] selects among workload-specialized indexes via an analytical cost model. They embed ﬁlter information into the index at build time. On the disk side, FilteredDiskANN [3] constructs a single label-aware Vamana graph with per-label medoids, and NaviX [20] adapts HNSW for disk-resident graph databases with adaptive preﬁltering. Our work diﬀers from all of the above in two respects: it operates on an unmodiﬁed graph index, supporting arbitrary predicates without rebuild, and it targets SSD-resident search.

GateANN is predicate-agnostic: it applies equally to range predicates without any change to the index or search algorithm. 5.4.8 Pipeline Depth In PipeANN, pipeline depth 𝑊 controls the number of concurrent in-ﬂight I/Os via io_uring. Since GateANN issues ∼10× fewer I/Os per query, one might expect a smaller 𝑊 to suﬃce. We sweep 𝑊 ∈ {1, 2, 4, 8, 16, 32} on BigANN-100M. Figure 17 (b) conﬁrms that recall is invariant to 𝑊 . All values produce identical curves across 𝐿, since 𝑊 aﬀects only I/O scheduling, not candidate selection. Figure 17 (a) shows throughput at 𝐿=300 (∼93% recall). At 32 threads, throughput improves from 𝑊 =1 (8.1K QPS) to 𝑊 =8 (14.0K QPS), then plateaus through 𝑊 =32 (14.0K QPS). The remaining I/Os per query still beneﬁt from concurrency, but 8 concurrent I/Os suﬃce to hide per-read latency. At 1 thread, throughput plateaus earlier (𝑊 ≥4, ∼1.0K QPS), conﬁrming that a single thread is CPU-bound even at moderate depths. Note that tunneling naturally self-regulates the pipeline by injecting memory-resolved candidates (sub-microsecond) between I/O completions, partially compensating for the reduced I/O count. 5.4.9

Ablation: I/O Elimination vs. CPU Savings

GateANN’s speedup comes from two sources: (i) eliminating SSD I/Os for non-matching nodes, and (ii) skipping exact distance computation on them. To separate these eﬀects, we add an Early Filter variant (“PipeANN (Early)” in Figure 18) that applies ﬁltering after the SSD read. Non-matching nodes still incur the read but skip exact distance computation; neighbor expansion is unchanged to preserve connectivity. Figure 18 compares the three designs. At 1 thread (Figure 18(a)), PipeANN (Early) and PipeANN (Post) are nearly identical: at 90% recall, latency is 1.54 ms vs. 1.56 ms. Skipping exact distance saves only ∼16 𝜇s per query because BigANN’s 128-dimensional vectors make each computation

7 Conclusion This paper presented GateANN, an I/O-eﬃcient SSD-based system for ﬁltered vector search. The key idea is to separate the lightweight routing information needed for traversal from the full-precision vectors needed for ﬁnal ranking. This decoupling allows GateANN to check ﬁlters before issuing SSD reads and to traverse non-matching nodes using 12

compact in-memory metadata, thereby avoiding wasted I/O while preserving graph connectivity and recall. Experimental results show that GateANN reduces SSD I/Os by up to 10× and improves throughput by up to 7.6× at comparable recall.

https://doi.org/10.14778/3749646.3749725 [15] Yury A. Malkov and Dmitry A. Yashunin. 2020. Eﬃcient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Trans. Pattern Anal. Mach. Intell. 42, 4 (2020), 824–836. [16] Microsoft. 2025. Azure AI Search. https://azure.microsoft.com/en-us/products/ai-services/ai-search. (2025). [17] Jason Mohoney, Devesh Sarda, Mengze Tang, Shihabur Rahman Chowdhury, Anil Pacaci, Ihab F. Ilyas, Theodoros Rekatsinas, and Shivaram Venkataraman. 2025. Quake: Adaptive Indexing for Vector Search. In Proc. of USENIX OSDI. Boston, MA, USA. [18] Liana Patel, Peter Kraft, Carlos Guestrin, and Matei Zaharia. 2024. ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data. In Proc. of ACM SIGMOD. ACM. https://doi.org/10.1145/3654923 [19] Siddhant Ray, Rui Pan, Zhuohan Gu, Kuntai Du, Shaoting Feng, Ganesh Ananthanarayanan, Ravi Netravali, and Junchen Jiang. 2025. METIS: Fast Quality-Aware RAG Systems with Conﬁguration Adaptation. In Proc. of ACM SOSP. Association for Computing Machinery. https://doi.org/10.1145/3731569.3764855 [20] Gaurav Sehgal and Semih Salihoglu. 2025. NaviX: A Native Vector Index Design for Graph DBMSs With Robust Predicate-Agnostic Search Performance. Proc. VLDB Endow. 18, 11 (2025), 4438–4450. https://doi.org/10.14778/3749646.3749704 [21] Harsha Vardhan Simhadri, Martin Aumüller, Amir Ingber, Matthijs Douze, George Williams, Magdalen Dobson Manohar, Dmitry Baranchuk, Edo Liberty, Frank Liu, Ben Landrum, et al. 2024. Results of the Big ANN: NeurIPS’23 Competition. arXiv preprint arXiv:2409.17424 (2024). [22] Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Krishaswamy, and Harsha Vardhan Simhadri. 2019. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. In Proc. of NeurIPS. Curran Associates, Inc., 13748–13758. [23] 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 USENIX ATC. Santa Clara, CA, USA. [24] Bing Tian, Haikun Liu, Yuhang Tang, Shihai Xiao, Zhuohui Duan, Xiaofei Liao, Hai Jin, Xuecang Zhang, Junhua Zhu, and Yu Zhang. 2025. Towards High-throughput and Low-latency Billion-scale Vector Search via CPU/GPU Collaborative Filtering and Re-ranking. In Proc. of USENIX FAST. Santa Clara, CA, USA. [25] Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, Kun Yu, Yuxing Yuan, Yinghao Zou, Jiquan Long, Yudong Cai, Zhenxiang Li, Zhifeng Zhang, Yihua Mo, Jun Gu, Ruiyi Jiang, Yi Wei, and Charles Xie. 2021. Milvus: A Purpose-Built Vector Data Management System. In Proc. of ACM SIGMOD. Association for Computing Machinery, 2614–2627. https://doi.org/10.1145/3448016.3457550 [26] Mengzhao Wang, Lingwei Lv, Xiaoliang Xu, Yuxiang Wang, Qiang Yue, and Jiongkang Ni. 2023. An Eﬃcient and Robust Framework for Approximate Nearest Neighbor Search with Attribute Constraint. In Advances in Neural Information Processing Systems 36 (NeurIPS). [27] 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-Eﬃcient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment. In Proc. of ACM SIGMOD. Association for Computing Machinery, Article 14. https://doi.org/10.1145/3639269 [28] Puqing Wu, Minhui Xie, Enrui Zhao, Dafang Zhang, Jing Wang, Xiao Liang, Kai Ren, and Yunpeng Chai. 2025. Turbocharge ANNS on Real Processing-in-Memory by Enabling Fine-Grained Per-PIM-Core Scheduling. In Proc. of USENIX ATC. Boston, MA, USA.

References [1] Yuzheng Cai, Jiayang Shi, Yizhuo Chen, and Weiguo Zheng. 2024. Navigating Labels and Vectors: A Uniﬁed Approach to Filtered Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 2, 6, Article 246 (2024). https://doi.org/10.1145/3698822 [2] Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. 2021. SPANN: Highlyeﬃcient Billion-scale Approximate Nearest Neighborhood Search. In Proc. of NeurIPS. Curran Associates, Inc., 5199–5212. [3] Siddharth Gollapudi, Neel Karia, Varun Sivashankar, Ravishankar Krishnaswamy, Nikit Begwani, Swapnil Raz, Yiyong Lin, Yin Zhang, Neelam Mahapatro, Premkumar Srinivasan, Amit Singh, and Harsha Vardhan Simhadri. 2023. Filtered-DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters. In Proc. of the ACM Web Conference (WWW). ACM, 3406–3416. https://doi.org/10.1145/3543507.3583552 [4] Hao Guo and Youyou Lu. 2025. Achieving Low-Latency Graph-Based Vector Search via Aligning Best-First Search Algorithm with SSD. In Proc. of USENIX OSDI. Boston, MA, USA. [5] Hao Guo and Youyou Lu. 2026. OdinANN: Direct Insert for Consistently Stable Performance in Billion-Scale Graph-Based Vector Search. In Proc. of USENIX FAST. Santa Clara, CA, USA. [6] Zhengding Hu, Vibha Murthy, Zaifeng Pan, Wanlu Li, Xiaoyi Fang, Yufei Ding, and Yuke Wang. 2025. HedraRAG: CoOptimizing Generation and Retrieval for Heterogeneous RAG Workﬂows. In Proc. of ACM SOSP. Association for Computing Machinery. https://doi.org/10.1145/3731569.3764806 [7] Chengying Huan, Lizheng Chen, Zhengyi Yang, Shaonan Ma, Rong Gu, Renjie Yao, Zhibin Wang, Mingxing Zhang, Fang Xi, Jie Tao, Gang Zhang, Guihai Chen, and Chen Tian. 2025. OrchANN: A Uniﬁed I/O Orchestration Framework for Skewed Out-of-Core Vector Search. arXiv preprint arXiv:2512.22838 (2025). [8] Amir Ingber and Edo Liberty. 2025. Accurate and Eﬃcient Metadata Filtering in Pinecone’s Serverless Vector Database. In Proc. of ICML Workshop on Vector Databases. [9] Junhyeok Jang, Hanjin Choi, Hanyeoreum Bae, Seungjun Lee, Miryeong Kwon, and Myoungsoo Jung. 2023. CXL-ANNS: SoftwareHardware Collaborative Memory Disaggregation and Computation for Billion-Scale Approximate Nearest Neighbor Search. In Proc. of USENIX ATC. Boston, MA, USA. [10] Yicheng Jin, Yongji Wu, Wenjun Hu, Bruce M. Maggs, Jun Yang, Xiao Zhang, and Danyang Zhuo. 2026. Curator: Eﬃcient Vector Search with Low-Selectivity Filters. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). [11] Jeﬀ Johnson, Matthijs Douze, and Hervé Jégou. 2021. Billion-Scale Similarity Search with GPUs. IEEE Trans. Big Data 7, 3 (2021), 535– 547. [12] Dingyi Kang, Dongming Jiang, Hanshen Yang, Hang Liu, and Bingzhe Li. 2025. Scalable Disk-Based Approximate Nearest Neighbor Search with Page-Aligned Graph. arXiv preprint arXiv:2509.25487 (2025). [13] Sukjin Kim, Seongyeon Park, Si Ung Noh, Junguk Hong, Taehee Kwon, Hunseong Lim, and Jinho Lee. 2025. PathWeaver: A HighThroughput Multi-GPU System for Graph-Based Approximate Nearest Neighbor Search. In Proc. of USENIX ATC. Boston, MA, USA. [14] Zhaoheng Li, Silu Huang, Wei Ding, Yongjoo Park, and Jianjun Chen. 2025. SIEVE: Eﬀective Filtered Vector Search with Collection of Indexes. Proc. VLDB Endow. 18, 11 (2025), 4723–4736. 13

[29] Haike Xu, Guy Blelloch, Laxman Dhulipala, Lars Gottesbüren, Rajesh Jayaram, and Jakub Łącki. 2026. JAG: Joint Attribute Graphs for Filtered Nearest Neighbor Search. arXiv preprint arXiv:2602.10258 (2026). [30] Yuming Xu, Hengyu Liang, Jin Li, Shuotao Xu, Qi Chen, Qianxi Zhang, Cheng Li, Ziyue Yang, Fan Yang, Yuqing Yang, Peng Cheng, and Mao Yang. 2023. SPFresh: Incremental In-Place Update for Billion-Scale Vector Search. In Proc. of ACM SOSP. Association for Computing Machinery. https://doi.org/10.1145/3600006.3613166 [31] Jiayi Yao, Hanchen Li, Yuhan Liu, Siddhant Ray, Yihua Cheng, Qizheng Zhang, Kuntai Du, Shan Lu, and Junchen Jiang. 2025. CacheBlend: Fast Large Language Model Serving for RAG with Cached Knowledge Fusion. In Proc. of ACM EuroSys. Association for Computing Machinery. https://doi.org/10.1145/3689031.3696098 Best Paper Award. [32] Ziyang Yue, Bolong Zheng, Ling Xu, Tiejian Luo, and Xiaofang Zhou. 2025. Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-Based ANN Search. Proc. VLDB Endow. 18, 11 (2025), 4337–4349. https://doi.org/10.14778/3749646.3749697 [33] Qianxi Zhang, Shuotao Xu, Qi Chen, Guoxin Sui, Jiadong Xie, Zhizhen Cai, Yaoqi Chen, Yinxuan He, Yuqing Yang, Fan Yang, Mao Yang, and Lidong Zhou. 2023. VBASE: Unifying Online Vector Similarity Search and Relational Queries via Relaxed Monotonicity. In Proc. of USENIX OSDI. Boston, MA, USA. [34] Weichen Zhao, Yuncheng Lu, Yao Tian, Hao Zhang, Jiehui Li, Minghao Zhao, Yakun Li, and Weining Qian. 2026. Optimizing SSDResident Graph Indexing for High-Throughput Vector Search. arXiv preprint arXiv:2602.22805 (2026). [35] Zilliz. 2024. VDBBench: A Benchmark for Vector Databases. https://github.com/zilliztech/VDBBench. (2024).

Record · ID 2717 · SHA-256 79d8002b28d29e44
Conceptio Open Knowledge Archive — every document is proof-bundled with source, license, and retrieval metadata.