FeOx ANN

HNSW approximate nearest neighbor search for Rust. Deterministic builds, SIMD distance kernels, zero dependencies.

Documentation | FeOxDB | Issues

Part of the FeOx family. For a persistent vector store with metadata filtering, see feox-vector, built on FeOxDB and this index.

Features

• SIMD Distance Kernels: NEON on aarch64, AVX2+FMA on x86_64 with runtime detection, scalar fallback elsewhere. Four-accumulator fused multiply-add loops, written as intrinsics so LLVM can inline them into the search loops.
• Deterministic Builds: Node levels come from a stable hash of the record id. The same records in the same order produce the same graph, every time. See Why Deterministic Builds.
• Parallel Bulk Load: bulk_load() runs candidate searches on worker threads against a frozen graph and applies the results in fixed order. No locks, no shared mutable state, and the output does not depend on the thread count: 1 thread and 16 threads produce identical graphs.
• Checksummed Persistence: save_to() / load_from() write a compact binary snapshot (FXA1) with a CRC32 integrity check and fsync on save. Corrupted or truncated snapshots are rejected. save_in_background() snapshots without blocking.
• Concurrent Queries: Queries take &self and use thread-local scratch buffers. Zero allocation per query, no coordination between readers.
• Diversity-Heuristic Neighbor Selection: Links are selected with the HNSW paper's diversity heuristic, then backfilled to the degree limit. This yields far higher recall per edge than plain top-M selection.
• Zero Dependencies: thiserror only.
• Cosine Similarity: Vectors are normalized on insert and scored with the SIMD dot product.
• Filtered Search: Pass any Fn(&str) -> bool closure (or AnnFilter impl) to restrict results at query time.
• Soft Deletes and Upserts: Deletes tombstone nodes without a rebuild. Upserts replace visible records in place.
• Multi-Entry-Point Search: Keeps a capped set of entry points and starts from the best one for each query. Improves recall on clustered data.

Quick Start

[dependencies]
feox-ann = "0.1"

use feox_ann::{AnnConfig, AnnIndex, AnnQuery};

fn main() -> feox_ann::Result<()> {
    let mut index = AnnIndex::new(AnnConfig::for_dimensions(384))?;

    index.upsert("doc-1".to_string(), &embedding_1)?;
    index.upsert("doc-2".to_string(), &embedding_2)?;

    let matches = index.query(AnnQuery {
        vector: &query_embedding,
        top_k: 10,
        ef_search: None,          // use the configured default
        filter: None,
    })?;

    for candidate in matches {
        println!("{} scored {:.4}", candidate.id, candidate.score);
    }
    Ok(())
}

Filtered search takes any closure over the record id:

let filter = |id: &str| allowed_ids.contains(id);
let matches = index.query(AnnQuery {
    vector: &query_embedding,
    top_k: 10,
    ef_search: Some(128),
    filter: Some(&filter),
})?;

Parallel bulk loading:

let threads = std::thread::available_parallelism().map(|t| t.get()).unwrap_or(1);
let mut index = AnnIndex::new(AnnConfig::for_dimensions(384))?;
index.bulk_load(records, threads)?;

Persistence:

index.save_to("/var/lib/myapp/docs.fxa")?;
let restored = AnnIndex::load_from("/var/lib/myapp/docs.fxa")?;

let handle = index.save_in_background("/var/lib/myapp/docs.fxa".into());

Tuning

AnnConfig::for_dimensions(d) gives sensible defaults (max_neighbors: 24, ef_construction: 160, ef_search: 64). The usual HNSW trade-offs apply:

Why Deterministic Builds

Classic HNSW assigns each node a level by sampling from a random number generator. Two builds of the same data produce two different graphs that answer some queries differently. The index becomes state with its own identity: you build it once, back it up, and distribute the artifact, because a rebuild will not reproduce it.

FeOx ANN derives the level from an FNV-1a hash of the record id, two bits per level, which follows the same geometric distribution in expectation. The graph is a pure function of the records and their insertion order. In production this means:

• Replicas agree. Servers that rebuild the index independently from the same records serve identical results. No artifact distribution, no answer drift between nodes behind a load balancer.
• Deploys are diffable. If retrieval changes after a rollout, the cause is the code change, never build randomness.
• Bugs reproduce. Rebuild from the source records and you get the exact graph that misbehaved, on any machine.
• Recall is testable. CI can assert an exact recall number. Tuning changes compare against a noise-free baseline.

Sequential builds of other HNSW libraries can be made reproducible with a fixed seed. Parallel builds cannot: per-node locking makes the graph depend on thread scheduling, with or without a seed. FeOx ANN keeps determinism at full parallel build speed.

Benchmarks

cargo bench                              # build + query latency
cargo run --release --example recall     # recall@10 vs exact ground truth

The criterion benches build a 10,000 x 128d index from a seeded generator and measure top-10 query latency at ef_search values of 32, 64, 128, and 256, plus a filtered variant and 1-thread vs N-thread builds. Deterministic inputs make the numbers comparable across machines and commits.

Reference numbers on Apple Silicon, single-threaded queries, 10k x 128d uniform random vectors. Random vectors are a worst case for ANN; real embeddings reach higher recall at the same ef:

Comparison

A reproducible head-to-head against usearch (SIMD C++ with Rust bindings) and instant-distance (pure Rust) lives in comparison/:

./comparison/run.sh    # downloads SIFT1M, builds, runs all three engines sequentially

SIFT1M: 1,000,000 x 128d SIFT descriptors, cosine similarity over normalized vectors, ground truth computed exactly, recall@10 over 500 queries. All engines configured with graph degree 24 and build breadth 160. Queries single-threaded, engines run one at a time. Apple Silicon.

Read the table as a recall/latency frontier. At 0.99 recall feox-ann answers in roughly 60% of usearch's time on this dataset, and at each latency point it reaches equal or higher recall than both. Build times differ in parallelism model and are listed for context only: feox-ann 237 s deterministic parallel on 16 threads, instant-distance 116 s with rayon, usearch 510 s through a single-threaded add loop. One dataset on one machine; run the harness on your own data before deciding.

Deletes and Rebuilds

delete() marks nodes as tombstones. They stop appearing in results immediately and remain in the graph as routing waypoints until you rebuild. For collections with heavy churn, rebuild periodically from the source of truth (feox-vector automates this with dirty tracking and background rebuilds). Snapshots preserve tombstones, so a saved and restored index behaves identically to the original.

Limitations

• In-memory graph: the index (vectors plus neighbor lists) lives in RAM. Snapshots persist it to disk, but querying requires loading it back. At roughly 4 bytes per dimension plus about 250 bytes of graph per record, 1M x 128d costs about 750 MB. Use a disk-native engine for datasets that exceed memory.
• Cosine similarity only: vectors are normalized on insert. No L2, no inner product on unnormalized vectors, no quantization. f32 only.
• Tombstones until rebuild: deletes hide records immediately but leave graph nodes in place. Heavy churn degrades the graph until you rebuild from source.
• Determinism is per architecture: NEON and AVX accumulate in different orders, so scores can differ in the last bit across CPU families. Same machine, same build: identical graphs and results.

License

Licensed under the Apache License, Version 2.0. See LICENSE.

Contributing

Contributions are welcome! See CONTRIBUTING.md.