Within Half a Point of FAISS Recall, from the Standard Library Alone: A Pre-registered Study of Two C++20 Approximate Nearest Neighbour Indexes Built from Scratch

How close does a dependency-free approximate nearest neighbour (ANN) index, written from scratch in C++20 with the standard library only, come to FAISS-class recall, and at what latency and memory cost? This study pre-registered the question and the verdict rules before any benchmark ran. On a corpus of 58,999 embedded text chunks (SQuAD v1.1, 30-word windows, 256-dimensional L2-normalized embeddings) with 300 held-out queries and exact brute-force ground truth (cross-validated against an independent NumPy computation, 300 of 300 queries), two indexes were measured under one frozen protocol: an inverted file index (IVF) with spherical k-means training, and an HNSW-style layered graph index with simple neighbour selection. All three registered hypotheses are CONFIRMED. H1: IVF reaches recall@10 0.9487 at its tuned point (nlist 512, nprobe 32, chosen by the frozen smallest-nprobe rule) with p99 latency 1.281 ms, 8.42 times faster than brute force p99 (10.788 ms) on the same machine; the nlist 128 tuned point fails the same speed rule (0.65 times), because its id-gather layout turns random-access bound at high nprobe. H2: at or below the IVF tuned point's p99, the graph index reaches recall@10 0.9750 (M 16, ef 128, p99 0.971 ms) and 0.9620 at p99 0.514 ms (M 32, ef 32), strictly better recall at equal or lower latency. H3: every configuration stays inside the frozen memory budget of 1,536 bytes per vector; the heaviest, graph M 32, totals 1,340.8 bytes per vector, and IVF needs 1,030.2 to 1,037.0. Against the labelled cross-study FAISS reference (IndexHNSWFlat, recall@10 0.967 on the same corpus and query set, measured by the earlier vector-systems-benchmark study under its own protocol), this study's graph index at M 32, ef 32 measures recall@10 0.9620 with p50 0.177 ms: within half a point of FAISS recall at a comparable operating point, from an implementation with no external ANN library. The claims are deliberately narrow: one corpus, one machine, one query set, one frozen protocol, and a brute-force tail on the shared study machine noisy enough that the paper reports the variance alongside every verdict it feeds.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-18
DOI
https://doi.org/10.5281/zenodo.24328299
Primary Topic
Advanced Image and Video Retrieval Techniques
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Within Half a Point of FAISS Recall, from the Standard Library Alone: A Pre-registered Study of Two C++20 Approximate Nearest Neighbour Indexes Built from Scratch

Jesun Ahmad Ushno
1 links
Zenodo (CERN European Organization for Nuclear Research)
Advanced Image and Video Retrieval Techniques
preprint

Within Half a Point of FAISS Recall, from the Standard Library Alone: A Pre-registered Study of Two C++20 Approximate Nearest Neighbour Indexes Built from Scratch

Jesun Ahmad Ushno
preprint en

Abstract

How close does a dependency-free approximate nearest neighbour (ANN) index, written from scratch in C++20 with the standard library only, come to FAISS-class recall, and at what latency and memory cost? This study pre-registered the question and the verdict rules before any benchmark ran. On a corpus of 58,999 embedded text chunks (SQuAD v1.1, 30-word windows, 256-dimensional L2-normalized embeddings) with 300 held-out queries and exact brute-force ground truth (cross-validated against an independent NumPy computation, 300 of 300 queries), two indexes were measured under one frozen protocol: an inverted file index (IVF) with spherical k-means training, and an HNSW-style layered graph index with simple neighbour selection. All three registered hypotheses are CONFIRMED. H1: IVF reaches recall@10 0.9487 at its tuned point (nlist 512, nprobe 32, chosen by the frozen smallest-nprobe rule) with p99 latency 1.281 ms, 8.42 times faster than brute force p99 (10.788 ms) on the same machine; the nlist 128 tuned point fails the same speed rule (0.65 times), because its id-gather layout turns random-access bound at high nprobe. H2: at or below the IVF tuned point's p99, the graph index reaches recall@10 0.9750 (M 16, ef 128, p99 0.971 ms) and 0.9620 at p99 0.514 ms (M 32, ef 32), strictly better recall at equal or lower latency. H3: every configuration stays inside the frozen memory budget of 1,536 bytes per vector; the heaviest, graph M 32, totals 1,340.8 bytes per vector, and IVF needs 1,030.2 to 1,037.0. Against the labelled cross-study FAISS reference (IndexHNSWFlat, recall@10 0.967 on the same corpus and query set, measured by the earlier vector-systems-benchmark study under its own protocol), this study's graph index at M 32, ef 32 measures recall@10 0.9620 with p50 0.177 ms: within half a point of FAISS recall at a comparable operating point, from an implementation with no external ANN library. The claims are deliberately narrow: one corpus, one machine, one query set, one frozen protocol, and a brute-force tail on the shared study machine noisy enough that the paper reports the variance alongside every verdict it feeds.

Zenodo (CERN European Organization for Nuclear Research)
Advanced Image and Video Retrieval Techniques
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon