HNSW Indexing
Relevant source files
The following files were used as context for generating this wiki page:
HNSW (Hierarchical Navigable Small World) Indexing serves as the primary algorithm for approximate nearest neighbor (ANN) search within EdgeVec. It provides $O(\log n)$ search and insertion complexity, enabling high-performance vector retrieval in browser-native environments. The implementation is designed to be deterministic and memory-efficient, maintaining a per-vector overhead of approximately 82 bytes.
Sources: GATE_1_COMPLETE.md:105-107, README.md:175-188, CONTRIBUTING.md:143-145
Architecture and Components
The HNSW Indexing system is structured as a multi-layered graph where each layer is a subset of the layer below it. This hierarchical structure allows for rapid navigation to the proximity of a query point in higher layers before performing a fine-grained search in lower layers.
Core Structures
The system relies on several key data structures to manage the graph and its metadata:
| Structure | Description |
|---|---|
HnswIndex | The primary coordinator for graph navigation, layer management, and neighbor updates. |
VectorStorage | An arena-based contiguous allocator for SIMD-friendly vector data and tombstone bitmaps. |
HnswConfig | Stores parameters such as dimensions, $M$ (max neighbors), and $ef_construction$. |
HnswNode | Represents a single point in the graph, containing links to neighbors across different layers. |
Sources: GATE_1_COMPLETE.md:105-115, GATE_1_COMPLETE.md:38-46, examples/filter_persistence.rs:18-24
Component Interaction
The following diagram illustrates the relationship between the index, the storage layer, and the configuration.
The HNSW Index layer manages the graph logic while offloading physical vector management to VectorStorage. Sources: GATE_1_COMPLETE.md:105-115, CONTRIBUTING.md:173-181
Search Logic
EdgeVec implements a navigable small-world search that descends through layers. It uses a FilteredSearcher when metadata filters are provided, allowing the index to skip nodes that do not satisfy the criteria while navigating the graph.
Search Process Flow
The search starts at the entry point of the highest layer and proceeds greedily until the local optimum is found at the current layer, then moves down.
At Layer 0, the searcher maintains a candidate list of size $ef$ to ensure high recall, eventually returning the top $k$ results. Sources: README.md:135-145, fuzz/FUZZING_STRATEGY.md:105-110, examples/filter_persistence.rs:75-85
Insertion and Graph Construction
Insertion in HNSW involves determining the maximum layer for a new node using a deterministic RNG and then connecting it to the nearest neighbors in each layer from its maximum layer down to Layer 0.
Insertion Algorithm
- Layer Assignment: A random layer is assigned using an exponentially decaying probability distribution.
- Pathfinding: The algorithm navigates from the top layer to the assigned layer to find the nearest entry point.
- Neighbor Linking: At each layer from the assigned layer down to 0, the nearest neighbors are found and mutual links are established.
- Link Pruning: If a node exceeds the maximum allowed neighbors ($M$), links are pruned using a heuristic to maintain graph connectivity.
Sources: GATE_1_COMPLETE.md:105-110, CONTRIBUTING.md:108-115, fuzz/CORPUS_METHODOLOGY.md:46-52
Data Layout Invariants
To ensure compatibility and performance, the implementation enforces strict memory layout invariants via const_assert!.
const_assert!(size_of::<HnswConfig>() == 32);
const_assert!(size_of::<SectionHeader>() == 24);
const_assert!(align_of::<VectorId>() == 8);
Sources: GATE_1_COMPLETE.md:125-130, GATE_1_COMPLETE.md:38-45
Soft Delete and Compaction
EdgeVec implements a "soft-delete" mechanism using tombstones. This allows for $O(1)$ deletion by marking a vector as deleted in a bitmap without immediately restructuring the HNSW graph.
Compaction Workflow
When the tombstone ratio exceeds a threshold (e.g., in needs_compaction), the system can trigger a compaction. This process reclaims space by physically removing deleted nodes and re-indexing the remaining ones.
Performance and Verification
The HNSW implementation is subject to "Nvidia Grade" verification, requiring extensive testing for both correctness and recall.
| Test Layer | Requirement | Source |
|---|---|---|
| Recall Test | 95% threshold on SIFT dataset | CONTRIBUTING.md:158 |
| Property-Based | Verify invariants (8+ tests) | CONTRIBUTING.md:160 |
| Fuzzing | No panics on adversarial input | fuzz/FUZZING_STRATEGY.md:12-18 |
| Miri | Verify memory safety | GATE_1_COMPLETE.md:70 |
The search latency target for 100k vectors is <10ms P99, and the implementation uses SIMD-accelerated distance calculations (Dot Product, L2, Hamming) to achieve these goals on supported browsers. Sources: GATE_1_COMPLETE.md:135-140, README.md:110-120, Cargo.toml:195-200
Summary
HNSW Indexing in EdgeVec provides a robust, hierarchical graph-based approach to vector search optimized for WebAssembly. By combining navigable small-world logic with arena-based storage, metadata filtering, and a soft-delete mechanism, it delivers server-grade features directly to client-side applications while maintaining strict performance and memory budgets.