Complexity and theory specific to HNSW

Complexity and theory specific to HNSW collect the claims and caveats around hierarchy height, logarithmic search, Delaunay-like assumptions, routing work, construction cost, and space overhead.
Created: Updated: 2 min read

These are the topics in this section, each on its own page with a stable path you can bookmark or share.

What topics are covered in this section?

Complexity and theory specific to HNSW collect the claims and caveats around hierarchy height, logarithmic search, Delaunay-like assumptions, routing work, construction and space cost, and adversarial topologies.

What can theory say about HNSW?

Expected hierarchy height and bounded routing work under idealized geometric assumptions motivate the logarithmic search narrative. Construction complexity and space complexity split vector storage from graph edge overhead. Idealized analyses differ sharply from worst-case graphs; adversarial graph topology names the hostile extreme that greedy search can face when assumptions fail. These pages exist so “HNSW is O(log n)” is never repeated without knowing the fine print.

Part III’s proof-limits chapter is the narrative companion to this glossary.

How should practitioners use theoretical pages?

Use them to interpret papers and to set expectations: good average behavior is not a per-query certificate. When production misses occur, theory says to inspect geometry and connectivity, not only Big-O slogans. Weaviate’s empirical ANN benchmarks are the operational counterpart – measure recall on your data rather than citing asymptotic folklore. Space-complexity terms help RAM planning alongside maxConnections.

Theory vocabulary also clarifies frontier work on certified search and robust routing.

What is a sensible reading path?

Start with logarithmic search claim, expected hierarchy height, and worst-case versus idealized analysis, then construction and space complexity. Continue into Part III and the accuracy-certification frontier pages if you need guarantees beyond heuristics.

This section keeps HNSW’s theory honest. Next, read “What is the logarithmic search claim about HNSW?” or Part III’s complexity chapter, then adversarial topology when you want the pessimistic boundary.