TL;DR
The article explains how HNSW converts brute-force vector comparisons into a multi-level graph search to speed nearest-neighbor lookups, and walks through a PHP implementation from the Vektor project. It outlines the core search and insertion logic, the role of parameters ef and M, and why HNSW yields large performance gains over linear search.
What happened
The author introduces Hierarchical Navigable Small World (HNSW) as an alternative to linear vector search and demonstrates how to implement it in PHP using code from the open-source Vektor project. HNSW arranges points into layered graphs: sparse, long-range connections at higher levels and dense, short-range links at level 0. A search begins at the top layer and greedily descends, choosing neighbors that increase cosine similarity until reaching level 0. At level 0 a priority-queue-driven greedy expansion (controlled by the ef parameter) maintains a candidate list of promising nodes and returns the top-K results. The implementation also covers insertion: a new vector gets a randomly assigned max level (via an exponential distribution), finds its nearest neighbors by running the search, and connects up to M neighbors, dropping the least similar if necessary. The article highlights the big reduction in comparisons compared to O(N) linear scan.
Why it matters
- HNSW reduces nearest-neighbor work from linear O(N) comparisons to a sublinear process, often yielding orders-of-magnitude speedups.
- Layered, probabilistic topology lets searches quickly narrow to relevant regions before performing detailed local exploration.
- Parameters ef and M allow tuning the trade-off between search precision, latency, and memory consumption.
- Understanding HNSW clarifies the inner workings of many modern vector databases and retrieval systems used in recommendation and RAG workflows.
Key facts
- Similarity metric used in the examples is cosine similarity.
- Search starts at the highest graph level and greedily moves to closer neighbors until descending to level 0.
- At level 0 the searchLayer routine uses a priority queue and a visited set to explore promising nodes until the candidate list size ef stabilizes.
- The ef parameter controls the size of the candidate/winner list; higher ef increases accuracy and cost.
- The M parameter sets the maximum number of connections per node and affects graph connectivity and memory usage.
- Node levels are assigned probabilistically (exponential distribution), so most points stay at level 0 and a few occupy higher levels.
- Insertion reuses the search logic to find neighbors for the new point and may evict the least similar connection when a neighbor list is full.
- On large datasets (example: 1 million items), HNSW can reduce comparisons from 1,000,000 to a few hundred or thousand.
What to watch next
- Tuning ef and M to balance latency, accuracy, and memory use — higher values improve recall but cost more resources.
- The complete PHP implementation and source code available in the Vektor GitHub repository: https://github.com/centamiv/vektor
- Real-world benchmark variations across different datasets and hardware: not confirmed in the source
Quick glossary
- HNSW: Hierarchical Navigable Small World — a multi-layer graph structure for approximate nearest-neighbor search that uses long-range upper layers and dense local lower layers.
- ef: Search (or construction) size parameter that sets how many candidate neighbors the algorithm keeps and examines during a query.
- M: Maximum number of connections allowed per node in the graph; higher M increases connectivity and memory usage.
- Cosine similarity: A measure of similarity between two vectors based on the cosine of the angle between them, commonly used in vector search.
- Priority queue: A data structure that always extracts the highest-priority element first; used here to explore the most promising neighbors first.
Reader FAQ
What is HNSW in simple terms?
HNSW is a layered graph approach that narrows search from broad, sparsely connected levels to dense local connections, avoiding full dataset scans.
How do ef and M affect results?
ef increases the candidate set explored during search (trade-off: accuracy vs cost); M limits per-node connections and impacts memory and graph navigability.
Is there a PHP implementation to inspect?
Yes — the article references the Vektor project on GitHub for the full implementation: https://github.com/centamiv/vektor.
Does this guarantee exact nearest neighbors?
Not explicitly confirmed in the source.
Hierarchical Navigable Small World (HNSW) in PHP Or: How to find a needle in a haystack without checking all the hay In the previous article we saw how vectors can…
Sources
- Implementing HNSW (Hierarchical Navigable Small World) Vector Search in PHP
- Implementing HNSW (Hierarchical Navigable Small World) …
- centamiv/vektor: A native PHP Vector Database …
- Hierarchical Navigable Small Worlds (HNSW)
Related posts
- 2025 Letter: Silicon Valley’s seriousness and San Francisco’s contradictions
- Build a Simple Deep Learning Library from Scratch with NumPy and Autograd
- OpenWorkers: Rust-based self-hosted runtime for Cloudflare Workers