EdgeVector

A header-only C++17 vector search library for edge devices: binary quantization + HNSW + memory-mapped storage in three headers, ~2,000 lines, zero dependencies — with a two-stage retrieval pipeline that reaches float32-exact accuracy from a 32x-compressed RAM index.

• 32x smaller vectors in RAM — 512-d float32 (2,048 B) quantizes to 64 B
• recall@10 = 0.995–1.000 against true float32 ground truth (embedding-like data, 100k vectors) via exact re-ranking at ~7,700 QPS single-thread, while RAM holds only the codes — the full-precision vectors can stay on flash and each query touches just ef of them
• Scale-validated at 1M vectors: 12-thread build in 72 s, 0.28 s startup, 64 MB of codes in RAM, recall@10 = 0.988 at 118 µs/query (~8,500 QPS, 1 thread) — 50x faster than an exact scan
• Memory-latency-aware traversal and an AVX2 Hamming kernel (software prefetching plus a nibble-LUT popcount, both gated bit-identical to naive references by tests): ~3x query speedup and 2.5x serial-build speedup over the unprefetched implementation, with recall unchanged to the last digit
• Zero-allocation queries, proven — every search mode is covered by tests that replace the global operator new and require zero allocations
• Concurrent queries and concurrent construction — per-thread SearchContext scratch pools for queries, and a striped-lock parallel build: 100k vectors in 7.9 s on 12 threads vs 64.3 s serial (8.1x), validated by a full referential-integrity sweep after every parallel build
• A fully dynamic index — soft deletion and filtered search (tombstones plus caller-supplied allow-bitmaps, composable, persisted in the graph file); slot reclamation for brand-new vectors in ~2.9 ms at 100k (remove → overwrite bytes → reinsert, zero dangling edges by construction); and growable capacity (grow() extends the id space and rebinds a relocated vector block, preserving every existing link)
• Selectivity-adaptive filtering — sparse filters switch to an exact scan of the allowed set: recall 1.000 at 7 µs/query for a 0.1% filter (faster than unfiltered search), while dense filters keep routed traversal (0.998 recall at 10%)
• ~0.05 s startup at 100k vectors — mmap the codes, load the prebuilt graph (~1,400x faster than rebuilding)
• Learned ITQ rotation for anisotropic (real-embedding-shaped) data: +21 recall points at the same beam width, or the same accuracy at a fraction of the compute — while preserving cosine exactly
• CI-validated on every push across Linux gcc + clang, Windows (MinGW-w64), and native arm64 silicon — where the benchmark runs on real ARM hardware: 0.995 float-recall at 166 µs/query (~6,000 QPS, 1 thread) — plus ASan/UBSan on all suites and ThreadSanitizer on the concurrent build, debug and -DNDEBUG, always -Wall -Wextra -Werror

The accuracy architecture

Ranking by Hamming distance alone is coarse: distances are small integers with massive ties, and 1-bit codes discard the query's magnitudes. EdgeVector layers three search modes over one Hamming-navigated graph:

Mode	Ranks by	Extra memory	Use when
search()	Hamming distance	none	binary similarity is the target metric
search_reranked()	asymmetric score dot(q_float, sign(x)), ADC-style per-byte tables	none (64 KB per-query table, pre-allocated)	float query available, floats for the corpus are not
search_exact_reranked()	true float32 cosine over the ef-candidate pool	corpus floats readable (flash/mmap is the intent; ~ef·dim·4 bytes touched per query)	you want float-exact results from a code-sized RAM index

Measured performance

100,000 × 512-d vectors, M = 16, ef_construction = 200, k = 10, single thread (i7-1355U, WSL2/Linux, g++ 13, -O3 -march=native -DNDEBUG). Recall is measured against exact float32 cosine ground truth — the number an application actually experiences — and against exact binary ground truth (the graph in isolation). Reproduce with make -C tests bench.

Clustered data (embedding-like, 1,000 clusters)

ef	recall@10 (binary GT)	float GT, Hamming rank	float GT, asym re-rank	float GT, exact re-rank	lat Hamming	lat asym	lat exact
10	0.899	0.262	0.262	0.262	10 µs	20 µs	19 µs
25	0.992	0.264	0.319	0.514	24 µs	33 µs	40 µs
50	1.000	0.264	0.328	0.775	42 µs	50 µs	72 µs
100	1.000	0.264	0.330	0.995	69 µs	78 µs	130 µs
200	1.000	0.264	0.330	1.000	158 µs	169 µs	295 µs

Read the last column: ~7,700 QPS single-thread at 99.5% float-exact recall from a RAM index 32x smaller than the float vectors. The graph itself is essentially perfect (binary-GT recall 1.000 from ef = 50); the Hamming-rank column shows the 1-bit representation ceiling that re-ranking removes.

Quantized vectors (RAM)	6.4 MB (float32 equivalent: 204.8 MB — 32x)
Graph links + scratch	15.0 MB
Build (one-time): 1 thread / 12 threads	25.8 s / 7.6 s (integrity-validated)
Reclaim one slot (remove + relink new vector)	2.4 ms (avg of 100, integrity-validated)
Load prebuilt graph at startup	0.033 s (~780x faster than rebuilding)

1M vectors: the scale check

Same recipe at 1,000,000 × 512-d (clustered), single-thread queries:

Build (insert_batch, 12 threads, integrity-validated)	71.9 s
Load prebuilt graph at startup	0.28 s
Quantized vectors (RAM)	64 MB (float32 equivalent: 2,048 MB)
Graph links + scratch	150 MB
Exact binary scan baseline	5.90 ms/query (169 QPS)

ef	recall@10 (binary GT)	mean latency	QPS (1 thread)
10	0.528	21 µs	48,152
50	0.936	75 µs	13,289
100	0.988	118 µs	8,475

(Float32-truth metrics at 1M are omitted — the exact ground truth would need 2 GB of resident floats; the 100k tables above carry the accuracy story, this one carries scale.)

Filtered search: selectivity-adaptive

A sparse allow-bitmap makes graph traversal the wrong algorithm (too few eligible nodes ever fill the beam), so while popcount(allow) ≤ max(16·ef, capacity/8) the search switches to a zero-allocation exact scan of the allowed set — cheaper than the degraded walk and recall-1.0 by construction. The crossover was measured, not guessed: scanning wins up to ~15–20% selectivity (at 2%, the scan is 88 µs/1.000 recall vs 6,654 µs/0.989 for forced traversal), so the default switches at 12.5% of capacity; set_filter_scan_limit() overrides it. Measured at 100k vectors, ef = 100, k = 10, against exact filtered ground truth (arm64 CI runner, single thread):

selectivity	allowed ids	recall@10	mean latency	QPS (1 thread)
0.1%	100	1.000	7 µs	145,744
1%	1,000	1.000	30 µs	33,171
10%	10,000	0.998	745 µs	1,342

The sparse rows take the exact-scan path — note they are faster than unfiltered search (7 µs vs 72 µs at ef = 100 on the same runner). The 10% row exercises the routed graph traversal. Tests gate the scan path equal to brute force on ids and distances both.

xychart-beta
    title "recall@10 vs float32 truth (100k clustered vectors, 512-d)"
    x-axis "ef" [10, 25, 50, 100, 200]
    y-axis "recall@10" 0 --> 1
    line "Hamming ranking" [0.262, 0.264, 0.264, 0.264, 0.264]
    line "asymmetric re-rank" [0.262, 0.319, 0.328, 0.330, 0.330]
    line "exact re-rank" [0.262, 0.514, 0.775, 0.995, 1.000]

Loading

The honest caveat: iid random data

The benchmark's second scenario is 100k structureless iid Gaussian vectors — the known adversarial case for every ANN index: with no manifold to exploit, high-dimensional distances concentrate (σ/µ ≈ 4% at 512 bits) and graph navigation loses its gradient.

ef	recall@10 (binary GT)	float GT, Hamming rank	float GT, asym re-rank	float GT, exact re-rank
50	0.075	0.016	0.026	0.030
100	0.134	0.024	0.046	0.061
200	0.231	0.034	0.071	0.110

Low absolute numbers here are the nature of the data, not a defect (it is why standard ANN benchmarks use real embeddings rather than noise) — but note the re-ranking ladder still triples the float-truth recall at every beam width. Real embedding data behaves like the clustered scenario. Both tables ship in the benchmark so you can judge for yourself.

ITQ rotation: better bits for anisotropic data

Sign quantization spends exactly one bit per dimension, but real embedding spectra decay — most of the energy lives in a few directions, so most bits measure noise. itq_rotation.hpp implements Iterative Quantization (Gong & Lazebnik, 2011): a learned orthogonal rotation that spreads variance evenly across dimensions before quantizing. Deliberately rotation-only — no centering, no PCA — so cosine similarity is preserved exactly: float32 ground truth is unchanged, and search_exact_reranked() can re-rank with the original floats and query even over a rotated index.

Measured at 50k × 512-d vectors with an exp(-4d/512) decaying spectrum (recall@10 vs float32 truth; rotation trained on a 5k subsample in 21 s, orthogonality residual 1.2e-8):

ef	raw Hamming	ITQ Hamming	raw asym	ITQ asym	raw exact	ITQ exact
25	0.290	0.500	0.389	0.569	0.619	0.846
100	0.290	0.500	0.418	0.570	1.000	1.000

Two readings: at fixed ef the codes get much better (+21 points on Hamming ranking); at fixed accuracy the exact-re-rank pipeline needs a far narrower beam (0.846 at ef = 25 vs 0.619 without). Training is deterministic for a fixed seed — bit-identical matrices, verified across x86-64 and AArch64 — and the polar-decomposition solver (inverse-free Newton–Schulz, double precision, spectrally pre-scaled) reports failure rather than silently degrading. The EVRT rotation file format validates magic, version, dimension, exact length, finiteness, and orthogonality on load.

When EdgeVector is the right choice — even over Faiss

Each of these maps to a property this repo demonstrates, not a marketing claim. The pattern: EdgeVector wins wherever trust, footprint, or portability constraints dominate raw throughput.

1. Regulated / certified firmware (IEC 62304 medical, ISO 26262 automotive, aerospace, industrial safety) — the strongest case. Every third-party line must be reviewed and justified; a dependency is a certification liability. This is ~2,600 vendorable lines with no exceptions on the query path, no allocation after load (proven by instrumented tests — the kind of evidence a safety review wants), and every file format validated against corrupt input. Faiss brings BLAS, OpenMP, and a build system to that meeting.
2. Hard-real-time query paths (robotics control loops, audio pipelines) where a malloc-induced latency spike or an allocator lock is a correctness bug. The zero-allocation, zero-syscall, noexcept search is a tested contract here, not a happenstance. (Caveat: kernels are compiler-vectorized, not hand-tuned SIMD — profile if you need peak throughput too.)
3. Fleet devices that reboot often on tiny RAM budgets (smart cameras, retail edge boxes, on-device RAG caches): mmap the 64 B/vector codes, load the prebuilt graph in ~0.05 s, keep float vectors on flash and touch only ~ef of them per query — a ~6 MB working set at 100k × 512-d with float-exact results.
4. Air-gapped and supply-chain-sensitive builds: vendor four headers and the entire supply chain is the diff you reviewed — no package manager, no transitive CVE feed.
5. Exotic toolchain targets (WASM, RTOS, unikernels): header-only C++17 with the platform layer confined to one file, and the graph works over any in-memory block if mmap does not exist at all.
6. Teaching, research baselines, and forkable foundations: modifying 2,600 documented lines guarded by recall, integrity, and allocation gates beats reverse-engineering a large library's internals, and the published adversarial benchmark makes it a clean experimental control.

When to say no: server-side workloads with big RAM, GPUs, billions of vectors, or a need for bindings and ops tooling — use Faiss, USearch, or a vector database. And across all six cases above: ARM is validated for correctness, not yet performance — run make -C tests bench on your actual silicon (the Makefile's ARCH/RUNNER knobs make that a ten-minute job) before committing a product.

Getting it into your project

Three routes, all ending at #include <edgevector/edgevector.hpp> (one umbrella header; or include the individual headers you use). Requires GCC or Clang with C++17 — MSVC is not supported.

1. Vendor the headers (firmware-style). Copy include/edgevector/ into your tree, add the directory to your include path. Done — there is nothing to link.

2. CMake FetchContent:

include(FetchContent)
FetchContent_Declare(edgevector
  GIT_REPOSITORY https://github.com/JonathanKash/EdgeVector.git
  GIT_TAG v0.8.0)        # or a commit hash, or main for latest
FetchContent_MakeAvailable(edgevector)
target_link_libraries(your_app PRIVATE edgevector::edgevector)

3. CMake subdirectory: vendor the repo and add_subdirectory(EdgeVector); the same edgevector::edgevector target appears.

Then start from examples/quickstart.cpp — a complete, runnable, self-checking tour of the whole pipeline (quantize → multi-threaded build → persist → reload → all three search modes → filtering → deletion → slot reclamation), built and executed by CI on every push so it can never drift from the library:

make -C examples run                                  # or:
cmake -B build -DEDGEVECTOR_BUILD_EXAMPLES=ON && cmake --build build && ./build/quickstart

Compile flags that matter: -O2 -march=native (or -march=armv8-a when cross-compiling) so the Hamming kernel gets POPCNT/AVX2 or NEON. EDGEVECTOR_VERSION in edgevector.hpp identifies the vendored version.

Quick start

Everything is three #includes; no linking, no build step for the library itself.

#include "edgevector/quantize_math.hpp"
#include "edgevector/mmap_storage.hpp"
#include "edgevector/hnsw_graph.hpp"
using namespace edgevector;

const std::size_t dim = 512;
const std::uint32_t n  = /* vector count */;
const std::size_t rb   = padded_bytes(dim);   // 64 bytes at dim = 512

// ---- Index build (offline, allocation allowed) --------------------------
std::vector<std::uint64_t> buf((rb / 8) * n);          // 8-byte aligned block
auto* base = reinterpret_cast<std::uint8_t*>(buf.data());
for (std::uint32_t i = 0; i < n; ++i)
    quantize(float_vectors[i], dim, base + i * rb);    // bit i = (x[i] > 0)
write_storage_file("index.evec", dim, n, base);

HNSWGraph builder(base, rb, dim, n);                   // M=16, efC=200 defaults
std::vector<std::uint32_t> ids(n);
std::iota(ids.begin(), ids.end(), 0u);
builder.insert_batch(ids.data(), n, 0);                // 0 = all hardware threads
// (or serial, deterministic: for (auto id : ids) builder.insert(id);)
builder.save_graph("index.evhg");

// ---- Device startup (no rebuild: map codes, load graph) -----------------
MMapStorage store;
store.open("index.evec");                              // zero-copy mmap
HNSWGraph graph(store.vector(0), store.record_bytes(),
                static_cast<std::size_t>(store.dim()),
                static_cast<std::uint32_t>(store.count()));
graph.load_graph("index.evhg");                        // ~0.05 s at 100k

// ---- Query (hot path: zero allocation, noexcept) ------------------------
alignas(8) std::uint8_t q[64];
quantize(query_floats, dim, q);

SearchResult by_hamming[10];
graph.search(q, /*k=*/10, /*ef=*/50, by_hamming);

// Float-exact results while RAM holds only the codes: `corpus_floats` can be
// your own read-only mmap of the raw float file - each query touches just
// the ef candidates it re-ranks.
ScoredResult best[10];
graph.search_exact_reranked(q, query_floats, corpus_floats, dim,
                            /*k=*/10, /*ef=*/100, best);

// ---- Concurrency, deletion, filtering -----------------------------------
SearchContext ctx = graph.make_context();  // one per querying thread
graph.search(ctx, q, 10, 50, by_hamming);  // thread-safe on a const graph

graph.remove(42);                          // tombstone: gone from results,
graph.restore(42);                         //   still routes; persisted (v2)

// Slot reclamation: replace a dead slot's vector with a brand-new one.
graph.remove(42);
quantize(new_floats, dim, base + 42 * rb); // caller overwrites the bytes...
graph.reinsert(42);                        // ...then the graph relinks: ~3 ms
                                           //   at 100k, no dangling edges

// Growable capacity: enlarge (or relocate) YOUR vector block first, then
// hand the graph the new base. Existing links are untouched; the new ids
// become insertable (insert_batch works). Contexts created before a grow
// safely return 0 results - recreate them with make_context().
buf.resize((rb / 8) * 2 * n);              // caller grows the block...
base = reinterpret_cast<std::uint8_t*>(buf.data());
graph.grow(2 * n, base);                   // ...graph extends and rebinds

std::vector<std::uint64_t> allow((n + 63) / 64, 0);
// ... set one bit per permitted id ...
graph.search(ctx, q, 10, 50, by_hamming, allow.data());

// ---- Optional: ITQ rotation for anisotropic embedding data --------------
#include "edgevector/itq_rotation.hpp"
ItqRotation rot(dim);
rot.train(corpus_floats, n, dim);          // offline; deterministic per seed
rot.save("rotation.evrt");                 // ship next to the index files
// Index build: quantize rotated vectors; query: rotate first, then quantize.
std::vector<float> tmp(dim);
rot.rotate_quantize(query_floats, tmp.data(), q);
// exact re-rank still takes the ORIGINAL floats: rotation preserves cosine.

Architecture

Header	Role
quantize_math.hpp	float32 → 1 bit/component sign quantization; Hamming distance with an AVX2 nibble-LUT popcount path and an ILP-unrolled portable path (both test-gated bit-identical to a naive per-bit reference); SimHash cosine estimator; asymmetric ADC scorer (per-byte lookup tables for dot(q_float, sign(x)))
mmap_storage.hpp	Validated on-disk vector format (EVEC v1) and a zero-copy, read-only mmap reader. POSIX primary; Win32 shim confined to detail:: for development
hnsw_graph.hpp	HNSW (Malkov & Yashunin) over the quantized block: build with heuristic neighbor selection + keep-pruned backfill; three zero-allocation search modes with software-prefetched traversal (beam search is memory-latency bound; issuing the neighbor loads early is worth ~3x); per-thread SearchContexts; soft-delete tombstones and allow-bitmap filtering; validated graph persistence (EVHG v2, loads v1)
itq_rotation.hpp	Learned ITQ rotation (rotation-only, cosine-preserving): double-precision training with an inverse-free Newton–Schulz Procrustes solver; allocation-free rotate()/rotate_quantize(); validated EVRT persistence

Engineering rules the code holds itself to (and tests enforce):

• No allocation on the query path. Visited-epoch arrays, both heaps, the ADC table, and the re-rank buffer are pre-allocated in the SearchContext; heaps are raw arrays with explicit size counters. The test suites replace the global operator new and fail if a single allocation occurs in any search mode — including searches served directly from an mmaped file.
• No aliasing tricks. Bytes cross into uint64_t via std::memcpy only; on-disk headers are never reinterpret_cast to structs.
• Deterministic ordering. All comparisons tie-break by (distance, id) — or (score, id) after re-ranking — so results are reproducible and exactly comparable to brute-force baselines.
• Every failure is a status value. No exceptions; a failed graph load leaves the graph empty, never half-populated, and every load is fully validated (magic, version, parameter compatibility, per-node level/count bounds, referential integrity of every edge, tombstone integrity, exact file length).

Formats are little-endian and documented byte-by-byte in the headers.

Build and test

Requires g++ or clang with C++17 (uses __builtin_popcountll; MSVC not supported). Linux, WSL, or MinGW-w64 on Windows.

cd tests
make run          # 6 test suites, asserts enabled
make run-release  # same suites under -DNDEBUG
make bench        # the benchmarks reported above (-DNDEBUG; pass a scenario
                  # to the binary: ./benchmark_100k clustered|random|itq)

The suites cover: quantization bit-exactness and padding hygiene, cosine parity gates, Hamming-kernel equivalence (AVX2 and portable paths gated bit-identical to a naive per-bit reference across five dimension shapes), ADC-table exactness against a naive dot(q, sign(x)), storage round-trips and header-corruption rejection, mapped record alignment, HNSW recall gates at two scales, result ordering, the re-ranking accuracy ladder against float32 ground truth, graph persistence round-trips (bitwise-identical results and surviving tombstones after reload), context isolation plus a 4-thread concurrency test, delete/restore/filter composition, slot reclamation (new-vector serving, no-dangling-edge integrity after churn of 100 slots, full entry-point turnover, single-node bootstrap), deterministic fuzzing of all three format loaders (6,000 mutated/truncated/extended files per run, under ASan in CI: rejected files must leave objects empty, accepted files must satisfy full structural invariants), growable capacity (2x growth with a relocated block, parallel fill of the new region, stale-context invalidation, persistence at the new capacity), ITQ invariants (orthogonality, exact cosine preservation, monotone objective, determinism, hostile-file rejection, end-to-end recall gain), concurrent construction (single-thread batch bit-identical to serial insert; 4-thread build passing the full referential-integrity sweep and the recall gate), and the zero-allocation proof for all three search modes.

AArch64: validated on real arm64 silicon in CI on every push (the Hamming kernel compiles to NEON cnt), with the clustered benchmark run on hardware and uploaded as an artifact. Measured there (4-core runner, single- thread queries): 0.995 float-exact recall@10 at 166 µs/query, 4-thread build of 100k vectors in 9.5 s, slot reclaim 1.8 ms, graph load 0.018 s — and every recall figure bit-identical to x86-64. tests/arm64.Dockerfile reproduces the ARM run locally under QEMU when no ARM hardware is at hand.

Status and roadmap

v0.8. Known limitations, in priority order:

1. Dynamic operations are serial — reinsert (~2.9 ms each at 100k; O(total links) by design, exhaustive unlinking over heuristic repair) and grow must not run concurrently with queries or builds, and a grow invalidates outstanding SearchContexts (their searches safely return 0 until recreated). Growing the vector block itself is the caller's job — an mmap'ed block means writing and remapping a larger file
2. Filters between ~12.5% and ~50% selectivity pay a traversal penalty — below the measured crossover the exact scan is both faster and perfect; above ~50% the beam barely notices; the band between runs the routed walk with a partially-filled beam (recall ~0.94–0.98 at a few-fold latency cost). An ACORN-style two-hop expansion was evaluated and rejected: it targets recall (already ≥0.94 here) at the price of latency (the actual cost), so it does not earn its complexity
3. Parallel builds are nondeterministic in link structure (insertion order interleaves); use serial insert() or insert_batch(..., 1) when bit-reproducible graphs matter

If you need a mature production system in this space today, look at USearch or Faiss's IndexBinaryHNSW. EdgeVector's niche is the opposite trade: a codebase small enough to read in an afternoon, audit completely, and vendor into firmware-style projects where every dependency is a liability — now with a retrieval pipeline that gives up none of the accuracy.

Development process

This library was built with an AI-agent workflow — an overseer model (Claude) planning, specifying, and adversarially reviewing; worker agents implementing against strict gates — with every module required to pass measured, machine-checked acceptance criteria (parity thresholds, recall gates, an instrumented allocator) before merging. The working documents (CLAUDE.md, PLAN.md) are checked in unedited, as part of the record.

License

MIT