Exploiting Structural Properties for Efficient Constraint-Aware HNSW Hyperparameter Tuning

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Exploiting Structural Properties for Efficient Constraint-Aware HNSW Hyperparameter Tuning

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

databases datamanagement sql storage

databases, sql, data management, storage

Exploiting Structural Properties for Efficient Constraint-Aware HNSW Hyperparameter Tuning Hoeun Lee

Jaeyoung Do∗

Seoul National University South Korea [email protected]

arXiv:2607.04630v1 [cs.DB] 6 Jul 2026

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 44× faster. These results show that principled, structure-aware tuning enables efficient and robust HNSW deployment beyond generic black-box optimization.

CCS Concepts • Information systems → Nearest-neighbor search; Database query processing; • Computing methodologies → Machine learning; • Theory of computation → Design and analysis of algorithms.

∗ Corresponding Author.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. SIGMOD ’27, Huntington Beach, CA, USA © 2027 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-1-4503-XXXX-X/2018/06 https://doi.org/XXXXXXX.XXXXXXX

Recall (QPS Constraint Q90)

Geon Choi

1.0 0.9 0.8 0.7 0.6 0.5 0.4 3 10

nytimes

glove

sift

104

deep1M

QPS (Recall Constraint = 0.95)

youtube

105

Figure 1: Performance differences between default and optimal HNSW hyperparameter configurations across datasets using Faiss [22]. Filled markers indicate optimal configurations, while outlined markers indicate default configurations. See Section 6.1 for details.

Keywords Vector databases, Approximate nearest neighbor search, HNSW, Hyperparameter tuning, Constraint-aware optimization, Index construction ACM Reference Format: Geon Choi, Hoeun Lee, and Jaeyoung Do. 2027. Exploiting Structural Properties for Efficient Constraint-Aware HNSW Hyperparameter Tuning. In Proceedings of the 2027 International Conference on Management of Data (SIGMOD ’27), June 13–19, 2027, Huntington Beach, CA, USA. ACM, New York, NY, USA, 20 pages. https://doi.org/XXXXXXX.XXXXXXX

Introduction

Recent advances in large language models (LLMs) have led to strong performance in text-based retrieval, generation, and summarization [34, 48]. However, their limited parameterization and training data can still lead to hallucinated or stale outputs [3, 17, 30, 45]. Retrieval-Augmented Generation (RAG) mitigates this limitation by retrieving external knowledge at inference time, avoiding costly fine-tuning while improving factual grounding [5, 11, 21, 24, 25, 37]. At the core of RAG pipelines are vector databases (VectorDBs) [14, 41], which store large-scale embeddings and support Approximate Nearest Neighbor Search (ANNS) [13, 15, 23, 28, 32]. Among ANNS algorithms, Hierarchical Navigable Small World (HNSW) graphs [31] are widely adopted for their strong recall-latency tradeoff and scalability [2]. Despite its popularity, deploying HNSW effectively remains difficult [31, 49]. HNSW performance is governed by three core hyperparameters: M, the maximum number of connections allowed per node; efc, the construction-time candidate-list size used during insertion; and efs, the query-time candidate-list size used during search. These parameters jointly affect recall, throughput, build

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA, USA

Choi et al.

(a) HNSW Insertion (b) HNSW Query time, and index size. As shown in Figure 1, fixed default HNSW conLayer=2 Layer=2 figurations often do not coincide with the dataset-specific feasible frontier or constraint-aware optimum. Thus, even under identical Layer=1 Layer=1 recall or QPS targets, tuned configurations can avoid constraint violations or recover performance left on the table by defaults, achieving up to 144% higher throughput or 16% higher recall. Layer=0 Layer=0 q HNSW tuning is challenging because these parameters interact nonBeam=efs Beam=efc q linearly and often trade off competing objectives [47]. For example, ≤ M retained edges increasing efc can improve graph quality and recall, but may also increase build cost, index size, and query traversal overhead. Existing Figure 2: HNSW insertion and query processing. (a) Insertion tuning methods, including Grid/Random Search [4, 27], Optuna [1], uses efc to search candidate neighbors and M to bound the NSGA-II [6], ECI [12], and VDTuner [46], largely treat HNSW as close/diverse edges retained by Select-Neighbors. (b) Query an opaque objective. More broadly, generic surrogate-based and processing uses efs to control base-layer search after topBayesian optimizers can be sample-inefficient in discrete, noisy, and down greedy traversal. narrow-feasibility search spaces [36, 38, 43], while Pareto-oriented methods [33] do not directly target the single constraint-satisfying 2 Background optimum required here. These methods therefore spend substantial Hierarchical Navigable Small World (HNSW) [31] is a hierarchituning budget exploring expensive configurations without directly cal graph-based index for Approximate Nearest Neighbor Search exploiting the structural regularities induced by HNSW construc(ANNS). Each data point is represented as a node, and proximity tion and search. relationships are represented as graph edges. HNSW exposes three We propose CHAT, a constraint-aware, API-level black-box but core tuning parameters used throughout this paper: M, the degree HNSW-structure-aware tuning framework. CHAT does not inspect budget that controls how many neighbors a node can retain; efc, the internal graph statistics; it uses only standard build/query APIs construction-time candidate-list size used when inserting nodes; and measured validation signals. However, it exploits public HNSW and efs, the search-time candidate-list size used when answering mechanisms to decompose tuning into structured subproblems: queries. The construction parameters M and efc determine the graph guided search over construction parameters (M,efc), binary boundstructure, whereas efs controls query-time traversal over a fixed ary search over efs, and resource-feasibility filtering before full graph. index construction. Resource estimates are used only to avoid unFigure 2 illustrates the layered structure and the two main HNSW necessary builds; configurations that survive this filter are still procedures. Each node is assigned a maximum layer by randomized built, measured, and validated before selection. This design leverlevel generation and appears in every layer from Layer 0 up to that ages monotonic, dominant unimodal, and separable relationships in level. Since upper layers contain progressively fewer nodes, they the HNSW configuration space to reduce unnecessary evaluations provide sparse long-range routing links, while Layer 0 contains all while selecting configurations validated against user-specified perdata points and supports fine-grained search. Both insertion and formance and resource constraints. We intentionally scope these query processing therefore follow a coarse-to-fine pattern: HNSW structural claims to standard HNSW implementations; extending first performs greedy top-down traversal through upper layers and the methodology to other ANN families requires identifying analothen conducts a broader search near the Layer 0. gous search-time, construction-time, and resource regularities. During insertion (Figure 2(a)), a new point 𝑞 first uses greedy deWe evaluate CHAT on Faiss [22], Hnswlib [31], and Milvus [41] scent with Beam = 1 to locate an entry point near 𝑞. From the across five datasets. Compared with strong baselines, CHAT achieves assigned layer of 𝑞 down to Layer 0, HNSW runs Search-Layer up to 45% higher throughput or 11% higher recall, and converges with candidate-list size efc to collect candidate neighbors. These up to 44× faster, while satisfying accuracy, throughput, build-time, candidates are then passed to Select-Neighbors, which retains index-size, and tuning-budget constraints. close and diverse neighbors up to the layer-specific degree budget Our key contributions are: induced by M; fewer than M edges may be retained when candidates • We formulate constraint-aware HNSW hyperparameter tuning are redundant. During query processing (Figure 2(b)), the query vecunder performance, resource, and tuning-budget constraints. tor 𝑞 is not inserted into the graph. After the same greedy top-down • We characterize HNSW-specific structural regularities—monotone feasibility boundaries induced by efs, dominant unimodal construction- traversal, HNSW runs Search-Layer at Layer 0 with candidate-list size efs and returns the top-𝑘 candidates from the final working parameter trends, and separable resource dependencies. set. Thus, increasing efs broadens query-time search on a fixed • We introduce CHAT, an API-level black-box but HNSW-structuregraph, while changing M or efc changes the graph and requires aware tuner that uses hierarchical search and measured validarebuilding the index. Appendix A provides formal pseudocode for tion to identify constraint-satisfying configurations efficiently. these procedures. • We develop analytic resource models for build time and index size, enabling feasibility-aware pruning before full index construction. 3 Decoding HNSW Hyperparameter Trade-offs • We validate CHAT across datasets and HNSW-based VectorDB backends, showing substantial performance and convergence This section presents an in-depth analysis of the three key HNSW gains over strong baselines. hyperparameters (i.e., M, efc, and efs) and their non-trivial interactions in shaping search performance [31]. Because these parameters

Exploiting Structural Properties for Efficient Constraint-Aware HNSW Hyperparameter Tuning

QPS

0.75

0.80

Recall (a)

0.85

0.90

QPS

6K 5K 4K 3K 2K 1K 10240

256

512

efs

768

are tightly coupled, changing one often requires compensatory adjustments in others; understanding these trade-offs is essential for principled tuning and motivates our CHAT framework. We focus here on Recall and query throughput (QPS), and show that the strict monotonicity of efs with respect to recall and latency induces a total order over configurations, enabling binary feasibility search for constraint satisfaction rather than heuristic exploration. Resourceusage metrics (index build time and size) are analyzed in Section 4 to inform our constraint surrogate models. Unless otherwise specified, figures referenced in this section are generated using Faiss [22] on the nytimes dataset [2] (see Section 6.1 for details on the experimental setup). The qualitative patterns described below were consistent across query parallelism levels (1, 4, 16, and 64 threads); the figures in this section use 64 threads, and we focus on these structural trends rather than absolute QPS values.

Effect of efs on Search Accuracy and Speed

The hyperparameter efs controls the size of the candidate set maintained and expanded during query-time traversal at the base layer. Increasing efs broadens the search scope, thereby improving recall, but also incurs higher computational costs due to additional distance evaluations, resulting in lower query throughput (QPS). This monotonic accuracy–speed trade-off is illustrated in Figure 3(a). Beyond this monotonic trade-off, efs exhibits diminishing returns in the high-efs regime. As shown in Figure 3(b), recall improvements rapidly saturate once most informative candidates near the query have already been explored, making additional candidates largely distant or redundant. QPS degradation also flattens in this regime because the number of candidates that can be meaningfully expanded is constrained by the graph structure and by the finite set of nearby nodes that can contribute to the top-𝑘 results. Thus, while the nominal candidate budget increases, the marginal performance change from additional search effort decreases. These saturation behaviors stem from the greedy search mechanism employed at layer 0 in HNSW. As the search converges toward a local optimum, discovering substantially better candidates becomes increasingly difficult, causing the marginal utility of additional search effort—measured as performance gain per unit cost—to drop sharply. Crucially, this structure induces a monotone feasibility ordering over efs: larger efs improves recall but increases query cost. This property enables binary feasibility search for constraint satisfaction, rather than costly heuristic exploration, and explains

Recall Constraint = 0.95

200

400

600

efc

(a)

(b)

Figure 3: Effect of efs on search performance. (a) Recall-QPS trade-off as efs increases. (b) Individual performance curves showing recall saturation and QPS decline with increasing efs.

3.1

300 250 200 150 100 50

1000 800 600 400 200 00

QPS Constraint = 10,000

efs

Recall

efs

0.99 0.98 0.97 0.96 0.95 0.94 0.93 0.920

Recall

efs

QPS

35K 30K 25K 20K 15K 10K 5K 0 0.70

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA, USA

800

1000

(b)

Figure 4: Hyperparameter interactions under performance constraints. (a) Increasing efc shifts the Recall-feasibility boundary toward smaller efs. (b) Increasing M shifts the QPSfeasibility boundary toward smaller efs. Both exhibit steep initial movement followed by saturation. why blindly increasing efs is inefficient for balancing accuracy and latency.

3.2

Interaction between Construction Parameters and efs

The construction-time parameters efc and M shape the HNSW graph through complementary mechanisms. The parameter efc controls the breadth of candidate search during insertion: a larger efc exposes Select-Neighbors to a richer candidate pool, increasing the likelihood that high-quality, diverse edges survive pruning. Because Select-Neighbors often retains fewer than M edges due to its diversification criterion, larger efc can improve realized connectivity even when the degree cap is not the binding constraint. M, in contrast, directly caps per-node degree. Thus, efc shapes which candidate edges are available, while M bounds how many are retained. To characterize the coupling with query-time search, we use the constraint-boundary efs: the minimum efs that reaches the target Recall under a Recall constraint, or the maximum efs that keeps throughput above the target under a QPS constraint. Figure 4(a) shows that increasing efc shifts this boundary downward under a Recall constraint, because a richer candidate pool improves graph quality and fewer query-time candidates suffice. Figure 4(b) shows the similar shift for M under a QPS constraint: larger degree caps increase work per expanded node, reducing the maximum feasible efs. The boundary moves in the same direction under the opposite constraint for both parameters, because stronger realized connectivity simultaneously improves Recall (lowering minimum-feasible efs) and raises traversal cost (lowering maximum-feasible efs). The steep-to-gradual shape in both panels reflects a common saturation mechanism in construction-time graph improvement. For efc, the benefit saturates because Select-Neighbors increasingly rejects redundant candidates once the candidate pool is sufficiently rich. For M, realized connectivity can grow sublinearly and saturate below the nominal cap because the same diversification rule limits which additional neighbors are retained. Thus, efc and M can both reduce the boundary efs, but their marginal benefit diminishes once the graph becomes sufficiently navigable. These observations have two implications for tuning. First, stronger realized connectivity typically shifts the constraint-boundary efs downward, allowing CHAT to narrow the efs search range using previous evaluations (Section 5.3). Second, when graph-quality gains saturate while traversal overhead continues to grow, the

QPS

5800

200

5600 250

500

efc

(a)

750

1000

0.914

120

0.912

100 250

500

efc

750

M = 16

200

400

1000

(b)

Figure 5: Dominant unimodal performance patterns with varying efc under fixed M. (a) Under a Recall constraint, QPS first improves as increasing efc reduces the constraintboundary efs, then declines as traversal overhead dominates. (b) Recall under a QPS constraint follows the same pattern. constrained objective moves from a quality-improving regime to an overhead-dominated regime. This crossover underlies the dominant unimodal trends analyzed in Sections 3.3 and 3.4.

3.3

1.00 0.98 0.96 0.94 0.92 0.90 0.88 0.86 0.84 0.82 0.80

Unimodality over efc under Fixed M

We fix M and study how efc affects the constrained objective after efs has been chosen at the feasibility boundary. For each efc, CHAT selects the boundary efs under the active performance constraint: the smallest efs satisfying the Recall target, or the largest efs satisfying the QPS target. Let 𝑓𝑀 (𝑒 𝑓 𝑐) denote the resulting objective value, namely QPS under a Recall constraint and Recall under a QPS constraint. We call 𝑓𝑀 unimodal if it is non-decreasing up to some peak index and non-increasing thereafter. Figure 5 shows this dominant unimodal behavior under both constraints. When efc is small, the graph is poorly connected, so the boundary efs is unfavorable: Recall constraints require large efs, while QPS constraints force small efs and sacrifice Recall. Increasing efc enlarges the construction-time candidate pool and improves graph navigability, allowing the constraint to be met more efficiently and raising the objective. Beyond the peak, additional candidates become increasingly redundant under Select-Neighbors and the fixed degree cap M, while traversal overhead continues to grow. The objective therefore shifts from a quality-improving regime to an overhead-dominated regime. Lemma 3.1 (Sufficient condition for unimodality over efc). Fix M and an active constraint 𝐶 ∈ {Recall, QPS}. On the ordered grid 𝑒 𝑓 𝑐 1 < · · · < 𝑒 𝑓 𝑐𝑛 , write the marginal change as Δ𝑓𝑀 (𝑒 𝑓 𝑐𝑖 ) = Δ𝐵𝑀 (𝑒 𝑓 𝑐𝑖 ) − Δ𝑇𝑀 (𝑒 𝑓 𝑐𝑖 ), where Δ𝐵𝑀 is the marginal graph-quality benefit and Δ𝑇𝑀 is the residual traversal/search cost. Any reduction in expanded nodes from better graph navigability is counted in Δ𝐵𝑀 , not as negative cost. If (i) Δ𝑇𝑀 (𝑒 𝑓 𝑐𝑖 ) ≥ 0 for all 𝑖, and (ii) once Δ𝐵𝑀 (𝑒 𝑓 𝑐𝑖 ) ≤ Δ𝑇𝑀 (𝑒 𝑓 𝑐𝑖 ), larger efc values do not reveal a delayed high-utility connectivity regime that restores Δ𝐵𝑀 > Δ𝑇𝑀 , then 𝑓𝑀 (𝑒 𝑓 𝑐) is unimodal. Proof. Due to space limitations, we defer the proof sketch to Appendix B.2. Lemma 3.1 is sufficient, not universal. It captures the standard HNSW regime targeted by CHAT: bounded degree, diversificationbased pruning, and no delayed high-utility connectivity regime.

600

efc

800

1000

50M

M = 64

40M 30M 20M

200

400

(a)

600

800

efc

1000

(b)

Figure 6: Graph quality and realized edge growth across different M values. (a) Recall as a function of efc, showing that larger M values reach high graph quality with smaller efc. (b) Number of edges as a function of efc, showing saturation in realized connectivity under fixed degree caps. efc*M

QPS (Recall Constraint = 0.95) 1000 800

4000

1000

3800

800

3600 3400

600 400 20

(a) efc*M and QPS vs M

Recall (QPS Constraint = 10,000)

600

3200

400

3000

200

0.92 0.91 0.90 0.89 0.88 0.87 0.86

Recall

250

6000

Recall

140

0.916

efs Recall

6200

Recall (QPS Constraint = 10,000)

0.918

efc*M

300

QPS efc*M

efs

QPS (Recall Constraint = 0.95)

efs

6400

Choi et al.

Number of Edges

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA, USA

(b) efc*M and Recall vs M

Figure 7: Optimized efc and objective performance across ∗ and resulting QPS versus M under varying M values. (a) 𝑒 𝑓 𝑐 𝑀 ∗ and resulting Recall versus M a Recall constraint. (b) 𝑒 𝑓 𝑐 𝑀 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-style procedure in Section 5.

3.4

Outer-Objective Unimodality over M

We next analyze how the best achievable objective changes as M varies. For each M, CHAT chooses the best construction effort, de∗ ∈ arg max noted 𝑒 𝑓 𝑐 𝑀 𝑒 𝑓 𝑐 𝐹𝐶 (𝑀, 𝑒 𝑓 𝑐), and the boundary efs satisfying the active performance constraint. Let 𝑔(𝑀) = max𝑒 𝑓 𝑐 𝐹𝐶 (𝑀, 𝑒 𝑓 𝑐) denote the resulting outer objective: QPS under a Recall constraint and Recall under a QPS constraint. We call 𝑔(𝑀) unimodal if it is non-decreasing up to some peak index and non-increasing thereafter. ∗ generally decreases as M increases. Figure 6 explains why 𝑒 𝑓 𝑐 𝑀 When M is small, each node can retain only a limited number of neighbors, so larger efc is useful for exposing high-quality and diverse candidate edges. When M is larger, the graph can already retain more useful routing alternatives, so similar navigability can be achieved with a smaller construction-time candidate pool. Figure 6(b) confirms this substitution effect: realized edges saturate quickly under tight degree caps, while larger M allows the graph to keep growing as larger efc exposes more useful candidates. Thus, M and efc act as partial substitutes for graph quality, explaining the ∗ . dominant decreasing trend of 𝑒 𝑓 𝑐 𝑀 Figure 7 shows the resulting outer objective. Under a Recall constraint, small M produces poor connectivity, so the Recall target requires a large boundary efs and suppresses QPS. Increasing M

Lemma 3.2 (Sufficient condition for outer-objective unimodality over M). Fix an active constraint 𝐶 ∈ {Recall, QPS}. On the ordered grid 𝑀1 < · · · < 𝑀𝑛 , write the marginal change as Δ𝑔(𝑀𝑖 ) = Δ𝐵 out (𝑀𝑖 ) − Δ𝑇out (𝑀𝑖 ), where Δ𝐵 out is the marginal graph-quality benefit from increasing M with efc re-optimized at each M, and Δ𝑇out is the residual traversal/search cost. Any reduction in expanded nodes from better graph navigability is counted in Δ𝐵 out , not as negative cost. If (i) Δ𝑇out (𝑀𝑖 ) ≥ 0 for all 𝑖, (ii) once Δ𝐵 out (𝑀𝑖 ) ≤ Δ𝑇out (𝑀𝑖 ), larger M values do not reveal a delayed high-utility connectivity regime that restores Δ𝐵 out > Δ𝑇out , and (iii) re-optimizing efc at larger M does not create a new high-performing branch, i.e., M and efc remain partial substitutes for graph quality, then 𝑔(𝑀) is unimodal over the ordered M grid. Proof. Due to space limitations, we defer the proof sketch to Appendix B.2. Lemma 3.2 is sufficient, not universal. In particular, Lemma 3.1 alone does not imply unimodality of the outer envelope 𝑔(𝑀); condition (iii) rules out recoveries caused by re-optimizing efc into a delayed high-utility regime at larger M. If these conditions fail, 𝑔(𝑀) may become bimodal or multi-modal, as discussed in Section 6.4. When they hold, the outer search over M can be performed efficiently using the ternary-style procedure in Section 5.

3.5

Structural Implications

Taken together, these observations reveal that the HNSW hyperparameter space is not an unstructured three-dimensional landscape. Instead, it forms a partially ordered search space with distinct structural properties: • efs induces a monotonic trade-off between recall and latency, enabling binary feasibility search. • M exhibits unimodal objective behavior under fixed constraints, enabling efficient ternary optimization. • efc acts as a feasibility gate that constrains construction-time resources. These properties fundamentally distinguish HNSW tuning from generic black-box optimization problems. They enable deterministic, low-sample optimization strategies that exploit algorithmic structure rather than relying on random exploration. While the precise curvature of these trade-offs varies across datasets and backends, the monotonic and unimodal structures consistently appear in standard HNSW implementations with bounded degree and greedy layer-wise search. These structural properties also provide a lens for reasoning about how the optimal construction effort responds to corpus and workload updates, as discussed next.

Boundary tightens Harder

6500

6250 QPS

6250 6000 5750 5500

Boundary relaxes Easier

6500

200

400

600

800

6000 5750

old new

5500

1000

old new

200

400

efc 0.920 0.918 0.916 0.914 0.912 0.910

QPS tighter

old new

200

400

600

efc

600

800

1000

efc

Recall

QPS Constraint Recall

initially improves graph navigability and reduces the required efs, so QPS improves. At larger M, however, additional degree capacity provides diminishing graph-quality benefit while increasing neighbor processing per expanded node, shifting the objective to an overhead-dominated regime. Under a QPS constraint, the same trade-off appears in the opposite objective: increasing M initially improves Recall, but excessive degree forces a smaller boundary efs to preserve throughput, eventually reducing Recall. Both cases show a dominant unimodal trend in 𝑔(𝑀).

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA, USA

Recall Constraint QPS

Exploiting Structural Properties for Efficient Constraint-Aware HNSW Hyperparameter Tuning

800

1000

0.920 0.918 0.916 0.914 0.912 0.910

QPS relaxed

old new

200

400

600

800

1000

efc

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 change when the corpus or ∗ query distribution changes. Under a Recall constraint, efc𝑀 marks the transition between a quality-limited region—where increasing efc still substantially reduces the required efs—and a cost-limited region, where graph-quality gains have saturated. A change that ∗ tightens the Recall boundary 𝑒 𝑓 𝑠 Recall (𝑀, 𝑒 𝑓 𝑐) (the minimum efs satisfying the Recall target increases) expands the quality-limited ∗ toward larger efc; relaxing the boundary region and moves 𝑒 𝑓 𝑐 𝑀 ∗ shifts 𝑒 𝑓 𝑐 𝑀 in the opposite direction. Under a QPS constraint, tight∗ (𝑀, 𝑒 𝑓 𝑐) (the maximum feasible efs deening the boundary 𝑒 𝑓 𝑠 QPS creases) makes high-efc configurations cost-dominated earlier, so ∗ moves leftward; relaxing it shifts 𝑒 𝑓 𝑐 ∗ rightward. 𝑒 𝑓 𝑐𝑀 𝑀 Figure 8 summarizes these directional effects. Insertions, deletions, and query-distribution shifts can each tighten or relax the active boundary depending on their net effect; the change type alone therefore does not determine the direction of movement. These directions should be understood as typical structural behaviors rather than universal guarantees, especially under near-duplicate insertions, targeted deletions, or strong query distribution shifts.

Relationship between Hyperparameters and HNSW Resources

This section characterizes how the HNSW construction hyperparameters (𝑀, efc) affect build time and index size. We separate the algorithmic dependence induced by Insert, Search-Layer, and Select-Neighbors from backend-specific constants, treating 𝑁 and 𝑑 as fixed workload parameters. The goal is not to introduce a new objective, but to identify structural resource dependencies that enable feasibility-aware pruning. Unless otherwise specified, measurements use the same experimental setup as Section 3.

200 100 0

200

400

600

efc

800

1000

100 80 60 40 20 0

efc = 144 sift gist

320

640

200 100 0

(a)

100 80 60 40 20 0

200

400

600

efc

(a)

Index Construction Time

HNSW constructs the index by inserting points sequentially. For a 𝑁 , the total build time decomposes over insertions: dataset 𝐷 = {𝑥𝑖 }𝑖=1 𝑇build (𝑁 , 𝑀, efc, 𝑑) =

𝑁 ∑︁

𝑇ins (𝑖; 𝑀, efc, 𝑑).

(1)

𝑖=1

Each insertion descends from the top layer to layer 0, performs Search-Layer to identify candidate neighbors at each visited layer, and then applies Select-Neighbors to finalize outgoing edges. Let 𝐿𝑖 denote the maximum layer of the 𝑖-th inserted point. The insertion cost can be decomposed as 𝑇ins (𝑖; 𝑀, efc, 𝑑) =

1.0M 0.9M 0.8M 0.7M 0.6M

efc = 96

800

1000

1.0M 0.9M 0.8M 0.7M 0.6M 0.5M

192

512

1024

(b)

Figure 9: Build time and realized connectivity of HNSW as functions of the construction hyperparameters (𝑴, efc). Index construction time (left y-axis) and average out-degree (AOD; right y-axis) are shown. (a) For fixed 𝑴, both build time and AOD increase monotonically with efc. (b) For fixed efc, build time grows sublinearly in 𝑀, while AOD saturates as 𝑴 increases.

4.1

M = 16

1024

300

Index Size

Build Time

Choi et al.

Average Out-Degree

M = 16 sift gist

300

Average Out-Degree Build Time

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA, USA

𝐿𝑖 ∑︁ ℓ=0

𝑇search (𝑖, ℓ; 𝑀, efc, 𝑑) +

𝐿𝑖 ∑︁

𝑇select (𝑖, ℓ; 𝑀, 𝑑).

ℓ=0

(2) Search-cost accounting. The dominant cost in SEARCH-LAYER comes from graph exploration: the algorithm expands candidate nodes, inspects their adjacency lists, and evaluates previously unseen candidates. Let 𝑋𝑖,ℓ (𝑀, efc) denote the number of expanded nodes when inserting point 𝑖 at layer ℓ, and let 𝛿¯𝑖,ℓ (𝑀, efc) denote the average realized out-degree inspected per expansion. The dominant search cost can then be summarized as 𝑇search (𝑖, ℓ; 𝑀, efc, 𝑑) ≈ 𝑐𝑑 𝑋𝑖,ℓ (𝑀, efc)𝛿¯𝑖,ℓ (𝑀, efc) + 𝐶 impl,

Figure 10: Index size dependence on construction hyperparameters. Index size as a function of (𝑀, efc). (a) For a fixed 𝑀, index size is largely insensitive to efc. (b) For a fixed efc, index size increases approximately linearly with 𝑀, and curves for different efc largely overlap. expansion term 𝑋𝑖,ℓ (𝑀, efc), explaining the build-time increase observed in Figure 9(a). A broader construction search can also expose SELECT-NEIGHBORS to more candidate neighbors, which explains the accompanying increase in realized connectivity. Saturation effects with increasing 𝑀. The parameter 𝑀 sets the per-layer degree cap up to a constant-factor difference at layer 0. To quantify realized connectivity, we define the average out-degree across the HNSW layer hierarchy as Í Í (ℓ ) ℓ 𝑣 ∈𝑉 (ℓ ) deg (𝑣) AOD(𝑀, efc) = . (4) Í (ℓ ) | ℓ |𝑉 AOD is the realized counterpart of the degree cap: it measures how many neighbors are retained after diversification and re-pruning. Although the degree cap grows with 𝑀, realized AOD need not grow linearly. HNSW’s neighbor selection procedure favors diverse neighbors and may reject redundant candidates even when the cap increases; when existing neighborhoods exceed their degree limits, the same pruning logic is applied again. As a result, increasing 𝑀 yields diminishing marginal increases in realized connectivity. In Equation (3), this means that 𝛿¯𝑖,ℓ (𝑀, efc) grows sublinearly with the cap, which is consistent with the build-time saturation observed in Figure 9(b). Overall, HNSW construction induces a separable resource dependence: efc primarily governs the breadth of construction search, while 𝑀 controls per-expansion connectivity through the realized graph degree. Section 5.4 instantiates this structure as a compact build-time feasibility estimator.

(3)

where 𝑐𝑑 captures the cost of candidate inspection and distance evaluation for a fixed 𝑑-dimensional workload, and 𝐶 impl absorbs backend-specific bookkeeping overheads. This accounting abstracts away implementation constants. In particular, implementations that maintain visited sets may avoid repeated distance computations for the same node, so adjacency inspection and distance evaluation need not be in one-to-one correspondence. The structural dependence is nevertheless unchanged: efc primarily controls the expansion term, whereas 𝑀 controls the degree cap that bounds the realized-degree term. Role of efc. The construction parameter efc bounds the candidate set maintained by SEARCH-LAYER and therefore controls the breadth of graph exploration during insertion. Increasing efc allows the search to retain more candidates and expand more nodes before termination. In Equation (3), this primarily increases the

4.2

Index Size

For fixed 𝑁 and 𝑑, vector storage and metadata are constant over (𝑀, efc); the hyperparameter-dependent term is adjacency storage. Since HNSW stores 𝑂 (𝑀) outgoing edges for an expected 𝑂 (𝑁 ) node copies across layers, the dominant index-size dependence is 𝑆 index (𝑁 , 𝑀) = 𝐶 fixed (𝑁 , 𝑑) + Θ(𝑁 𝑀),

(5)

where 𝐶 fixed (𝑁 , 𝑑) includes vector storage and fixed metadata. Backendspecific choices such as memory layout, alignment, and auxiliary bookkeeping change the constants, but not the qualitative dependence on (𝑀, efc). The construction parameter efc does not appear in Equation (5) because it changes the search budget used during construction, not the degree cap that determines adjacency capacity. A larger efc may affect which neighbors are selected, and can therefore slightly

Exploiting Structural Properties for Efficient Constraint-Aware HNSW Hyperparameter Tuning

change realized connectivity, but it does not change the dominant storage budget induced by 𝑀. Thus, unlike build time, index size is governed primarily by the degree-cap-induced adjacency storage rather than by the amount of construction search. This explains why index size remains largely invariant to efc in Figure 10(a), while increasing approximately linearly with 𝑀 in Figure 10(b).

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA, USA

Constraints (Recall, QPS / Build Time, Index Size / Tuning Time) 1

Efficient Constraint-Aware Hyperparameter Optimization

This section presents CHAT, a constraint-aware framework for tuning HNSW hyperparameters. Given user constraints on search quality, search efficiency, resource usage, and tuning time, CHAT seeks the configuration (𝑀, 𝑒 𝑓 𝑐, 𝑒 𝑓 𝑠) that maximizes the target objective while satisfying these constraints. CHAT combines three ideas: it decomposes HNSW tuning into structured subproblems, exploits the monotonicity and dominant unimodality analyzed in Section 3, and filters resource-infeasible configurations using the models in Section 4. CHAT is API-level black-box but HNSW-structure-aware. It uses only standard build/query APIs and validation-workload measurements, including Recall, QPS, build time, and index size, without inspecting adjacency lists, layer populations, or degree distributions. However, it is not ANN-agnostic: its search decomposition relies on public HNSW mechanisms, namely bounded-degree construction controlled by M, greedy layer-wise Search-Layer, and diversification-based Select-Neighbors. We therefore scope its structural claims to standard CPU HNSW implementations that preserve these semantics, including Faiss [22], Hnswlib [31], and Milvus [41]. These assumptions may weaken for variants with different neighbor selection, disk- or GPU-dominated bottlenecks, or dynamic graph maintenance. They also do not automatically transfer to non-HNSW families such as IVF+PQ [23], ScaNN [15], or NSG [9].

5.1

System Overview

This subsection outlines the end-to-end tuning workflow of CHAT. Figure 11 illustrates the system architecture and the iterative interaction among its core components. The workflow begins when 1 the user specifies a target dataset, an HNSW-based vector database

Final Optimal

Hyperparameter

(M, efc, efs)

candidate (M, efc) if not feasible 3 -1

shrink

M, efc range

Search Engine

for efs

Feasibility-Aware Tuning Implications

The analysis above yields three structural properties of HNSW resource usage: • construction time increases with the search budget efc. • construction time grows sublinearly with 𝑀 because realized connectivity saturates under neighbor selection and pruning. • index size scales approximately linearly with 𝑀 and is largely independent of efc. These separable dependencies allow infeasible regions of the hyperparameter space to be identified without constructing every candidate index. Build-time constraints can be evaluated using the dependence of search breadth on efc and realized connectivity on 𝑀, while index-size constraints can be evaluated primarily from 𝑀. Section 5.4 uses these structural properties to construct compact feasibility estimators, and Section 5 applies them to prune resourceviolating configurations before expensive index construction.

Search Engine

for (M, efc)

4.3

CHAT

Search Engines

shrink

calibration

efs range

identify

index

efs

(M, efc)

CHAT Search Engine

Constraint Model

Resource

Constraint

Model

performance

Input Constraints CHAT Final Output

3 -2 if feasible

optimized

External Components

build index

IF Statement Feedback Loop

(M, efc)

VectorDB

Figure 11: The overall architecture and iterative tuning workflow of CHAT. backend, and a set of constraints, including performance requirements (e.g., minimum Recall or QPS), resource limits on build time and index size, and a total tuning-time budget. These inputs jointly define the optimization objective and the feasible search space. 2 Guided by the user inputs, the Search Engine for (M, efc) proposes a candidate construction configuration (M, efc). This component orchestrates the outer loop of the tuning process, exploring the structural parameter space. 3 The proposed candidate is immediately evaluated by the Resource Constraint Models, which predicts whether the configuration is likely to satisfy the specified resource constraints using learned cost models. If the candidate is predicted to be infeasible, 3 -1 the search engine receives feedback to prune the corresponding region of the search space without incurring actual build costs. Otherwise, 3 -2 the system proceeds to construct an HNSW index on the target backend using the candidate (M, efc). 4 Once the index is built, the Search Engine for efs takes over to identify the optimal efs value that maximizes the objective performance while adhering to the performance constraint. 5 The measured performance and resource usage are used to calibrate the resource constraint models, thereby shrinking the search space in subsequent iterations. Finally, 6 once the tuning budget is exhausted or the search converges, CHAT reports the final optimal hyperparameter configuration (𝑀, efc, efs). Through this iterative process, CHAT efficiently converges to a near-optimal configuration. When the indexed corpus or query workload subsequently changes, CHAT reuses the same history as a cross-run warm start, as detailed in Section 5.5.

5.2

Search for Optimal Construction Configuration

CHAT searches the construction parameters using a nested but simple strategy. For each probed M, it searches for a promising efc, skips candidates that are model-infeasible under the resource budgets, builds only the remaining candidates, and then selects efs by boundary search on the built index. Thus, the original threedimensional tuning problem is reduced to three one-dimensional decisions: localizing a good M region, selecting the best efc for that M, and choosing the boundary efs that satisfies the active performance constraint. We write 𝑔(𝑀) for the best validated objective value returned after optimizing efc and efs under a fixed M; formally,

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA, USA

Choi et al.

Algorithm 1 Search Engine for (M,efc)

Algorithm 3 Optimize-EFS

Input: Dataset D ; HNSW backend V ; performance constraint Cperf ; resource constraints Cres ; tuning budget T Output: Best validated configuration 𝑏𝑒𝑠𝑡𝐶 𝑓 𝑔 = ( M ,efc,efs ) 1: Initialize resource models ℎˆ𝑏𝑡 , ℎˆ𝑖𝑠 and history H ← ∅ 2: Initialize domains M ← [4, 64] , E𝑐 ← [8, 1024] 3: 𝑏𝑒𝑠𝑡𝐶 𝑓 𝑔 ← ⊥, 𝑏𝑒𝑠𝑡𝑃𝑒𝑟 𝑓 ← −∞ 4: while remaining tuning time > 0 and M not converged do 5: Choose ternary probes M 1 ,M 2 ∈ M 6: for M ∈ { M 1 ,M 2 } do 7: (𝑝𝑒𝑟 𝑓𝑀 , 𝑐 𝑓 𝑔𝑀 ) ← Optimize-EFC ( M , E𝑐 , D, V, Cperf , Cres , T, ℎˆ𝑏𝑡 , ℎˆ𝑖𝑠 , H) 8: if 𝑝𝑒𝑟 𝑓𝑀 > 𝑏𝑒𝑠𝑡𝑃𝑒𝑟 𝑓 then 9: 𝑏𝑒𝑠𝑡𝑃𝑒𝑟 𝑓 ← 𝑝𝑒𝑟 𝑓𝑀 ; 𝑏𝑒𝑠𝑡𝐶 𝑓 𝑔 ← 𝑐 𝑓 𝑔𝑀 10: end if 11: end for 12: Update M toward the probe with higher validated performance 13: end while 14: return 𝑏𝑒𝑠𝑡𝐶 𝑓 𝑔

Input: Pre-built index 𝐼 ( M ,efc ) ; performance constraint Cperf ; history H Output: Boundary value efs∗ and measured objective 𝑝𝑒𝑟 𝑓 1: [𝑒 𝑓 𝑠 min , 𝑒 𝑓 𝑠 max ] ← shrink interval using H // history-based interval 2: if Cperf is 𝑅𝑒𝑐𝑎𝑙𝑙 ≥ 𝑅𝑒𝑐𝑎𝑙𝑙 min then 3: efs∗ , 𝑝𝑒𝑟 𝑓 ← BSearchMinFeasibleEFS (𝐼, [𝑒 𝑓 𝑠 min , 𝑒 𝑓 𝑠 max ], 𝑅𝑒𝑐𝑎𝑙𝑙 min ) 4: else if Cperf is 𝑄𝑃𝑆 ≥ 𝑄𝑃𝑆 min then 5: efs∗ , 𝑝𝑒𝑟 𝑓 ← BSearchMaxFeasibleEFS (𝐼, [𝑒 𝑓 𝑠 min , 𝑒 𝑓 𝑠 max ], 𝑄𝑃𝑆 min ) 6: end if 7: if no feasible efs exists then 8: return (⊥, −∞) 9: end if 10: return ( efs∗ , 𝑝𝑒𝑟 𝑓 )

Algorithm 2 Optimize-EFC Input: Fixed M; efc domain E𝑐 ; dataset D ; backend V ; performance constraint Cperf ; resource constraints Cres ; tuning budget T ; models ℎˆ𝑏𝑡 , ℎˆ𝑖𝑠 ; history H Output: Best validated score 𝑔 (𝑀 ) and configuration 𝑐 𝑓 𝑔𝑀 1: Shrink E𝑐 using history H 2: 𝑔 (𝑀 ) ← −∞, 𝑐 𝑓 𝑔𝑀 ← ⊥ 3: while remaining tuning time > 0 and E𝑐 not converged do 4: Choose ternary probes efc 1 ,efc 2 ∈ E𝑐 5: for efc ∈ { efc 1 ,efc 2 } do 6: if ℎˆ𝑏𝑡 ( M ,efc ) or ℎˆ𝑖𝑠 ( M ) violates Cres then 7: Record model-infeasibility in H ; continue 8: end if 9: 𝐼 ← BuildIndex ( V, D,M ,efc ) 10: Measure build time and index size; update ℎˆ𝑏𝑡 , ℎˆ𝑖𝑠 11: if measured resource usage violates Cres then 12: Record measured infeasibility in H ; continue 13: end if 14: ( efs∗ , 𝑝𝑒𝑟 𝑓 ) ← Optimize-EFS (𝐼, Cperf , H) 15: if efs∗ = ⊥ then 16: Record performance infeasibility in H ; continue 17: end if 18: Record ( M ,efc,efs∗ , 𝑝𝑒𝑟 𝑓 ) in H 19: if 𝑝𝑒𝑟 𝑓 > 𝑔 (𝑀 ) then 20: 𝑔 (𝑀 ) ← 𝑝𝑒𝑟 𝑓 ; 𝑐 𝑓 𝑔𝑀 ← ( M ,efc,efs∗ ) 21: end if 22: end for 23: Update E𝑐 toward the probe with higher validated performance 24: end while 25: return (𝑔 (𝑀 ), 𝑐 𝑓 𝑔𝑀 )

𝑔(𝑀) = max𝑒 𝑓 𝑐 perf(𝑀, 𝑒 𝑓 𝑐, 𝑒 𝑓 𝑠 ∗ (𝑀, 𝑒 𝑓 𝑐)) over configurations feasible under Cperf and Cres . Algorithm 1 implements the outer search over M. Each probed M is evaluated by Optimize-EFC, which returns the best measured feasible triplet found for that M. The outer loop then shrinks the M interval toward the probe with higher validated performance, following the dominant unimodal trend of 𝑔(𝑀) analyzed in Section 3.4. The best measured feasible configuration is tracked throughout the search, so CHAT can return a validated configuration even if the tuning budget expires before the intervals fully converge. Algorithm 2 performs the inner search over efc for a fixed M. Before ternary search, CHAT uses prior optima in H to narrow the candidate range: larger M values typically need smaller construction effort because additional degree capacity already improves graph connectivity. This rule only reduces the search range; the final choice is still made using measured resource feasibility and validation performance.

The resource models and validation measurements play different roles. The models are used only to avoid unnecessary index builds under the conservative resource test. Candidates that pass this filter are still built, measured for build time and index size, and then evaluated by Optimize-EFS. Thus, early pruning reduces tuning cost, while the reported configuration is selected only from configurations explicitly validated against the user constraints.

5.3

Search for Optimal efs

Given a fixed constructed index 𝐼 (M,efc), CHAT only needs to tune the search-time parameter efs. Unlike M and efc, changing efs does not alter the graph, so all probes reuse the same built index. As analyzed in Section 3.1, efs induces an ordered feasibility boundary: larger efs broadens base-layer traversal, improving Recall but increasing query cost. CHAT therefore finds the boundary efs by binary search rather than by rebuilding or re-exploring construction parameters. Algorithm 3 handles the two main performance constraints symmetrically. Under a Recall constraint, CHAT returns the smallest feasible efs, which maximizes QPS while meeting the Recall target. Under a QPS constraint, it returns the largest feasible efs, which maximizes Recall while meeting the throughput target. The resulting pair (efs∗, 𝑝𝑒𝑟 𝑓 ) is returned to Optimize-EFC and used to compare candidate construction settings. The initial search interval is tightened using previous boundary values stored in H . Intuitively, stronger construction settings often require no larger efs to satisfy the same performance constraint, because better graph connectivity reduces the query-time exploration needed for Recall and can also tighten the QPS-feasible upper bound. Formally, for a prior configuration (𝑀 ′, 𝑒 𝑓 𝑐 ′ ) with boundary ∗ ′ ′ ∗ ∗ value efs𝑀 ′ ,𝑒 𝑓 𝑐 ′ , if 𝑀 ≥ 𝑀 and 𝑒 𝑓 𝑐 ≥ 𝑒 𝑓 𝑐, then efs𝑀,𝑒 𝑓 𝑐 ≥efs𝑀 ′ ,𝑒 𝑓 𝑐 ′ ; reversing both inequalities gives the corresponding upper bound. CHAT uses this history only to reduce the number of probes; the returned efs is still selected by measured feasibility on the current index. Thus, history accelerates binary search but does not replace validation. The same boundary-search view supports query-subset constraints. For example, a deployment may require both average Recall and hard-query Recall: Recall(𝑄 all ) ≥ 𝜌 all and Recall(𝑄 hard ) ≥ 𝜌 hard . Because Recall on any fixed query subset is monotone in efs, the conjunction remains a monotone predicate and can be handled by the same binary search. We identify 𝑄 hard using Steiner-hardness [44]. Tail-latency constraints can be handled analogously. For a fixed index and validation workload, CHAT measures the requested tail

Exploiting Structural Properties for Efficient Constraint-Aware HNSW Hyperparameter Tuning

metric, such as P95 or P99 latency, at each probed efs. Because increasing efs only enlarges the Search-Layer candidate budget, the permitted traversal work is monotone non-decreasing in efs; consequently, a fixed-workload latency quantile defines an upperbound feasibility predicate up to measurement noise. A service-level constraint such as P𝛼 (Latency) ≤ 𝜏𝛼 is therefore handled using the same max-feasible binary search as 𝑄𝑃𝑆 ≥ 𝑄𝑃𝑆 min , returning the largest efs whose measured tail latency satisfies the constraint. If Recall lower bounds and tail-latency upper bounds are specified together, the feasible efs values form an interval, provided that the minimum Recall-feasible efs does not exceed the maximum latencyfeasible efs. The selected point in this interval depends on the active objective.

5.4

Verifying Resource Constraints Satisfaction

Efficient hyperparameter tuning requires an early mechanism to rule out configurations that violate user-specified resource budgets. Performance feasibility (QPS/Recall) is evaluated during search on a fixed index (Section 3 and Algorithm 3). This subsection addresses resource feasibility. Build time and index size budgets cannot be verified for every candidate (𝑀, efc) by fully constructing an index, as doing so would dominate tuning cost. We therefore employ a lightweight resource-feasibility filter that instantiates the algorithmdriven dependencies derived in Section 4 into closed-form surrogates and continuously calibrates their remaining constants using measurements obtained during the search process. 5.4.1 Closed-form Instantiation. Section 4 establishes two structural properties. First, build time is governed by a search-breadth component controlled by efc and a per-expansion scan component governed by realized out-degree, whose marginal growth in 𝑀 saturates due to neighbor diversification and pruning. Second, index size is dominated by the cap-induced adjacency capacity and therefore scales linearly with 𝑀 while remaining invariant to efc. We instantiate these dependencies using compact parametric surrogates that preserve monotonicity and saturation while leaving scale and offset to be determined by calibration. We use two resource surrogates: ℎ bt (𝑀, efc) for build time and ℎ is (𝑀) for index size. For build time, we adopt a log-like surrogate in 𝑀 to represent saturating realized connectivity, while retaining an explicit dependence on efc to capture increased exploration: ℎ bt (𝑀, efc) = 𝛼 0 +𝛼 1 efc+(𝛽 0 +𝛽 1 efc)·log2 (1+𝑀)+𝛾 efc·log22 (1+𝑀). (6) The linear term in efc captures the monotone increase in construction search budget (Figure 9(a)). The log2 (1 + 𝑀) terms represent a representative monotone concave dependence on 𝑀, consistent with the saturation of realized out-degree observed empirically (Figure 9(b)). Logarithmic growth is a convenient member of a broader class of concave monotone functions consistent with the algorithmic upper bounds derived in Section 4.1; it preserves sublinear growth while remaining analytically simple and stable under incremental calibration from a limited number of observations. The interaction term efc log22 (1 + 𝑀) captures that higher connectivity increases the number of candidate evaluations performed per unit of exploration during construction.

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA, USA

For index size, Section 4.2 implies a linear dependence on 𝑀 and no dependence on efc: ℎ is (𝑀) = 𝜂 0 + 𝜂 1 𝑀.

(7)

Although efc may influence realized connectivity (Figure 9(a)), it does not affect the cap-induced adjacency budget that dominates index size (Figure 10); accordingly, efc is excluded from ℎ is . 5.4.2 Online Calibration from Search-time Measurements. The functional forms in (6) and (7) are fixed by the algorithmic structure; only their scale and offset parameters are backend-dependent. These parameters are calibrated using all configurations that are actually constructed during the search process. Whenever the search engine builds an index to evaluate performance feasibility, the resulting build time and index size are recorded and incorporated into calibration. Let C denote the set of configurations (𝑀 𝑗 , efc 𝑗 ) that have been constructed so far during search, with measured build times 𝑇 𝑗 and index sizes 𝑆 𝑗 . Define the feature maps 𝜙 bt (𝑀, efc) = 1, efc, log2 (1+𝑀), efc log2 (1+𝑀), efc log22 (1+𝑀) , (8) 𝜙 is (𝑀) = [1, 𝑀]. (9) The surrogate parameters are obtained by solving linear leastsquares problems over C: ℎ bt = ⟨𝜃 bt, 𝜙 bt ⟩,

ℎ is = ⟨𝜃 is, 𝜙 is ⟩,

(10)

where 𝜃 bt = (𝛼 0, 𝛼 1, 𝛽 0, 𝛽 1, 𝛾) and 𝜃 is = (𝜂 0, 𝜂 1 ). Because calibration is linear in the number of accumulated measurements, its overhead is negligible relative to index construction. As search progresses, the calibration set C naturally expands to cover a wider range of (𝑀, efc) values, including regions where saturation in 𝑀 becomes apparent. This incremental calibration improves alignment between the surrogates and backend-specific constants without altering the surrogate structure. 5.4.3 Conservative Feasibility Test. Let 𝑇max and 𝑆 max denote userspecified budgets for build time and index size. To avoid accepting configurations whose resource usage is underestimated by the calibrated surrogates, CHAT applies one-sided safety margins to the build-time and index-size estimates. Each margin is computed from the positive relative underestimation residuals observed on constructed configurations in C and is recomputed whenever C grows. A candidate is pruned before construction only when the marginadjusted build time or index size estimate exceeds the corresponding budget. This is a conservative false-feasible guard, not a deterministic no-pruning guarantee; larger margins reduce false-feasible risk at the cost of pruning aggressiveness.

5.5

Drift-Aware Retuning

CHAT supports retuning when the indexed corpus or query workload changes after an initial tuning run. Rather than restarting from scratch, it reuses the previous tuning history H as a cross-run warm start. The system refreshes the validation workload using recent queries and the current corpus, monitors Recall, QPS, and the efs feasibility boundary, and first reruns only Optimize-Efs at the previous (M,efc). Construction retuning is invoked only when

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA, USA

the deployed configuration becomes infeasible or when changing efs alone is insufficient. When construction retuning is needed, CHAT applies ConstraintDirected Hard Pruning with Sentinel Safety (CDHP). CDHP uses the feasibility-boundary shift in Section 3.6 to predict the movement ∗ . Under a Recall constraint, a of the best construction effort 𝑒 𝑓 𝑐 𝑀 tighter boundary, i.e., a larger minimum efs to reach the Recall target, indicates that graph quality has become more important and suggests moving toward larger efc. Under a QPS constraint, a tighter boundary, i.e., a smaller maximum feasible efs, makes high-efc configurations cost-dominated earlier and suggests moving toward smaller efc. Relaxed boundaries induce the opposite directions. Guided by this signal, CDHP keeps only the corresponding one∗,𝑜𝑙𝑑 sided construction region: efc ≥ 𝑒 𝑓 𝑐 𝑀 for a rightward move ∗,𝑜𝑙𝑑 and efc ≤ 𝑒 𝑓 𝑐 𝑀 for a leftward move. For unseen M values, the ∗ . CHAT then cutoff is inferred from the historical envelope of 𝑒 𝑓 𝑐 𝑀 runs the standard Optimize-Efc and Optimize-Efs procedures within the retained domain, with the same resource filtering as in the initial run. Since the boundary-shift signal is structural rather than universal, CDHP places sentinel probes on the pruned side and expands the cached search domain if a sentinel is competitive within measurement tolerance; in the worst case, it completes the remaining search domain using cached measurements rather than restarting from scratch. For deletions, CHAT first cleanly rebuilds the updated corpus using the previous (M,efc) to distinguish inplace deletion artifacts from true hyperparameter drift.

6 Experiments 6.1 Experimental Setup We evaluated CHAT across multiple vector database backends, datasets, baselines, and metrics. We used Hnswlib [31] and Faiss [22] as reference HNSW implementations, as they expose the core behavior of HNSW with minimal system-level optimizations, allowing us to isolate the intrinsic performance characteristics analyzed in Section 3. To assess real-world applicability, we additionally evaluated CHAT on Milvus [41], a production-grade vector database that uses HNSW internally. Across all platforms, we varied three hyperparameters: the maximum node degree 𝑀 ∈ [4, 64], the construction candidate size efc ∈ [8, 1024], and the search candidate size efs ∈ [10, 1024]. We benchmarked CHAT on five representative datasets. Four of them—nytimes, glove, sift, and deep1M—were standard public datasets provided by ANN-Benchmarks [2], widely adopted for evaluating approximate nearest neighbor search (ANNS) algorithms. In addition, we constructed the youtube dataset [7], a realistic video retrieval workload built by encoding extracted I-frames from public high-view-count YouTube videos with OpenCLIP H-14 [19], providing a diverse and complementary evaluation point. The characteristics of all datasets are summarized in Appendix C, which further details the youtube construction pipeline, including the data source, frame extraction, and embedding model . As comparison baselines, we considered a diverse set of black-box hyperparameter tuning methods, covering model-free search, sequential model-based optimization, evolutionary multi-objective search, constrained Bayesian optimization, and vector-database tuning. We included Random Search [4] and Grid Search [27], which

Choi et al.

respectively sample configurations uniformly and enumerate a predefined grid; both enforce constraints by discarding infeasible configurations. We also evaluated Optuna [1], a TPE-based sequential optimizer that proposes trials from past observations. In our implementation, Optuna handles constraints through a large-penalty scalar objective, assigning infeasible trials a penalty proportional to the degree of violation. NSGA-II [6] is a population-based evolutionary optimizer that uses Pareto dominance to balance objective value and constraint violation; we implement it as a bi-objective search that minimizes violation while maximizing the target metric. We additionally included Expected Constrained Improvement (ECI) [12], a Gaussian-process constrained Bayesian optimization method that models both objective and feasibility and selects configurations by feasibility-weighted expected improvement. We also compared against VDTuner [46], a Bayesian-optimization framework designed for vector database tuning, restricted to the same HNSW parameter space for fairness. All baselines are treated as black-box tuners that do not inspect internal HNSW graph statistics. A more detailed introduction to each baseline, together with its hyperparameter configurations and experimental settings, is provided in Appendix D. For evaluation, we measured Recall@10 and Queries Per Second (QPS) to assess search accuracy and throughput, respectively, and recorded build time and index size to capture index construction cost and memory footprint. All experiments were conducted on a single Ubuntu server with an AMD Ryzen Threadripper 3970X CPU (32 cores, 64 threads, 3.7 GHz), 188 GB RAM, and 14 GB swap, using CPU-only execution to reflect typical vector database deployments. To reduce runtime noise, each index configuration was built once and evaluated with the same query workload over 10 runs, reporting the average Recall and QPS.

6.2

Constraint-Aware Tuning Results

We evaluated the effectiveness of CHAT in identifying optimal HNSW hyperparameter configurations under user-specified performance constraints, using a common 4-hour wall-clock cap for all methods. We considered two performance constraints: (1) Recall ≥ 0.95, where QPS is maximized, and (2) QPS ≥ 𝜏, where Recall is maximized. CHAT always takes 𝜏 as a raw throughput target, e.g., QPS ≥ 5000; the 75th percentile is used only in our evaluation to choose comparably difficult targets across dataset-backend pairs. In practice, 𝜏 can come from a service SLO or a small pilot probe—a quick QPS measurement at minimal 𝑀, 𝑒 𝑓 𝑐, and 𝑒 𝑓 𝑠 values that estimates the high-throughput scale of the workload. Appendix E reports the raw QPS values used. To assess the effectiveness of our search strategy, we first compared CHAT against an Oracle (Exhaustive Search) that evaluates all valid hyperparameter configurations within the predefined search ranges under the same performance constraint, providing an upper bound on achievable performance. Despite this strong reference, CHAT achieved 98.03%–99.97% of the Oracle’s QPS (under the Recall constraint) and 99.11%–99.99% of the Oracle’s Recall (under the QPS constraint). These results show that CHAT identifies near-optimal configurations with only a fraction of the exhaustive search cost, quantifying a small optimality gap under strict tuning budgets.

Exploiting Structural Properties for Efficient Constraint-Aware HNSW Hyperparameter Tuning

CHAT (Our solution) nytimes

Hnswlib

3600

7200

10800

14400

3600

7200

10800

14400

3600

7200

10800

14400

3600

7200

10800

14400

Recall

0% 0 100% 95% 90% 80% 70%

Recall

Faiss

QPS

0% 0 100% 95% 90% 80% 70%

Time (seconds)

0% 0 100% 95% 90% 80% 70% 0% 0 100% 95% 90% 80% 70% 0% 0 100% 95% 90% 80% 70% 0%

VDTuner

glove

100% 95% 90% 80% 70%

QPS

100% 95% 90% 80% 70%

Oracle

ECI (GP) sift

100% 95% 90% 80% 70%

3600

7200

10800

14400

3600

7200

10800

14400

3600

7200

10800

14400

3600

7200

10800

14400

Time (seconds)

0% 0 100% 95% 90% 80% 70% 0% 0 100% 95% 90% 80% 70% 0% 0 100% 95% 90% 80% 70% 0%

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA, USA

Optuna

NSGA-II youtube

100% 95% 90% 80% 70%

3600

7200

10800

14400

3600

7200

10800

14400

3600

7200

10800

14400

3600

7200

10800

14400

Time (seconds)

0% 0 100% 95% 90% 80% 70% 0% 0 100% 95% 90% 80% 70% 0% 0 100% 95% 90% 80% 70% 0%

Random

Grid deep1M

100% 95% 90% 80% 70%

3600

7200

10800

14400

3600

7200

10800

14400

3600

7200

10800

14400

3600

7200

10800

14400

Time (seconds)

0% 0 100% 95% 90% 80% 70% 0% 0 100% 95% 90% 80% 70% 0% 0 100% 95% 90% 80% 70% 0%

3600

7200

10800

14400

3600

7200

10800

14400

3600

7200

10800

14400

3600

7200

10800

14400

Time (seconds)

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 constraint settings. Figure 12 summarizes the tuning performance of all methods by plotting the best objective values attained over time, normalized to the Oracle, across all datasets and constraint settings. In all cases, CHAT (shown in red) either converged to the best-performing configuration substantially faster than baseline methods or maintained superior objective performance throughout the tuning process. Under the Recall constraint (i.e., when maximizing QPS), CHAT outperformed all baseline methods by margins ranging from 1% to 45% (1% on the nytimes dataset with Hnswlib, and 45% on the youtube dataset with Hnswlib) in QPS. Under the QPS constraint (i.e., when maximizing Recall), CHAT again demonstrated strong performance, achieving Recall improvements of 0.6% to 11% (0.6% on the nytimes dataset with Faiss, and 11% on the glove dataset with Faiss) over the best baselines. CHAT converges quickly enough for practical deployment. Using the time to reach 95% of the Oracle objective as a convergence metric, CHAT is the only method to reach this threshold within the 4-hour cap in 13 out of 20 settings; in the remaining cases, it reaches the target 1.5×–44× faster than the best competing baseline. The 4-hour cap is an evaluation budget rather than the runtime of CHAT: across the 10 backend–dataset combinations (two HNSW backends, Faiss and hnswlib, evaluated on five datasets) under the Recall=0.95 constraint, CHAT reaches 99% of the Oracle objective in 48 minutes on average (range 13–123 minutes), consuming only 20% of the cap. Under a conservative no-serving-during-tuning break-even model, the mean break-even time is 3 hours and every backend–dataset combination recovers the tuning cost within 7 hours; over one week, the tuned configuration serves 0.25–2 billion additional queries per combination. Beyond average Recall and QPS, we also evaluate query-side SLOs supported by Optimize-EFS in Section 5.3. For hard-query Recall, we rank validation queries by Steiner-hardness and define Hard-20 as the hardest 20% of queries. Average-only tuning satisfies the

all-query Recall target but leaves Hard-20 Recall below 0.95 in nine of ten Faiss/Hnswlib settings. When Hard-20 Recall is added as an explicit constraint, CHAT satisfies both the all-query and Hard-20 Recall targets in all ten settings while achieving 98.21%–99.69% of the corresponding Oracle objective. For tail latency, we evaluate raw P95 and P99 latency upper-bound constraints. Across the same ten Faiss/Hnswlib settings, the structural properties exploited by CHAT continue to hold empirically under these query-side SLOs: the efs feasibility predicate remains monotone, and the fixed-M objective over efc and the outer objective over M continue to show dominant unimodal trends. Under the P95/P99 latency constraints, CHAT satisfies the requested tail-latency bounds while achieving 99.07%–99.99% of the corresponding Oracle objective. Why CHAT Outperforms. The superior performance and rapid convergence of CHAT stem from its structure-exploiting design. Unlike prior approaches (e.g., VDTuner, Optuna, ECI, NSGA-II, and Random/Grid Search), which treat HNSW tuning as a black-box optimization problem, CHAT explicitly leverages the monotonic and unimodal performance structure of HNSW. By decomposing the search space into sequential one-dimensional subproblems and applying deterministic binary and ternary search, CHAT progressively eliminates suboptimal regions and can identify when further exploration is unlikely to yield meaningful improvement, allowing it to terminate tuning early while still achieving near-optimal performance. Lightweight resource constraint models (Section 5.4) further enable pruning of infeasible regions without the overhead of full index construction. In contrast, baseline methods suffer from a fundamental mismatch between their optimization mechanisms and the structural properties of HNSW. Structure-agnostic approaches such as Grid and Random Search incur excessive or unguided exploration costs and provide no guarantees of convergence, making them unreliable

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA, USA

(a) Search Process Index Builds / Visited Configs Pruned Before Build Constraint-Violating Builds Feasibility Coverage (b) Search Results Total Search Time (s) Average Performance Gain Best Performance Gain Performance Preservation

Hnswlib

Faiss

Hnswlib

29.8 / 38.3 22.44% 4.0 / 10.5 0.9800

25.5 / 33.1 25.95% 4.0 / 10.4 0.9817

34.8 / 38.3 4.20% 2.9 / 9.7 0.9956

29.4 / 33.1 11.60% 2.4 / 9.3 0.9873

4791 / 6531 1.36 × 6.26 × 100.0%

5042 / 7557 1.50 × 5.21 × 100.0%

4787 / 6531 1.36 × 2.57 × 100.0%

5327 / 7557 1.42 × 2.32 × 100.0%

Table 1: Impact of analytic resource-constraint models on the tuning process. All values are reported as with constraint model / without constraint model. Resource-feasibility filtering substantially reduces unnecessary index constructions and total tuning time while fully preserving the final selected configuration. under tight tuning budgets when high-performing feasible configurations are sparse. Bayesian optimization–based methods, including Optuna, VDTuner, and ECI, rely on probabilistic modeling or surrogate-based feasibility estimation to localize the constraint boundary. However, in the discrete and sharply structured HNSW configuration space, learning this boundary stochastically requires expending a substantial portion of the tuning budget on exploration. Similarly, NSGA-II preserves population diversity to approximate a Pareto frontier across objectives, which inherently dilutes selection pressure toward the single constrained optimum required in our setting. As a result, although these methods are powerful general-purpose optimizers, they lack the domain-specific structural awareness needed to efficiently navigate feasibility boundaries in constraint-critical HNSW hyperparameter tuning.

6.3

No margin

Build Time Constraint

Faiss

Tuning under Resource Constraints

This section evaluates the effect of analytic resource constraint models on the tuning process. In contrast to Section 6.2, which compares tuning strategies under performance constraints (recall and QPS), this section isolates the contribution of the resourcefeasibility filter itself. The resource constraint model is treated as a black-box module that can be attached to any search strategy; evaluating it separately avoids biasing cross-baseline comparisons and allows its standalone impact to be assessed under identical tuning budgets. Table 1 summarizes the results under two resource constraints (index size and build time) and two HNSW backends (Faiss and Hnswlib). All values are reported as with constraint model / without constraint model and are averaged over the five datasets described in Section 6.1. Search Process Efficiency. Table 1(a) summarizes the tuning process. Index Builds / Visited Configs shows that resource-feasibility filtering substantially reduces the number of index constructions required to explore the same configuration space by pruning infeasible candidates prior to construction. This behavior is reflected in the Pruned Before Build rate (4.2%–26.0%) and the consistently lower number of Constraint-Violating Builds when constraint models are applied. The safety of early pruning is quantified by Feasibility Coverage, computed over all configurations visited during the search. Coverage exceeds 0.98 across all settings, indicating that the

Fixed (5/10/20%)

4 3 2 1 0 50

Pruning Rate (%)

(a) Build time

False-feasible Rate (%)

Index Size Constraint

Engine

False-feasible Rate (%)

Metric

Choi et al.

Residual (0.5/1.0/1.5/2.0×)

4 3 2 1 0 50

Pruning Rate (%)

(b) Index size

Figure 13: Safety-margin sensitivity under resource constraints. 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. Impact on Search Outcomes. As shown in Table 1(b), Total Search Time, which is dominated by index construction, is consistently lower when resource-feasibility filtering is enabled. This reduction is consistent with the decrease in index builds observed in Table 1(a), indicating that pruning infeasible configurations prior to construction is the primary source of the time savings. Despite the reduced exploration cost, the quality of the final tuning result is fully preserved. As shown in Table 1(b), Performance Preservation is 100% across all settings, indicating that the configuration selected with resource constraints achieves identical performance to that selected without constraints. Across all five datasets, Average Performance Gain remains stable in the range of 1.36×–1.50×, showing that feasibility filtering does not restrict access to competitive configurations. Figure 13 isolates the safety-margin mechanism by comparing no-margin, fixed-margin, and residual-based variants. No-margin pruning is more exposed to false-feasible decisions, while fixed margins require a hand-tuned conservatism level. Residual-based margins adapt to observed underestimation residuals, reducing false-feasible risk while maintaining high pruning rates. Together with the performance preservation and best-case gains in Table 1, this shows that resource-feasibility filtering lowers tuning cost without blocking high-performing configurations.

6.4

Robustness of Structural Trends and Measurements

CHAT uses ternary-style localization over measured objective values, but it does not assume convexity or universal unimodality. Section 3 already verifies that changing query parallelism shifts absolute QPS but preserves the efs feasibility boundary and the dominant trends over efc and M. Here we audit two further risks: whether measurement noise perturbs the pairwise comparisons used during search, and whether the dominant structural trends— formalized as sufficient conditions in Lemmas 3.1 and 3.2—persist across different data geometries. We first evaluate robustness to measurement noise using the 10-run average as a reference. We recompute configuration scores using 1, 3, and 5 runs, and measure QPS 𝑃95 relative error, pairwise comparison flip rate, same-or-adjacent optimum stability, and retained objective value. Pairwise flips exclude candidate pairs whose reference objective gap is below 0.5%, so near-ties are not counted

Exploiting Structural Properties for Efficient Constraint-Aware HNSW Hyperparameter Tuning

(a)

sift deep1M youtube

Oracle

VDTuner

100% 95% 92% 90%

70% 0

(b)

as unstable decisions. Even with a single run, the QPS 𝑃95 error is 1.86%, the pairwise flip rate is only 1.1%, the selected optimum remains the same or adjacent grid point in 98.8% of cases, and the selected configuration retains 99.21% of the 10-run reference objective. With five runs, these improve to 0.62%, 0.4%, 99.7%, and 99.79%, respectively. Thus, runtime noise does not materially perturb the pairwise comparisons used by CHAT. We further stress-test the structural trends on six synthetic workloads that vary cluster separation/overlap, cluster-size imbalance, anisotropy, dimensionality, and cluster structure. For the wellseparated, overlapping, imbalanced, and anisotropic workloads, the trends exploited by CHAT continue to hold empirically under both Recall and QPS constraints: the efs feasibility predicate remains monotone, fixed-M slices over efc remain dominantly unimodal, and the outer envelope 𝑔(𝑀) remains dominantly unimodal. In these cases, HNSW construction exposes useful routing alternatives early, after which additional construction effort becomes increasingly redundant. The high-dimensional and uniform workloads expose the main failure mode. Distance concentration or the absence of cluster structure can delay useful routing edges until larger construction budgets, producing a delayed graph-quality gain and a second objective peak. This effect is most visible under a Recall constraint, where the delayed gain can reduce the minimum feasible efs and recover QPS; under a QPS constraint, the same branch must reduce efs to preserve throughput, so the gain is dampened. This behavior is consistent with the sufficient conditions in Lemmas 3.1 and 3.2; it illustrates cases where the diminishing-utility condition required by these lemmas fails. CHAT is therefore not a global optimizer for arbitrary multi-modal objectives, but a sample-efficient search procedure for dominant discrete trends induced by standard HNSW mechanisms. In the high-dimensional counterexample, CHAT selects (𝑀, 𝑒 𝑓 𝑐, 𝑒 𝑓 𝑠) = (16, 400, 160), while the full-grid Oracle selects (32, 660, 320); both satisfy the Recall constraint. CHAT achieves QPS 4,970 versus the Oracle’s 5,280, retaining 94.1% of the Oracle objective. Thus, when the sufficient conditions fail, ternary-style localization may converge to a local peak, but best-so-far tracking over validated configurations substantially limits the loss.

Impact of Heuristic Search Space Reduction

To assess the effectiveness of the two heuristics used in CHAT for narrowing the search ranges of efs and efc, we performed an ablation study comparing four configurations: (1) CHAT, which incorporates both heuristics described in Sections 5.2 and 5.3; (2) EFS_HEURISTIC, which applies only the efs range narrowing heuristic; (3) EFC_HEURISTIC, which applies only the efc heuristic; and

ECI

Optuna

NSGA

Rand

Grid

7200

10800

14400

100% 95% 92% 90%

80%

sift deep1M youtube

Figure 14: Impact of heuristic search-space reduction. (a) Tuning time. (b) Average performance (Recall and QPS). All values are normalized to BASE.

6.5

CHAT

Recall

EFC_HEURISTIC

1.0 0.8 0.6 0.4 0.2 0.0 nytimes glove

Normalized Performance

Normalized Tuning Time

EFS_HEURISTIC

QPS

BASE

1.0 0.8 0.6 0.4 0.2 0.0 nytimes glove

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA, USA

80%

3600

7200

10800

Time (seconds)

14400

70% 0

3600

Time (seconds)

Figure 15: Performance of CHAT and baselines on the nytimes dataset using Milvus. (4) BASE, which disables both heuristics and performs exhaustive search over the entire range using binary and ternary search procedures. The performance metric was defined as the aggregated objective value under a Recall threshold of 0.95 and a QPS threshold set at the 75th percentile. Figure 14(a) shows that each heuristic individually reduces tuning time relative to BASE, with the efs heuristic achieving speedups of 1.13×–4.96× and the efc heuristic yielding 1.05×–3.85× improvements. When combined, CHAT attains speedups of 1.17×–6.85×, indicating a complementary effect between the two heuristics. Figure 14(b) further shows that these gains do not compromise solution quality: CHAT achieves normalized performance of 98.03%–99.9%, while EFS_HEURISTIC and EFC_HEURISTIC attain 99.4%–99.9% and 98.7%–99.9%, respectively, demonstrating that heuristic search space reduction substantially accelerates tuning with only negligible loss in objective performance.

6.6

Evaluation on a Commercial VectorDB

To validate the generality and practical effectiveness of our approach, we conducted additional experiments on Milvus, a widely adopted commercial vector database, beyond the open-source HNSW implementations evaluated earlier. We followed the same experimental setup described in Section 6.1. Specifically, we applied a minimum Recall constraint of 0.95, or a minimum QPS constraint defined as the 75th percentile of all configurations for each dataset, with a fixed tuning time budget of four hours. As shown in Figure 15, which presents results on the nytimes dataset, our method consistently outperformed all baseline methods under both types of constraints1 . Under the Recall constraint, it achieved up to 99.2% and at least 96.8% of the Oracle’s optimal QPS. Under the QPS constraint, it successfully matched the Oracle’s optimal Recall. These results demonstrate that our method remains effective and stable even in production-grade vector database environments, maintaining high performance and constraint satisfaction under limited tuning budgets.

Related Work

VectorDB and ANN Indexing. Vector databases and approximate nearest neighbor (ANN) search methods are central to highdimensional data retrieval [26, 42]. Early methods such as localitysensitive hashing (LSH) [18, 20] and product quantization (PQ) [23, 35] introduced efficient hashing and compression techniques. Graphbased ANN indices, including Hierarchical Navigable Small World 1We observed similar trends on the other datasets used in this experiment.

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA, USA

(HNSW) [31] and Navigating Spreading-out Graph (NSG) [10], improve recall–speed trade-offs by organizing points into navigable proximity graphs [8]. DiskANN [39] scales graph-based search to billion-scale datasets through memory–disk optimized storage and retrieval. Libraries such as Faiss [22] and ScaNN [16] combine quantization and GPU acceleration for large-scale search, with adoption in systems such as Milvus [41]. Database Auto-Tuning. Automated database tuning has progressed from heuristic methods to machine-learning-based approaches. OtterTune [40] introduced supervised learning for knob tuning, while QTune [29] extended this direction with reinforcement learning (RL) for query-level precision. Recent works emphasize constraintawareness and multi-objective optimization.

Conclusion

We presented CHAT, an API-level black-box but HNSW-structureaware tuning framework that exploits monotone search-time feasibility boundaries, dominant unimodal trends over construction parameters, and separable resource dependencies to guide a hierarchical search with resource surrogates. Across datasets and HNSW backends, CHAT efficiently identifies and validates configurations that satisfy user-d efined performance and resource constraints, offering a practical path toward predictable tuning for production HNSW deployments.

References [1] Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. 2019. Optuna: A Next-generation Hyperparameter Optimization Framework. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (Anchorage, AK, USA) (KDD ’19). Association for Computing Machinery, New York, NY, USA, 2623–2631. doi:10.1145/3292500.3330701 [2] Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. 2020. ANNBenchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems 87 (2020), 101374. doi:10.1016/j.is.2019.02.006 [3] 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 [4] James Bergstra and Yoshua Bengio. 2012. Random search for hyper-parameter optimization. J. Mach. Learn. Res. 13, null (Feb. 2012), 281–305. [5] Sebastian Borgeaud, Arthur Mensch, Jordan Hoffmann, Trevor Cai, Eliza Rutherford, Katie Millican, George Bm Van Den Driessche, Jean-Baptiste Lespiau, Bogdan Damoc, Aidan Clark, et al. 2022. Improving language models by retrieving from trillions of tokens. In International conference on machine learning. PMLR, 2206–2240. [6] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6, 2 (2002), 182–197. doi:10.1109/4235.996017 [7] dnotitia. [n. d.]. SeahorseDB-dataset. https://huggingface.co/datasets/dnotitia/ SeahorseDB-dataset/tree/main. Accessed: 2025-07-16. [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 Intelligence 44, 8 (2022), 4139–4150. doi:10.1109/TPAMI.2021.3067706 [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 Endowment 12, 5 ([n. d.]). [10] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2025. Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph. arXiv:1707.00143 [cs.LG] https://arxiv.org/abs/1707.00143 [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 [12] Jacob R Gardner, Matt J Kusner, Zhixiang Eddie Xu, Kilian Q Weinberger, and John P Cunningham. 2014. Bayesian optimization with inequality constraints..

Choi et al.

In ICML, Vol. 2014. 937–945. [13] Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013. Optimized Product Quantization for Approximate Nearest Neighbor Search. In 2013 IEEE Conference on Computer Vision and Pattern Recognition. 2946–2953. doi:10.1109/CVPR.2013. 379 [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 [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. In Proceedings 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. https://proceedings.mlr.press/v119/guo20h. html [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 [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 Systems 43, 2 (Jan. 2025), 1–55. doi:10.1145/3703155 [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 [19] 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.. [20] Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings 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 [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 [22] Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2021. Billion-Scale Similarity Search with GPUs. IEEE Transactions on Big Data 7, 3 (2021), 535–547. doi:10. 1109/TBDATA.2019.2921572 [23] Herve Jégou, Matthijs Douze, and Cordelia Schmid. 2011. Product Quantization for Nearest Neighbor Search. IEEE Transactions on Pattern Analysis and Machine Intelligence 33, 1 (2011), 117–128. doi:10.1109/TPAMI.2010.57 [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 [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 Systems 33 (2020), 9459–9474. [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 Knowledge and Data Engineering 32, 8 (2020), 1475–1488. doi:10.1109/TKDE.2019. 2909204 [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 [28] Ting Liu, Andrew W. Moore, Alexander Gray, and Ke Yang. 2004. An investigation of practical approximate nearest neighbor algorithms. In Proceedings of the 18th International Conference on Neural Information Processing Systems (Vancouver, British Columbia, Canada) (NIPS’04). MIT Press, Cambridge, MA, USA, 825–832. [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 [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.DB] https://arxiv.org/abs/ 2310.11703 [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 intelligence 42, 4 (2018), 824–836.

Exploiting Structural Properties for Efficient Constraint-Aware HNSW Hyperparameter Tuning

[32] Marius Muja and David G. Lowe. 2014. Scalable Nearest Neighbor Algorithms for High Dimensional Data. IEEE Transactions on Pattern Analysis and Machine Intelligence 36, 11 (2014), 2227–2240. doi:10.1109/TPAMI.2014.2321376 [33] P. Ngatchou, A. Zarei, and A. El-Sharkawi. 2005. Pareto Multi Objective Optimization. In Proceedings of the 13th International Conference on, Intelligent Systems Application to Power Systems. 84–91. doi:10.1109/ISAP.2005.1599245 [34] OpenAI. 2024. GPT-4 Technical Report. arXiv:2303.08774 [cs.CL] https://arxiv. org/abs/2303.08774 [35] Zhibin Pan, Liangzhuang Wang, Yang Wang, and Yuchen Liu. 2020. Product Quantization with Dual Codebooks for approximate Nearest Neighbor Search. Neurocomputing 401 (03 2020). doi:10.1016/j.neucom.2020.03.016 [36] Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P. Adams, and Nando de Freitas. 2016. Taking the Human Out of the Loop: A Review of Bayesian Optimization. Proc. IEEE 104, 1 (2016), 148–175. doi:10.1109/JPROC.2015.2494218 [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. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 8371–8384. [38] Jasper Snoek, Hugo Larochelle, and Ryan P. Adams. 2012. Practical Bayesian optimization of machine learning algorithms. In Proceedings 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. [39] Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Krishaswamy, and Harsha Vardhan Simhadri. 2019. DiskANN: fast accurate billionpoint nearest neighbor search on a single node. Curran Associates Inc., Red Hook, NY, USA. [40] Dana Van Aken, Andrew Pavlo, Geoffrey J. Gordon, and Bohan Zhang. 2017. Automatic Database Management System Tuning Through Large-scale Machine Learning. In Proceedings of the 2017 ACM International Conference on Management of Data (Chicago, Illinois, USA) (SIGMOD ’17). Association for Computing Machinery, New York, NY, USA, 1009–1024. doi:10.1145/3035918.3064029 [41] Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu 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. In Proceedings of the 2021 International Conference on Management of Data (Virtual Event, China) (SIGMOD ’21). Association for Computing Machinery, New York, NY, USA, 2614–2627. doi:10.1145/3448016.3457550 [42] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A comprehensive 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 [43] Ziyu Wang, Frank Hutter, Masrour Zoghi, David Matheson, and Nando De Freitas. 2016. Bayesian optimization in a billion dimensions via random embeddings. J. Artif. Int. Res. 55, 1 (Jan. 2016), 361–387. [44] 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 Endowment 17, 13 (2024), 4668–4682. [45] 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 [46] 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. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 4357–4369. [47] 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 [48] 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://arxiv.org/abs/2303.18223 [49] 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

A Index Construction Algorithms of HNSW A.1 Data Insertion

Choi et al.

A.2

Search Layers

Algorithm 5 SEARCH-LAYER(𝑞, 𝑒𝑝, efs, 𝑙𝑐 ) Algorithm 4 INSERT(ℎ𝑛𝑠𝑤, 𝑞, 𝑀, 𝑀max, efc, 𝑚𝐿 ) Input: multilayer graph ℎ𝑛𝑠𝑤 , new element 𝑞 , number of established connections 𝑀 , maximum number of connections for each element per layer 𝑀max , size of the dynamic candidate list efc, normalization factor for level generation 𝑚𝐿 Output: update ℎ𝑛𝑠𝑤 inserting element 𝑞 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

𝑊 ←∅ 𝑒𝑝 ← get enter point for ℎ𝑛𝑠𝑤 𝐿 ← level of 𝑒𝑝 𝑙 ← ⌊ − ln(unif (0..1) ) · 𝑚𝐿 ⌋ for 𝑙𝑐 ← 𝐿 . . . 𝑙 + 1 𝑊 ← SEARCH-LAYER(𝑞, 𝑒𝑝, efc =1, 𝑙𝑐 ) 𝑒𝑝 ← get the nearest element from 𝑊 to 𝑞 for 𝑙𝑐 ← min(𝐿, 𝑙 ) . . . 0 𝑊 ← SEARCH-LAYER(𝑞, 𝑒𝑝, efc, 𝑙𝑐 ) 𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑟𝑠 ← SELECT-NEIGHBORS(𝑞,𝑊 , 𝑀, 𝑙𝑐 ) add bidirectional connections from 𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑟𝑠 to 𝑞 at layer 𝑙𝑐 for each 𝑒 ∈ 𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑟𝑠 𝑒𝐶𝑜𝑛𝑛 ← 𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑢𝑟ℎ𝑜𝑜𝑑 (𝑒 ) at layer 𝑙𝑐 if |𝑒𝐶𝑜𝑛𝑛 | > 𝑀max 𝑒𝑁 𝑒𝑤𝐶𝑜𝑛𝑛 ← SELECT-NEIGHBORS(𝑒, 𝑒𝐶𝑜𝑛𝑛, 𝑀max , 𝑙𝑐 ) set 𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑢𝑟ℎ𝑜𝑜𝑑 (𝑒 ) at layer 𝑙𝑐 to 𝑒𝑁 𝑒𝑤𝐶𝑜𝑛𝑛 𝑒𝑝 ← 𝑊 if 𝑙 > 𝐿 set enter point for ℎ𝑛𝑠𝑤 to 𝑞

Algorithm 4 describes the incremental insertion procedure used to construct the HNSW index. Each data point is inserted sequentially into a multi-layer proximity graph, where the number of layers and the connectivity at each layer are determined probabilistically and by fixed degree constraints. For each inserted element 𝑞, the algorithm first samples a maximum layer ℓ from an exponentially decaying distribution controlled by the normalization parameter 𝑚𝐿 . This mechanism ensures that the expected number of layers in the structure is 𝑂 (log 𝑁 ), yielding a hierarchy in which higher layers contain progressively fewer nodes and serve as long-range routing shortcuts. The insertion proceeds in two phases. In the first phase, the algorithm performs a greedy descent from the current entry point, starting at the topmost layer and continuing down to layer ℓ + 1. At each of these layers, SEARCH-LAYER is executed with 𝑒 𝑓 = 1, producing a single closest candidate that becomes the entry point for the next lower layer. This phase localizes the insertion position coarsely and incurs minimal search cost. In the second phase, for layers min(𝐿, ℓ) down to the base layer, SEARCH-LAYER is executed with a larger candidate list size efc. This broader search identifies a set of candidate neighbors that are then filtered by SELECT-NEIGHBORS to retain at most 𝑀 connections. The resulting neighbors are connected bidirectionally to 𝑞, and degree constraints are enforced by reapplying SELECTNEIGHBORS to existing nodes whose neighborhoods exceed the layer-specific maximum degree. This insertion procedure ensures that each node maintains bounded degree while preserving the navigability of the graph. Importantly, the construction cost is dominated by the repeated execution of SEARCH-LAYER across layers, where the breadth of exploration is controlled by efc and the pernode scan cost is bounded by the realized degree. These properties directly motivate the resource-usage analysis in Section 4.

Input: query element 𝑞 , enter points 𝑒𝑝 , number of nearest to 𝑞 elements to return efs, layer number 𝑙𝑐 Output: efs closest neighbors to 𝑞 1 𝑣 ← 𝑒𝑝𝑐 2 𝐶 ← 𝑒𝑝𝑐 3 𝑊 ← 𝑒𝑝𝑐 4 while |𝐶 | > 0 5 𝑐 ← extract nearest element from 𝐶 to 𝑞 6 𝑓 ← get furthest element from 𝑊 to 𝑞 7 if 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 (𝑐, 𝑞) > 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 (𝑓 , 𝑞) 8 break 9 for each 𝑒 ∈ 𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑢𝑟ℎ𝑜𝑜𝑑 (𝑐 ) at layer 𝑙𝑐 10 if 𝑒 ∉ 𝑣 11 𝑣 ← 𝑣 ∪𝑒 12 𝑓 ← get furthest element from 𝑊 to 𝑞 13 if 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 (𝑒, 𝑞) < 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 (𝑓 , 𝑞) or |𝑊 | < efs 14 𝐶 ←𝐶 ∪𝑒 15 𝑊 ←𝑊 ∪𝑒 16 if |𝑊 | > efs 17 remove furthest element from 𝑊 to 𝑞 18 return 𝑊

Algorithm 5 defines the SEARCH-LAYER procedure, which serves as the fundamental primitive for both index construction and query processing in HNSW. Given a query element 𝑞, an entry point 𝑒𝑝, a layer index ℓ, and a candidate list size efs, the procedure performs a best-first graph traversal restricted to layer ℓ. The algorithm maintains two priority queues: a candidate queue 𝐶, which stores nodes to be expanded, and a working set 𝑊 , which stores the current best efs candidates found so far. At each iteration, the closest element 𝑐 in 𝐶 is extracted and compared against the worst element in 𝑊 . If no improvement is possible, the search terminates early. Otherwise, the algorithm scans the neighbors of 𝑐 at layer ℓ. For each previously unvisited neighbor, a distance evaluation is performed, and the neighbor is inserted into 𝐶 and 𝑊 if it improves the current candidate set. When 𝑊 exceeds size efs, the farthest element is removed, maintaining a bounded working set. This greedy best-first traversal ensures that SEARCH-LAYER explores only a limited subset of the graph, with the total number of expansions controlled by efs. As a result, increasing efs monotonically enlarges the exploration budget, while the cost of each expansion is bounded by the degree constraints imposed during construction. This monotonic dependence underlies the performance and resource trade-offs analyzed in Sections 3 and 4.

A.3

Search Neighborhoods to Connect

Algorithm 6 specifies the SELECT-NEIGHBORS using heuristic to search, which enforces bounded degree while maintaining graph navigability. Given a candidate set 𝐶, the procedure iteratively selects neighbors based not only on proximity to the target node 𝑞, but also on diversity among selected neighbors. At each step, the closest remaining candidate is selected if it is sufficiently closer to 𝑞 than any previously selected neighbor. Candidates that fail this condition are temporarily discarded but may be reconsidered if the optional "keep pruned connections" flag is enabled. The process continues until 𝑀 neighbors are selected or the candidate pool is exhausted.

Exploiting Structural Properties for Efficient Constraint-Aware HNSW Hyperparameter Tuning

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA, USA

Δ𝑇𝑀 (efc𝑖 ), then Δ𝑓𝑀 (efc𝑖 ) ≤ 0, so the objective no longer improves at this step. Condition (ii) of Lemma 3.1 rules out a later recovery after this Input: base element 𝑞 , candidate elements 𝐶 , number of neighbors to return 𝑀 , layer number 𝑙𝑐 , crossing: once the marginal benefit no longer exceeds the residual flag indicating whether or not to extend candidate list 𝑒𝑥𝑡𝑒𝑛𝑑𝐶𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠 , flag indicating whether or not to add discarded elements 𝑘𝑒𝑒𝑝𝑃𝑟𝑢𝑛𝑒𝑑𝐶𝑜𝑛𝑛𝑒𝑐𝑡𝑖𝑜𝑛𝑠 cost, larger efc values do not reveal a delayed high-utility conOutput: 𝑀 elements selected by the heuristic nectivity regime that restores Δ𝐵𝑀 > Δ𝑇𝑀 . Therefore, after the first non-positive marginal step, all later marginal steps remain 1 𝑅←∅ non-positive. The sequence 𝑓𝑀 (efc 1 ), . . . , 𝑓𝑀 (efc𝑛 ) therefore has no 2 𝑊 ←𝐶 3 if 𝑒𝑥𝑡𝑒𝑛𝑑𝐶𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠 negative-to-positive marginal reversal. It is non-decreasing up to 4 for each 𝑒 ∈ 𝐶 some peak grid point and non-increasing thereafter, allowing ties. 5 for each 𝑒𝑎𝑑 𝑗 ∈ 𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑢𝑟ℎ𝑜𝑜𝑑 (𝑒 ) at layer 𝑙𝑐 Thus, 𝑓𝑀 (efc) is unimodal on the ordered grid. 6 if 𝑒𝑎𝑑 𝑗 ∉ 𝑊 7 𝑊 ← 𝑊 ∪ 𝑒𝑎𝑑 𝑗 If condition (ii) fails, a delayed graph-quality gain can make the 8 𝑊𝑑 ← ∅ marginal benefit exceed the residual cost again after an earlier 9 while |𝑊 | > 0 and |𝑅 | < 𝑀 10 𝑒 ← extract nearest element from 𝑊 to 𝑞 decline, producing a second peak. This is precisely the failure mode 11 if 𝑒 is closer to 𝑞 compared to any element from 𝑅 examined in Section 6.4. 12 𝑅 ← 𝑅 ∪𝑒

Algorithm 6 SELECT-NEIGHBORS(𝑞, 𝐶, 𝑀, 𝑙𝑐 , 𝑒𝑥𝑡𝑒𝑛𝑑𝐶𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠, 𝑘𝑒𝑒𝑝𝑃𝑟𝑢𝑛𝑒𝑑𝐶𝑜𝑛𝑛𝑒𝑐𝑡𝑖𝑜𝑛𝑠)

13 else 14 𝑊𝑑 ← 𝑊𝑑 ∪ 𝑒 15 if 𝑘𝑒𝑒𝑝𝑃𝑟𝑢𝑛𝑒𝑑𝐶𝑜𝑛𝑛𝑒𝑐𝑡𝑖𝑜𝑛𝑠 16 while |𝑊𝑑 | > 0 and |𝑅 | < 𝑀 17 𝑅 ← 𝑅∪ extract nearest element from 𝑊𝑑 to 𝑞 18 return 𝑅

This heuristic induces two important structural effects. First, it limits the realized out-degree even when the degree cap increases, leading to saturation in average out-degree as 𝑀 grows. Second, it favors diverse connections that improve long-range navigability, which directly impacts search efficiency. These effects explain why the realized connectivity grows sublinearly with 𝑀 and why build time exhibits diminishing returns, as discussed in Section 4.

Proof Sketches for Unimodality Lemmas

The lemmas in Sections 3.3 and 3.4 give sufficient conditions for discrete unimodality on the ordered grids used by CHAT. They are not universal guarantees. The purpose of the proof sketches below is to show that, under the stated marginal benefit–cost conditions, the corresponding objective sequence has no negative-to-positive marginal reversal. Section 6.4 gives empirical stress cases where these sufficient conditions fail.

B.1

Proof Sketch for Lemma 3.1

Fix 𝑀 and an active constraint 𝐶 ∈ {Recall, QPS}. Consider the ordered construction-effort grid efc 1 < efc 2 < · · · < efc𝑛 . For each efc𝑖 , let 𝑓𝑀 (efc𝑖 ) denote the constrained objective after choosing the boundary efs that satisfies 𝐶. Define the discrete marginal change Δ𝑓𝑀 (efc𝑖 ) = 𝑓𝑀 (efc𝑖+1 ) − 𝑓𝑀 (efc𝑖 ) = Δ𝐵𝑀 (efc𝑖 ) − Δ𝑇𝑀 (efc𝑖 ), where Δ𝐵𝑀 is the marginal graph-quality benefit and Δ𝑇𝑀 is the residual traversal/search cost. By construction, reductions in expanded nodes caused by better graph navigability are counted as graph-quality benefit, not as negative cost. Hence the residual cost term satisfies Δ𝑇𝑀 (efc𝑖 ) ≥ 0. If Δ𝐵𝑀 (efc𝑖 ) > Δ𝑇𝑀 (efc𝑖 ), then Δ𝑓𝑀 (efc𝑖 ) > 0, so increasing efc improves the constrained objective at this grid step. If Δ𝐵𝑀 (efc𝑖 ) ≤

B.2

Proof Sketch for Lemma 3.2

The proof for the outer objective follows the same marginal-crossing argument, but it applies to the best constrained objective obtainable after re-optimizing efc for each 𝑀. Consider the ordered degree grid 𝑀1 < 𝑀2 < · · · < 𝑀𝑛 . For each 𝑀𝑖 , define the outer envelope 𝑔(𝑀𝑖 ) = max 𝐹𝐶 (𝑀𝑖 , efc), efc

where 𝐹𝐶 (𝑀𝑖 , efc) is the constrained objective after choosing the boundary efs satisfying the active constraint 𝐶. Let Δ𝑔(𝑀𝑖 ) = 𝑔(𝑀𝑖+1 ) − 𝑔(𝑀𝑖 ) = Δ𝐵 out (𝑀𝑖 ) − Δ𝑇out (𝑀𝑖 ), where Δ𝐵 out is the marginal graph-quality benefit from increasing 𝑀 with efc re-optimized, and Δ𝑇out is the residual traversal/search cost. As in Lemma 3.1, reductions in expanded nodes caused by better graph navigability are counted as graph-quality benefit. Thus, Δ𝑇out (𝑀𝑖 ) ≥ 0. If Δ𝐵 out (𝑀𝑖 ) ≤ Δ𝑇out (𝑀𝑖 ), then Δ𝑔(𝑀𝑖 ) ≤ 0. Condition (ii) of Lemma 3.2 prevents a within-branch recovery: after additional degree no longer provides enough marginal graph-quality benefit to offset residual traversal cost, larger 𝑀 values do not by themselves restore a positive marginal gain. The outer-envelope case also requires an additional condition because 𝑔(𝑀) re-optimizes efc at every 𝑀. Even if each fixed-𝑀 slice is unimodal, re-optimizing efc could create a new high-performing branch at larger 𝑀. Condition (iii) rules out this cross-branch recovery by requiring 𝑀 and efc to remain partial substitutes for graph quality: larger 𝑀 should not make a substantially different efc branch suddenly dominate after the outer objective has already entered the overhead-dominated regime. Together, conditions (ii) and (iii) imply that once Δ𝑔(𝑀𝑖 ) becomes non-positive, all later marginal changes remain non-positive. Hence the sequence 𝑔(𝑀1 ), . . . , 𝑔(𝑀𝑛 ) has no negative-to-positive marginal reversal. It is non-decreasing up to some peak grid point and non-increasing thereafter, allowing ties. Therefore, 𝑔(𝑀) is unimodal over the ordered 𝑀 grid. If condition (iii) fails, re-optimizing efc at larger 𝑀 may create a new high-performing branch and make the outer envelope bimodal

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA, USA

Choi et al.

or multi-modal. Section 6.4 reports such stress cases and shows that CHAT still returns the best-so-far validated feasible configuration, although it is not a global optimizer for arbitrary multi-modal objectives.

C Dataset C.1 Dataset Statistics Table 2 summarizes the datasets used in our evaluation. Four datasets (nytimes, glove, sift, and deep1M) are drawn from ANN Benchmarks. The youtube dataset is constructed to emulate a realistic video embedding retrieval workload. The datasets span a wide range of dimensionalities (100–1024), corpus sizes (290K–1.2M), and distance metrics, covering diverse operating regimes for HNSW hyperparameter tuning. Dataset

Dimension

# Data Points

# Queries

Distance

nytimes glove sift deep1M youtube

256 100 128 256 1024

290,000 1,183,514 1,000,000 1,000,000 990,072

10,000 10,000 10,000 1,000 10,000

Angular Angular Euclidean Angular Angular

Table 2: Dataset characteristics.

C.2

Youtube dataset

The youtube dataset is built from publicly available YouTube metadata of high-view-count videos in a late-2024 snapshot. Each vector corresponds to an extracted I-frame (keyframe), not to the whole video, so multiple vectors may share the same video_id. We encode each I-frame into a 1024-dimensional vector using OpenCLIP H-14 (frames only; no audio, subtitles, or text metadata) and evaluate under angular distance. The final corpus contains 990,072 vectors with 10,000 held-out queries. We removed only items whose metadata contained unusable special characters or emojis; no other cleaning or vector post-processing was applied.

D Baselines D.1 Details of Baselines We provide a brief overview of the baseline tuners used in our experiments. All baselines are treated as black-box methods: they propose HNSW configurations (M,efc,efs) and observe the resulting Recall, QPS, build time, and index size, without accessing internal graph statistics. Grid Search and Random Search. Grid Search evaluates configurations over a predefined discretized grid, while Random Search samples configurations uniformly from the same search space. These two methods serve as standard model-free baselines. Grid Search is deterministic but sensitive to grid granularity, whereas Random Search is simple and broadly exploratory but does not use past observations to guide future trials. Optuna. Optuna is a general-purpose model-based hyperparameter optimization framework that uses the Tree-structured Parzen Estimator (TPE) sampler to propose configurations from past observations. In our experiments, infeasible trials (those violating Recall

or QPS targets) are penalized via a large-penalty scalar objective proportional to the degree of violation, so feasibility is enforced softly through the objective rather than explicit filtering. Optuna therefore represents a strong generic Bayesian optimization baseline, but it does not exploit HNSW-specific structural properties such as monotonicity or unimodality. NSGA-II. NSGA-II is a population-based evolutionary algorithm for multi-objective optimization. It maintains a diverse population of candidate solutions and evolves them to approximate a Pareto frontier over competing objectives. In our experiments, constraint violation is treated as one objective to minimize alongside maximizing the remaining objective (Recall or QPS), so feasibility is encouraged through Pareto dominance rather than explicit filtering. NSGA-II thus serves as a representative evolutionary baseline for HNSW tuning under the same Recall/QPS performance targets. ECI. ECI is a constrained Bayesian optimization baseline based on Expected Constrained Improvement. It models both objective performance and constraint feasibility, and selects configurations that are expected to improve the objective while satisfying the constraints. Compared with generic Bayesian optimization, ECI is more explicitly constraint-aware, making it a natural baseline for evaluating constraint-driven HNSW tuning. VDTuner. VDTuner is a Bayesian optimization-based tuning framework designed for vector database systems. It searches for highquality configurations by modeling trade-offs between search quality and efficiency. We restrict VDTuner to the HNSW parameter space for a fair comparison, and evaluate it under the same Recall/QPS feasibility constraints and tuning-time budget as other methods. Oracle Solution. The Oracle Solution exhaustively evaluates the full predefined HNSW search space without a tuning-time budget and selects the best feasible configuration. It is not a practical tuner, but serves as an upper bound for measuring how close each method comes to the best achievable performance in our search space.

D.2

Hyperparameters of Baselines

Table 3 summarizes the key hyperparameter configurations and experimental settings used for all baseline tuning methods evaluated in this study. All stochastic methods were evaluated using the same random seed to ensure fair and reproducible comparisons across baselines. Unless otherwise stated, all baselines share the same search space over (𝑀, 𝑒 𝑓 𝑐, 𝑒 𝑓 𝑠), enforce the hard constraint 𝑀 ≤ 𝑒 𝑓 𝑐, and are evaluated under an identical wall-clock tuning budget. The table highlights the method-specific differences in search strategies, discretization schemes, and constraint-handling mechanisms.

Raw QPS Thresholds Used in the Evaluation

For each dataset–backend pair, we computed the QPS target by measuring QPS over the predefined HNSW search space and taking the 75th percentile of the resulting distribution. This percentile is used only to make the QPS constraint comparably challenging across workloads; after it is computed, CHAT receives the threshold as a raw QPS constraint. Table 4 reports these raw values.

Search strategy Search space Parameter constraint Discretization Tuning budget

Uniform random sampling (𝑀, 𝑒 𝑓 𝑐, 𝑒 𝑓 𝑠 ) 𝑀 ≤ 𝑒 𝑓 𝑐 (enforced at sampling) None 14,400 seconds (4 hours)

Search strategy 𝑀 step size 𝑒 𝑓 𝑐 step size 𝑒 𝑓 𝑠 step size Parameter constraint Tuning budget

Exhaustive grid enumeration 4 64 128 𝑀 ≤ 𝑒𝑓 𝑐 14,400 seconds (or grid exhaustion)

Optuna (TPE)

Search strategy Discretization Constraint handling Objective Tuning budget

Bayesian optimization (TPE sampler) Δ𝑀=1, Δ𝑒 𝑓 𝑐=8, Δ𝑒 𝑓 𝑠=16 Large infeasible penalty − QPS or − Recall 14,400 seconds

NSGA-II

Search strategy Population size Discretization Constraint handling Tuning budget

Evolutionary multi-objective search 32 Δ𝑀=1, Δ𝑒 𝑓 𝑐=8, Δ𝑒 𝑓 𝑠=16 Violation-first objective 14,400 seconds

Search strategy Warm-up samples Discretization Feasibility model Acquisition Tuning budget

Constrained Bayesian optimization 16 Δ𝑀=1, Δ𝑒 𝑓 𝑐=8, Δ𝑒 𝑓 𝑠=16 Gaussian Process classifier Constrained Expected Improvement 14,400 seconds

Grid Search

ECI

Faiss

Hnswlib

(a) Residual tail 20 10 0 4

(b) Conservative coverage

100

Coverage (%)

Value

CPU Threads

Figure 16: CPU-thread sensitivity of the resource feasibility test. We report the build-time underestimation residual tail and conservative-test coverage across CPU-thread counts for Faiss and Hnswlib. nytimes Faiss

glove Hnswlib

sift deep1M p50 residual

(a) Build-time calibration 103

point size = dataset size

102 101 100 100

101

102

youtube p95 residual

(b) Index-size calibration Predicted Index Size

Random Search

Parameter

Predicted Build Time

Stage

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA, USA

Build-time Residual p95 (%)

Exploiting Structural Properties for Efficient Constraint-Aware HNSW Hyperparameter Tuning

point size = dataset size

106

103

106

Measured Build Time

Measured Index Size

(d) Index-size residual by scale

Search strategy Acquisition Initialization Constraint handling Tuning budget

Multi-objective Bayesian optimization qEHVI Default configuration Implicit (CEI-style) 14,400 seconds

Table 3: Hyperparameter settings of baseline tuning methods used in our experiments. All baselines were evaluated under the same wall-clock tuning budget of 14,400 seconds (4 hours) per dataset.

Dataset

Faiss

Hnswlib

nytimes glove sift deep1M youtube

29,225 49,940 59,298 24,039 12,909

27,207 37,410 46,038 27,150 9,795

Table 4: Raw QPS values corresponding to the 75th-percentile QPS constraints used in Section 6.2. The percentile is used only to make constraint difficulty comparable across workloads; CHAT receives the raw QPS value shown here.

Analysis of Constraint Resource Models

This appendix provides the resource-model diagnostics referenced in Section 6.3. We evaluate the calibrated closed-form surrogates for build time and index size from three perspectives: sensitivity to CPU parallelism, calibration between predicted and measured resource usage, and residual behavior across dataset scales and backends. Since the resource filter is used to reject candidates before construction, the relevant error is one-sided underestimation: cases where the model predicts a lower resource cost than the measured value. Figure 16 reports CPU-thread sensitivity. Across the evaluated thread counts, the build-time underestimation residual tail and

Residual (%)

VDTuner

Residual (%)

60 40 20 0

4 2 0

~150K

~300K

Dataset Size

~1M

~150K

~300K

~1M

Dataset Size

Figure 17: Calibration and residual diagnostics for the closedform resource models. (a) and (b) compare predicted and measured build time and index size; the dashed diagonal indicates perfect calibration, and marker size denotes dataset scale. (c) and (d) report p50 and p95 one-sided underestimation residuals for build time and index size across dataset scales, datasets, and backends. Build-time residuals are larger and more variable, whereas index-size residuals remain small because index size is dominated by degree-cap-induced adjacency storage. conservative-test coverage remain stable for both Faiss and Hnswlib, indicating that the online calibration and safety margin absorb backend and parallelism effects. Figure 17 further shows that the calibrated models track measured build time and index size across dataset scales. Build-time residuals are larger and more variable because construction time is affected by implementation and scheduling variability, whereas index size is dominated by degreecap-induced adjacency storage. These diagnostics support using the compact resource models as conservative feasibility filters rather than exact performance predictors.

Synthetic Datasets for Structural Robustness Tests

This appendix describes the synthetic workloads used in Section 6.4: six regular workloads that vary common dataset characteristics, and one adversarial workload designed to violate the diminishing-utility condition of Lemmas 3.1 and 3.2.

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA, USA

Common methodology. Each dataset contains 𝑁 train = 100,000 training vectors and 𝑁 query = 1,000 query vectors. For the six regular workloads, training and query vectors are drawn from the same distribution. For the adversarial workload, the query set is intentionally biased toward local and bridge-requiring queries to expose a delayed high-utility connectivity regime. All datasets use 𝐿2 distance with 𝑘 = 10, and ground truth is computed by exact brute-force 𝑘-NN over the training set. All generators use a fixed random seed of 42. Well-separated. Eight isotropic Gaussian clusters in 128 dimensions, 12,500 points per cluster, with 𝜎 = 0.5. Cluster centers are sampled from [−10, 10] 128 subject to a target nearest-center distance of at least 8. This serves as a baseline case with cleanly separated clusters. Overlapping. Same as well-separated except 𝜎 = 2.0 and centers are generated with a target nearest-center distance of approximately 5, so that cluster boundaries overlap substantially. This yields blurred local neighborhoods and a harder 𝑘-NN problem.

Choi et al.

Imbalanced. Eight clusters in 128 dimensions with skewed sizes {50,000, 25,000, 10,000, 5,000, 4,000, 3,000, 2,000, 1,000}, 𝜎 = 0.8, target nearest-center distance 8. This tests robustness to highly nonuniform cluster populations. High-dimensional. Eight isotropic Gaussian clusters in 4096 dimensions with 𝜎 = 1.0, points equally distributed across clusters. This case tests sensitivity to high dimensionality, where pairwise distances concentrate. Anisotropic. Eight Gaussian clusters in 128 dimensions with diagonal covariance matrices whose entries are sampled from [0.2, 5.0] independently per cluster, producing elongated, axis-aligned clusters. This tests robustness to non-spherical local geometry. Uniform. A single uniform distribution over [−10, 10] 128 with no cluster structure. We include it as a stress case where the index cannot rely on dense cluster-local neighborhoods. Received 20 February 2007; revised 12 March 2009; accepted 5 June 2009

Exploiting Structural Properties for Efficient Constraint-Aware HNSW Hyperparameter Tuning

Related documents