HNSW Vector Search Explained: How AI Memory Retrieval Works

HNSW (Hierarchical Navigable Small World) is the algorithm that makes sub-millisecond vector search possible at scale. It builds a layered graph where each layer is a progressively sparse network of vector nodes — queries start at the top (sparse) layer and greedily navigate down to the bottom (dense) layer to find approximate nearest neighbors. Feather DB's HNSW implementation delivers 0.19ms p50 retrieval at 97.2% recall@10 on a 500,000-node index, which means memory lookups in an AI agent add less than 1ms to the agent's response time.

The Problem HNSW Solves

Finding the nearest vector to a query in a database of 500,000 vectors by brute-force comparison would require computing cosine similarity 500,000 times. At modern hardware speeds, this takes roughly 50–200ms per query — too slow for an agent making 8 memory lookups per turn. The alternative is a tree-based index (KD-tree, ball tree), but these fail at high dimensions (the curse of dimensionality: at 1,536 dimensions, every point is roughly equidistant from every other).

HNSW solves both problems: it reduces the number of comparisons from N (brute force) to O(log N) by navigating a graph structure, and it works in high-dimensional spaces because it does not partition space geometrically.

How HNSW Works: The Layered Graph Structure

Layer 0: The Complete Graph (Dense Layer)

The base layer (layer 0) contains every node in the index. Each node has edges to its M nearest neighbors, where M is the HNSW parameter for the number of bidirectional connections per node. For a 500K-node index with M=16, each node has up to 16 edges, and the total edge count is roughly 8M (each edge counted once).

Layer 0 is the precision layer — the most thorough search happens here. Queries end at layer 0 and traverse a local neighborhood to find the true approximate nearest neighbors.

Upper Layers: Navigable Small World Shortcuts

Upper layers (1, 2, 3...) contain progressively fewer nodes. Each layer is a subset of the layer below, sampled with exponentially decreasing probability. A node appears in layer k with probability:

# HNSW layer assignment during insert
import math
import random

def assign_layer(m_l: float) -> int:
    """Assign a node to layers 0..L where L is geometrically distributed."""
    return int(-math.log(random.random()) * m_l)

# m_l is typically 1/ln(M) where M is the number of connections per layer
# With M=16: m_l = 1/ln(16) = 0.361
# Most nodes (63%) appear only in layer 0
# ~23% appear in layers 0 and 1
# ~8% appear in layers 0, 1, and 2
# etc.

The upper layers act as "highways" — they allow the search to jump quickly across large distances in vector space before zooming in. This is the "navigable small world" property: any two nodes can be reached in O(log N) hops.

Search Algorithm: Top-Down Greedy Navigation

HNSW search works top-down:

1. Start at the entry point (a fixed node in the topmost layer).
2. Greedily navigate toward the query: move to whichever neighbor is closer to the query vector.
3. When no neighbor is closer than the current node, move down one layer.
4. Repeat from step 2 at the new layer, starting from the best node found above.
5. At layer 0, expand the search to ef candidates (the ef_search parameter) and return the top k.

# Conceptual HNSW search pseudocode
def hnsw_search(query_vector, k=10, ef_search=100):
    # Start at entry point in top layer
    entry_point = get_entry_point()
    current_layer = max_layer

    # Greedy navigation through upper layers
    current_best = entry_point
    for layer in range(current_layer, 0, -1):
        changed = True
        while changed:
            changed = False
            for neighbor in get_neighbors(current_best, layer):
                if distance(neighbor, query_vector) < distance(current_best, query_vector):
                    current_best = neighbor
                    changed = True

    # Beam search at layer 0 with ef_search candidates
    candidates = beam_search(current_best, query_vector, ef=ef_search, layer=0)

    # Return top k closest
    return sorted(candidates, key=lambda n: distance(n, query_vector))[:k]

HNSW Parameters: M and ef

HNSW has two primary tuning parameters that govern the accuracy/speed trade-off:

Feather DB Default Parameters

Feather DB uses tuned defaults for agent memory workloads:

• M = 16: Good balance of recall and memory efficiency for 1,536-dimension embeddings
• ef_construction = 200: High-quality index build for agent memory (insert latency is less critical than query latency)
• ef_search = 100: Delivers 97.2% recall@10 at 0.19ms p50

import feather_db as fdb

# Configure HNSW parameters (optional — defaults work for most use cases)
db = fdb.FeatherDB(
    path="agent_memory.feather",
    hnsw_m=16,              # Edges per node
    hnsw_ef_construction=200,  # Build quality
    hnsw_ef_search=100      # Query recall target
)

# For higher recall at the cost of latency:
high_recall_db = fdb.FeatherDB(
    path="agent_memory_hq.feather",
    hnsw_m=32,
    hnsw_ef_construction=400,
    hnsw_ef_search=200
)  # ~0.35ms p50, 99%+ recall@10

# For lower latency at slight recall trade-off:
low_latency_db = fdb.FeatherDB(
    path="agent_memory_fast.feather",
    hnsw_m=8,
    hnsw_ef_construction=100,
    hnsw_ef_search=50
)  # ~0.08ms p50, ~93% recall@10

HNSW Performance at Scale: 500K Vectors

Feather DB's benchmark results on a 500K-node index with 1,536-dimension OpenAI embeddings (text-embedding-3-small):

At the default ef_search=100, HNSW delivers 97.2% recall at 0.19ms — 273x faster than brute force with only 2.8% recall loss. For agent memory workloads where the retrieved memories are not ground-truth answers but contextual inputs, 97.2% recall@10 is effectively lossless: the probability of missing a critical memory on any given query is under 3%, and the graph traversal layer (context_chain()) often catches these edge cases via related node traversal.

HNSW vs Other ANN Algorithms

How Feather DB Extends HNSW with BM25 and Decay

Pure HNSW retrieves by vector similarity alone. Feather DB adds two layers on top:

Layer 1: BM25 Fusion (Hybrid Search)

BM25 is a lexical ranking algorithm that scores documents by term frequency and inverse document frequency. When a query contains exact terms (function names, error codes, identifiers), BM25 often ranks the correct memory higher than cosine similarity alone. Feather DB runs both HNSW and BM25 searches independently, then fuses their ranked lists using Reciprocal Rank Fusion (RRF):

# Reciprocal Rank Fusion formula
def rrf_score(rank: int, k: int = 60) -> float:
    return 1.0 / (k + rank)

# RRF fuses the two ranked lists:
# final_score[doc] = rrf_score(hnsw_rank) + rrf_score(bm25_rank)
# Documents appearing high in both lists get highest combined score

Layer 2: Adaptive Temporal Decay

After RRF fusion, Feather DB applies temporal scoring:

# Applied after HNSW + BM25 RRF fusion:
stickiness    = 1 + log(1 + recall_count)  # Reward for frequent recall
effective_age = age_in_days / stickiness
recency       = 0.5 ^ (effective_age / half_life_days)
final_score   = ((1 - time_weight) * rrf_score + time_weight * recency) * importance

This makes memories that are semantically relevant AND temporally current rank highest, with frequently recalled memories resisting age decay. No other vector database applies this scoring model automatically.

Practical Tuning Guide

For agent memory (default use case):

db = fdb.FeatherDB("memory.feather")  # Use defaults: M=16, ef_search=100
# 0.19ms p50, 97.2% recall — optimal for agent memory

For large indexes (1M+ vectors):

db = fdb.FeatherDB(
    "large_memory.feather",
    hnsw_m=32,              # More connections for better navigation at scale
    hnsw_ef_construction=300
)
# Slightly larger memory footprint, better recall at 1M+ nodes

For edge/mobile (memory-constrained):

db = fdb.FeatherDB(
    "edge_memory.feather",
    hnsw_m=8,               # Fewer connections = less memory
    hnsw_ef_search=40,      # Faster queries, ~92% recall
    quantization="int8"     # 4x memory reduction via quantization (v0.16)
)

FAQ

What does HNSW stand for and who invented it?

HNSW stands for Hierarchical Navigable Small World. It was introduced by Malkov and Yashunin in a 2016 paper ("Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs"). It became the dominant ANN algorithm by 2019 and is now the standard for production vector databases.

Why is HNSW faster than tree-based indexes for high-dimensional vectors?

Tree-based indexes (KD-tree, ball tree) partition space geometrically. At high dimensions (512+), the partitions become meaningless — almost every point lies near every partition boundary, requiring the search to explore exponentially many branches. HNSW avoids this by navigating a graph rather than partitioning space.

What is the memory cost of an HNSW index?

With M=16, each node requires approximately (M * 2 * 4 bytes) = 128 bytes of edge data, plus the vector itself (1536 floats * 4 bytes = 6KB). A 500K-node index with 1536-dim vectors requires approximately 3.1 GB for vectors + 64 MB for edges = ~3.2 GB total without quantization. With int8 quantization, the vector portion drops to ~0.8 GB.

Does HNSW support dynamic inserts?

Yes. Unlike some ANN algorithms (Annoy, IVF), HNSW supports dynamic inserts without rebuilding the index. New nodes are inserted by finding their neighbors in the graph and adding edges. Feather DB uses dynamic HNSW — you can add memories at runtime with no rebuild required.

What is the difference between recall@10 and accuracy?

Recall@10 measures how often the true 10 nearest neighbors appear in the ANN algorithm's top-10 results. A recall@10 of 97.2% means that on average, 9.72 of the true 10 nearest neighbors are returned. For agent memory, this means 97.2% of the most relevant memories are retrieved correctly — the 2.8% miss rate is further mitigated by graph traversal covering adjacent nodes.