A Faster more efficient FAISS

[nikitph]

view (8).pdf

Abstract
We present REWA-Retriever, a novel approximate nearest neighbor (ANN) search system that
achieves 80× speedup over brute force while maintaining > 97% recall at 500K vectors. Our key insight is an information-theoretic scaling law: the binary code length m must grow as O(log N) with
dataset size N to preserve recall. Existing systems use fixed m, causing a “scaling wall” where recall
degrades from 96.4% to 33% as N grows from 50K to 500K. We introduce Witness-LDPC codes—binary
encodings that capture the most distinctive dimensions of high-dimensional vectors via expander-graphinspired hashing. Combined with three systems-level optimizations (SIMD-friendly Hamming distance,
early termination heaps, and cache-optimized storage), REWA-Retriever outperforms FAISS-IVF by
3.5× at equivalent recall. Our theoretical framework provides the first rigorous characterization of the
recall-speedup-scale tradeoff in binary code methods, with practical implications for large-scale retrieval
systems.