arXiv CSopen access

Revisiting Filtered ANN Benchmarks: A Hardness-Controlled Benchmark Generator for Realistic Evaluation

Revisiting Filtered ANN Benchmarks: A Hardness-Controlled Benchmark Generator for Realistic Evaluation Mintaek Lim

Dogeun Kim

Minwoo Kim

Jaeyoung Do∗

Seoul National University South Korea, Seoul [email protected]

Seoul National University South Korea, Seoul [email protected]

Seoul National University South Korea, Seoul [email protected]

Seoul National University Seoul, South Korea [email protected]

RWalks [38] ACORN [45]

PVLDB Reference Format: Mintaek Lim, Dogeun Kim, Minwoo Kim, and Jaeyoung Do. Revisiting Filtered ANN Benchmarks: A Hardness-Controlled Benchmark Generator for Realistic Evaluation. PVLDB, 14(1): XXX-XXX, 2020. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/yoon123seul/hardness_aware_fann_benchmarking.git.

1

INTRODUCTION

Vector search [22, 24, 32] has become a first-class primitive in modern data management, powering retrieval-augmented generation (RAG)[26], recommendation engines[8, 34], e-commerce search[27, ∗ Corresponding author.

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

NHQ [39] UNG [6]

HCBGen (Ours, High-Car.) HCBGen (Ours, High-Sel.)

1.0 0.8

Recall@10

arXiv:2606.14193v1 [cs.DB] 12 Jun 2026

ABSTRACT Filtered approximate nearest neighbor (FANN) search must satisfy both vector similarity and structured predicates, yet evaluations remain brittle because real hybrid workloads are rarely shareable and existing benchmarks rely on ad-hoc synthetic or semi-real constructions. We argue that realism hinges on execution-driven query difficulty: failures in early filtering trigger over-fetching of additional candidates, shaping latency, throughput, and recall. Building on this insight, we propose 𝛼-Hardness, a query-level hardness metric that models the conditional execution chain via the overfetch factor and extends naturally to strategy-conditioned settings. Across diverse datasets and hybrid strategies, 𝛼-Hardness exhibits strong monotonic alignment with empirical performance, while common proxies such as selectivity or attribute–vector correlation are frequently unstable or strategy-inconsistent. We further introduce HCBGen, a hardness-controlled benchmark generator that uses 𝛼-Hardness as an explicit control signal to synthesize workloads under coarse bias modes or to match a target hardness profile. Our experiments show that widely used benchmarks occupy a narrow, relatively easy portion of the hardness spectrum, masking robustness gaps that emerge under harder queries. Finally, we demonstrate that matching hardness distributions enables privacypreserving proxy workloads that closely reproduce performance trends, bridging research benchmarks and real evaluation.

0.6 0.4 0.2 0.0

103

104

QPS

105

Figure 1: Recall–QPS trade-off curves of the RWalks index evaluated on six synthetic hybrid workloads built from the same vector-only dataset under different label-synthesis policies (four adopted from prior studies and two generated by our hardness-controlled framework: High Cardinality and Highly Selective). Although the workload configuration used in the RWalks paper (red) achieves near-perfect Recall@10 at high throughput, the other workload designs induce substantially different trade-offs, demonstrating that hybrid-index performance can be highly sensitive to workload construction, even with the underlying vector corpus and index fixed. 61], and multi-modal analytics[31, 36]. In production, however, similarity alone is insufficient: queries must also enforce structured predicates such as category, time, or product attributes[11, 38, 39, 42, 57] that are non-negotiable for correctness and safety. For example, in ANN-based scholarly search systems, users issue queries in natural language, which are then embedded to retrieve relevant papers based on vector similarity. However, users may also require results restricted to specific venues or publication years. In such cases, the query must include structured predicates in addition to the embeddings, such as "year = 2026 and venue = VLDB". Without these constraints, the system may return semantically relevant but out-of-scope papers. This requires the system to index data containing both structured attributes and unstructured embeddings, and to optimize retrieval so that the returned points satisfy the filter predicates while remaining closest to the query embedding. While algorithmic progress has been rapid, the field faces a quieter but consequential bottleneck: we still lack a reliable and practical way to benchmark hybrid indexing methods [19, 46]. Reported results often fail to transfer across datasets, query patterns, and deployment contexts, making it difficult for practitioners to trust which method to adopt and for researchers to draw durable conclusions [19, 39]. The root cause is not that hybrid queries are uncommon, but that real-world hybrid workloads are rarely shareable due to privacy constraints [2, 3], proprietary concerns [9, 12, 17], and limited public coverage [38]. As a result, most studies evaluate

hybrid indices using synthetic or semi-real workloads, typically constructed by taking a vector-only dataset and synthesizing labels, attributes, and filtered queries [39, 55, 59]. Benchmarks therefore exist and are widely used, but they suffer from a fundamental reliability issue: a “hybrid workload” is not uniquely determined by the underlying vector dataset. Instead, it depends on benchmark design choices such as how attributes are assigned to vectors, how filters are composed, and how queries are generated, which are often implicit or inconsistent across studies [6, 45, 46]. Even when the base vectors are identical, seemingly minor design changes can substantially alter effective workload difficulty and thus the observed ranking of methods. Figure 1 makes this sensitivity concrete: RWalks [38], evaluated on multiple synthetic hybrid workloads built from the same vector-only dataset, SIFT1M [21], under different label-synthesis policies, exhibits widely different recall–QPS trade-offs, implying that without a principled way to characterize and control workload difficulty, hybrid benchmarking may inadvertently favor particular strategies. Because current synthetic benchmarks neither explicitly model nor sufficiently control query difficulty, such variability is often masked by aggregate reporting based on average-case metrics [6, 39]. In practice, however, real hybrid workloads span a wide range of difficulty, and a small fraction of hard queries can dominate tail latency and expose system-level failures [12, 29, 51, 56, 58]. Consequently, current benchmarking practices hinder reliable assessment and pose a practical barrier to the adoption of FANN techniques in commercial vector database systems [1, 5, 58]. This challenge stems from the absence of a principled notion of query-level hardness for hybrid search. Existing proxies such as selectivity and correlation [30, 45] capture only partial aspects of difficulty and cannot explain the large performance variance among queries with similar proxy values (Section 3.1). As a result, prior work mainly controls dataset properties such as cardinality, skew, correlation, and missingness [6, 39, 45], while query workloads are generated through simple heuristics such as random attribute combinations or selectivity targets [46]. To overcome these limitations, we propose 𝛼-Hardness, a principled definition of query-level hardness for hybrid search, and introduce a hardness-controlled benchmarking methodology in which the construction and evaluation of workloads are directly guided by hardness. Our key insight is that query difficulty arises from the execution process itself, rather than from isolated static properties. We model FANN execution as a conditional chain, capturing how vector retrieval, over-fetching, and conditional filtering interact and how computational cost accumulates along the execution path [55]. This execution-driven formulation yields a unified hardness metric that (i) closely aligns with empirical search performance and (ii) remains robust to previously unmodeled factors, since new influences naturally manifest as changes within the same execution structure rather than requiring ad-hoc proxy extensions. Hardness is not only diagnostic; it enables a new benchmarking methodology by making workload difficulty explicit and controllable. Building on this model, we introduce a hardness-controlled benchmark generator(HCBGen) that treats hardness as an explicit control knob for workload construction. Instead of generating queries via ad-hoc rules (e.g., targeting selectivity alone or sampling random filter combinations) the generator systematically

synthesizes workloads with prescribed hardness profiles. In particular, it can (i) construct workloads spanning Random-, Low-, and High-hardness regimes for controlled evaluation, and (ii) approximate realistic workloads by matching a target hardness distribution. This design unlocks three practical capabilities: (1) Fair comparison: it evaluates methods under comparable difficulty regimes, reducing the risk that workload construction implicitly advantages a specific strategy. (2) Systematic stress testing: it deliberately instantiates high-hardness workloads to expose failure modes and tail-latency behavior, rather than only average-case performance. (3) Privacy-preserving workload sharing: it enables organizations to share hardness specifications (e.g., hardness distributions) in lieu of raw query logs or sensitive attributes, while still supporting reproducible and predictive performance characterization. Finally, our extensive experiments show that widely used synthetic hybrid benchmarks occupy only a narrow—and relatively easy—portion of the hardness spectrum, highlighting the need for hardness-controlled benchmarking to obtain results that generalize beyond favorable workloads. Our contributions are as follows: • We define 𝛼-Hardness, an execution-driven metric for querylevel difficulty in FANN that aligns with empirical performance. • We revisit common hybrid benchmarking practices and show that many evaluations are biased toward easy queries, masking tail behavior and limiting generalizability. • We present a hardness-controlled benchmark generator (HCBGen) that enables controlled workload construction, fair and index-agnostic benchmarking, stress testing under targeted hardness regimes, and privacy-preserving approximation of real workloads through hardness specifications.

2 PRELIMINARY 2.1 Filtered ANNs FANN search extends semantic search by jointly enforcing vector similarity and structured filter constraints. In standard ANN search, a query retrieves nearest neighbors based only on vector distance. In contrast, FANN additionally imposes predicates over structured attributes such as categorical labels, numeric ranges, or other metadata constraints [39, 45]. Formally, let the base data be defined as D = {(v𝑖 , a𝑖 ) | 𝑖 = 1, . . . , 𝑁 }, where v𝑖 ∈ R𝑑 denotes the 𝑑 dimensional embedding vector of data point 𝑖, and a𝑖 represents its associated set of structured attributes. A FANN (hybrid) query 𝑞 is specified by a vector predicate 𝑞 𝑣 ∈ R𝑑 and a set of filter predicates 𝑞 𝑓 , which together define the similarity requirement and the desired attribute constraints of the query. The goal of FANN search is to retrieve the top-𝐾 nearest neighbors to 𝑞 𝑣 among only those data points satisfing the filter constraint 𝑞 𝑓 : ∑︁ FANN(𝑞 hybrid ) = arg min 𝑑 (𝑞 𝑣 , v𝑖 ). 𝑆 ⊆ {𝑖 |𝑞 𝑓 ⊆a𝑖 } 𝑖 ∈𝑆 |𝑆 |=𝐾

where 𝑑 (·, ·) denotes a distance function defined on the embedding space. The additional filter constraints beyond traditional ANN search make FANN fundamentally a two-dimensional retrieval problem, forcing the system to trade off which condition to prioritize 2

B1

during pruning, and thus requiring the index to simultaneously handle unstructured vector similarity and structured evaluation.

2.2

Hard

B4

B5

B6

B7

B8

B9

B10

Easy

Figure 2: Success and failure cases of query ordering for recall–QPS trade-offs. For each proxy, queries are sorted by the estimated score and split into 10 equal-sized percentile bins (B1=hardest 10% → B10=easiest 10%). We plot recall–QPS curves for each bin on a synthetic SIFT1M-based benchmark using RWalks: (a) Successfully aligned (Ours), (b) Misaligned (Selectivity), and (c) Misaligned (Correlation). points align with the query vector’s neighborhood [30, 45]. In general, lower selectivity tends to increase difficulty because an index must examine more candidates to obtain 𝐾 valid results, degrading throughput and/or recall [38]. Likewise, higher correlation typically makes queries easier: when filter-satisfying points are spatially clustered near the query vector, graph-based indices are more likely to reach valid targets through graph paths, improving recall while shrinking the explored search space and increasing throughput. However, selectivity and correlation only partially describe the execution of FANN. Both are one-dimensional, static statistics, whereas actual difficulty is shaped by execution dynamics (i.e., how candidate retrieval, over-fetching, and filtering interact until 𝐾 valid neighbors are obtained.) Consequently, the same global selectivity can induce very different local availability of filter-satisfying points around the query, and correlation do not directly determine how many candidates must be explored before 𝐾 valid results are found. As a result, the ordering implied by selectivity or correlation can differ substantially from the ordering induced by empirical recall–QPS trade-offs. Figure 2 illustrates representative failure cases of this misalignment. Using SIFT1M [21], we synthesize a hybrid workload by assigning three categorical attributes (cardinality 6 each) and generating 10,000 queries (details in Section 3.4). We sort queries by each proxy, partition them into 10 bins, and evaluate each bin independently using RWalks [38]. A lower bin index corresponds to a lower proxy value (interpreted as “harder”), while curves closer to the upper-right indicate better recall–QPS trade-offs (“easier”). (a) is included as a reference case (sorted by 𝛼-Hardness, Section 3.4), illustrating a setting where bin-wise query performance is well aligned and exhibits a consistent ordering. Yet, in both (b) and (c), neither selectivity nor correlation yields a consistent ordering that aligns with actual performance. These observations indicate that query hardness cannot be reliably characterized by static, measurement-based proxies alone. More broadly, a straightforward attempt to define a single scalar hardness by composing multiple measurements suffers from two

QUERY-LEVEL HARDNESS MODELING

FANN (hybrid) query performance variance is dominated not only by the dataset and index, but also by the execution dynamics induced by enforcing both constraints. We therefore model querylevel hardness as an execution-grounded quantity that predicts how much work a system must perform to return 𝐾 valid neighbors. This section (i) explains why conventional proxy measures fail to model query hardness, (ii) proposes an execution-grounded hardness model, and (iii) extends the model to be strategy-conditioned.

3.1

B3

Filtered ANN Approaches

With the growing attention in FANN search, a range of approaches have been proposed, from simple baselines to hybrid-native indexing methods. The two most common baseline strategies are Post-Filtering and Pre-Filtering. Post-Filtering retrieves candidates based solely on vector similarity to the query vector 𝑞 𝑣 and applies the filter predicate afterward. Because the fraction of filtersatisfying candidates is unknown, this approach typically relies on over-fetching, using a vector-only index such as HNSW [32] followed by filtering. Pre-filtering applies the filter predicate before vector search, considering only filter-satisfying data points. While this avoids over-fetching and guarantees full recall, the lack of query-specific indices often forces a brute-force scan over the filtered subset, resulting in poor scalability and query throughput. Beyond these baselines, several hybrid-native indices have been proposed to more tightly integrate vector similarity and filtering during search, including NHQ[39], ACORN[45], UNG[6], RWalks[38], and Filtered-DiskANN (FDANN) [16]. NHQ extends graph-based ANN search by defining a hybrid distance metric that augments the original vector distance with an attribute-based distance, enabling joint navigation over vector and attribute spaces. ACORN builds upon HNSW by constructing a denser graph at index build time and restricting traversal at query time to nodes that satisfy the filter predicate, thereby approximating an oracle index tailored to each query. UNG groups base data points by shared attribute values and constructs a unified navigable graph that explicitly models both intra-group and inter-group connectivity based on attribute inclusion relationships. RWalks propagates attribute information across the graph during index construction, in a manner reminiscent of node information propagation in graph neural networks [62] to build an attribute matrix, and leverages it at query time to guide search toward filter-satisfying data points. FDANN extends graphbased ANN search with label-aware filtering by starting traversal from entry points guaranteed to contain the query label and exploring only filter-satisfying nodes during search.

3

B2

Why Proxy-Based Hardness Fails

Unlike relational database systems[5, 20, 25, 52], query-level hardness in FANN search has been relatively under explored [30, 63]. Prior work therefore relies on two intuitive proxy measurements for hybrid query difficulty: selectivity, the fraction of base points satisfying the filter, and correlation, the degree to which filter-satisfying 3

fundamental limitations. First, such measurements provide only indirect signals and do not explicitly model search execution, so alignment with performance is not guaranteed. Second, measurementbased definitions are inherently incomplete: newly discovered hardnessrelated factors require revising both the hardness definition and the associated measurement set. This motivates an execution-grounded hardness definition that is anchored in the search process rather than in ad-hoc proxy statistics.

the cost of scanning these 𝑚 candidates and extracting 𝐾 filtersatisfying results. Then the 𝛼-Hardness of 𝑞 is defined as

3.2

Plugging 𝑚 = 𝛼 (𝑞; 𝐾) into Eq. (2) and substituting into Eq. (1) yields

Execution-Grounded Hardness via Conditional Over-Fetching

𝐻𝛼 (𝑞|𝐾) ≜ 𝐻 fetch (𝑞 𝑣 |𝛼 (𝑞; 𝐾)) × 𝐻 scan (𝑞 𝑓 |𝑞 𝑣 , 𝛼 (𝑞; 𝐾), 𝐾).

Under post-filtering, predicate checking incurs an (approximately) constant per-candidate cost, so scan hardness scales linearly with the number of examined candidates: 𝐻 scan (𝑞 𝑓 | 𝑞 𝑣 , 𝑚, 𝐾) = 𝐶 scan · 𝑚.

𝐻𝛼 (𝑞 | 𝐾) ∝ 𝐻 fetch (𝑞 𝑣 | 𝛼 (𝑞; 𝐾)) · 𝛼 (𝑞; 𝐾).

To overcome the limitations of measurement-based proxies, we define query-level hardness by explicitly modeling FANN execution as a conditional chain. The key challenge in hybrid search is that the system must jointly satisfy vector similarity and a structured predicate; when early-stage filtering fails to produce enough valid results, the search must over-fetch and continue exploring, a behavior commonly observed in practical systems (e.g., post-filtering pipelines) [39, 55]. Our formulation captures this execution dynamic through an over-fetch factor, yielding (i) stronger alignment with empirical performance and (ii) a structurally complete definition whose functional form does not require revision when new hardness-related phenomena are discovered.

(1)

(2)

(3)

Monotonicity and alignment with performance. Hardness should increase monotonically with chain cost: larger 𝛼 raises scanning cost and drives retrieval deeper, increasing 𝐻 fetch (𝑞 𝑣 | 𝛼). Thus, higher 𝐻𝛼 implies lower throughput and/or recall under a fixed budget. Equivalently, on a given dataset  D, 𝐻𝛼 is designed to be

1 1 positively associated with Recall · QPS , as validated in Section 3.4. Reducing 𝐻 fetch to vector-only difficulty. Conditioned on the re-

quired depth 𝑚 = 𝛼 (𝑞; 𝐾), the fetch component depends only on the vector predicate, reducing to vector search up to depth 𝑚. Thus, 𝛼-Hardness generalizes Steiner-Hardness [56] from vector-only to hybrid search: 𝐻 fetch captures the Steiner-Hardness of the full graph at depth 𝛼 (𝑞; 𝐾), while the overall formulation also accounts for filter-induced over-fetching. Since 𝛼 (𝑞; 𝐾) is not known a priori, we estimate it with 𝛼b(𝑞; 𝐾) and substitute 𝛼b(𝑞; 𝐾) into 𝐻𝛼 .

Query and execution setting. A hybrid query is 𝑞 = (𝑞 𝑣 , 𝑞 𝑓 ) where 𝑞 𝑣 is the query vector and 𝑞 𝑓 is a set of structured predicates. Let 𝐾 be the target number of returned neighbors. Let 𝑉0 denote the full base data and 𝑉𝑓 ⊆ 𝑉0 the subset satisfying 𝑞 𝑓 .

3.2.3 Estimating 𝛼b(𝑞; 𝐾) via selectivity and local availability. Semantically, 𝛼b(𝑞; 𝐾) represents how many vectors must be traversed around the query vector 𝑞 𝑣 in order to obtain 𝐾 filter-satisfying results. A natural first signal for this quantity is the global selectivity of the filter, 𝑠 = |𝑉𝑓 |/|𝑉0 |. When this fraction is small, valid results are rare in the dataset as a whole, and 𝛼b is therefore likely to increase. However, global selectivity alone is insufficient because it ignores how 𝑉𝑓 is distributed around 𝑞 𝑣 . Vectors and labels can be correlated; for example, papers from a specific year may cluster around certain topics in the embedding space. As a result, even when a filter is globally selective, the filter-satisfying vectors may still be concentrated near the query, in which case the effective over-fetching required to collect 𝐾 valid results can remain small. To capture this effect, we estimate the over-fetching needed to obtain 𝐾 valid results using both global selectivity and a local availability (density) correction:

Key idea. Hybrid query difficulty is governed by how many vectorranked candidates must be examined before execution outputs 𝐾 filter-satisfying results. To make this execution-grounded notion concrete, we start from a canonical execution chain in which overfetching is explicit (post-filtering), and then extend the model to be strategy-conditioned in Section 3.3. 3.2.1 A canonical conditional execution chain. We instantiate querylevel hardness by tracing a simple yet representative post-filtering execution chain: (1) retrieve candidates according to vector similarity; (2) scan candidates and keep only those satisfying 𝑞 𝑓 until 𝐾 valid neighbors are obtained. This chain is methodological rather than restrictive: it is the simplest setting in which over-fetching is explicit, making it a clean basis for defining and estimating hardness, and it matches the vector-centric execution behavior studied throughout this section.

𝛼b(𝑞; 𝐾) ≜

Definition 3.1 (Over-fetch factor). For a hybrid query 𝑞 = (𝑞 𝑣 , 𝑞 𝑓 ) and target 𝐾, the over-fetch factor 𝛼 (𝑞; 𝐾) is the number of vectorranked candidates that must be examined so that the scan phase outputs 𝐾 results satisfying 𝑞 𝑓 .

1 1 · · 𝐾, 𝑠 𝜌 (𝑞)

(4)

where 𝜌 (𝑞) quantifies how much denser filter-satisfying points are around 𝑞 𝑣 compared to the full data. To operationalize local availability, we use a query-local density proxy based on the ratio of 𝐾-NN distances in 𝑉0 and 𝑉𝑓 :
|𝑉0 | 𝑑 𝑞 𝑣 , 𝐾-NN | 𝑉𝑓 𝛼b(𝑞; 𝐾) = · · 𝐾, (5) |𝑉𝑓 | 𝑑 (𝑞 𝑣 , 𝐾-NN | 𝑉0 )

3.2.2 𝛼-Hardness as conditional execution cost. We define 𝛼-Hardness as the execution cost induced by the above conditional chain. To capture the conditional dependence between stages, namely that over-fetching amplifies not only predicate check work but also the required candidate retrieval effort under a fixed operating point, we use a multiplicative form. Let 𝐻 fetch (𝑞 𝑣 | 𝑚) denote the cost of generating the top-𝑚 vectorranked candidates for 𝑞 𝑣 from 𝑉0 . Let 𝐻 scan (𝑞 𝑓 | 𝑞 𝑣 , 𝑚, 𝐾) denote

where 𝑑 (𝑞 𝑣 , 𝐾-NN | 𝑉 ) denotes the distance from 𝑞 𝑣 to its 𝐾-th nearest neighbor within set 𝑉 . Eq. (5) increases 𝛼b when (i) the filter is globally selective (small |𝑉𝑓 |) and/or (ii) valid points are locally sparse near the query (large 𝑑 (· | 𝑉𝑓 ) relative to 𝑑 (· | 𝑉0 )). 4

Finally, substituting 𝛼b(𝑞; 𝐾) into Eq. (3) yields a practical hardness score that can be computed without running the target hybrid index, while remaining tightly coupled to the execution chain. We empirically validate that ordering queries by 𝐻𝛼 aligns well with recall–QPS trends (Section 3.4).

strategy-dependent: different indices enforce vector and filter constraints in different orders, leading to different dominant cost drivers. Accordingly, we denote the resulting score as 𝐻 (𝑞 | strategy). Pre-filtering execution chain. For filter-centric approaches such as UNG, FANN execution can be modeled as first inducing a filtersatisfying subgraph from the full graph index, and then performing vector search within that subgraph. Let 𝐺 0 denote the original graph over the full dataset 𝑉0 , and let 𝐺 𝑓 denote the induced subgraph over 𝑉𝑓 . The corresponding execution chain is

Completeness and extensibility. This formulation supports a structurally complete notion of hybrid query hardness: 𝐻𝛼 is determined by the execution chain and its cost components, rather than by an open-ended set of ad-hoc proxies. Thus, new hardness-related phenomena can be incorporated by refining estimators of the existing chain variables, most notably 𝛼b(𝑞; 𝐾), within the same framework. Our results in Section 3.4 show that this estimation already captures the dominant sources of over-fetching in practice and aligns well with empirical performance.

𝐻 PreFiltering (𝑞 | 𝐾) ≜ 𝐻 restrict (𝑞 𝑓 | 𝐺 0 ) · 𝐻 search (𝑞 𝑣 | 𝐺 𝑓 ), where 𝐻 restrict denotes the cost of identifying the filter-satisfying search space and 𝐻 search the cost of vector search within 𝐺 𝑓 . This hardness can be interpreted as an execution-based approximation to the Steiner-Hardness [56] of the filter-induced subgraph 𝐺 𝑓 , extending the same perspective in Section 3.2.3 to the filter-centric setting. Since the restriction step is relatively stable for a fixed index, and search over 𝐺 𝑓 degrades toward a linear scan as selectivity decreases, the dominant cost factor is the size of the filtered vectors:

3.2.4 Extending the Execution Chain to Complex Predicates. Eq. (2) is sufficient for the categorical-predicate regime targeted by existing FANN indices (e.g., UNG, RWalk, NHQ, and FDANN), where treating per-candidate predicate-check cost as approximately constant is appropriate. However, real applications may involve more complex predicates supported by systems such as pgvector [23], including polygon and regex matching. To accommodate future indices that may support such queries, we show that Eq. (2) can be naturally extended to cases where predicate-evaluation cost varies substantially across queries. The framework handles this by refining the scan-cost term while preserving the hardness formulation:
𝐻 scan 𝑞 𝑓 | 𝑞 𝑣 , 𝛼b(𝑞; 𝐾), 𝐾 = 𝛼b(𝑞; 𝐾) · 𝑐 scan (𝑞 𝑓 ), (6)

𝐻 PreFiltering (𝑞 | 𝐾) ∝ 𝐻 search (𝑞 𝑣 | 𝐺 𝑓 ) ∝ |𝑉𝑓 |. By rearranging Eq. (4), we obtain |𝑉𝑓 | =

Pre-filtering already restricts search to the filter-satisfying subgraph 𝐺 𝑓 , so the dominant family-level cost is governed mainly by the size of that restricted search space, |𝑉𝑓 |, rather than by the localdensity term 𝜌 (𝑞). Since 𝜌 (𝑞) governs how quickly post-filtering accumulates valid results during vector-centric traversal—it ceases to be a primary cost driver once search is already confined to 𝑉𝑓 . With 𝐾 and |𝑉0 | fixed for a given benchmark setting, the dominant filter-centric cost follows the opposite monotone trend from vectorcentric cost and decreases as the effective 𝛼b increases.

where 𝑐 scan (𝑞 𝑓 ) is the average per-candidate predicate-evaluation cost. A natural refinement is to write 𝑐 scan (𝑞 𝑓 ) = 𝑐 (𝑞 𝑓 ) · 𝜙 (𝑞 𝑓 ),

(7)

where 𝑐 (𝑞 𝑓 ) is a predicate-type-specific unit cost, calibrated empirically [44], and 𝜙 (𝑞 𝑓 ) captures predicate complexity in terms of required unit operations [15]. For example, 𝜙 (𝑞 𝑓 ) may correspond to the number of vertices in a polygon predicate [35] or the number of wildcards in a regular-expression predicate [10, 50]. For simple categorical predicates, 𝑐 scan (𝑞 𝑓 ) is approximately constant, recovering Eq. (2). This natural extension preserves the main advantage of the execution-grounded framework: richer hardness-related phenomena can be incorporated by refining existing chain variables, rather than by introducing an unrelated proxy. Experimental validation of this extension is provided in Section 3.4.4.

3.3

|𝑉0 | 𝐾 𝜌 (𝑞) . 𝛼b(𝑞; 𝐾)

Why a simple inversion is sufficient. The above derivation establishes a monotone duality between the two execution families: queries that are hard for vector-centric execution tend to be easy for filter-centric execution, and vice versa. Rather than introducing separate hardness models per family, we therefore apply a monotone inversion to reuse the same execution-grounded score:   𝐻𝛼 (𝑞), if the strategy is vector-centric,  1   𝐻 (𝑞) , if the strategy is filter-centric.  𝛼 This transformation is intentionally conservative: it only assumes that the two strategy families exhibit opposite monotone trends with respect to over-fetching-driven difficulty (as observed empirically), without committing to a specific internal implementation. As shown in Section 3.4, although this minimal strategy-aware transformation is not intended as an exact cost model for the filtercentric implementations, it is sufficient to achieve strong alignment with empirical performance across both families. 𝐻 (𝑞 | strategy) ≜

Strategy-Conditioned Hardness Estimation

Although 𝐻𝛼 is defined by modeling the post-filtering execution chain from a vector-centric viewpoint, existing FANN approaches are not limited to this family. As discussed in prior surveys on FANN indices [30], existing methods can be broadly categorized into vector-centric and filter-centric pruning families1 . Filter-centric strategies do not follow the post-filtering chain; instead, they first restrict the search space using the filter predicate and then perform vector search within the filtered subset. Because hybrid-query difficulty is defined through the execution chain, it is inherently

3.4

1 Although indices such as UNG and ACORN incorporate both filter and vector predi-

Hardness Validation

We empirically validate whether the proposed 𝛼-Hardness induces a query ordering that is consistent with observed recall–throughput trade-offs in FANN search. Our goal is not to fit a particular index,

cates through hybrid pruning mechanisms, they can still be classified into one of the two families according to the dominant pruning behavior. This categorization is also consistently supported by our experimental results. 5

!

Figure 3: Spearman rank correlation between query hardness estimates (𝛼-Hardness (ours) or baseline proxies: selectivity and correlation) and search performance across 29 datasets (25 synthetic and 4 semi-real), evaluated under seven hybrid query processing strategies. Semi-real workloads are constructed by taking a vector-only dataset and synthesizing labels, attributes, and filtered queries. Synthetic datasets are identified using the configuration IDs (Table 1). Values closer to −1 indicate stronger alignment (harder queries → worse performance), whereas values in [0.3, 1] indicate unintended reverse alignment. Table 1: Parameter configurations for synthetic datasets. The configuration ID encodes the source base vectors (prefix). For brevity, a single value indicates a setting applied uniformly to all attributes; mixed settings list per-attribute values.

but to test whether the hardness definition remains predictive across (i) diverse dataset/workload characteristics and (ii) fundamentally different hybrid execution strategies. 3.4.1 Dataset & Workload Suite. Following prior hybrid benchmarking practice [6, 39, 45], we construct a suite of synthetic hybrid datasets by augmenting standard vector-only benchmarks with synthesized categorical labels, while systematically controlling the core label/workload factors: the source base vectors, number of attributes, attribute cardinalities, value distributions, per-attribute missing probabilities, and data–label correlation (DLC) between base vectors and base labels2 . Query workloads are generated using the same synthesis policy used for the base data to ensure structural compatibility. All synthetic configurations are summarized in Table 1. In addition, to verify that 𝛼-Hardness is not an artifact of fully synthetic construction, we include four semi-real datasets whose base data—base vectors paired with corresponding labels—are drawn from real-world corpora, and whose query workloads are sampled or synthetically generated from the base data [33, 40, 43, 49]. We evaluate alignment under seven representative hybrid query processing strategies: FAISS[22]-based Post-Filtering and Pre-Filtering, and five hybrid-native indices (NHQ [39], ACORN [45], UNG [6], RWalks [38]), and FDANN [16]3 .) For each method, we sweep its parameters to obtain recall–QPS trade-offs, following the recommended settings in the corresponding original papers . To further examine whether the observed behavior remains robust when the dataset size exceeds CPU cache capacity, we additionally include the Deep10M and Deep50M datasets, which are subsets of Deep1B [60]. For additional experimental details refer to Section 5.1.

ID

#Attr Cardi. Distribution Missing Prob. DLC

SIFT1M-1 SIFT1M-2 SIFT1M-3 SIFT1M-4 SIFT1M-5 SIFT1M-6 SIFT1M-7

1 3 3 12 12 12 12

12 6 12 1 3 6 12

Zipf

0.5

0.0

SIFT1M-8 SIFT1M-9

3 12

12 3

Random

0.5

0.0

SIFT1M-10 SIFT1M-11 SIFT1M-12

3

12

Zipf

0.5

0.5 1.0 mix

SIFT1M-13 SIFT1M-14 SIFT1M-15

3

12

Zipf

0.0 0.8 mix

0.0

GIST1M-1 GIST1M-2 GIST1M-3 GIST1M-4

1 3 3 3

12 12 12 12

Zipf Random Zipf Zipf

0.5 0.5 0.5 0.0

0.0 0.0 0.0 0.5

GloVe1M-1 GloVe1M-2 GloVe1M-3 GloVe1M-4

1 3 3 3

12 12 12 12

Zipf Random Zipf Zipf

0.5 0.5 0.5 0.0

0.0 0.0 0.0 0.5

Deep10M Deep50M

3 3

12 12

Zipf Zipf

0.5 0.5

0.0 0.0

degrade monotonically. We use Recall@10 and refer to it simply as recall throughout this section. For each dataset and strategy, we compute 𝐻 (q | strategy) (Section 3.3), sort queries by increasing hardness, and partition them into 𝐵=10 equal-sized batches. This operationalizes the ordering soundness requirement: later batches should contain queries that are no easier than earlier ones4 . For each batch, we evaluate the target strategy across operating points, yielding one recall–QPS trade-off curve. To summarize each curve while preserving the trade-off, we compute a Pareto-optimal score by extracting the Pareto frontier, averaging recall and QPS over frontier points, and taking their product [14]. Higher scores indicate more efficient query processing.

3.4.2 Alignment Protocol and Metrics. FANN search performance is commonly summarized by recall–QPS trade-offs under varying parameters [22, 46]. Accordingly, a hardness measure is well-aligned if sorting queries by hardness yields groups whose trade-off curves 2 DLC is distinct from the query–vector correlation (QVC) used as a hardness proxy in

Section 3.1; DLC characterizes correlation in the data/label generation process, whereas QVC is measured at the query level 3 Since FDANN can handle only queries with a single filter attribute, we report results only for SIFT1M-1, GIST1M-1, and GloVe1M-1.

4We use 𝐵=10 to balance resolution and stability; our conclusions are unchanged for

nearby choices such as 5 or 20. 6

Hardness Estimator

𝜌 (Extended)

Δ|𝜌 |

Simple

-0.99 -0.96

-0.99 -0.92

+0.00 -0.04

Medium

p-simple p-medium p-complex set-overlap

3.75 3.75 3.75 10.76

-0.82 -0.62 -0.59 -0.90

-0.98 -1.00 -1.00 -1.00

+0.16 +0.38 +0.41 +0.10

Complex

r-simple r-complex

287.92 287.92

-0.89 -0.66

-0.99 -0.95

+0.10 +0.29

Synthesis Conditions Generate Mode

Base Label Generator

Strategy

Base Labels

Submit

%!!

%"$

%!$

%"#

%!#

Strategy Analyzer

Test Dataset

Filter-Centric Or Vector-Centric

Query Label Generator

%"!

!!"!

𝜌 (Original)

1.56 2.18

Base Vectors

Metadata Extractor

!!!

𝑐 (𝑞 𝑓 )

Base Labels

Label Generator

Meta Data

Dataset categorical range

Load Mode

…

Complexity

: Input : Output : Generator Component

…

Table 2: Alignment comparison between Extended and Original 𝛼-Hardness across predicate workloads. Predicate complexity is grouped by calibrated unit scan cost 𝑐 (𝑞 𝑓 ). Improvement is measured as Δ|𝜌 | = |𝜌 Adaptive | − |𝜌 Original |.

Regeneration Loop

Calculation Module Target PDF Target Bin: !!

Reject

Query Vectors

Fine-Ctrl Query Set

Bias Mode

! Low" −H$ IGH

Coarse-Ctrl Query Set

Figure 4: Overview of the hardness-controlled benchmark generator (HCBGen). The generator supports both Load and Generate modes for constructing the base data, and controls query-level hardness using either a target hardness profile or coarse-grained bias modes (High, Low, Random).

Let 𝐻 𝑏 be the average hardness of batch 𝑏, and let Score𝑏 be the Pareto-optimal score of that batch. We quantify alignment by the 𝐵 and {Score }𝐵 [48]. Spearman rank correlation between {𝐻 𝑏 }𝑏=1 𝑏 𝑏=1 Because higher hardness should correspond to lower performance, stronger alignment is reflected by Spearman’s 𝜌 closer to −1. For conventional hardness proxies (selectivity and correlation), we negate them before batching so that larger values consistently indicate higher difficulty, matching the direction of 𝐻 (·) 5 .

3.4.4 Validation on Complex Predicates. We further validate the extended formulation(Eq. (6)) on complex-predicate workloads built on SIFT100K, a randomly sampled subset of SIFT1M. The evaluated predicates include range filters, polygon matching with 4–12 (psimple), 30–70 (p-medium), or 150–250 (p-complex) vertices, regex matching over strings of length 100 with either no wildcard (rsimple) or 1–8 wildcards (r-complex), and set-overlap predicates with a vocabulary pool of size 100. Since no existing hybrid index directly supports this predicate set, we use HNSW-based post-filtering as the representative execution strategy. Table 2 shows that the original 𝛼-Hardness aligns well when predicate complexity is low, but its ordering quality degrades as per-candidate validation cost becomes more query-dependent, especially for polygon and regex workloads. By contrast, the extended formulation remains stably aligned across all workloads, with 𝜌 < −0.9 throughout, and yields the largest gains on structurally complex predicates such as p-medium, p-complex, and r-complex. These results show that 𝛼-Hardness extends naturally to compute-bound settings, where the dominant cost shifts from over-fetching to candidate scanning, without changing the underlying conditional chain.

3.4.3 Results and Takeaways. Figure 3 reports Spearman’s 𝜌 across datasets and strategies. Across diverse dataset/strategy combinations, the proposed hardness exhibits strong monotonic alignment with empirical search performance (typically 𝜌 ≤ −0.7), whereas proxy measurements are frequently near zero or unstable, indicating that they do not reliably order query difficulty. The baseline query–vector correlation (QVC) becomes informative only when strong positive data–label correlation (DLC) is explicitly enforced in the synthetic construction (e.g., SIFT1M-10, -11, -12, GIST1M-4, and GloVe1M-4), a condition that is neither universal nor guaranteed in realistic workloads; outside such regimes, QVC provides limited explanatory power. Selectivity exhibits opposite signs of 𝜌 across strategy families because it is intrinsically entangled with the pruning order, leading to reversed alignment with the intended ordering under certain strategies. For vector-centric strategies, lower selectivity typically makes queries harder by increasing over-fetching and predicate checks, whereas for filter-centric strategies it can make queries easier by shrinking the pre-filtered search space and reducing downstream vector traversal. Without explicit knowledge of the execution family, which is typically unavailable to a benchmark designer, selectivity cannot even determine a consistent direction of difficulty, and in many settings yields weak alignment. If we treat 𝜌 ∈ [−0.3, 0.3] as an alignment failure case [7], 𝛼Hardness incurs no such failures in any of our evaluated settings, including scaled-out regimes, whereas selectivity fails in a nontrivial fraction of cases. This gap arises because selectivity isolates only the filter predicate while ignoring the vector predicate and their joint interaction along the execution chain, thereby violating the validity and ordering soundness criteria discussed in Section 3.2.

4

BENCHMARK GENERATOR

Because real-world hybrid workloads are rarely shareable, FANN evaluations often rely on synthetic benchmarks, whose hidden design choices can bias rankings and obscure robustness. We present HCBGen, which uses 𝛼-Hardness to synthesize hybrid workloads with controllable, interpretable, and strategy-consistent difficulty. The generator supports (i) reproducible, hardness-neutral fixed benchmarks for fair comparison, (ii) stress testing by emphasizing hard queries, and (iii) workload approximation by matching a hardness profile that can be shared without exposing raw query logs.

4.1

Architecture

Figure 4 separates the generator into a Label Generator and a Hardness Estimator. The label generator proposes candidate queries, while the hardness estimator enforces hardness-aware acceptance through a regeneration loop. This separation allows hardness control to remain strategy-consistent across heterogeneous indices.

5We intentionally do not choose proxy directions per strategy, since that would leak

strategy knowledge into the baseline and artificially improve its alignment. 7

Algorithm 1 Coarse-Grained Hardness-Controlled Query Generation (High/Low/Random).

Algorithm 2 Fine-Grained Hardness-Controlled Query Generation (Match-PDF) with Budgeted Closest-Fill Fallback.

Require: Base vectors 𝑉 , base labels 𝐿 , mode M , target size 𝑁 , Budget 𝐵 Ensure: Query set Q with | Q | = 𝑁 . 1: Sample an initial query pool and compute hardness values 2: if M ∈ { High, Low } then 3: Set threshold 𝜏 ← perc80 (𝐻 ) for High, perc20 (𝐻 ) for Low 4: end if 5: for each query vector 𝑞 𝑣 in the initial pool do 6: Initialize candidate set C ← ∅ 7: for 𝑖 = 1 to 𝐵 do 8: Sample filter 𝑞 𝑓 and form 𝑞 = (𝑞 𝑣 , 𝑞 𝑓 ) 9: if M = Random or 𝑞 satisfies 𝜏 then 10: Q ← Q ∪ {𝑞 } ; break 11: end if 12: C ← C ∪ {𝑞 } 13: end for 14: if no query accepted then 15: Q ← Q ∪ {arg min𝑞 ∈C |𝐻 (𝑞) − 𝜏 | } ; 16: end if 17: end for 18: return Q

Require: Base vectors 𝑉 , base labels 𝐿 , target hardness PDF P , target size 𝑁 , bin count 𝐵 . Ensure: Query set Q with | Q | = 𝑁 . 1: Initialize Q ← ∅ . 2: Discretize hardness into 𝐵 disjoint intervals {𝐼 𝑗 } 𝐵 𝑗 =1 according to P ; assign target counts 𝑛 𝑗 . 3: Initialize candidate pools 𝑅 𝑗 ← empty list for all bins 𝑗 . 4: while | Q | < 𝑁 do 5: Sample candidate query 𝑞 = (𝑞 𝑣 , 𝑞 𝑓 ) ; compute hardness ℎ ← 𝐻 (𝑞) . 6: Find bin 𝑗 such that ℎ ∈ 𝐼 𝑗 . 7: if 𝑛 𝑗 > 0 then 8: Q ← Q ∪ {𝑞 } ; 𝑛 𝑗 ← 𝑛 𝑗 − 1. 9: end if 10: for each bins 𝑗 with 𝑛 𝑗 > 0 do 11: if ℎ ∉ 𝐼 𝑗 then store (dist(ℎ, 𝐼 𝑗 ), 𝑞𝑖 ) in 𝑅 𝑗 . 12: end for 13: if 𝑞 is the last candidate query then 14: for each bin 𝑗 with 𝑛 𝑗 > 0 do 15: fill remaining slots with arg min-dist unused candidates from 𝑅 𝑗 . 16: end for 17: end if 18: end while 19: return Q .

4.1.1 Label Generator. The label generator supports two base data modes—Load and Generate—because hybrid benchmarking arises in two fundamentally different settings. In one setting, practitioners have a labeled base data (i.e., base vectors with associated base labels), but the corresponding query logs cannot be shared; the community often has only public vector-only corpora, where structured base labels are unavailable and must be synthesized to support hybrid (vector+filter) benchmarking. The two modes trade off semantic fidelity and controlled synthesis: Load preserves the semantics and structure of a given corpus, whereas Generate creates a synthetic label space with explicit control over workload properties. In Load mode, the generator takes base vectors together with their existing base labels and uses a Metadata Extractor to infer the structural metadata needed for query construction—such as attribute domains, cardinalities, value frequencies, and missingness patterns. This metadata is forwarded to the Query Label Generator, which samples query labels that are schema-compatible with the loaded base labels. As a result, generated predicates respect the original label vocabulary and distributional structure, enabling realistic query synthesis when the original query workload is unavailable. In Generate mode, the generator takes only base vectors and a set of label synthesis conditions, and uses a Base Label Generator to synthesize base labels from scratch. The synthesis conditions define the label space and its statistical properties, and also include an explicit control for vector–label alignment. Concretely, our default synthesizer partitions the vector space into clusters and assigns attribute values in a DLC-controlled manner so that vectors within the same cluster share values with a tunable strength. This is important because vector–label alignment strongly influences the effectiveness of pruning behaviors in hybrid indices, and thus determines the regime in which a benchmark evaluates robustness versus best-case performance. The synthesized labels are then summarized into the same type of metadata as in Load, ensuring that subsequent query generation remains structurally consistent. Given the extracted or synthesized metadata and the query vectors, the Query Label Generator samples candidate predicates and forms hybrid queries. Since most hybrid-native indices primarily support categorical predicates, it generates predicates composed of one or more label = value conditions. Because FANN assumes

single-table data with vector embeddings, cross-table operations such as joins are out of scope. Candidates are then passed to the hardness estimator, and rejected queries are returned for regeneration, forming a hardness-controlled regeneration loop (Section 4.2). This design decouples label construction from hardness control: the label generator defines what predicates are valid and realistic, while the hardness estimator decides which valid queries are retained to satisfy the target hardness regime.

4.1.2 Hardness Estimator. Hardness-based control requires strategy awareness because different hybrid indices enforce vector and filter constraints in different orders (Section 3.3). Accordingly, the hardness estimator consists of a Strategy Analyzer and a Hardness Calculation Module. The strategy analyzer first classifies the target strategy into a pruning family, which fixes the strategy-consistent interpretation of hardness. The hardness calculation module then computes the strategy-conditioned hardness score of each candidate query (Section 3.3) and applies the user-specified control rule to decide whether to keep the query or reject it. To classify a strategy with minimal overhead, we maintain two fixed probe datasets that were chosen empirically to exhibit the most opposing characteristics across the two pruning families. Specifically, these probes are reduced versions of SIFT1M-1 and SIFT1M-7 from Table 1, where both the number of base vectors and the number of queries are downsampled by a factor of ten. Given a target strategy, the analyzer builds the index if needed, runs searches on both probes, and records the resulting recall–QPS trade-off curves. It then summarizes each curve using a single Pareto-optimal score computed by the same procedure described in Section 3.4.1, and classifies the strategy by comparing the two scores. This estimation pipeline correctly classifies not only Post-Filtering and Pre-Filtering, but also all hybrid-native FANN strategies, including ACORN, UNG, NHQ, RWalks, and FDANN, in exact agreement with the theoretical categorization in [30]. This is also reflected in Figure 3, where the ordering induced by 𝛼-Hardness remains consistently negative across all strategies. 8

Distribution

Missing Prob.

DLC

(3, 2, 2) (12) (1, 1, . . . 1) (100, 20, 10, 5, 3, 2)

Random Random – Random

0 0 Zipf 0

No No No No

To handle future implementations that may not show a clear preference for either probe workload, we classify a strategy as Mixed when the two probe scores are too close to distinguish. Mixed is a robust fallback for ambiguous cases: rather than relying on a single family decision, the generator enforces hardness constraints under both interpretations, reducing vulnerability to borderline misclassification. This keeps probing a one-time, cacheable process while preventing classification uncertainty from affecting hardness control. Because the index analyzer uses small probe datasets, this step requires at most one minute.

4.2

NHQ

UNG

RWalks

Frequency

Cardi.

3 1 12 6

10000

5000 5000 2000 2500 00 1 2 3 4 5 6 00 1 2 3 4 5 6 00 1 2 3 4 5 6 00 1 2 3 4 5 6

Frequency

#Attr

NHQ ACORN UNG6 RWalks

ACORN

400 400 100 500 200 200 50 00 1 2 3 4 5 6 00 1 2 3 4 5 6 00 1 2 3 4 5 6 00 1 2 3 4 5 6

4000

5000

Frequency

Method

(c) Hardness-Ctrl (b) Semi-Real (a) Synthetic

Table 3: Label-synthesis configurations used in prior hybrid indexing studies, summarizing the number of attributes, attribute cardinalities, value distributions, missing probabilities, and data–label correlation (DLC).

arxiv

1000

LAION1M

SIFT-High

SIFT-Low

5000

500

GIST-High

1000

2500

00 1 2 3 4 5 6

Hardness

tripclick

00 1 2 3 4 5 6

Hardness

yfcc

5000

GIST-Low

2500

00 1 2 3 4 5 6

Hardness

00 1 2 3 4 5 6

Hardness

Figure 5: Comparison of 𝛼-Hardness distribution coverage across three workload classes: (a) synthetic workloads adopted from prior studies (SIFT1M-based), (b) semi-real workloads, and (c) hardness-controlled workloads generated by our framework. of queries to each interval according to the desired profile. During generation, each sampled candidate query is scored and placed into the corresponding interval; it is accepted only if that interval still needs more queries, and otherwise it is rejected and regeneration continues. To keep the procedure practical, we enforce a finite sampling budget. If generation stalls because some intervals are extremely unlikely under the current base data, we trigger explicit fallback mechanisms, such as filling the remaining slots with the closest available candidates. We validate this behavior in Section 5.4 by comparing both the similarity of the resulting difficulty profiles and the downstream search behavior.

Hardness-Controlled Query Generation

The generator supports two hardness-control families. The first provides coarse-grained modes for stress testing and hardnessneutral fixed benchmarks, while the second enables fine-grained profile matching for workload approximation. Both use the same accept/reject loop and differ only in the acceptance rule. 4.2.1 Coarse-Grained Bias Modes. The coarse-grained modes bias the workload toward hard or easy queries (Algorithm 1). Rather than using a fixed, absolute hardness threshold, which can vary widely across datasets and label constructions, we derive a cutoff adaptively from a small initial sample of generated queries. For example, High uses a cutoff corresponding to the top portion of the sampled 𝛼-Hardness, while Low uses a cutoff corresponding to the bottom portion. A candidate query is accepted if its 𝛼-Hardness falls into the desired region (hard for High, easy for Low); Random disables hardness-based selection and accepts randomly generated queries. Random performs no hardness-based filtering, producing a reproducible, strategy-independent fixed benchmark. Because it retains queries spanning a broad range of hardness values, it yields a benchmark with diverse query difficulty that can be used for fair comparison across hybrid index designs. To ensure termination and stable generation time, we cap the number of regeneration attempts per query. If no candidate meets the desired condition within this retry limit, we accept the candidate whose difficulty score is closest to the cutoff, which guarantees completion while still preserving a strong bias.

5

EVALUATION

This section evaluates the proposed HCBGenfrom three perspectives: coverage, controllability, and workload approximation. We investigate the following research questions: • RQ1 (Hardness coverage): How much of the hardness spectrum is covered by workloads used in prior FANN studies and by semi-real workloads? • RQ2 (Hardness controllability): Can our generator reliably shift the workload toward easy vs. hard regimes under identical synthesis settings? • RQ3 (Robustness under controlled regimes): How do representative strategies behave when evaluated across matched, systematically varied hardness regimes? • RQ4 (Hardness as a bridge): If only a hardness profile can be shared, can the generator produce proxy workloads that induce similar performance trends?

4.2.2 Fine-Grained Target-Profile Matching. Fine-grained control targets a user-specified hardness profile to approximate an unknown real workload using 𝛼-Hardness as a shareable signal (Algorithm 2). Concretely, the generator first partitions the difficulty range into a fixed number of intervals and assigns a target number

5.1

Experimental Setup

We evaluate on three classes of hybrid workloads: (i) synthetic workloads adopted in prior hybrid indexing studies (NHQ, ACORN, UNG, and RWalks [6, 38, 39, 45]), (ii) four semi-real datasets, typically constructed by augmenting a vector-only dataset with synthesized labels, used in prior work (arxiv, LAION1M, tripclick, and yfcc [33, 40, 43, 49]), and (iii) four hardness-controlled benchmarks

6 UNG synthesizes labels by treating each attribute–value pair as a single label and

assigning 12 such labels under a Zipfian distribution. To replicate this, we use 12 attributes of cardinality 1 and implement the Zipfian skew through missing probabilities, yielding a functionally equivalent labeling policy. 9

Figure 6: Recall–QPS trade-off curves for five hybrid query processing strategies (Post-Filtering and four hybrid-native indices) across 12 workloads spanning three workload families: (i) synthetic workloads adopted in prior hybrid indexing studies, (ii) semi-real workloads, and (iii) hardness-controlled workloads generated by our method. Red markers overlay the performance reported in each strategy’s original paper (when available), providing a reference anchor for cross-workload comparison. generated by our framework. We follow the original synthesis procedures and parameter recommendations to ensure that our comparisons isolate the effect of workload design, rather than retuning or re-implementing indices. In all cases, label synthesis uses predicates composed of categorical conditions of the form label=value, combined with conjunctions. For performance benchmarking, we report recall–QPS tradeoffs following the parameter sweeps recommended by the corresponding papers to ensure fair and representative evaluation. All experiments run on a single Amazon EC2 instance (c5a.8xlarge; 32 vCPUs @ 3.3 GHz; 64 GB RAM). For synthetic workloads from prior studies, we fix the base vector dataset to SIFT1M [21] and vary only the label/query synthesis policy, so that differences are attributable to workload construction. Label synthesis configurations are summarized in Table 3 and are adopted from the original papers. Query workloads follow the original generation procedures (e.g., single-predicate queries for RWalks and no missing-value constraint on NHQ query filters). The four semi-real benchmarks are widely used benchmarks in prior FANN studies [6, 38, 45]. They span diverse vector dimensionalities, and attribute configurations [46]. Using the proposed generator, we construct four representative hardness-controlled hybrid benchmarks. These benchmarks are based on two widely used vector datasets, SIFT1M [21] and GIST1M [21], whose vector dimensionalities are 128 and 960, respectively, chosen because SIFT1M has served as a standard baseline across prior hybrid indexing studies, whereas GIST1M offers a markedly higher-dimensional space that stresses vector-centric behavior. For each base data, we synthesize 3 attributes with a cardinality of 12 per attribute, following a Zipfian distribution with skewness parameter 1.5, a missing probability of 0.5, and 0.0 DLC

(data-labal correlation). To isolate the effect of hardness control, we generate two workload variants under identical synthesis settings using the coarse-grained Low and High modes (Section 4.2). This yields SIFT-Low, SIFT-High, GIST-Low, and GIST-High.

5.2

Hardness Coverage and Control

We first examine how query hardness is distributed across different workloads and whether our generator enables systematic control. 5.2.1 Coverage Comparison (RQ1). Figure 5 compares 𝛼-Hardness distributions. Across these workloads, hardness is typically heavytailed: many queries fall into an easy regime with a smaller hard tail. Prior synthetic workloads, notably those used by ACORN and NHQ, are concentrated toward the easy end of the hardness spectrum, and the semi-real workloads similarly occupy a narrow easy range with little mass in harder regimes. In contrast, our SIFT-High and GIST-High benchmarks span a substantially wider hardness range, including a visible fraction of queries with hardness > 1 and a hard tail extending beyond 6. This broader coverage is important because it enables stress-testing and robustness evaluation in challenging regimes that are weakly represented in commonly used benchmarks, reducing the risk that conclusions hinge on an implicitly “mild” workload slice. 5.2.2 Hardness-Aware Generation (RQ2). To verify controllability, we compare Low vs. High workloads generated under identical synthesis settings. As shown in Figure 5(c), Low concentrates queries in the [0, 1] hardness range, whereas High shifts the mass sharply toward harder queries (over 99% of queries have hardness > 1). Crucially, this distributional shift translates into empirical behavior: Figure 6(c) shows that Low workloads yield consistently better 10

Table 4: Indexing time and memory footprint of four methods on three different synthetic datasets.

Method NHQ ACORN UNG RWalks

Indexing Time (seconds) ACORN Syn. UNG Syn. RWalks Syn.

Memory Footprint (MB) ACORN Syn. UNG Syn. RWalks Syn.

(Simple)

(Medium)

(Complex)

(Simple)

(Medium)

(Complex)

56 659 38 342

40 657 40 344

23 685 281 348

684 1202 695 1110

695 1202 693 1203

689 1202 731 2073

!

!

!

Figure 7: 𝛼-Hardness density on four semi-real datasets, comparing the original workload with two MATCH-PDF workloads generated by HCBGen to match the given distribution, with and without base data. Insets report KS and W1 distances to the original workload (lower is better).

recall–QPS trade-offs, while High workloads shift curves toward lower recall under the same search budgets across all evaluated strategies. This validates that hardness is not merely a descriptive statistic: it is an actionable control signal that induces predictable differences in measured performance.

5.3

!

robust performance because sufficient graph connectivity is preserved, albeit at the cost of substantially higher index construction overhead. As shown in Table 4, this design requires UNG to preserve connectivity for rare labels during indexing by partitioning the data into smaller groups, causing both indexing time and memory overhead to increase as the label distribution of the base data becomes more complex. These smaller groups can also improve search efficiency. However, in workloads such as RWalks with single-label filters, UNG must traverse a large number of groups, which results in lower QPS than in other workloads. NHQ incorporates attribute similarity by averaging binary matches across attributes. As the number of attributes grows, each match contributes less, reducing recall under complex, high-cardinality labels. Interestingly, indexing time decreases as the number of attributes grows, suggesting that index construction may terminate early when too few base vectors share a label to form sufficient edges, resulting in weak graph connectivity and lower recall. This pattern is reflected in the recall drops on UNG, RWalks, and YFCC in Figure 6-NHQ. Consequently, NHQ is the least robust strategy under hard workloads. ACORN evaluates filter satisfaction before traversal and expands only filter-qualified nodes, achieving strong performance under most workloads. However, its denser-HNSW strategy breaks down under high-hardness workloads, especially when selectivity falls below approximately 0.1%. In this regime, dense connectivity alone cannot preserve meaningful connectivity among filter-satisfying nodes, causing the search to terminate prematurely before reaching the true targets and thus inflating QPS despite failed retrieval. This behavior is especially evident in SIFT-High and GIST-High. Because this denser-HNSW strategy is predicate-agnostic, its indexing cost is largely insensitive to the base data label distribution, but it consistently requires the highest indexing time and memory footprint among the evaluated methods. RWalks requires base labels to be flattened into binary vectors, making it sensitive to attribute count and missing probability and causing greater performance variation than in other strategies. RWalks also degrades under high-hardness workloads, consistent with its original finding that recall collapses at extremely low selectivity when index construction fails to establish effective traversal paths. Its binary label representation also increases memory overhead as the number of base labels grows, as in RWalks. However, this design is effective when there are few query filters and remains reliable even with large attribute cardinalities. This behavior aligns with the workload configuration of RWalks, enabling strong performance with few active labels and high-cardinality attributes.

Strategy Robustness (RQ3)

We next revisit the performance and indexing / maintenance overhead of representative hybrid query processing strategies under a common workload suite. A key challenge in interpreting the FANN literature is that each method is often evaluated on a workload designed with a method-specific label/query synthesis policy (Table 3), which complicates cross-paper comparison. Our goal here is not to claim any prior result is “wrong”; rather, we assess sensitivity: whether conclusions drawn under a narrow workload slice remain stable when the hardness regime is varied in a controlled way. As shown in Figure 6, strategy rankings and trade-off shapes vary substantially across workloads. In particular, results reported in the original papers tend to align with easier regions of our workload space, suggesting that performance claims can be workloadsensitive and that robustness under harder regimes is not well captured by commonly used benchmarks. This sensitivity is most evident on High workloads, where recall drops sharply for most strategies, often below 0.2, consistent with the known difficulty of extremely low-selectivity regimes (e.g., around or below 0.1%) in which hybrid indices struggle to find enough filter-satisfying candidates [38]. We also report indexing time and memory footprint in Table 4. These results are measured on the three synthetic datasets in Table 3, all built on the same SIFT1M base vectors. Since index construction is independent of the query workload, these costs are driven mainly by the base data label synthesis policy rather than by the 𝛼-Hardness. Overall, the table shows that indexing overhead is sensitive to label organization: some methods remain stable across datasets, whereas others vary despite sharing the same base vectors. 5.3.1 Strategy-Specific Behavior Analysis. While all methods degrade under hard workloads, the severity and underlying causes of degradation differ substantially across index designs. Post Filtering relies exclusively on over-fetched vector candidates to satisfy filter predicates. Under high-hardness workloads, increasing the over-fetch factor has limited effect, as filter-satisfying candidates remain rare, leading to consistently low recall. As shown in Figures 5 and 6, higher 𝛼-Hardness directly translates to poorer search performance across datasets. UNG is one of the most robust methods to dataset variation among those evaluated. Even extremely low-selectivity queries targeting rare labels, such as SIFT-High in Figure 6(c), can still maintain 11

Figure 8: Recall–QPS trade-offs on four semi-real datasets for Post-Filtering and RWalks, comparing the original workload with two MATCH-PDF workloads generated by our generator with and without base data. The generated workloads largely preserve the performance trends of the original workload, including the workload generated without base data.

5.4

Hardness as a Bridge (RQ4)

6

Another practical implication of 𝛼-Hardness and HCBGenis that they bridge research benchmarks and real-world hybrid workloads. Because such workloads are rarely released or standardized, we conduct a fidelity experiment by emulating the query workloads of four semi-real datasets. We consider two deployment scenarios. In the first, the base data is available but the original query workload is not, so the generator receives only the target hardness information; this corresponds to the base labels loading configuration with Match-PDF mode (Generated with base data). In the second, more challenging scenario, neither base data nor query logs are available, and the generator again receives only the target hardness information (Generated w/o base data). In this case, base labels are synthesized using a fixed configuration with 2 attributes of cardinality 12. This extreme but practical setting demonstrates the generality of hardness as a standalone workload descriptor. Figure 7 compares the hardness distributions of the original workloads (given) with those of the two proxy workloads generated by our method. Match-PDF enables the generator to closely fit the target hardness distribution across all four datasets. To quantify distributional similarity, we report (i) the Kolmogorov–Smirnov statistic[47] and (ii) the 1-Wasserstein distance[41] between the generated and given hardness distributions. Both metrics consistently show that the generated workloads closely match the given ones. We further test this argument by asking whether matching hardness distributions also matches performance. Figure 8 reports recall– QPS trade-offs for Post-Filtering and RWalks under three workloads per dataset. The generated workloads closely track the trade-off curves of the given workloads. Notably, even when the generator has no access to the base data, it still reproduces similar performance trends. This supports two conclusions: (i) 𝛼-Hardness is a strong proxy for performance-relevant workload difficulty, and (ii) hardness-controlled generation can faithfully emulate unseen workloads using only hardness profiles. These results show that our approach can generate privacy-preserving proxy benchmarks that retain the performance-critical properties of real-world hybrid workloads. This enables realistic benchmarking of hybrid search systems without access to sensitive user logs or proprietary query traces. More broadly, the results suggest that 𝛼-Hardness captures the dominant factors governing hybrid search performance, making it an effective surrogate for approximating unseen workloads.

RELATED WORKS

Vector Search Hardness Estimation. Prior work on vector search has characterized query hardness using intrinsic data properties such as intrinsic dimensionality, local density variation, and hubness, which influence nearest-neighbor structure and distance concentration in high-dimensional spaces [4, 18, 37]. More recently, Steiner Hardness provides an execution-oriented notion of query difficulty for graph-based ANN search by estimating the minimum traversal effort required to reach the target neighborhood [56]. Our work complements this line by treating 𝛼-Hardness as a broader hybrid extension of Steiner-Hardness. Specifically, 𝛼-Hardness generalizes the Steiner-Hardness view from vector-only ANN to FANN by retaining graph-traversal difficulty as the fetch component while additionally modeling the over-fetching and filter-induced execution effects unique to hybrid search. To the best of our knowledge, no prior work has explicitly defined FANN query hardness. FANN Benchmarking. Recent work has also introduced FANN benchmarking studies. Shi et al. [46] construct semi-real datasets under controlled settings such as label length, selectivity, and dataset size, but still generate queries by sampling labels from the dataset; under our hardness estimator, these queries are biased toward easy cases (Figure 5). Lin et al. [30] discuss possible query-difficulty factors conceptually, but still rely on query sampling, inheriting label-distribution bias and limiting robustness evaluation. Iff et al. [19] introduce a semi-real hybrid dataset with diverse query labels, yet without an explicit notion of query-level difficulty, the representativeness of those queries remains unclear. Existing FANN benchmarks therefore lack an explicit notion of query-level hardness, leaving robustness under hard queries unexplored. Benchmark Sensitivity in Database Systems. Benchmark brittleness is a recognized problem across database research. In relational systems, TPC-H and TPC-DS have been shown to miss real-world workloads in schema type, expression complexity, and operator structure [54], while cloud-scale production workloads exhibit write-heavy pipelines and long-tailed distributions absent from standard benchmarks [53]. In ANN search, algorithm rankings shift substantially across datasets [28] and also depend on whether queries are easy or hard [13]. Together, these results show that benchmark design choices often determine performance rankings.

12

7

CONCLUSION

[21] Hervé Jégou, Matthijs Douze, and Cordelia Schmid. 2011. Product Quantization for Nearest Neighbor Search. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI) 33, 1 (2011), 117–128. [22] Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data (2019). https://doi.org/10.1109/ TBDATA.2019.2921572 [23] Andrew Kane. 2024. pgvector: Open-source vector similarity search for Postgres. https://github.com/pgvector/pgvector. GitHub repository, accessed 2026-04-19. [24] Vladimir Karpukhin et al. 2020. Dense Passage Retrieval for Open-Domain Question Answering. In EMNLP. [25] Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, and Thomas Neumann. 2015. How Good Are Query Optimizers, Really? Proceedings of the VLDB Endowment 9, 3 (2015), 204–215. https://doi.org/10.14778/2850583.2850594 [26] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, and Sebastian Riedel. 2020. Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks. In Advances in Neural Information Processing Systems (NeurIPS), Vol. 33. 9459–9474. [27] Sen Li, Fuyu Lv, Taiwei Jin, Guli Lin, Keping Yang, Xiaoyi Zeng, Xiao-Ming Wu, and Qianli Ma. 2021. Embedding-based Product Retrieval in Taobao Search. arXiv:2106.09297 [cs.IR] https://arxiv.org/abs/2106.09297 [28] Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. 2020. Approximate Nearest Neighbor Search on High Dimensional Data — Experiments, Analyses, and Improvement . IEEE Transactions on Knowledge & Data Engineering 32, 08 (Aug. 2020), 1475–1488. https: //doi.org/10.1109/TKDE.2019.2909204 [29] Wilfred W.K. Lin. 2021. MyBenchmark: generating databases for query workloads. https://doi.org/10.7910/DVN/ISQYCH [30] Yanjun Lin, Kai Zhang, Zhenying He, Yinan Jing, and X. Sean Wang. 2025. Survey of Filtered Approximate Nearest Neighbor Search over the Vector-Scalar Hybrid Data. arXiv preprint arXiv:2505.06501 (2025). https://arxiv.org/abs/2505.06501 [31] Jiasen Lu, Dhruv Batra, Devi Parikh, and Stefan Lee. 2019. ViLBERT: Pretraining Task-Agnostic Visiolinguistic Representations for Vision-and-Language Tasks. arXiv:1908.02265 [cs.CV] https://arxiv.org/abs/1908.02265 [32] Yu. A. Malkov and D. A. Yashunin. 2018. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. IEEE TPAMI (2018). https://doi.org/10.1109/TPAMI.2018.2889473 [33] Malteos. 2022. Aspect Paper Embeddings. https://huggingface.co/datasets/ malteos/aspect-paper-embeddings Accessed: 2026-01-01. [34] Maxim Naumov, Dheevatsa Mudigere, Hao-Jun Michael Shi, et al. 2019. Deep Learning Recommendation Model for Personalization and Recommendation Systems. arXiv preprint arXiv:1906.00091 (2019). [35] Joseph O’Rourke. 1998. Computational Geometry in C (2nd ed.). Cambridge University Press, USA. [36] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. 2021. Learning Transferable Visual Models From Natural Language Supervision. arXiv:2103.00020 [cs.CV] https://arxiv. org/abs/2103.00020 [37] Miloš Radovanović, Alexandros Nanopoulos, and Mirjana Ivanović. 2010. Hubs in space: Popular nearest neighbors in high-dimensional data. JMLR (2010). [38] Jonas Rasch et al. 2024. RWalks: Random Walks as Attribute Diffusers for Filtered Vector Search. https://doi.org/10.1145/3626246.3653392 [39] Prashant Ravikumar et al. [n.d.]. Native Hybrid Queries for Approximate Nearest Neighbor Search. arXiv. https://arxiv.org/abs/2203.13601 [40] Navid Rekabsaz, Oleg Lesota, Markus Schedl, Jon Brassey, and Carsten Eickhoff. 2021. TripClick: The Log Files of a Large Health Web Search Engine. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 2507–2513. https://doi.org/10.1145/ 3404835.3463274 [41] Yossi Rubner, Carlo Tomasi, and Leonidas J. Guibas. 2000. The Earth Mover’s Distance as a Metric for Image Retrieval. In Proceedings of the IEEE International Conference on Computer Vision (ICCV). 747–754. https://doi.org/10.1109/ICCV. 2000.937632 [42] R.S. Sandhu, E.J. Coyne, H.L. Feinstein, and C.E. Youman. 1996. Role-based access control models. Computer 29, 2 (1996), 38–47. https://doi.org/10.1109/2.485845 [43] Christoph Schuhmann, Richard Vencu, Romain Beaumont, Robert Kaczmarczyk, Clayton Mullis, Aarush Katta, Theo Coombes, Jenia Jitsev, and Aran Komatsuzaki. 2021. LAION-400M: Open Dataset of CLIP-Filtered 400 Million Image–Text Pairs. arXiv preprint arXiv:2111.02114 (2021). https://arxiv.org/abs/2111.02114 [44] Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, and Thomas G. Price. 1979. Access Path Selection in a Relational Database Management System. In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data. ACM, 23–34. https://doi.org/10.1145/582095. 582099 [45] Yijing Shao et al. [n.d.]. ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data. arXiv. https://arxiv.org/abs/2403.04871

In this paper, we presented 𝛼-Hardness, an execution-driven measure of hybrid-query difficulty that aligns consistently with observed FANN performance across datasets and strategies, unlike selectivity- or correlation-based proxies. Using 𝛼-Hardness as a control knob, HCBGen generates hardness-controlled benchmarks and can approximate real workloads by matching hardness profiles, revealing that many existing benchmarks are biased toward easy queries and can overstate robustness.

ACKNOWLEDGMENTS This work was supported by the [...] Research Fund of [...] (Number [...]). Additional funding was provided by [...] and [...]. We also thank [...] for contributing [...].

REFERENCES [1] Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. 2018. ANNBenchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms. arXiv:1807.05614 [cs.IR] https://arxiv.org/abs/1807.05614 [2] Michael Barbaro and Tom Zeller. 2006. A Face Is Exposed for AOL Searcher No. 4417749. The New York Times (2006). [3] Joeran Beel et al. 2016. Paper Recommender Systems: A Literature Survey. IJDL (2016). [4] Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, and Uri Shaft. 1999. When is “nearest neighbor” meaningful? ICDT (1999). [5] Peter A. Boncz, Marcin Zukowski, and Niels Nes. 2005. MonetDB/X100: HyperPipelining Query Execution. CIDR (2005). [6] Yuzheng Cai, Jiayang Shi, Yizhuo Chen, and Weiguo Zheng. 2024. Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 2, 6, Article 246 (Dec. 2024), 27 pages. https://doi.org/10.1145/3698822 [7] Jacob Cohen. 1988. Statistical Power Analysis for the Behavioral Sciences. Lawrence Erlbaum Associates. [8] Paul Covington, Jay Adams, and Emre Sargin. 2016. Deep Neural Networks for YouTube Recommendations. In Proceedings of the 10th ACM Conference on Recommender Systems (RecSys). 191–198. https://doi.org/10.1145/2959100.2959190 [9] Paul Covington, Jay Adams, and Emre Sargin. 2016. Deep Neural Networks for YouTube Recommendations. In Proceedings of the 10th ACM Conference on Recommender Systems. [10] Russ Cox. 2007. Regular Expression Matching Can Be Simple And Fast. 2007 (2007). https://swtch.com/~rsc/regexp/regexp1.html Online article. [11] Hanjun Dai, Bethany Yixin Wang, Xingchen Wan, Bo Dai, Sherry Yang, Azade Nova, Pengcheng Yin, Phitchaya Mangpo Phothilimthana, Charles Sutton, and Dale Schuurmans. 2024. UQE: A Query Engine for Unstructured Databases. arXiv:2407.09522 [cs.DB] https://arxiv.org/abs/2407.09522 [12] Jeffrey Dean and Luiz André Barroso. 2013. The Tail at Scale. Commun. ACM (2013). https://doi.org/10.1145/2408776.2408794 [13] Karima Echihabi, Kostas Zoumpatianos, Themis Palpanas, and Houda Benbrahim. 2018. The lernaean hydra of data series similarity search: an experimental evaluation of the state of the art. 12, 2 (Oct. 2018), 112–127. https://doi.org/10. 14778/3282495.3282498 [14] Joshua Engels, Benjamin Landrum, Shangdi Yu, Laxman Dhulipala, and Julian Shun. 2024. Approximate Nearest Neighbor Search with Window Filters. arXiv:2402.00943 [cs.DS] https://arxiv.org/abs/2402.00943 [15] Simon F. Goldsmith, Robert B. Michael, Yih-Kuen Tsay, and Riccardo Bettati. 2007. Measuring Empirical Computational Complexity. In Proceedings of the 15th ACM Conference on Computer and Communications Security. ACM. Empirical cost calibration / regression-based measurement methodology. [16] Siddharth Gollapudi et al. [n.d.]. Filtered-DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters. arXiv / Tech report. https: //harsha-simhadri.org/pubs/Filtered-DiskANN23.pdf [17] Ruiqi Guo et al. 2020. Accelerating Large-Scale Inference with Anisotropic Vector Quantization. In ICML. [18] Michael E Houle. 2017. Local intrinsic dimensionality. IEEE TKDE (2017). [19] Patrick Iff, Paul Brügger, Marcin Chrapek, Maciej Besta, and Torsten Hoefler. 2025. Benchmarking Filtered Approximate Nearest Neighbor Search Algorithms on Transformer-based Embedding Vectors. arXiv preprint arXiv:2507.21989 (2025). https://arxiv.org/abs/2507.21989 [20] Yannis E. Ioannidis. 1996. Query Optimization. Comput. Surveys 28, 1 (1996), 121–123. https://doi.org/10.1145/234313.234366 13

[55] Yi Wang et al. 2021. Milvus: A Purpose-Built Vector Data Management System. In SIGMOD. https://doi.org/10.1145/3448016.3457550 [56] Yifan Wang et al. 2024. Steiner Hardness: Measuring Query Difficulty in GraphBased ANN Search. PVLDB (2024). [57] Chuangxian Wei, Bin Wu, Sheng Wang, Renjie Lou, Chaoqun Zhan, Feifei Li, and Yuanzhe Cai. 2020. AnalyticDB-V: a hybrid analytical engine towards query fusion for structured and unstructured data. Proc. VLDB Endow. 13, 12 (Aug. 2020), 3152–3165. https://doi.org/10.14778/3415478.3415541 [58] Tianming Wu and Dixin Tang. [n.d.]. PathFinder: Efficiently Supporting Conjunctions and Disjunctions for Filtered Approximate Nearest Neighbor Search. arXiv:2511.00995. [59] Xiaoliang Xu, Chang Li, Yuxiang Wang, and Yixing Xia. 2020. Multiattribute Approximate Nearest Neighbor Search Based on Navigable Small World Graph. Concurrency and Computation: Practice and Experience 32, 24 (2020), e5970. https: //doi.org/10.1002/cpe.5970 [60] Artem Babenko Yandex and Victor Lempitsky. 2016. Efficient Indexing of BillionScale Datasets of Deep Descriptors. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2055–2063. https://doi.org/10.1109/CVPR.2016. 226 [61] Han Zhang, Songlin Wang, Kang Zhang, Zhiling Tang, Yunjiang Jiang, Yun Xiao, Weipeng Yan, and Wen-Yun Yang. 2020. Towards Personalized and Semantic Retrieval: An End-to-End Solution for E-commerce Search via Embedding Learning. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval (Virtual Event, China) (SIGIR ’20). Association for Computing Machinery, New York, NY, USA, 2407–2416. https://doi.org/10.1145/3397271.3401446 [62] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. 2021. Graph Neural Networks: A Review of Methods and Applications. arXiv:1812.08434 [cs.LG] https://arxiv.org/abs/1812.08434 [63] Zijian Zhu, Yongli Wang, and Dongmei Liu. 2025. Hybrid Query of Boolean Filter and Vector Similarity Search: Benchmark, Comparison and Direction. In Proceedings of the 5th Asia Conference on Information Engineering (ACIE). Nanjing, China.

[46] Jiayang Shi, Yuzheng Cai, and Weiguo Zheng. 2025. Filtered Approximate Nearest Neighbor Search: A Unified Benchmark and Systematic Experimental Study [Experiment, Analysis & Benchmark]. arXiv:2509.07789 [cs.DB] https: //arxiv.org/abs/2509.07789 [47] N. V. Smirnov. 1948. Table for estimating the goodness of fit of empirical distributions. The Annals of Mathematical Statistics 19, 2 (1948), 279–281. https://doi.org/10.1214/aoms/1177730256 [48] Charles Spearman. 1904. The proof and measurement of association between two things. The American Journal of Psychology 15, 1 (1904), 72–101. https: //doi.org/10.2307/1412159 [49] Bart Thomee, David A. Shamma, Gerald Friedland, Benjamin Elizalde, Karl Ni, Douglas Poland, Damian Borth, and Li-Jia Li. 2016. YFCC100M: The New Data in Multimedia Research. Commun. ACM 59, 2 (Jan. 2016), 64–73. https: //doi.org/10.1145/2812802 [50] Ken Thompson. 1968. Programming Techniques: Regular Expression Search Algorithm. Commun. ACM 11, 6 (1968), 419–422. https://doi.org/10.1145/363347. 363387 [51] Transaction Processing Performance Council. [n.d.]. TPC-H Benchmark Specification. TPC. https://www.tpc.org/tpch/ [52] Immanuel Trummer, Ryan Marcus, Olga Papaemmanouil, and Tim Kraska. 2017. SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 1153–1168. https://doi.org/10.1145/3035918.3035933 [53] Alexander van Renen, Dominik Horn, Pascal Pfeil, Kapil Vaidya, Wenjian Dong, Murali Narayanaswamy, Zhengchun Liu, Gaurav Saxena, Andreas Kipf, and Tim Kraska. 2024. Why TPC is Not Enough: An Analysis of the Amazon Redshift Fleet. Proc. VLDB Endow. 17, 11 (July 2024), 3694–3706. https://doi.org/10.14778/ 3681954.3682031 [54] Adrian Vogelsgesang, Michael Haubenschild, Jan Finis, Alfons Kemper, Viktor Leis, Tobias Muehlbauer, Thomas Neumann, and Manuel Then. 2018. Get Real: How Benchmarks Fail to Represent the Real World. In Proceedings of the Workshop on Testing Database Systems (Houston, TX, USA) (DBTest ’18). Association for Computing Machinery, New York, NY, USA, Article 1, 6 pages. https://doi.org/ 10.1145/3209950.3209952

14

Related documents

• String Diagrams for Process Mining#978502
• ZigZag Trie: A Novel Index for Contextual Queries#978503
• A Functional Pilot for Certified Freshness-Aware Semantic--Spatial Range Retrieval#978504
• Efficiently Linking Unstructured Data for Multi-step Reasoning#978505