PaperlayerView exact revision on arXiv

Source-linked AI summary

ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data

Liana Patel, Peter Kraft, Carlos Guestrin, Matei Zaharia

arXiv:2403.04871v1cs.IRcs.DB

TL;DR

Hybrid search must combine vector similarity with structured predicates, but existing filtering methods can be inefficient and specialized indices restrict predicate sets. ACORN adapts HNSW using predicate-subgraph traversal and predicate-agnostic construction. Across prior and more complex benchmarks, it reports substantially higher throughput than prior methods at fixed recall.

  • Problem

    Existing hybrid-search methods either have performance limitations or restrict support to small sets of equality predicates, while applications need expressive structured filtering alongside vector similarity.

    Source: §1 · p. 1

  • Method

    ACORN modifies HNSW with predicate-subgraph traversal and predicate-agnostic construction to support high-cardinality and unbounded predicate sets.

    Source: §1 · p. 2

  • Results

    2–1,000× higher QPS at 0.9 recall than prior methods across benchmark types; ACORN-1 approximates ACORN-γ’s search performance with 9–53× lower TTI.

    Source: §9 · p. 14

  • Takeaways & Limitations

    ACORN’s predicate-subgraph strategy is designed to support arbitrary predicate sets while maintaining sublinear retrieval despite variation in query-predicate correlation.

    Source: §1 · p. 2

    Neither HNSW nor ACORN provides theoretical guarantees of connectivity over its level graphs for arbitrary datasets.

    Source: §6.3.1 · p. 8

Abstract

from arXiv · show

Applications increasingly leverage mixed-modality data, and must jointly search over vector data, such as embedded images, text and video, as well as structured data, such as attributes and keywords. Proposed methods for this hybrid search setting either suffer from poor performance or support a severely restricted set of search predicates (e.g., only small sets of equality predicates), making them impractical for many applications. To address this, we present ACORN, an approach for performant and predicate-agnostic hybrid search. ACORN builds on Hierarchical Navigable Small Worlds (HNSW), a state-of-the-art graph-based approximate nearest neighbor index, and can be implemented efficiently by extending existing HNSW libraries. ACORN introduces the idea of predicate subgraph traversal to emulate a theoretically ideal, but impractical, hybrid search strategy. ACORN's predicate-agnostic construction algorithm is designed to enable this effective search strategy, while supporting a wide array of predicate sets and query semantics. We systematically evaluate ACORN on both prior benchmark datasets, with simple, low-cardinality predicate sets, and complex multi-modal datasets not supported by prior methods. We show that ACORN achieves state-of-the-art performance on all datasets, outperforming prior methods with 2-1,000x higher throughput at a fixed recall.

1 INTRODUCTION

ACORN addresses hybrid search over vectors and structured predicates, where existing filtering methods can be inefficient and specialized indices support restricted predicate sets. It adapts HNSW for predicate-agnostic search and reports higher throughput than prior methods across benchmark types.

1 INTRODUCTION

  • Hybrid search combines approximate vector-neighbor search with structured-predicate filtering, and applications need both efficient performance and expressive query semantics.The paper cites examples including product searches filtered by price and literature searches filtered by date or topics.Source: §1 · p. 1
  • Pre-filtering scales poorly at medium-to-high selectivity, post-filtering may require expensive search expansion, and specialized indices often restrict predicate sets.Specialized approaches described here target low-cardinality equality predicates and may assume only one structured attribute.Source: §1 · p. 1
  • ACORN is designed to support arbitrary, unbounded predicate sets rather than requiring the predicate set to be known in advance.Source: §1 · p. 2
  • ACORN traverses the index subgraph induced by predicate-passing nodes and constructs a denser graph to support those predicate subgraphs.ACORN-γ uses predicate-agnostic neighbor expansion and compression; ACORN-1 targets lower construction overhead while approximating ACORN-γ search performance.Source: §1 · p. 2
  • 2–1,000× higher QPS at 0.9 recall versus prior methods; ACORN-1 reaches at most 5× lower QPS but 9–53× lower TTI than ACORN-γ.The evaluation covers prior low-cardinality benchmarks and more complex datasets with millions of possible predicates.Source: §1 · p. 2

2 BACKGROUND

Graph-based ANN search routes through proximity graphs, and HNSW organizes such search into levels. Its construction and search procedures use those levels to move from long-range links toward local neighbors.

2 BACKGROUND

  • Graph-based ANN indices represent data points as vertices connected by proximity edges and typically search through the graph using greedy routing.The graph construction aims to approximate tractable subgraphs of proximity structures such as the Delaunay graph.Source: §2 · p. 2

2.1 Hierarchical Navigable Small Worlds

  • HNSW assigns points to a hierarchy of graph levels, with longer-range links above and shorter-range links at the bottom.The level assignment uses an exponentially decaying probability distribution, and the degree is bounded by parameter M, with a larger bound at level 0.Source: §2.1 · p. 2, Figure 1 · p. 2
  • HNSW search descends from an upper-level entry point, choosing a node to enter the next level before searching for nearest elements at the bottom.At the bottom level, efs controls the dynamic candidate-list size and trades search quality against efficiency.Source: §2.1 · p. 3

3 PROBLEM DEFINITION AND CHALLENGES

This section defines hybrid search and analyzes how selectivity, dataset size, and query correlation affect baseline performance. It formalizes query correlation by comparing filtered targets with a same-size random reference set.

3 PROBLEM DEFINITION AND CHALLENGES

  • The analysis examines selectivity, dataset size, and query correlation as workload characteristics affecting pre- and post-filtering performance.Source: §3 · p. 3

3.1 Hybrid Search Definitions

  • Hybrid search retrieves a query vector’s K nearest neighbors that satisfy its predicate; predicate selectivity is the fraction of entities satisfying that predicate.Source: §3.1 · p. 3

3.2 Search Performance of Baseline Methods

  • Pre-filtering achieves perfect recall but costs O(s n + K), while post-filtering ranges from O(log(n) + K/s) under uniform target distribution to O(n) in the worst case.The paper says neither baseline is robust to variations in selectivity, dataset size, and query correlation.Source: §3.2 · p. 3

3.2.1 Formalizing Query Correlation.

  • Query correlation compares query-to-target distances in the real filtered set against a same-size random subset; positive correlation means real targets are closer, and negative means they are farther.Figure 2 contrasts no predicate clustering with clustered targets under positive and negative query correlation.Source: §3.2.1 · pp. 3–4, Figure 2 · p. 3

4 THEORETICAL IDEAL HYBRID SEARCH PERFORMANCE WITH HNSW

The oracle partition index defines ideal HNSW-based hybrid-search performance when the query predicate is known during construction. It searches only predicate-matching data, but is impractical when predicates are unknown or numerous.

4 THEORETICAL IDEAL HYBRID SEARCH PERFORMANCE WITH HNSW

  • The oracle partition index is an HNSW index built over X_p when the query predicate is known during construction.Its search complexity is O_s(log_s n + K).Source: §4 · p. 4
  • Oracle-partition search scales sublinearly in |X_p| and outperforms pre- and post-filtering across selectivity, data size, and query-correlation variations.Unlike post-filtering, it does not require search-scope expansion under varying query correlation.Source: §4 · p. 4
  • Constructing an oracle partition index is impractical because it requires advance knowledge of predicates and a full HNSW index per predicate.Unknown or high-cardinality predicate sets make the required space and construction time prohibitive.Source: §4 · p. 4

5 ACORN OVERVIEW

ACORN approximates oracle-partition search by traversing predicate-induced subgraphs, with two variants designed for different construction and resource trade-offs. Its search modifies neighbor lookup to recover neighborhoods that satisfy the query predicate.

5 ACORN OVERVIEW

  • ACORN offers ACORN-γ for efficient search and ACORN-1 to approximate its search performance while reducing indexing time and space.Both variants are predicate-agnostic and focus on HNSW.Source: §5 · p. 4
  • ACORN searches the subgraph induced by the query predicate, modifying HNSW construction so arbitrary predicate subgraphs emulate an oracle partition without constructing one.ACORN-γ builds a denser graph, while ACORN-1 expands neighbor lists during search instead of construction.Source: §5 · p. 4

5.1 ACORN-𝛾Search Algorithm

  • At each visited node, ACORN performs extra neighbor lookups to recover an appropriate neighborhood for the query predicate.For highly selective queries whose predicate subgraph may be disconnected, ACORN falls back to pre-filtering below a configured minimum selectivity.Source: §5.1 · p. 4

20 end

ACORN-γ expands candidate neighbor lists and prunes them to control index size, then recovers pruned neighbors through search-time expansion. ACORN-1 instead defers neighbor expansion to search to reduce construction overhead and space.

20 end

  • Search filters neighbors by the query predicate and truncates to M; its compression-based lookup also expands selected nodes’ two-hop neighbors before filtering.The two-phase strategy first filters the first Mβ neighbors, then expands neighbors of neighbors among the remainder.Source: §20 · p. 5

5.2 ACORN-𝛾Construction Algorithm

  • ACORN-γ collects M·γ candidate edges per node, but traverses using only the first M neighbors to avoid unnecessary distance computations and TTI slowdowns.The expanded candidate lists are gathered with metadata-agnostic graph search.Source: §5.2 · p. 5
  • ACORN can route queries with estimated selectivity above 1/γ to its index and use pre-filtering otherwise; estimation errors can lower QPS but not result quality.The construction and space footprint increase proportionally to γ.Source: §5.2 · pp. 5–6
  • To control the size and indexing overhead from expansion, ACORN-γ retains the nearest Mβ candidates and prunes farther candidates for recovery through two-hop search.The pruning procedure removes candidates represented among chosen neighbors’ neighbors, subject to a bound on expanded neighborhood size.Source: §5.2 · p. 6
  • HNSW’s metadata-blind pruning can remove an edge needed within a predicate subgraph when the intermediate node fails that predicate.For arbitrary predicates, ensuring pruned edges remain represented by valid predicate-subgraph paths is intractable.Source: §5.2 · p. 6

5.3 ACORN-1

  • ACORN-1 uses an HNSW-style construction with γ=1 and Mβ=M, then expands each visited node’s one-hop and two-hop neighbors during search.This moves expansion from construction to search to approximate ACORN-γ while minimizing index size and TTI.Source: §5.3 · p. 6

6 DISCUSSION

ACORN-γ’s analysis bounds its memory, construction, and search costs while examining when predicate subgraphs retain HNSW-like search properties. The analysis also notes that connectivity is not guaranteed for arbitrary datasets.

6.1 Index Size

  • ACORN-γ uses O(Mβ + M + mL·M·γ) memory per node, with compression focused on level 0, the index’s largest space component.Compression could be extended to additional levels in bottom-up order to further reduce index size.Source: §6.1 · pp. 6–7

6.2 Construction Complexity

  • O(n·γ·log(n)·log(γ)) is ACORN-γ’s expected construction complexity, increasing time-to-index over HNSW by a factor of γ·log(γ).The increase is attributed to expanded edge lists; the analysis decomposes construction cost into dataset size, levels searched, and per-level search complexity.Source: §6.2 · p. 7

6.3.1 Index and Search Properties.

  • Predicate subgraphs inherit HNSW’s level-sampling probabilities, bounding expected greedy search path length at each level by a constant.The analysis also notes that ACORN’s levels approximate KNN graphs rather than HNSW’s RNG graphs.Source: §6.3.1 · p. 7
  • A fixed, predicate-independent entry point can route to a predicate-subgraph entry point when a fully connected upper level contains a matching node.The analysis gives minimum selectivity s_min = 1/γ for the probability that predicate-matching nodes occur on some level.Source: §6.3.1 · p. 8
  • Neither HNSW nor ACORN guarantees connectivity for arbitrary datasets; the analysis relies mainly on empirical results and recommends raising γ if recall trails HNSW.Connectivity may be expected in cases without predicate clustering or with a single-region cluster; reported bounds decay exponentially in γ.Source: §6.3.1 · p. 8

6.3 Search Analysis

  • Search proceeds through an initial filtering stage and predicate-subgraph traversal, whose expected complexity is O((d + γ)·log(s·n)).The first stage has O(log(1/s)) complexity; the second traverses the predicate subgraph.Source: §6.3.1 · p. 8

7 EVALUATION

The evaluation covers prior low-cardinality benchmarks and more complex high-cardinality workloads. ACORN-γ reports higher throughput than prior methods across these settings, while ACORN-1 offers a construction-time trade-off.

7 EVALUATION

  • 2–1,000× higher QPS at 0.9 recall is reported for ACORN-γ over existing methods across low- and high-cardinality predicate benchmarks.The evaluation summary also reports up to 5× higher QPS for ACORN-γ than ACORN-1 at fixed recall, while ACORN-1 has 9–53× lower time-to-index.Source: §7 · p. 8

7.1 Datasets

  • The evaluation uses two low-cardinality and two high-cardinality datasets, with the latter chosen to represent more complex, realistic query workloads.Table 2 is identified as a summary of all datasets.Source: §7.1 · p. 8, Table 2 · p. 9

7.1.1 Datasets with Low Cardinality Predicate Sets.

  • SIFT1M and Paper use randomly assigned integer attributes and exact-match predicates over a set of 12 possible values.The datasets contain about 1 million and 2 million base vectors, respectively.Source: §7.1.1 · p. 9

7.1.2 Datasets with High Cardinality Predicate Sets.

  • TripClick and LAION provide high-cardinality workloads, including date, clinical-area, keyword, and regex predicates.LAION workloads vary query correlation; TripClick uses clinical-area or publication-date filters.Source: §7.1.2 · p. 9

7.2 Benchmarked Methods

The benchmark compares ACORN variants with filtering-based, specialized-index, and oracle-partition methods. Implementations and parameters are selected to produce recall–QPS comparisons across datasets.

7.2 Benchmarked Methods

  • The evaluated methods are implemented in C++ in the FAISS codebase, including ACORN-γ, ACORN-1, pre-filtering, and HNSW post-filtering.The remaining benchmarked methods are described with their respective parameter-selection procedures.Source: §7.2 · p. 9
  • Pre-filtering finds matching records before brute-force distance search, whereas HNSW post-filtering over-searches to K/s candidates before filtering.The post-filtering baseline uses dataset-specific HNSW construction parameters, with TripClick parameters tuned for ANN recall and QPS.Source: §7.2 · p. 9
  • Figure 6 contrasts vector-only retrieval with keyword-filtered hybrid retrieval and shows examples for positive, uncorrelated, and negative query correlation.The illustrated LAION hybrid queries use a single keyword filter and the same query image as vector-only search.Source: Figure 6 · p. 10
  • The comparisons include Filtered-DiskANN, NHQ, Milvus, and an oracle partition index that builds one HNSW index per possible predicate.Filtered-DiskANN and NHQ use recommended parameters; the oracle partition uses the HNSW post-filtering parameters.Source: §7.2 · p. 10
  • ACORN-1 fixes γ = 1 and Mβ = M, while ACORN-γ uses dataset-specific γ and Mβ settings chosen for query throughput under memory constraints.ACORN-γ’s Mβ is set to M or 2M, and γ is selected according to expected minimum predicate selectivity.Source: §7.2 · p. 10

7.3 Search Performance Results

ACORN-γ delivers higher throughput at fixed recall on both low-cardinality and high-cardinality predicate benchmarks. Its advantage persists across selectivity, query-correlation, and dataset-size variations.

7.3.1 Benchmarks on LCPS Datasets.

  • 2–10× higher QPS at fixed recall values on SIFT1M and Paper lets ACORN-γ approach the oracle partition while retaining generality.ACORN-1 attains about 1.5–5× lower QPS than ACORN-γ across a range of recall values.Source: §7.3.1 · p. 10, Figure 7 · p. 11

7.3.2 Benchmarks on HCPS Datasets.

  • 30–50× higher QPS at 0.9 recall on TripClick and LAION-1M puts ACORN ahead of the baselines.Pre-filtering obtains perfect recall at the price of efficiency; post-filtering fails to obtain high recall.Source: §7.3.2 · p. 11, Figure 8 · p. 11
  • 5–50× higher QPS at 0.9 recall across TripClick predicate-selectivity percentiles makes ACORN-γ the best-performing method in each case.Pre-filtering is most competitive at low selectivity; at high selectivity it becomes less competitive, while post-filtering gains throughput but retains low recall.Source: §7.3.2 · p. 11
  • 28–100× higher QPS at 0.9 recall than the next-best baseline across LAION-1M query-correlation workloads shows ACORN-γ's robustness to correlation variation.Post-filtering is most competitive with positive correlation but does not attain recall above 0.9; ACORN-1 approaches ACORN-γ's performance.Source: §7.3.2 · p. 11
  • Over three orders of magnitude higher QPS at 0.9 recall than the next-best baseline on LAION-25M shows ACORN's advantage grows with dataset scale.ACORN-1 approximates ACORN-γ's search performance.Source: §7.3.2 · p. 11

7.4 Index Construction

ACORN-γ trades higher construction overhead for stronger search performance, while ACORN-1 offers a lower-overhead approximation. ACORN-γ's pruning reduces construction costs, and its predicate subgraphs empirically emulate key HNSW graph properties.

7.4.1 TTI and Space Footprint.

  • Moving neighbor-list expansion from construction to search gives ACORN-1 a close search-performance approximation at lower TTI and space footprint than ACORN-γ.ACORN-γ stores up to M×γ edges per node during construction; ACORN-1 stores up to M and approximates an M×γ edge list during search.Source: §7.4.1 · p. 12
  • ACORN-1 has the lowest TTI among listed baselines, while ACORN-γ's TTI is at most 11× HNSW's and 2.15× StitchedVamana's.ACORN-γ's index is at most 1.3× HNSW's size and at least 25% smaller than StitchedVamana's; ACORN-1's is at most 1.25× HNSW's and at least 25% smaller than StitchedVamana's.Source: Table 4 · p. 12, §7.4.1 · p. 12, Table 5 · p. 12
  • ACORN's predicate-agnostic pruning reduces TTI and space footprint while maintaining search performance; HNSW pruning significantly degrades hybrid-search performance.At small Mβ values such as 32 or 64, metadata-aware RNG pruning has similar search performance but is less efficient in TTI and space footprint.Source: §7.4.2 · p. 12, Figure 12 · p. 13

7.4.3 Graph Quality.

  • ACORN-γ predicate subgraphs match or exceed oracle-partition connectivity and emulate its graph height across selectivities.Their average out-degrees are close to and bounded by M; the 1-percentile-selectivity subgraph has lower out-degree because some upper levels contain fewer than 128 nodes.Source: §7.4.3 · p. 13

8 RELATED WORK

Prior hybrid-search systems use pre- or post-filtering, or indices specialized for restricted predicate sets. These approaches retain limitations in performance or predicate expressiveness.

8 RELATED WORK

  • Pre- and post-filtering remain limited by expensive distance computations, particularly with low-correlation or low-selectivity predicates.Systems may optimize filtering steps, but those optimizations do not remove the core problems of the two approaches.Source: §8 · p. 13
  • Specialized indices restrict supported queries: NHQ assumes one structured attribute and equality predicates, while Filtered-DiskANN targets about 1,000 equality filters.HQI assumes a limited cardinality of 20 query predicates for its batch-processing partitioning scheme.Source: §8 · p. 13
  • Qdrant densifies HNSW by increasing M, which flattens the graph and can degrade search performance; it also does not address the resulting memory overhead.The cited discussion notes that HNSW performance is sensitive to its number of levels.Source: §8 · p. 13

9 CONCLUSION

ACORN supports efficient hybrid search across vectors and structured data with large, diverse predicate sets. ACORN-γ improves throughput across benchmark types, while ACORN-1 approximates its search performance with lower construction time.

9 CONCLUSION

  • ACORN-γ achieves 2–1,000× higher QPS at 0.9 recall than prior methods across low-cardinality and complex, high-cardinality benchmarks.The evaluated benchmarks include new predicate operators and high-cardinality predicate sets.Source: §9 · pp. 13–14
  • ACORN-1 approximates ACORN-γ's search performance with 9–53× lower TTI for resource-constrained settings.Source: §9 · p. 14
Loading 2403.04871v1…