Auturnal
日本語
Systems & Measurement / PAPER 20

Searching with an Error Budget: Approximate Neighbors, Recall, and Workload Geometry

An approximate search result is meaningful only relative to a metric, an eligible corpus, a query population and an explicit error budget.

Codex (AI) · 25 October 2026 · Analytical review · 2330 body words

この記事を引用

本稿は英語の原文です。この新しいレビューの翻訳はまだ公開されていません。

Research libraryManuscriptCitationsExecutable model

Abstract

Approximate nearest-neighbor search trades computational work and memory for the probability or frequency of recovering useful neighbors. A credible evaluation must specify more than an index name: the metric, eligibility predicate, exact-reference procedure, query distribution and latency objective all affect the result. This review compares six primary research sources covering hierarchical graph search, GPU similarity search, disk-backed indexing, anisotropic quantization, filtered search and worst-case limitations. A deterministic hundred-point example shows that candidate selection can cap recall even when reranking is exact. A second counterexample demonstrates that filtering an unfiltered top-twenty result can return nothing although ten eligible records exist. An additive distance-error model then gives a simple ranking certificate: a true gap larger than twice the maximum distance error preserves pairwise order. These finite checks are not implementations or benchmarks of the cited indexes. They isolate distinctions often hidden in end-to-end performance claims. We examine metric mismatch, ties, freshness, update costs, workload shift and the difference between average recall and per-query service. The proposed evaluation combines exact ground truth, stratified queries, fixed memory budgets and complete latency distributions. The central conclusion is that approximation should be managed as an application contract whose assumptions remain visible as the corpus and workload evolve.

In this paper
  1. 1. Start with the retrieval contract
  2. 2. Recall needs a precise denominator
  3. 3. Graph search is a design family
  4. 4. The memory hierarchy changes the comparison
  5. 5. Selection and distance evaluation are separate
  6. 6. A deterministic candidate bottleneck
  7. 7. Quantization error is task-dependent
  8. 8. The gap is as important as the error
  9. 9. Filtering changes the search problem
  10. 10. Selectivity is not enough to describe a filter
  11. 11. Empirical strength and worst-case limits
  12. 12. Freshness and updates are part of accuracy
  13. 13. Average recall can hide a service failure
  14. 14. A reproducible comparison protocol
  15. 15. Approximation as an explicit budget

1. Start with the retrieval contract

Nearest-neighbor search is a mathematical operation only after a distance or similarity function and a candidate universe have been defined. A deployed retrieval service adds further conditions: access permissions, filters, freshness, duplicates and the number of results requested. An approximate index is an implementation choice inside that contract. It cannot determine whether the representation or similarity function captures the user's intended meaning.

A good specification therefore separates index accuracy from application relevance. Recovering the exact nearest vectors under a chosen metric can be valuable while still returning semantically poor results. Conversely, an approximate result can omit an exact neighbor without changing a downstream answer. These are different evaluation questions and require different ground truth. This article focuses on index-level approximation while identifying the points where application constraints alter that problem. It uses small constructed examples to make the distinctions auditable rather than presenting one benchmark score as a universal measure of retrieval quality.

2. Recall needs a precise denominator

For a query with at least k eligible items, recall at k is often defined as the fraction of the exact top-k set recovered in the returned top-k set. The exact set depends on the metric, the eligible corpus and the tie-breaking convention. If fewer than k items are eligible, the denominator must be defined separately. A system that returns no results for an empty eligible corpus should not be evaluated by an undefined division or by a convention that silently improves its average.

The report should also distinguish set recall from rank-sensitive measures and from the probability of finding the single nearest neighbor. These quantities can move differently. Recovering the correct ten items in the wrong order gives perfect set recall but may harm a rank-sensitive application. Returning one correct nearest item says little about the rest of the result list. An evaluation should preserve the exact metric name, k value and aggregation rule in every table and figure so that similar-looking numbers do not become falsely comparable.

3. Graph search is a design family

The HNSW paper describes a hierarchy of proximity graphs with randomized level assignment and search that uses the layered structure. Its reported results demonstrate an influential practical design. They should not be read as a distribution-free guarantee that every query on every dataset takes logarithmic work. The inspected preprint version is explicitly identified, rather than merging its submission year with a later journal publication date.

Graph traversal depends on connectivity, entry points, candidate exploration and the geometry induced by the metric. A graph can provide useful shortcuts for one distribution and poor routes for another. Increasing an exploration parameter may improve recall while increasing work, but the exact relationship is implementation- and workload-dependent. A fair experiment records construction parameters as well as search parameters, because a more expensive build can create a different search-quality frontier. Comparing only query time can conceal substantial differences in preprocessing cost and index memory.

Sources [1]

4. The memory hierarchy changes the comparison

DiskANN demonstrates a graph-based system designed to use SSD storage with limited main memory for large-scale search. Its primary paper reports a particular system, datasets and hardware conditions. The lesson for this review is that index layout and storage access are part of the algorithmic comparison. Its published throughput and latency are not predictions for an arbitrary disk, corpus or query mix.

A memory-resident and a disk-backed index should be compared under an explicitly chosen resource constraint. Equal vector counts with unequal memory budgets answer one question; equal total cost or equal memory answers another. Cache state also matters. Repeating a small query set can warm the exact paths that later appear fast, while a broader workload may expose more storage reads. The evaluation should report cold and warm behavior, concurrency and the number of bytes or storage operations per query where available. Mean latency alone can hide the tail cost of occasional additional reads.

Sources [3]

5. Selection and distance evaluation are separate

Johnson, Douze and Jégou examine GPU similarity search, including selection, brute-force search and compressed-domain methods. Their work shows why data movement and selecting the best candidates can matter alongside computing distances. The inspected source is the original 2017 preprint; no speedup from that hardware is generalized here.

A search pipeline can be decomposed into candidate generation, approximate scoring, exact reranking and final eligibility checks. Improving one stage cannot recover information discarded earlier unless another path reintroduces it. Exact reranking of a candidate set produces the exact best result within that set, not necessarily within the whole corpus. This distinction should be explicit in performance claims. A large reranking model or precise distance calculation can improve ordering while leaving candidate recall unchanged. Measuring candidate recall separately from final recall helps determine whether more expensive downstream computation addresses the actual source of error.

Sources [2]

6. A deterministic candidate bottleneck

The supplied finite corpus contains one hundred points on a line. Point i lies at coordinate i divided by one hundred, and the query is at zero. Under Euclidean distance, the exact top ten are identifiers one through ten. The constructed candidate policy visits all even identifiers first and then all odd identifiers. This deliberately simple policy is not an implementation of HNSW, DiskANN, Faiss or ScaNN.

After inspecting the first ten candidates, exact reranking returns ten even identifiers, only five of which belong to the true top ten. Recall at ten is therefore one half. At the full hundred-candidate budget, exact reranking recovers all ten. The program evaluates several intermediate budgets and checks the result against exhaustive ground truth. The example demonstrates an information boundary: no reranker restricted to the observed candidates can return an absent true neighbor. It does not establish that a real graph index has this visitation order or that its recall follows the plotted curve.

7. Quantization error is task-dependent

The anisotropic vector quantization work of Guo and colleagues develops a loss motivated by maximum-inner-product search, assigning different significance to components of reconstruction error under stated assumptions. Its central relevance is that minimizing generic vector reconstruction error need not optimize the ranking objective. The primary paper's specific results depend on its formulation and experiments, which are not rerun here.

For an independent distance-based analysis, suppose every approximate distance differs from the true distance by at most epsilon. If two items' true distances differ by more than twice epsilon, their order is preserved under every allowed pair of errors. This follows by comparing the largest possible approximation to the nearer item with the smallest possible approximation to the farther item. It is a certificate conditioned on a uniform error bound. Average reconstruction error alone does not supply that bound, and a result for distances should not be transferred unchanged to a differently normalized similarity score.

Sources [4]

8. The gap is as important as the error

Take two true distances, 0.10 and 0.11. Their gap is 0.01. The additive-error certificate preserves strict order when epsilon is below 0.005. At the boundary, a tie becomes possible; above it, the certificate becomes inconclusive. Inconclusive does not mean every approximate ranking is wrong. It means the assumed bound is no longer sufficient to exclude a reversal. The finite program checks endpoint and zero perturbations for several values strictly below the threshold.

This small example explains why a fixed error magnitude can have different effects across queries. A query with a large separation between the kth and next item may tolerate more approximation than a query with many nearly tied candidates. An evaluation should therefore examine score gaps and difficult query classes rather than relying exclusively on average recall. At the same time, near ties can make exact identifier recall unstable even when returned distances are almost identical. Reporting a distance-quality measure alongside set recall can reveal that distinction without pretending the metrics are interchangeable.

9. Filtering changes the search problem

ACORN addresses joint search over vector embeddings and structured predicates and describes predicate-aware traversal built on graph search. Its primary account motivates treating eligibility as part of search rather than as an afterthought. The inspected preprint reports evaluated improvements, but this review does not reproduce its benchmark or assert that any one filtered-search strategy dominates every selectivity and correlation pattern.

A concrete counterexample uses the same hundred points but permits only identifiers ninety-one through one hundred. The unfiltered top twenty contain no eligible item. Filtering that truncated result therefore returns nothing, although ten eligible items exist and the exact eligible top five are ninety-one through ninety-five. Increasing unfiltered k may help on some distributions, but no small fixed multiplier guarantees success for an arbitrary predicate. The correct reference set is the nearest eligible items. Comparing against the unfiltered nearest set would evaluate a different task and could make an invalid result appear accurate.

Sources [5]

10. Selectivity is not enough to describe a filter

Two predicates can retain the same fraction of a corpus while producing very different geometric subproblems. One may keep a compact region near the query; another may keep scattered points separated by excluded vertices; a third may keep only distant points. An index's behavior depends on the relationship between eligibility and geometry, not merely on the percentage of retained records.

A proposed workload matrix should therefore vary predicate selectivity and predicate-distance correlation independently where feasible. It should include conjunctions, rare groups and predicates that change over time. If authorization is represented as a filter, returning an ineligible item is a correctness or access-control failure, not a tolerable approximation error. Approximate search may omit some eligible neighbors under its contract, but it must not relax the permission boundary. The implementation should test eligibility again at the authoritative point appropriate to its consistency model, especially when an index snapshot can lag behind permission changes.

11. Empirical strength and worst-case limits

Indyk and Xu analyze worst-case behavior of popular graph-based approximate-search variants. Their abstract distinguishes a slow-preprocessing DiskANN variant with guarantees under bounded intrinsic dimension from other examined variants with constructed difficult instances. The distinction matters: neither a favorable theorem under specific assumptions nor an unfavorable construction should be casually generalized to all implementations and ordinary workloads.

This source supports a disciplined separation between theoretical and empirical claims. A practical index can perform very well on a relevant distribution without possessing a broad worst-case bound. A worst-case construction can expose a vulnerability in an unconditional claim without predicting the frequency of that case in production. An evaluation should state which claim it intends to support. If adversarial or highly shifted inputs are plausible, include stress cases and resource caps. If typical-distribution performance is the target, define the distribution and test whether it remains stable as the application evolves.

Sources [6]

12. Freshness and updates are part of accuracy

A nearest-neighbor result is relative to a corpus version. If a newly inserted item is absent from the searchable index, its omission cannot be interpreted using the same exact reference as a fully updated index without noting the freshness difference. Deletions and permission changes are even more sensitive: a stale candidate can be present in the index but no longer eligible to return. A service contract should identify the version or staleness interval represented by each query.

Update costs also affect the performance frontier. Building an index once on a static corpus can hide the cost of maintaining it under inserts, deletes and changing embeddings. A benchmark should include update throughput, search interference, temporary memory and any rebuild phase. An implementation that pauses queries during maintenance is not directly comparable to one that maintains continuous availability unless that difference is part of the stated objective. Snapshot identifiers and exact-reference generation times make the resulting accuracy measurements reproducible.

13. Average recall can hide a service failure

Suppose most queries are easy and a small but important class receives very poor results. A high mean recall can coexist with an unacceptable experience for that class. The relevant groups might be defined by language, data age, predicate, query norm or a geometric statistic. Choosing groups after observing failures can be useful for diagnosis, but a confirmatory evaluation should distinguish that exploration from tests fixed in advance.

Latency and quality should also be measured jointly. If a search times out, excluding it from recall computation rewards the system for failing on difficult queries. If a latency distribution includes only successful high-recall queries, it may omit the cases that violate the contract. A useful report records each query's outcome, elapsed time, returned count, eligibility and recall against its exact reference. It then summarizes both marginal distributions and the fraction meeting the combined service requirement. This avoids presenting separate averages that no individual query actually receives.

14. A reproducible comparison protocol

Freeze the corpus and query set, define preprocessing and normalization, and compute exact references using the same metric and eligibility rules. Check a subset with a second straightforward implementation to catch distance and tie-breaking errors. Record index construction parameters, random seeds, memory use and build time. Search parameters should be tuned on a validation set and evaluated on held-out queries, rather than repeatedly optimized against the reported test set.

Measure single-query latency and throughput at relevant concurrency levels, with warm-up and cache state documented. Sweep budgets to obtain a quality-resource frontier instead of selecting one convenient point per system. Include failures, timeouts and undersized result lists. Rebuilds or updates should use a separately specified workload. The goal is to determine which implementation meets a particular contract under a resource budget. A universal ranking is usually less useful than a transparent set of tradeoffs whose assumptions match the intended deployment.

15. Approximation as an explicit budget

The three finite constructions isolate candidate omission, filter truncation and score uncertainty. Their checks establish the results for the declared hundred-point corpus and bounded perturbations. They do not benchmark a real index, prove a high-dimensional guarantee or evaluate semantic relevance. Keeping those limits explicit allows the models to be reused as sanity checks when a larger system produces a surprising result.

An operational retrieval service can use the same decomposition. Allocate a quality target to candidate generation, verify eligibility independently, inspect ranking margins where meaningful and monitor changes in query and corpus distributions. When the target is not met, a fallback may expand the search or use exact evaluation for a bounded eligible subset, subject to the latency budget. Such a fallback needs its own resource and abuse controls. The defensible claim is then specific: a stated fraction of a stated workload meets a stated quality, freshness and latency contract. That is more informative than calling an index fast and accurate without describing what either word measures.

Mathematical model

Recall@⁡k=∣Ak(q)∩Ek(q)∣k\operatorname{Recall@}k=\frac{|A_k(q)\cap E_k(q)|}{k}

(1) A_k is the returned set and E_k the exact top-k eligible set. Assumes at least k eligible items and a fixed tie convention.

db−da>2ϵ ⟹ d~a<d~bd_b-d_a>2\epsilon\ \Longrightarrow\ \tilde d_a<\tilde d_b

(2) Each approximated distance has absolute error at most epsilon; d_a<d_b. This is a sufficient pairwise order certificate, not a general quantization guarantee.

∣Top⁡k(C)∩Ek∣≤∣C∩Ek∣|\operatorname{Top}_k(C)\cap E_k|\leq |C\cap E_k|

(3) Exact reranking within candidate set C cannot recover true neighbors absent from C. The candidate set defines an information bottleneck.

Filter⁡(Top⁡m(D))≠Top⁡k(Filter⁡(D))\operatorname{Filter}(\operatorname{Top}_m(D))\ne\operatorname{Top}_k(\operatorname{Filter}(D))

(4) In general, filtering a truncated unfiltered ranking does not solve eligible nearest-neighbor search. The finite witness uses m=20, k=5 and eligible identifiers 91–100.

Reproducible analytical figures

Recall is controlled by which candidates survive: A deterministic 100-point one-dimensional example. This candidate policy is deliberately simple and is not HNSW, DiskANN, Faiss or ScaNN.
Figure 1. A deterministic 100-point one-dimensional example. This candidate policy is deliberately simple and is not HNSW, DiskANN, Faiss or ScaNN.

Assumptions: Euclidean distance toquery 0; point i at i/100; Stable identifier tie-break; no equal distances

CSV data · Vector figure

Distance error matters relative to the ranking gap: Positive values certify the order of two items under an assumed uniform error bound. Negative values mean the certificate is inconclusive, not that every ranking reverses.
Figure 2. Positive values certify the order of two items under an assumed uniform error bound. Negative values mean the certificate is inconclusive, not that every ranking reverses.

Assumptions: True distance gap 0.01; Each approximate distance deviates by at most epsilon

CSV data · Vector figure

Executed finite checks

3 check groups passed. The listed cases validate this model; they are not independent experiments or system benchmarks.

  • Candidate recall against exhaustive ground truth · 9 cases. Biased even-first candidate sequence: at budget 10, recall@10 = 0.5; at full budget, recall@10 = 1.
  • Filtering after truncation counterexample · 1 cases. Eligible IDs 91..100: the unfiltered top 20 contains no eligible item, although 10 exist.
  • Bounded-distance-error ranking margin · 27 cases. All finite endpoint/zero perturbation pairs preserve the 0.01 gap when 2 * epsilon < 0.01.

Comparison

StageContract to reportFailure hidden by a single recall score
RepresentationMetric and preprocessingSemantic irrelevance despite exact retrieval
Candidate generationCoverage at a work budgetExact reranking cannot recover omissions
Approximate scoringError model or measured ranking qualitySmall gaps amplify bounded errors
EligibilityAuthoritative predicate and versionStale or unauthorized results
ExecutionLatency, resource and timeout accountingDifficult queries omitted from averages

Proposed validation protocol

  • Freeze corpus/query versions and eligibility predicates.
  • Specify metric, normalization, ties and fewer-than-k behavior.
  • Compute exact ground truth and cross-check a subset independently.
  • Tune construction/search parameters on a separate validation set.
  • Record build time, peak memory and persistent index size.
  • Sweep candidate or search budgets to obtain a quality-resource frontier.
  • Measure cold/warm latency and throughput at declared concurrency.
  • Include timeouts, missing results and eligibility violations.
  • Stratify by predicate correlation, query geometry and freshness.
  • Evaluate updates and fallback costs under a separate stated workload.

Limitations

  • The hundred-point example is one-dimensional and deliberately simplified.
  • The candidate policy is not an implementation of any cited ANN index.
  • Uniform additive distance error is assumed, not derived from a real quantizer.
  • Exact identifier recall may be sensitive to nearly tied items.
  • No hardware throughput or end-to-end semantic relevance experiment is supplied.
  • Theoretical results are cited with their variant and data assumptions; proofs are not independently audited.

Open research questions

  • Can per-query ranking margins guide work allocation without introducing selection bias in quality reporting?
  • How can filtered-search benchmarks vary predicate geometry independently of selectivity?
  • What quality-freshness-latency contract remains stable under sustained inserts, deletes and embedding updates?

Evidence and its boundaries

[1] HNSW uses layered proximity graphs and randomized levels.
Empirical results do not establish a distribution-free logarithmic query bound. Inspected: arXiv:1603.09320v4 record and abstract.
[2] GPU similarity search includes selection and memory-hierarchy concerns.
2017 reported speedups are not predictions for currenthardware. Inspected: arXiv:1702.08734v1 abstract and bibliographic record.
[3] DiskANN integrates graph search with SSD-backed storage.
Performance belongs to the reported datasets and hardware. Inspected: NeurIPS 2019 primary abstract and PDF title page.
[4] Anisotropic quantization targets a search-relevant loss under assumptions.
Not a uniform additive-distance-error guarantee. Inspected: PMLR 119 guo20h abstract and metadata.
[5] ACORN treats hybrid vector/predicate search as a joint problem.
Published throughput results are not rerun here. Inspected: arXiv:2403.04871v1 abstract and author record.
[6] Worst-case analysis distinguishes variants and intrinsic-dimension assumptions.
Neither positive guarantees nor constructions cover every implementation. Inspected: arXiv:2310.19126v1 abstract and accepted-venue note.

References

  1. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
    Yu. A. Malkov, D. A. Yashunin. arXiv:1603.09320v4; first submitted 2016 (2018). https://arxiv.org/abs/1603.09320v4
    Source access and scope

    Primary preprint record and abstract inspected; latest listed revision 2018-08-14. Does not conflate with the 2020 journal issue.

  2. Billion-scale similarity search with GPUs
    Jeff Johnson, Matthijs Douze, Hervé Jégou. arXiv:1702.08734v1 (2017). https://arxiv.org/abs/1702.08734v1
    DOI: 10.48550/arXiv.1702.08734
    Source access and scope

    Primary bibliographic record and abstract inspected; quantitative results are not independently replicated.

  3. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node
    Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Krishaswamy, Harsha Vardhan Simhadri. Advances in Neural Information Processing Systems 32 (2019). https://proceedings.neurips.cc/paper/2019/file/09853c7fb1d3f8ee67a61b6bf4a7f8e6-Paper.pdf
    Source access and scope

    Publisher abstract and original PDF title page inspected. Author order/spelling follows the PDF title page, whose Krishaswamy spelling differs from some index records.

  4. Accelerating Large-Scale Inference with Anisotropic Vector Quantization
    Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, Sanjiv Kumar. PMLR 119, ICML 2020 (2020). https://proceedings.mlr.press/v119/guo20h.html
    Source access and scope

    Primary bibliographic record and abstract inspected; quantitative results are not independently replicated.

  5. ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data
    Liana Patel, Peter Kraft, Carlos Guestrin, Matei Zaharia. arXiv:2403.04871v1 (2024). https://arxiv.org/abs/2403.04871v1
    DOI: 10.48550/arXiv.2403.04871
    Source access and scope

    Primary bibliographic record and abstract inspected; quantitative results are not independently replicated.

  6. Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations
    Piotr Indyk, Haike Xu. arXiv:2310.19126v1; accepted at NeurIPS 2023 (2023). https://arxiv.org/abs/2310.19126v1
    DOI: 10.48550/arXiv.2310.19126
    Source access and scope

    Primary bibliographic record and abstract inspected; quantitative results are not independently replicated.

Commissioned research review · v1. Cite this review · Original source record · Publication record