Pith. sign in

REVIEW 3 major objections 6 minor 50 references

HNSW hyperparameter space has monotone and unimodal structure that can be exploited for fast constraint-aware tuning.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review

2026-07-11 16:06 UTC pith:LQD3755C

load-bearing objection Useful systems paper: HNSW structure (monotone efs, dominant unimodal M/efc, separable resources) turned into a fast constraint-aware tuner with real gains and honest failure cases. the 3 major comments →

arxiv 2607.04630 v1 pith:LQD3755C submitted 2026-07-06 cs.DB

Exploiting Structural Properties for Efficient Constraint-Aware HNSW Hyperparameter Tuning

Geon Choi , Hoeun Lee , Jaeyoung Do This is my paper
classification cs.DB
keywords vector databasesapproximate nearest neighbor searchHNSWhyperparameter tuningconstraint-aware optimizationindex construction
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

HNSW is the graph index behind many production vector databases, but its three knobs (M, efc, efs) interact nonlinearly and must meet hard limits on recall, throughput, build time, index size, and tuning budget. The paper argues that this space is not an unstructured black box: efs orders configurations by a monotone recall-latency trade-off, construction parameters show dominant unimodal objective curves under fixed constraints, and resource costs separate cleanly enough to be estimated before a full build. From those regularities the authors build CHAT, a hierarchical tuner that uses binary boundary search on efs, ternary-style localization over M and efc, and closed-form resource surrogates that prune infeasible candidates early. Across standard datasets and three HNSW backends, CHAT recovers nearly the exhaustive-oracle objective while beating strong black-box optimizers by large margins in final performance and by up to 44 imes in convergence speed. The practical claim is that production HNSW deployments can be tuned deterministically and sample-efficiently once the structure is recognized.

Core claim

The HNSW configuration space exhibits strong structural regularities—monotonic feasibility boundaries induced by efs, dominant unimodal trends over the construction parameters M and efc under performance constraints, and separable dependencies of build time and index size—that induce searchable feasibility boundaries and enable deterministic, sample-efficient constraint-aware tuning far beyond generic black-box optimization.

What carries the argument

CHAT: a hierarchical, structure-aware search that decomposes tuning into ternary localization over M, ternary localization over efc for fixed M, and binary boundary search over efs on a fixed index, with online-calibrated closed-form resource surrogates that prune candidates before full index construction.

Load-bearing premise

Once the marginal quality gain from more construction effort no longer beats residual search cost, no later high-utility connectivity regime appears that would create a second performance peak.

What would settle it

On a high-dimensional or uniform workload where the constrained objective over efc or M is clearly multi-modal, measure whether CHAT’s ternary localization still reaches within a few percent of the exhaustive-grid optimum under the same recall or QPS constraint; large, systematic shortfalls would refute the claim that the structure is reliable enough for production use.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper studies constraint-aware hyperparameter tuning for HNSW (M, efc, efs) under Recall/QPS, build-time, index-size, and tuning-budget constraints. It argues that the configuration space has exploitable structure—monotonic efs feasibility boundaries, dominant unimodal trends over efc (fixed M) and over the outer envelope in M, and separable resource dependence—and uses these to design CHAT: nested ternary localization over construction parameters, binary boundary search over efs, history-based range shrinking, and online-calibrated closed-form resource surrogates that prune before full builds. Final selection is always from measured, validated configurations. Experiments on Faiss, Hnswlib, and Milvus across five datasets report up to 45% higher QPS or 11% higher Recall than strong black-box baselines, up to 44× faster convergence to 95% of an exhaustive oracle, and 98–99.9% of oracle objective under the same performance constraints, with ablations of heuristics and resource filters and synthetic stress tests of the unimodality assumptions.

Significance. If the empirical picture holds, this is a useful systems contribution: production HNSW tuning is common, expensive, and poorly served by generic black-box optimizers, and a structure-aware, API-level method that is sample-efficient under hard resource and tuning budgets is practically valuable. Strengths include multi-backend validation (including Milvus), oracle-normalized convergence curves, resource-filter ablations with feasibility coverage, noise-robustness checks, heuristic ablations, and—importantly—an honest synthetic stress test (§6.4) that exposes when the unimodality lemmas fail and quantifies residual loss under best-so-far tracking. The resource surrogates are used only as conservative pruners with measured validation, which is methodologically sound for a systems paper. The work is more than an engineering wrapper around ternary search; the structural analysis of efs boundaries, construction-parameter substitution, and separable build-time/size dependence is a reusable lens for HNSW deployment.

major comments (3)
  1. [§§3.3–3.4, Lemmas 3.1–3.2; §6.4] Lemmas 3.1–3.2 (§§3.3–3.4) and the deterministic ternary design are load-bearing for the sample-efficiency story, yet they are only sufficient conditions. §6.4 correctly shows failure on high-dimensional/uniform synthetics (CHAT retains 94.1% of oracle QPS at a local peak). What is missing for the central claim is a landscape audit on the five real datasets already used for the oracle: for each fixed-M efc slice and for the outer g(M), report number of local peaks, gap between local and global constrained optima, and whether the configuration CHAT returns came from the ternary path or from best-so-far tracking. Without that, the large margins over black-box baselines and the “structure-aware” efficiency narrative are only partially grounded for the regimes the paper claims to cover.
  2. [§5.5; §6] Section 5.5 presents drift-aware retuning and CDHP (constraint-directed hard pruning with sentinel safety) as part of the CHAT system, including directional movement of efc*_M under boundary tightening/relaxation. Section 6 contains no systematic evaluation of corpus insertions/deletions or query-distribution shift, nor of CDHP’s pruning accuracy versus full re-search. Either add a focused retuning experiment (even on one backend/dataset with controlled drift) or clearly demote CDHP to design discussion / future work so the validated claims match the evaluated system.
  3. [§6.2; Appendix E] The QPS constraint targets in §6.2 are set to the 75th percentile of QPS over the predefined search space (Appendix E). That choice makes constraints “comparably difficult” but couples the evaluation target to the same grid the oracle exhausts, and may not reflect external SLOs. Please either (i) report sensitivity to alternative absolute QPS targets (e.g., pilot-probe or fixed absolute thresholds independent of the full grid), or (ii) state more carefully that relative ranking among tuners—not absolute SLO realism—is what the 75th-percentile protocol supports. This matters for interpreting the “up to 45% higher throughput” headline under production-like constraints.
minor comments (6)
  1. [Figure 1; §1] Figure 1 caption and intro claim “up to 144% higher throughput or 16% higher recall” for defaults vs optimal, while the abstract/results lead with 45%/11% vs baselines. Keep both, but label clearly which comparison is which to avoid conflation.
  2. [§§3.3–3.4; Appendix B] Proof sketches for Lemmas 3.1–3.2 are deferred to Appendix B; the main text should state in one sentence that the lemmas rule out negative-to-positive marginal reversals under the stated conditions, so readers need not hunt the appendix for the logical content of “sufficient.”
  3. [§5.4.1, Eq. (6); Appendix F] Equation (6) for h_bt uses a log-like form justified as a convenient concave surrogate. A short note that alternative concave forms were tried (or that calibration residuals in Appendix F are insensitive to the exact concave shape) would strengthen the modeling claim.
  4. [Figure 12; §6.2] Figure 12 is dense (many panels). Consider emphasizing the time-to-95%-oracle metric in a compact table so the 1.5×–44× speedups are easier to audit without reading every curve.
  5. [§7] Related work (§7) on database auto-tuning is brief relative to the ANN and HNSW literature; a sentence positioning CHAT against recent HNSW-specific auto-tuning (e.g., the SSRN/auto-tuning construction-parameter work already cited as [49]) would help novelty framing.
  6. [Abstract; §1] Minor consistency: abstract “44x” vs body “44 ×”; unify spacing and multiplication sign style.

Circularity Check

0 steps flagged

No significant circularity: CHAT's claims rest on measured validation and sufficient-condition structure, not on results forced by definition or self-citation.

full rationale

This is an empirical systems paper. The load-bearing claims (constraint-satisfying configs with higher QPS/Recall and faster convergence vs black-box baselines, near-oracle objective) are obtained by building indices, measuring Recall/QPS/build time/index size on validation workloads, and selecting among explicitly validated feasible configurations. The structural lemmas (3.1–3.2) state only sufficient conditions for discrete unimodality of constrained objectives over efc and M; they do not define the objective or the selected optimum into existence, and Section 6.4 openly exhibits counterexamples where the conditions fail. Resource surrogates (Eqs. 6–7) are calibrated online from constructed configs and used solely as conservative pre-build filters; candidates that pass are still built and measured, and the reported configuration is chosen only from measured feasible points. There is no self-definitional loop, no fitted parameter renamed as a prediction of the main objective, no load-bearing uniqueness theorem imported from the same authors, and no ansatz smuggled via self-citation. Failure modes of unimodality are a correctness/robustness risk, not circularity. Derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

5 free parameters · 5 axioms · 3 invented entities

The central claim rests on standard HNSW insertion/search semantics, empirically observed monotone/unimodal regularities treated as sufficient conditions, and online-fitted resource surrogates used only for pruning. Free parameters are calibration coefficients and search-domain/heuristic choices; invented entities are the CHAT workflow components rather than new physical objects.

free parameters (5)
  • Build-time surrogate coefficients θ_bt = (α0, α1, β0, β1, γ)
    Linear least-squares fit online from constructed configs (Eqs. 6–10); scale/offset are backend-dependent and not derived a priori.
  • Index-size surrogate coefficients θ_is = (η0, η1)
    Linear fit of S ≈ η0 + η1 M from measured builds; used for pre-construction pruning.
  • One-sided residual safety margins for resource pruning
    Computed from positive relative underestimation residuals on set C and recomputed as C grows; residual multipliers (0.5–2.0×) affect pruning aggressiveness (Fig. 13).
  • Initial search domains M∈[4,64], efc∈[8,1024], efs∈[10,1024]
    Hand-chosen discrete ranges that bound the reported optima and oracle comparisons.
  • History-based efc/efs interval shrink heuristics
    Heuristic range reduction from prior optima (Sections 5.2–5.3); ablated in Section 6.5 but still free design choices.
axioms (5)
  • domain assumption Standard HNSW semantics: bounded-degree construction via Select-Neighbors, greedy layer-wise Search-Layer, efs only affects query-time candidate budget on a fixed graph.
    Scoped explicitly in Section 5; structural claims may weaken for nonstandard neighbor selection, disk/GPU bottlenecks, or non-HNSW indexes.
  • domain assumption Recall (and fixed-workload latency quantiles) are monotone in efs, inducing a total order for binary feasibility search.
    Section 3.1 and Algorithm 3; treated as empirical/structural regularity of greedy base-layer search.
  • ad hoc to paper Sufficient conditions for discrete unimodality of f_M(efc) and outer g(M): non-negative residual cost and no delayed high-utility connectivity recovery after the benefit–cost crossing (Lemmas 3.1–3.2).
    Paper-stated sufficient conditions, not universal; counterexamples in Section 6.4 when diminishing-utility fails.
  • domain assumption Index size is dominated by Θ(NM) adjacency storage and is largely independent of efc; build time separates into efc-driven search breadth and M-driven realized degree with sublinear saturation.
    Section 4 resource analysis motivating surrogates (6)–(7).
  • standard math Standard discrete optimization facts: ternary-style localization works on unimodal sequences; binary search works on monotone predicates.
    Used to justify Algorithms 1–3 once structural regularities are assumed.
invented entities (3)
  • CHAT hierarchical constraint-aware tuner no independent evidence
    purpose: Decompose HNSW tuning into outer M search, inner efc search, efs boundary search, and resource filtering with measured validation.
    Primary proposed system; independent evidence is empirical performance vs baselines, not an external physical prediction.
  • Closed-form resource surrogates h_bt(M,efc) and h_is(M) no independent evidence
    purpose: Prune resource-infeasible (M,efc) before full index construction.
    Parametric forms chosen for monotonicity/saturation; coefficients fitted online.
  • CDHP (Constraint-Directed Hard Pruning with Sentinel Safety) no independent evidence
    purpose: Warm-start retuning after corpus/query drift by pruning one side of the efc domain using efs-boundary shift signals.
    Paper-specific retuning policy with sentinel probes for safety.

reviewed 2026-07-11 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Exploiting Structural Properties for Efficient Constraint-Aware HNSW Hyperparameter Tuning." pith.science (2026). https://pith.science/paper/LQD3755C

@misc{pith2026260704630,
  author       = {Pith},
  title        = {Pith review of: Exploiting Structural Properties for Efficient Constraint-Aware HNSW Hyperparameter Tuning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LQD3755C}},
  note         = {Machine review of arXiv:2607.04630}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

Vector databases (VectorDBs) are a core component of modern retrieval systems, including Retrieval-Augmented Generation (RAG), where efficient Approximate Nearest Neighbor Search (ANNS) is critical. Among ANNS algorithms, Hierarchical Navigable Small World (HNSW) graphs are widely adopted for their strong recalllatency trade-off. However, configuring HNSW remains challenging: its hyperparameters jointly affect search quality, latency, build time, and index size in nonlinear ways, while production deployments impose strict resource and tuning-time constraints.We study HNSW hyperparameter tuning from a systems perspective and show that its configuration space exhibits strong structural regularities. Specifically, we identify monotonic, dominant unimodal, and separable relationships among search-time and construction-time parameters, which induce feasibility boundaries under performance and resource constraints. Building on this insight, we propose CHAT, a constraint-aware tuning framework for HNSW. Unlike generic black-box optimizers, CHAT exploits HNSW-specific structure to perform deterministic, sample-efficient search and prune resource-infeasible configurations before full index construction. Across multiple datasets and HNSW-based vector search engines, CHAT identifies configurations that maximize recall or throughput while satisfying constraints on accuracy, latency, build time, index size, and tuning budget. Compared to strong baselines, CHAT achieves up to 45% higher throughput or 11% higher recall, and converges up to 44x faster. These results show that principled, structure-aware tuning enables efficient and robust HNSW deployment beyond generic black-box optimization.

Figures

Figures reproduced from arXiv: 2607.04630 by Geon Choi, Hoeun Lee, Jaeyoung Do.

Figure 1
Figure 1. Figure 1: Performance differences between default and opti [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: HNSW insertion and query processing. (a) Insertion uses efc to search candidate neighbors and M to bound the close/diverse edges retained by Select-Neighbors. (b) Query processing uses efs to control base-layer search after top￾down greedy traversal. 2 Background Hierarchical Navigable Small World (HNSW) [31] is a hierarchi￾cal graph-based index for Approximate Nearest Neighbor Search (ANNS). Each data poi… view at source ↗
Figure 4
Figure 4. Figure 4: Hyperparameter interactions under performance [PITH_FULL_IMAGE:figures/full_fig_p003_4.png] view at source ↗
Figure 6
Figure 6. Figure 6: Graph quality and realized edge growth across dif [PITH_FULL_IMAGE:figures/full_fig_p004_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Optimized efc and objective performance across varying M values. (a) 𝑒 𝑓 𝑐∗ 𝑀 and resulting QPS versus M under a Recall constraint. (b) 𝑒 𝑓 𝑐∗ 𝑀 and resulting Recall versus M under a QPS constraint. When condition (ii) fails, the constrained objective may become bimodal or multi-modal; Section 6.4 presents such a counterexample. When the conditions hold, 𝑓𝑀 can be searched efficiently using the ternary-sty… view at source ↗
Figure 8
Figure 8. Figure 8: Drift implications of efs-boundary shifts. Under a Recall constraint, efc∗ 𝑀 moves right when the required efs increases and left when it decreases. Under a QPS constraint, efc∗ 𝑀 moves left when the maximum allowed efs decreases and right when it increases. 3.6 Drift Implications of Feasibility Boundaries The preceding analysis assumes a fixed corpus and query set. We now consider how the same trade-offs … view at source ↗
Figure 10
Figure 10. Figure 10: Index size dependence on construction hyperpa [PITH_FULL_IMAGE:figures/full_fig_p006_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: The overall architecture and iterative tuning work [PITH_FULL_IMAGE:figures/full_fig_p007_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Tuning performance over time, showing the best-so-far objective value normalized to the Oracle (exhaustive search). Each column corresponds to a dataset, and rows represent QPS (under Recall constraint) and Recall (under QPS constraint) for Hnswlib and Faiss backends, respectively. CHAT consistently achieves faster convergence and higher final performance than baseline methods across all datasets and cons… view at source ↗
Figure 13
Figure 13. Figure 13: Safety-margin sensitivity under resource con￾straints. The figure compares no-margin, fixed-margin, and residual-based variants in terms of pruning rate and false-feasible rate for build-time and index-size constraints. Marker opacity increases with the numeric margin value, so darker markers indicate larger margins. constraint models remain conservative while effectively filtering infeasible regions. Imp… view at source ↗
Figure 14
Figure 14. Figure 14: Impact of heuristic search-space reduction. (a) [PITH_FULL_IMAGE:figures/full_fig_p013_14.png] view at source ↗
Figure 16
Figure 16. Figure 16: CPU-thread sensitivity of the resource feasibility [PITH_FULL_IMAGE:figures/full_fig_p019_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: Calibration and residual diagnostics for the closed￾form resource models. (a) and (b) compare predicted and measured build time and index size; the dashed diagonal in￾dicates perfect calibration, and marker size denotes dataset scale. (c) and (d) report p50 and p95 one-sided underestima￾tion residuals for build time and index size across dataset scales, datasets, and backends. Build-time residuals are lar… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

50 extracted references · 3 canonical work pages

  1. [1]

    Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. 2019. Optuna: A Next-generation Hyperparameter Optimization Framework. InProceedings of the 25th ACM SIGKDD International Confer- ence on Knowledge Discovery & Data Mining(Anchorage, AK, USA)(KDD ’19). Association for Computing Machinery, New York, NY, USA, 2623–2631. doi:10.1...

    doi:10.1145/3292500.3330701 2019

  2. [2]

    Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. 2020. ANN- Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems87 (2020), 101374. doi:10.1016/j.is.2019.02.006

    doi:10.1016/j.is.2019.02.006 2020

  3. [3]

    Do, Yan Xu, and Pascale Fung

    Yejin Bang, Samuel Cahyawijaya, Nayeon Lee, Wenliang Dai, Dan Su, Bryan Wilie, Holy Lovenia, Ziwei Ji, Tiezheng Yu, Willy Chung, Quyet V. Do, Yan Xu, and Pascale Fung. 2023. A Multitask, Multilingual, Multimodal Evaluation of ChatGPT on Reasoning, Hallucination, and Interactivity. arXiv:2302.04023 [cs.CL] https://arxiv.org/abs/2302.04023

    Pith/arXiv arXiv 2023

  4. [4]

    James Bergstra and Yoshua Bengio. 2012. Random search for hyper-parameter optimization.J. Mach. Learn. Res.13, null (Feb. 2012), 281–305

    2012

  5. [5]

    Sebastian Borgeaud, Arthur Mensch, Jordan Hoffmann, Trevor Cai, Eliza Ruther- ford, Katie Millican, George Bm Van Den Driessche, Jean-Baptiste Lespiau, Bog- dan Damoc, Aidan Clark, et al. 2022. Improving language models by retrieving from trillions of tokens. InInternational conference on machine learning. PMLR, 2206–2240

    2022

  6. [6]

    K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. 2002. A fast and elitist multiobjec- tive genetic algorithm: NSGA-II.IEEE Transactions on Evolutionary Computation 6, 2 (2002), 182–197. doi:10.1109/4235.996017

    doi:10.1109/4235.996017 2002

  7. [7]

    dnotitia. [n. d.]. SeahorseDB-dataset. https://huggingface.co/datasets/dnotitia/ SeahorseDB-dataset/tree/main. Accessed: 2025-07-16

    2025

  8. [8]

    Cong Fu, Changxu Wang, and Deng Cai. 2022. High Dimensional Similarity Search With Satellite System Graph: Efficiency, Scalability, and Unindexed Query Compatibility.IEEE Transactions on Pattern Analysis and Machine Intelligence44, 8 (2022), 4139–4150. doi:10.1109/TPAMI.2021.3067706

    doi:10.1109/tpami.2021.3067706 2022

  9. [9]

    Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. [n. d.]. Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph.Proceedings of the VLDB Endowment12, 5 ([n. d.])

  10. [10]

    Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2025. Fast Approx- imate Nearest Neighbor Search With The Navigating Spreading-out Graph. arXiv:1707.00143 [cs.LG] https://arxiv.org/abs/1707.00143

    Pith/arXiv arXiv 2025

  11. [11]

    Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, Meng Wang, and Haofen Wang. 2024. Retrieval-Augmented Generation for Large Language Models: A Survey. arXiv:2312.10997 [cs.CL] https://arxiv.org/abs/2312.10997

    Pith/arXiv arXiv 2024

  12. [12]

    Jacob R Gardner, Matt J Kusner, Zhixiang Eddie Xu, Kilian Q Weinberger, and John P Cunningham. 2014. Bayesian optimization with inequality constraints.. InICML, Vol. 2014. 937–945

    2014

  13. [13]

    Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013. Optimized Product Quantization for Approximate Nearest Neighbor Search. In2013 IEEE Conference on Computer Vision and Pattern Recognition. 2946–2953. doi:10.1109/CVPR.2013. 379

    doi:10.1109/cvpr.2013 2013

  14. [14]

    Rentong Guo, Xiaofan Luan, Long Xiang, Xiao Yan, Xiaomeng Yi, Jigao Luo, Qianya Cheng, Weizhi Xu, Jiarui Luo, Frank Liu, Zhenshan Cao, Yanliang Qiao, Ting Wang, Bo Tang, and Charles Xie. 2022. Manu: A Cloud Native Vector Database Management System. arXiv:2206.13843 [cs.DB] https://arxiv.org/abs/ 2206.13843

    Pith/arXiv arXiv 2022

  15. [15]

    Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. 2020. Accelerating Large-Scale Inference with Anisotropic Vector Quantization. InProceedings of the 37th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 119), Hal Daumé III and Aarti Singh (Eds.). PMLR, 3887–3896. http...

    2020

  16. [16]

    Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. 2020. Accelerating Large-Scale Inference with Anisotropic Vector Quantization. arXiv:1908.10396 [cs.LG] https://arxiv.org/abs/1908.10396

    Pith/arXiv arXiv 2020

  17. [17]

    Lei Huang, Weijiang Yu, Weitao Ma, Weihong Zhong, Zhangyin Feng, Haotian Wang, Qianglong Chen, Weihua Peng, Xiaocheng Feng, Bing Qin, and Ting Liu. 2025. A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions.ACM Transactions on Information Systems43, 2 (Jan. 2025), 1–55. doi:10.1145/3703155

    doi:10.1145/3703155 2025

  18. [18]

    Qiang Huang, Jianlin Feng, Yikai Zhang, Qiong Fang, and Wilfred Ng. 2015. Query-aware locality-sensitive hashing for approximate nearest neighbor search. Proc. VLDB Endow.9, 1 (Sept. 2015), 1–12. doi:10.14778/2850469.2850470

    doi:10.14778/2850469.2850470 2015

  19. [19]

    2021.OpenCLIP

    Gabriel Ilharco, Mitchell Wortsman, Ross Wightman, Cade Gordon, Nicholas Carlini, Rohan Taori, Achal Dave, Vaishaal Shankar, Hongseok Namkoong, John Miller, Hannaneh Hajishirzi, Ali Farhadi, and Ludwig Schmidt. 2021.OpenCLIP. doi:10.5281/zenodo.5143773 If you use this software, please cite it as below

    doi:10.5281/zenodo.5143773 2021

  20. [20]

    Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors: towards removing the curse of dimensionality. InProceedings of the Thirtieth Annual ACM Symposium on Theory of Computing(Dallas, Texas, USA)(STOC ’98). Association for Computing Machinery, New York, NY, USA, 604–613. doi:10.1145/276698. 276876

    doi:10.1145/276698 1998

  21. [21]

    Gautier Izacard and Edouard Grave. 2022. Distilling Knowledge from Reader to Retriever for Question Answering. arXiv:2012.04584 [cs.CL] https://arxiv.org/ abs/2012.04584

    Pith/arXiv arXiv 2022

  22. [22]

    Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2021. Billion-Scale Similarity Search with GPUs.IEEE Transactions on Big Data7, 3 (2021), 535–547. doi:10. 1109/TBDATA.2019.2921572

    arXiv 2021

  23. [23]

    Herve Jégou, Matthijs Douze, and Cordelia Schmid. 2011. Product Quantization for Nearest Neighbor Search.IEEE Transactions on Pattern Analysis and Machine Intelligence33, 1 (2011), 117–128. doi:10.1109/TPAMI.2010.57

    doi:10.1109/tpami.2010.57 2011

  24. [24]

    Urvashi Khandelwal, Omer Levy, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. 2020. Generalization through Memorization: Nearest Neighbor Language Models. arXiv:1911.00172 [cs.CL] https://arxiv.org/abs/1911.00172

    Pith/arXiv arXiv 2020

  25. [25]

    Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. 2020. Retrieval-augmented generation for knowledge-intensive nlp tasks. Advances in Neural Information Processing Systems33 (2020), 9459–9474

    2020

  26. [26]

    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 Knowl- edge and Data Engineering32, 8 (2020), 1475–1488. doi:10.1109/TKDE.2019. 2909204

    doi:10.1109/tkde.2019 2020

  27. [27]

    Petro Liashchynskyi and Pavlo Liashchynskyi. 2019. Grid Search, Random Search, Genetic Algorithm: A Big Comparison for NAS. arXiv:1912.06059 [cs.LG] https: //arxiv.org/abs/1912.06059

    Pith/arXiv arXiv 2019

  28. [28]

    Moore, Alexander Gray, and Ke Yang

    Ting Liu, Andrew W. Moore, Alexander Gray, and Ke Yang. 2004. An investigation of practical approximate nearest neighbor algorithms. InProceedings of the 18th International Conference on Neural Information Processing Systems(Vancouver, British Columbia, Canada)(NIPS’04). MIT Press, Cambridge, MA, USA, 825–832

    2004

  29. [29]

    Jiaheng Lu, Yuxing Chen, Herodotos Herodotou, and Shivnath Babu. 2019. Speedup your analytics: automatic parameter tuning for databases and big data systems.Proc. VLDB Endow.12, 12 (Aug. 2019), 1970–1973. doi:10.14778/3352063. 3352112

    work page doi:10.14778/3352063 2019

  30. [30]

    Le Ma, Ran Zhang, Yikun Han, Shirui Yu, Zaitian Wang, Zhiyuan Ning, Jinghan Zhang, Ping Xu, Pengjiang Li, Wei Ju, Chong Chen, Dongjie Wang, Kunpeng Liu, Pengyang Wang, Pengfei Wang, Yanjie Fu, Chunjiang Liu, Yuanchun Zhou, and Chang-Tien Lu. 2025. A Comprehensive Survey on Vector Database: Storage and Retrieval Technique, Challenge. arXiv:2310.11703 [cs.D...

    arXiv 2025

  31. [31]

    Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs.IEEE transactions on pattern analysis and machine intelligence42, 4 (2018), 824–836. Exploiting Structural Properties for Efficient Constraint-Aware HNSW Hyperparameter Tuning SIGMOD ’27, June 13–19, 2027, Hunti...

    2018

  32. [32]

    Marius Muja and David G. Lowe. 2014. Scalable Nearest Neighbor Algorithms for High Dimensional Data.IEEE Transactions on Pattern Analysis and Machine Intelligence36, 11 (2014), 2227–2240. doi:10.1109/TPAMI.2014.2321376

    doi:10.1109/tpami.2014.2321376 2014

  33. [33]

    Ngatchou, A

    P. Ngatchou, A. Zarei, and A. El-Sharkawi. 2005. Pareto Multi Objective Opti- mization. InProceedings of the 13th International Conference on, Intelligent Systems Application to Power Systems. 84–91. doi:10.1109/ISAP.2005.1599245

    doi:10.1109/isap.2005.1599245 2005

  34. [34]

    OpenAI. 2024. GPT-4 Technical Report. arXiv:2303.08774 [cs.CL] https://arxiv. org/abs/2303.08774

    Pith/arXiv arXiv 2024

  35. [35]

    Zhibin Pan, Liangzhuang Wang, Yang Wang, and Yuchen Liu. 2020. Product Quantization with Dual Codebooks for approximate Nearest Neighbor Search. Neurocomputing401 (03 2020). doi:10.1016/j.neucom.2020.03.016

    work page doi:10.1016/j.neucom.2020.03.016 2020

  36. [36]

    Adams, and Nando de Fre- itas

    Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P. Adams, and Nando de Fre- itas. 2016. Taking the Human Out of the Loop: A Review of Bayesian Optimization. Proc. IEEE104, 1 (2016), 148–175. doi:10.1109/JPROC.2015.2494218

    doi:10.1109/jproc.2015.2494218 2016

  37. [37]

    Weijia Shi, Sewon Min, Michihiro Yasunaga, Minjoon Seo, Richard James, Mike Lewis, Luke Zettlemoyer, and Wen-tau Yih. 2024. Replug: Retrieval-augmented black-box language models. InProceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Lan- guage Technologies (Volume 1: Long Papers). 8371–8384

    2024

  38. [38]

    Jasper Snoek, Hugo Larochelle, and Ryan P. Adams. 2012. Practical Bayesian opti- mization of machine learning algorithms. InProceedings of the 26th International Conference on Neural Information Processing Systems - Volume 2(Lake Tahoe, Nevada)(NIPS’12). Curran Associates Inc., Red Hook, NY, USA, 2951–2959

    2012

  39. [39]

    2019.DiskANN: fast accurate billion- point nearest neighbor search on a single node

    Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Kr- ishaswamy, and Harsha Vardhan Simhadri. 2019.DiskANN: fast accurate billion- point nearest neighbor search on a single node. Curran Associates Inc., Red Hook, NY, USA

    2019

  40. [40]

    Gordon, and Bohan Zhang

    Dana Van Aken, Andrew Pavlo, Geoffrey J. Gordon, and Bohan Zhang. 2017. Automatic Database Management System Tuning Through Large-scale Machine Learning. InProceedings of the 2017 ACM International Conference on Manage- ment of Data(Chicago, Illinois, USA)(SIGMOD ’17). Association for Computing Machinery, New York, NY, USA, 1009–1024. doi:10.1145/3035918.3064029

    doi:10.1145/3035918.3064029 2017

  41. [41]

    Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xi- angyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, Kun Yu, Yuxing Yuan, Yinghao Zou, Jiquan Long, Yudong Cai, Zhenxiang Li, Zhifeng Zhang, Yihua Mo, Jun Gu, Ruiyi Jiang, Yi Wei, and Charles Xie. 2021. Milvus: A Purpose-Built Vector Data Management System. InProceedings of the 202...

    doi:10.1145/3448016.3457550 2021

  42. [42]

    Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A com- prehensive survey and experimental comparison of graph-based approximate nearest neighbor search.Proc. VLDB Endow.14, 11 (July 2021), 1964–1978. doi:10.14778/3476249.3476255

    doi:10.14778/3476249.3476255 2021

  43. [43]

    Ziyu Wang, Frank Hutter, Masrour Zoghi, David Matheson, and Nando De Freitas

  44. [44]

    Bayesian optimization in a billion dimensions via random embeddings.J. Artif. Int. Res.55, 1 (Jan. 2016), 361–387

    2016

  45. [45]

    Zeyu Wang, Qitong Wang, Xiaoxing Cheng, Peng Wang, Themis Palpanas, and Wei Wang. 2024. Steiner-hardness: A query hardness measure for graph-based ann indexes.Proceedings of the VLDB Endowment17, 13 (2024), 4668–4682

    2024

  46. [46]

    Ziwei Xu, Sanjay Jain, and Mohan Kankanhalli. 2025. Hallucination is Inevitable: An Innate Limitation of Large Language Models. arXiv:2401.11817 [cs.CL] https: //arxiv.org/abs/2401.11817

    Pith/arXiv arXiv 2025

  47. [47]

    Tiannuo Yang, Wen Hu, Wangqi Peng, Yusen Li, Jianguo Li, Gang Wang, and Xiaoguang Liu. 2024. Vdtuner: Automated performance tuning for vector data management systems. In2024 IEEE 40th International Conference on Data Engi- neering (ICDE). IEEE, 4357–4369

    2024

  48. [48]

    Tong Yu and Hong Zhu. 2020. Hyper-Parameter Optimization: A Review of Algorithms and Applications. arXiv:2003.05689 [cs.LG] https://arxiv.org/abs/ 2003.05689

    Pith/arXiv arXiv 2020

  49. [49]

    Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang, Zican Dong, Yifan Du, Chen Yang, Yushuo Chen, Zhipeng Chen, Jinhao Jiang, Ruiyang Ren, Yifan Li, Xinyu Tang, Zikang Liu, Peiyu Liu, Jian-Yun Nie, and Ji-Rong Wen. 2025. A Survey of Large Language Models. arXiv:2303.18223 [cs.CL] https://ar...

    Pith/arXiv arXiv 2025

  50. [50]

    keep pruned connections

    Wenyang Zhou, Yuzhi Jiang, Yingfan Liu, Xiaotian Qiao, Hui Zhang, Hui Li, and Jiangtao Cui. 2024. Auto-Tuning the Construction Parameters of Hierarchical Navigable Small World Graphs. doi:10.2139/ssrn.4734062 SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA, USA Choi et al. A Index Construction Algorithms of HNSW A.1 Data Insertion Algorithm 4INSERT(ℎ𝑛𝑠...

    work page doi:10.2139/ssrn.4734062 2024

This paper was first reviewed by grok-4.5 on July 11, 2026.