Part III — HNSW algorithms and theory

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?

• Why does HNSW’s neighbor-selection heuristic matter more than raw distance?
• How does HNSW search a graph, step by step?
• How is an HNSW graph actually built, one insertion at a time?
• What can we actually prove about HNSW’s complexity, and what can’t we?
• Why do recall and query difficulty vary so much from query to query?

Part III is the algorithmic heart of the curriculum: how HNSW searches, how it inserts, why neighbor selection beats naive nearest edges, what complexity claims actually mean, and why recall varies across queries.

What does this Part expect you to leave with?

You should be able to walk a query down the layers on paper, describe one insertion’s candidate and prune steps, explain diversified neighbor selection, separate idealized logarithmic claims from worst-case gaps, and diagnose easy versus hard queries. Those skills unlock tuning, implementation, and debugging Parts that follow.

Five chapters move from search, to build, to heuristics, to proofs, to query difficulty.

How do the pieces reinforce each other?

Search and build share candidate-list machinery but optimize different objectives. The heuristic chapter explains graph quality. Complexity and difficulty chapters prevent overconfidence in averages. Keep HNSW parameter, construction, search, and recall glossaries nearby for definitions mid-read.

Weaviate’s ef, efConstruction, and maxConnections are the production names for ideas this Part teaches abstractly.

What should you read next?

Start with step-by-step search, then insertion, neighbor selection, complexity limits, and query difficulty. Continue to Part IV to implement, or Part VI to tune, once the algorithms click.

Part III teaches HNSW as an algorithm. Next, open “How does HNSW search a graph, step by step?” and proceed through the Part before changing production knobs.