ANNex: Efficient Filtered Approximate Nearest Neighbor Search via Graph-Traversal Metadata Filtering

Abstract

Approximate Nearest Neighbor (ANN) search is a foundational primitive in modern recommendation and retrieval systems. However, production deployments routinely require filtered ANN search-retrieving the top- K nearest neighbors that also satisfy metadata predicates-a requirement that popular highperformance libraries such as FAISS and ScaNN do not natively support without costly post-filtering loops. Existing solutions that support filtering, such as distributed search engines, introduce unacceptable latency and infrastructure overhead for latencysensitive candidate retrieval pipelines. We present ANNex, a production ANN system that integrates metadata filtering directly into HNSW graph traversal, eliminating the need for post-filtering iteration. ANNex introduces a Decreasing- K traversal strategy-the inverse of post-filtering's Increasing- K loop-in which already-visited nodes are tracked and excluded from subsequent traversals, reducing graph search depth with each iteration rather than increasing it. Combined with Product Quantization for memory compression, integer key optimization, and compiled filter functions for sub-millisecond predicate evaluation, ANNex achieves sub-30 ms p99 latency at production scale on 10 million 512-dimensional vectors with up to four concurrent clients per instance. We describe the system architecture, key design tradeoffs, and empirical evaluation results, providing a practical reference for practitioners building filtered ANN systems at scale.

Introduction

VECTOR search has become a fundamental building block of modern machine learning systems, powering semantic search, content recommendation, and candidate retrieval across a wide range of applications. Given a query vector, approx_imate nearest neighbor (ANN) algorithms efficiently find the most semantically similar items in large embedding spaces, typically achieving sub-linear query time at the cost of a small, controllable recall tradeoff.

In production recommendation systems, pure ANN retrieval is rarely sufficient. Practical deployments require filtered retrieval-finding the top- K - nearest neighbors that additionally satisfy metadata constraints. A content recommendation system may need to retrieve the most similar items that are available in a specific region, belong to a particular category, or meet eligibility criteria. These are not edge cases; filtered retrieval is the common case in production.

The standard workaround-post-filtering-retrieves a larger candidate set from the ANN index and then applies metadata filters after the fact. This approach is fundamentally broken at scale: the required overfetch multiplier is a function of the filter selectivity, which varies per query and cannot be statically tuned. High filter selectivity leads to iterative loops with ever increasing K values, driving latency and compute costs upward unpredictably.

Ex_isting solutions that support native filtering-distributed search engines and managed vector database services-address the problem but introduce new ones: they require expensive, specialized hardware to match the latency of FAISS or ScaNN, impose vendor lock-in, carry significant operational overhead, and are cost-prohibitive at scale when multiple independent indices are required for different retrieval flows.

We present ANNex, a production ANN system designed to close this gap. ANNex wraps the HNSW algorithm with a native filtering layer that applies metadata predicates during graph traversal rather than after it. The key algorithmic contribution is the Decreasing- K traversal strategy: by tracking visited nodes across iterations and instructing the graph to skip them, subsequent traversals search a strictly smaller graph, with K decreasing toward zero rather than increasing.

The contributions of this paper are as follows:

A graph-traversal filtering architecture that integrates metadata predicates natively into HNSW search, eliminating post-filtering iteration.

The Decreasing- K traversal strategy, which reduces graph search depth in subsequent iterations by excluding alreadyvisited nodes, bounding total traversal cost at O(|X|).

A compiled filter function approach that reduces predicate evaluation latency from single-digit milliseconds to under 1 ms compared to a runtime DSL.

An empirical evaluation on 10 million 512-dimensional vectors demonstrating sub-30 ms p99 latency at up to four concurrent clients per instance with zero errors.

A practical analysis of deployment tradeoffs including Python GIL constraints, memory-bound index sizing, and Product Quantization for a 256× reduction in per-vector storage.

ANNex does not propose a new graph index. Section II-C relates it to filter-aware indices and clarifies how the Decreasing-K strategy differs from them.

Background and related work

Approximate nearest neighbor search

Given a dataset of vectors $\mathcal{X}=\left\{x_1,\dots ,x_n\right\}$ in R^d and a query vector q, the nearest neighbor search problem asks for the vector x_i that minimizes a distance metric dist(q,x_i). Exact search requires O(nd) time, which is infeasible for largescale retrieval. ANN algorithms trade a small, bounded recall loss for dramatically improved query time, typically achieving O (lig n) average-case complexity.

The Hierarchical Navigable Small World (HNSW) algorithm [1] constructs a multi-layer proximity graph where each layer is a navigable small world graph. Search proceeds greedily from a single entry point at the top layer, descending through layers until reaching layer 0, where the nearest neighbors are found. HNSW achieves state-of-the-art recall-vs-speed tradeoffs and is the underlying algorithm powering FAISS, Pinecone, and numerous production systems.

Filtered ANN: The gap in ex_isting solutions

The filtered ANN problem has no universally satisfactory solution in the open-source ecosystem. Table 1 characterizes the solution landscape qualitatively across filtering support, deployment model, and cost model. It is based on documented features rather than measurements under equivalent conditions.

FAISS [2] and ScaNN [3] are the dominant open-source ANN libraries, but neither natively evaluates metadata predicates during traversal; filtering is typically implemented by post-filtering or by restricting search to a precomputed ID set. Elasticsearch and OpenSearch support filtered vector search via their HNSW implementation but require operating a search cluster. Managed services such as Pinecone support filtering but impose per-query costs and vendor dependency that are prohibitive when dozens of independent indices serve different retrieval flows.

Controlled comparisons of filtered-search methods under equivalent conditions have been conducted in the filtered-search track of the NeurIPS'23 Big-ANN benchmark [8].

Filter-aware indices and positioning of ANNex

Beyond post-filtering, two further families address filtered ANN. In-search filtering over a standard index evaluates predicates on candidates as the index is traversed; hnswlib, for example, exposes a filter callback that restricts which labels may be returned during search [9]. Filter-aware indices instead modify index construction or traversal to account for attributes. Filtered-DiskANN [10] builds graphs whose connectivity is aware of label constraints; ACORN [11] builds a denser predicate-agnostic graph and searches over the predicate subgraph; and NHQ [12] fuses vector and attribute information into a composite proximity graph. Vector data management systems such as Milvus [13] support attribute filtering as part of a full database system.

ANNex belongs to the first of these families. It does not propose a new graph index and does not claim improved recall over filter-aware indices. Its contribution is a production design around an unmodified HNSW library. The Decreasing- K strategy differs from single-pass in-search filtering in how it handles too few qualifying results: rather than enlarging the search, it restarts with all previously visited nodes excluded and requests only the number of results still needed. Combined with time-bounded termination, compiled predicates, and packaging as an ordinary model artifact, this lets filtered search be adopted without changing index construction, schema management, or serving infrastructure. Filter-aware indices are complementary: they target recall and efficiency under highly selective predicates, which we identify as a limitation of ANNex in Section VI-E.

Problem formulation

We formally define the Filtered ANN problem and the requirements that motivated ANNex.

Definition 1 (Filtered ANN): Given a dataset $\mathcal{X}=\left\{\left(x_i,m_i\right)\right\}$ where x_i is an embedding vector and m_i is a metadata object, a query vector q, a filter predicate $P:ℳ\to \{$ true, false}, and a desired result count K, return the set

$S^{\text{*}}=\underset{\begin{array}{c}S\subseteq \mathcal{X}\\ \left|S\right|=K,P\left(m_i\right)= true \forall i\in S\end{array}}{\text{argmin}}{\displaystyle \sum }_{i\in S}\text{dist}\left(q,x_i\right)$ (1)

In addition to correctness, production deployments impose the following requirements:

Millisecond latency: ANN search serves as the candidate retrieval step in a multi-stage ranking pipeline. Downstream hydration and ranking steps add latency, requiring ANN to terminate within 20-40 ms p99.

Predictable scaling: Latency must not degrade as filter selectivity varies across queries.

Cost efficiency: Multiple independent indices serve different retrieval flows. Per-query costs and premium hardware requirements are not acceptable at this multiplicity.

No vendor dependency: Cloud-agnostic deployment is required.

Developer velocity: Deployable by ML engineers without specialized infrastructure expertise.

The post-filtering problem

Increasing- K loop

Post-filtering retrieves a candidate set of size K’ > K from the ANN index and applies the filter predicate after the fact.

When the filtered result set $\mid \{x_i\in$ candidates: $P\left(m_i\right)=\text{true}\left\}\right|<K$ , the system must re-query with a larger K’, expanding outward in the embedding space. In the worst case this becomes an iterative loop where K’ grows unboundedly as filter selectivity increases. Figure 1 illustrates this loop.

Figure 1: Post-filtering Increasing- K loop -K grows with each iteration as filtered results fall short of the target.

Fundamental unscalability

The core problem is that the overfetch multiplier required to avoid multi-iteration loops is a function of the filter selectivity rate $s=\left|\left\{x_i:P\left(m_i\right)=\text{true}\right\}\right|/\left|\mathcal{X}\right|.$ Optimal static overfetch $K^{\text{'}}=K/s$ requires knowing s at query time. In practice, different queries carry different predicates with different selectivities, making a single static overfetch either wasteful or insufficient.

Annex: system design

Core architecture

ANNex is built on top of the hnswlib C++ library with Python bindings, augmented with a metadata index that colocates item metadata with HNSW graph nodes in a single in-memory data structure. Both the HNSW graph and the metadata index are loaded into RAM at serving time, enabling sub-millisecond node metadata access during traversal without network I/O. Figure 2 shows the full system.

Figure 2: ANNex system architecture - index_ing pipeline (left) and serving pipeline (right), packaged as a single deployable artifact.

At index time, each item is assigned a unique integer key that serves as its node identifier in the HNSW graph. The metadata object is stored separately in a metadata index keyed by this integer, as shown in Figure 3.

Figure 3: In-memory data structure - HNSW graph nodes reference integer keys which map to metadata objects. All lookups are in-process with zero network hops.

Decreasing-K traversal strategy

The central algorithmic contribution of ANNex is the Decreasing- K traversal strategy. When the initial traversal returns fewer than K qualifying results, ANNex tracks the set of visited nodes V from all prior traversals and passes this set to the HNSW engine, which excludes these nodes from subsequent traversal. Figure 4 contrasts this with the post-filtering approach.

Figure 4: ANNex Decreasing- K traversal - visited nodes are excluded in each iteration, shrinking the effective search space until K results are found or timeout is reached.

The effective search space shrinks with each iteration. The total graph traversal cost across all iterations is bounded by $O(|\mathcal{X}|)$ -the graph cannot be traversed more than once per node-compared to post-filtering's unbounded growth.

Compiled filter functions

Filter predicates must be evaluated on every candidate node during traversal. An initial design used a runtime DSL, adding 3-8 ms of interpretation overhead per query. ANNex instead uses compiled filter functions: users define filter logic as native Python functions conforming to a simple interface (object, filter_params) -> bool. This reduces per-query filter overhead from 3-8 ms to under 1 ms-a reduction of over 70%, as shown in Figure 5.

Figure 5: Filter predicate evaluation latency - compiled Python functions reduce overhead by over 70% compared to a runtime DSL interpreter.

Memory optimizations

Product Quantization (PQ). A 10 million vector index with 512 dimensions requires $512\times {10}^7\times 4\text{ bytes }=20 \text{GB}$ of raw embedding storage. ANNex integrates the FAISS Product Quantizer [4] to compress embeddings at index time. For $d=512,m=8$ , nbits = 8, each vector is compressed from 16,384 bits (512 float32 values) to 64 bits-a 256× memory reduction-with a small, controllable recall loss.

Integer Key Mapping. ANNex maps all string keys to a dense integer inverted index at index time, storing only 4-byte integers in the graph. For a 10 million node graph with 16-character string keys, this saves approximately 120 MB of graph memory.

Traversal termination

ANNex enforces two termination conditions: (1) the required K results have been found, or (2) a user-specified timeout in milliseconds has been reached. When the timeout triggers, ANNex returns whatever results have been accumulated, providing a graceful degradation guarantee rather than a latency spike.

Deployment architecture

ANNex is packaged as a PyTorch model artifact, enabling deployment on any inference serving tier that supports PyTorch models. Each worker process loads its own copy of the model artifact into dedicated memory, with the number of workers bounded by [available_memory/index_size]. This multi-worker deployment model is a deliberate response to Python's Global Interpreter Lock (GIL), which causes severe CPU contention in multithreaded deployments.

Evaluation

Experimental setup

We evaluate ANNex on a dataset of 10 million 512-dimensional float32 vectors with 4 metadata fields and 3 simultaneous filter predicates applied per query. The serving instance is an ml.m5.4xlarge (16 vCPUs, 64 GB RAM). Load tests are conducted using Locust with a linear rampup and 5-minute steady-state duration per configuration. We report p99 ModelLatency in milliseconds as the primary latency metric, invocation count as a throughput proxy, and CPU/memory utilization. CPU utilization is reported as a sum across cores, so its maximum on this instance is 1,600%. Product Quantization was not enabled during these load tests.

Reproducibility details. Each configuration was deployed as a PyTorch model endpoint whose model server launched the stated number of worker processes, each loading its own copy of the index. Load was generated with Locust in headless mode (locust --headless –u N-r 1 --run-time 5m), with N concurrent users and a spawn rate of one user per second. Latency, invocation, CPU, and memory metrics were read from the serving platform's monitoring at 1-second resolution, using the p99 statistic for model latency, the sum for invocations, and the maximum for CPU and memory utilization.

Multi-worker results

At 4 workers with up to 4 concurrent users, ANNex sustains sub-30 ms p99 latency with zero invocation errors across all configurations (Table 2 & Figure 6). Latency degrades gracefully as concurrency exceeds worker capacity, reaching 90.0 ms p99 at 10 concurrent users with 4 workers. The 6-worker configuration shows the cost of oversubscription: at 6 users, p99 latency rose to 424.3 ms and throughput fell to 2,542 invocations, with memory near 75% and CPU peaking at 1,559%. Latency for 6 workers at 4 users was not recorded. Memory utilization scales predictably with worker count, enabling straightforward capacity planning via:

Figure 6: p99 latency vs. concurrent users by worker count. The 30 ms SLA threshold (orange dashed) is met by 4- and 6-worker configurations at 2 concurrent users and by 4 workers at 4 users (log scale; the 6-worker, 4-user point was not recorded).

$workers =\frac{ available\_memory }{ index\_size\_per\_worker }.$ (2)

GIL impact: Multithreaded vs. multi-worker

We also deployed ANNex as a single worker process serving concurrent requests with multiple threads, using the same instance type, index, load generator, and metrics as the multiworker configurations. Table 3 compares this with the multiworker configurations.

The multithreaded single-worker model saturated CPU at 1,593% of the 1,600% available, p99 model latency reached approximately 59.8 s, and one model error was recorded. Because multi-worker configurations also reached high CPU utilization at elevated concurrency (up to 1,559%), CPU utilization alone does not distinguish the two modes; the decisive evidence is latency, roughly three orders of magnitude higher under multithreading at comparable CPU saturation. This is consistent with contention on Python's GIL, under which threads executing Python-level orchestration and filter code cannot run in parallel. This finding confirms that Pythonbased ANN serving must use process-level parallelism rather than thread-level parallelism. The multithreaded result is from a single load-test run.

Component contributions

Table 4 summarizes the contribution of each design component and whether its effect was measured in production or derived analytically.

Accuracy considerations

Because ANNex evaluates the predicate exactly on every candidate, every returned result satisfies the filter; precision with respect to the filter is therefore 1 by construction. Recall relative to exact filtered K-nearest-neighbor search was not measured in this production evaluation. It is governed by four factors: the standard HNSW parameters M and ef [1], quantization distortion when PQ is enabled [4], the restart behavior of Decreasing- K, and the timeout. Under highly selective predicates, qualifying nodes may be distant in the graph from the query's neighborhood, so search may reach the timeout and return fewer than K results. ANNex exposes per-query diagnostics, including the number of iterations and time spent in search and filtering, so that such cases can be monitored in production. A controlled Recall@ K evaluation against exact filtered search at varying selectivities is identified as future work.

Scaling and capacity planning

Single-node memory model

The memory required per worker can be estimated as

$index\_size \approx n\left(b_{vec }+b_{graph }+b_{key }\right)+B_{meta },$ (3)

where n is the number of items, b_vec is the per-vector storage (2,048 bytes for raw 512-dimensional float32 vectors, or 8 bytes for PQ codes with m = 8), b_graph is the per-node link storage (roughly M × 8 -10 bytes in hnswlib [9]), B_key is the integer key size, and B_meta is the total metadata footprint. Combined with Eq. (2), this model determines both the largest index that fits on a node and the number of workers the node can support. In our evaluation, memory scaled linearly at approximately 8 GB per worker, consistent with each worker holding an independent copy of the index.

Sharded deployments

Evaluating sharded deployments was outside the scope of this study. When an index exceeds single-node memory, a scattergather architecture would partition items across shards, query shards in parallel, and merge per-shard top- K results. This introduces a network hop and a merge step on the critical path, and tail latency becomes governed by the slowest shard. Filter selectivity may also vary across shards, so a shard with few qualifying items may exhaust its timeout while others return quickly. Per-shard timeouts with partial-result merging and partitioning items by frequently filtered attributes are natural directions for such a design.

Limitations and future work

ANNex has several limitations that represent opportunities for future work.

Memory-bounded index size. The index must fit in RAM. For very large indices, a sharded architecture with an aggregation layer would be required at the cost of additional network latency.

No incremental updates. Full index reconstruction is required when embeddings or metadata change. HNSW supports incremental insertion natively, but enabling thread-safe incremental updates in Python requires careful GIL-aware synchronization.

Per-worker index copies. Moving to a C++ serving tier with shared memory would enable true multithreading and eliminate per-worker memory duplication.

Filter function redeployment. A hybrid approach combining compiled functions for stable filters with a JITcompiled DSL for experimental filters could balance ergonomics and performance.

Recall not quantified. Recall@ K against exact filtered search was not measured (Section VI-E).

No controlled cross-system comparison. Comparisons with FAISS, ScaNN, Elasticsearch, Pinecone, and filteraware indices under identical hardware and data remain future work.

Decreasing- K not isolated experimentally. Its advantage over post-filtering is argued analytically; a controlled measurement at varying selectivities is future work.

Conclusion

We presented ANNex, a production ANN system that integrates metadata filtering directly into HNSW graph traversal. The central contribution-the Decreasing- traversal strategy- inverts the cost structure of post-filtering by tracking visited nodes across iterations and excluding them from subsequent traversals, bounding total traversal cost by O (|x|) and enabling predictable filtered search latency independent of per-query filter selectivity.

Empirical evaluation on 10 million 512-dimensional vectors demonstrates sub-30 ms p99 latency at up to four concurrent clients per instance with zero errors-meeting the latency requirements of multi-stage recommendation and retrieval pipelines. Combined with Product Quantization for 256× memory compression, integer key optimization, and compiled filter functions for sub-millisecond predicate evaluation, ANNex delivers a complete, cost-effective solution to filtered ANN search deployable on commodity serving instances.

Acknowledgment

The author thanks the open-source contributors to hnswlib and FAISS, whose foundational work made this system possible. LaTeX formatting assistance was provided by Claude (Anthropic), an AI assistant.

Malkov YA, Yashunin DA. Efficient and robust approx_imate nearest neighbor search using hierarchical navigable small world graphs. IEEE Trans Pattern Anal Mach Intell. 2018;42(4):824-36.

References

1. Malkov YA, Yashunin DA. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Trans Pattern Anal Mach Intell. 2018;42(4):824-36.

2. Johnson J, Douze M, Jegou H. Billion-scale similarity search with GPUs. IEEE Trans Big Data. 2019;7(3):535-47.

3. Guo R, et al. Accelerating large-scale inference with anisotropic vector quantization. In: Proc ICML. 2020.

4. Jegou H, Douze M, Schmid C. Product quantization for nearest neighbor search. IEEE Trans Pattern Anal Mach Intell. 2011;33(1):117-28.

5. Bernhardsson E. Annoy: Approximate nearest neighbors in C++/Python. GitHub repository. 2018. Available from: https://github.com/spotify/annoy

6. Babenko A, Lempitsky V. The inverted multi-index. IEEE Trans Pattern Anal Mach Intell. 2014;37(6):1247-60.

7. Simhadri HV, et al. Results of the NeurIPS 2021 challenge on billion-scale approximate nearest neighbor search. In: NeurIPS 2021 Competition Track. 2022.

8. Simhadri HV, et al. Results of the Big ANN: NeurIPS'23. arXiv. 2024. Available from: arXiv:2409.17424

9. Malkov Y, et al. hnswlib: Header-only C++/Python library for fast approximate nearest neighbors. GitHub repository. Available from: https://github.com/nmslib/hnswlib

10. Gollapudi S, et al. Filtered-DiskANN: Graph algorithms for approximate nearest neighbor search with filters. In: Proc ACM Web Conf (WWW). 2023. p. 3406-16.

11. Patel L, Kraft P, Guestrin C, Zaharia M. ACORN: Performant and predicate-agnostic search over vector embeddings and structured data. Proc ACM Manag Data (SIGMOD). 2024;2(3).

12. Wang M, Lv L, Xu X, Wang Y, Yue Q, Ni J. An efficient and robust framework for approximate nearest neighbor search with attribute constraint. In: Proc NeurIPS. 2023.

13. Wang J, et al. Milvus: A purpose-built vector data management system. In: Proc ACM SIGMOD. 2021. p. 2614-27.

About the Article

Cite this Article

Shaikh DN. ANNex: Efficient Filtered Approximate Nearest Neighbor Search via Graph-Traversal Metadata Filtering. IgMin Res. September 30, 2026; 4(9): 413-419. IgMin ID: igmin365; DOI:10.61927/igmin365; Available at: igmin.link/p365

• DOI10.61927/igmin365

24 Aug, 2026

Received

28 Sep, 2026

Accepted

30 Sep, 2026

Published

Share this Article

Anyone you share the following link with will be able to read this content:

Get shareable link

Topics

Machine Learning