From HNSW to Information-Theoretic Binarization: Rethinking the Architecture of Scalable Vector Search
Seyed Moein Abtahi, Majid Fekri, Tara Khani, Akramul Azim · 2026
Read From HNSW to Information-Theoretic Binarization: Rethinking the Architecture of Scalable Vector Search by Seyed Moein Abtahi, Majid Fekri, Tara Khani, Akramul Azim (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-11557.txt.
Introduction
Seyed Moein Abtahi, Majid Fekri, Tara Khani, and Akramul Azim rethink vector search. Their 2026 preprint runs from HNSW to information-theoretic binarization. Semantic search and RAG systems lean on approximate nearest neighbors. Most keep vectors in memory at full float precision.
That stack is HNSW plus float32 plus cosine similarity. Its operational cost keeps climbing with data scale. Latency, throughput, and accuracy trade off against each other. Past cost cuts include storage disaggregation and lossy quantization. Each cut sacrifices performance or accuracy in the end. Binarization guided by information theory is the proposed path. One-bit vectors could slash memory while holding accuracy.
Catalog record
| CREATOR | Seyed Moein Abtahi, Majid Fekri, Tara Khani, Akramul Azim |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-11557
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
From HNSW to Information-Theoretic Binarization: Rethinking the Architecture of Scalable Vector Search Seyed Moein Abtahi, Majid Fekri, Tara Khani, Akramul Azim Abstract Modern semantic search and retrieval-augmented generation (RAG) systems rely predominantly on in-memory approximate nearest neighbor (ANN) indexes over high-precision floating-point vectors, resulting in escalating operational cost and inherent trade-offs between latency, throughput, and retrieval accuracy. This paper analyzes the architectural limitations of the dominant “HNSW + float32 + cosine similarity” stack and evaluates existing cost-reduction strategies, including storage disaggregation and lossy vector quantization, which inevitably sacrifice either performance or accuracy. We introduce and empirically evaluate an alternative information-theoretic architecture based on maximally informative binarization (MIB), efficient bitwise distance metrics, and an information-theoretic scoring (ITS) mechanism. Unlike conventional ANN systems, this approach enables exhaustive search over compact binary representations, allowing deterministic retrieval and eliminating accuracy degradation under high query concurrency. Using the MAIR benchmark across 14 datasets and 10,038 queries, we compare this architecture against Elasticsearch, Pinecone, PGVector, and Qdrant. Results demonstrate retrieval quality comparable to full-precision systems, while achieving substantially lower latency and maintaining constant throughput at high request rates. We show that this architectural shift enables a truly serverless, cost-per-query deployment model, challenging the necessity of large in-memory ANN indexes for high-quality semantic search. I Introduction I-A The Vector Search Cost-Performance Problem Modern RAG systems and autonomous agents need semantic search with millisecond latency. Vector databases like Pinecone, Qdrant, Weaviate, Milvus, and Redis have all chosen the same approach: keep everything in RAM. But this creates a real problem. More vectors means more RAM, and RAM is expensive. The more your data grows, the more your costs grow. In this paper, we look at how today’s systems work, why they’re expensive, what companies have tried to fix it, and a new approach that might change everything. I-B Architectural Foundation and Cost Implications RAG systems need to search vectors quickly. They need results in milliseconds, not seconds, because search is blocking: the system waits for results before moving forward [ 15 ] . When search is slow, everything else breaks down. The answers get worse and the whole system fails more often [ 47 ] . To get millisecond results, everything has to be in RAM. If vectors live on disk, you have to read from disk, and that’s too slow for real-time search [ 40 , 49 ] . So the choice is forced: keep everything in memory. But this ties your costs directly to how much RAM you need. The bigger your dataset, the more you spend. The math is simple and brutal. One billion vectors, each 768 dimensions, stored as float32 takes about 3 terabytes of RAM [ 23 ] . That’s a lot of expensive hardware. When you scale to bigger datasets, your main cost is buying more RAM. There’s no way around it [ 49 ] . I-C The Three-Component Algorithmic Stack Every vector database does the same three things. First, it uses HNSW indexing to find nearby vectors fast. Second, it stores vectors as float32 numbers to keep precision high. Third, it measures distance between vectors using cosine similarity. Each of these choices affects both speed and cost. I-C 1 Index Structure: HNSW HNSW represents the state-of-the-art technique for approximate nearest neighbor (ANN) search [ 5 ] . This graph-based indexing structure employs a hierarchical topology enabling efficient location of semantically similar vectors through greedy traversal [ 29 , 5 ] . The algorithmic efficiency derives from superior recall-latency trade-offs; however, performance is contingent upon complete graph structure residency within RAM [ 6 ] , establishing a non-negotiable coupling between index cardinality and required memory capacity. I-C 2 Numerical Representation: Float32 Vectors Vector embeddings, high-dimensional numerical representations of unstructured data [ 23 ] , are standardly encoded using single-precision floating-point (float32) representation, requiring 32 bits of storage per dimension [ 29 ] . This high-precision format facilitates accurate distance calculations but substantially increases memory requirements. I-C 3 Distance Metric: Cosine Similarity Semantic search requires computing inter-vector similarity via cosine similarity, which quantifies the angular relationship between vector pairs: \text{sim}(\mathbf{A},\mathbf{B})=\frac{\mathbf{A}\cdot\mathbf{B}}{\|\mathbf{A}\|_{2}\cdot\|\mathbf{B}\|_{2}} (1) where \mathbf{A},\mathbf{B}\in\mathbb{R}^{d} represent d -dimensional embeddings [ 21 ] . Computational complexity scales linearly with embedding dimensionality, requiring substantial floating-point arithmetic operations (multiplication and accumulation), resulting in persistent high CPU utilization [ 44 ] . I-D Cost Structure Analysis Integration of HNSW, float32 representation, and cosine similarity generates a two-pronged cost structure. HNSW’s in-memory graph traversal requirement necessitates continuous, high-capacity RAM provisioning for both index and full-precision vectors [ 23 , 12 ] . Simultaneously, cosine similarity computation on high-dimensional float32 vectors imposes continuous, elevated computational load, generating sustained CPU resource consumption [ 21 , 44 ] . The problem is that you can’t change one part without breaking everything else. If you move vectors to cheaper disk storage, you break HNSW’s requirement to have everything in RAM, and your search gets too slow [ 8 ] . So, the only way to reduce costs is to replace all three parts at once with a fundamentally different execution model, including reconsideration of approximate indexing itself. II Existing Cost Mitigation Strategies: Compromise Architectures Faced with prohibitive total cost of ownership (TCO) in pure in-memory deployments, the vector database market has introduced architectures reducing costs through systematic sacrifices in either latency or accuracy. II-A Storage Disaggregation: The Latency-Cost Trade-off Storage disaggregation implements a hybrid topology, decoupling compressed index structures from full-precision vector data [ 40 ] . A memory-resident compressed index enables rapid candidate identification, while full-precision vectors are externalized to economical cold-tier storage such as Amazon S3 or solid-state drives, with implementations including Amazon S3 Vectors and Turbopuffer [ 8 , 47 ] . This topology replaces high-cost continuous RAM provisioning with consumption-based object storage [ 9 ] . However, rehydrating final vectors from cold storage for result reranking introduces I/O latency penalties fundamentally incompatible with in-memory system performance [ 8 ] . Quantitative analysis demonstrates recall rates typically stabilize at 85–90%, with significant degradation often below 50% when metadata filters are applied [ 50 ] . Temporal consistency issues additionally emerge, as index-data desynchronization produces stale results [ 25 ] . Consequently, this approach is suitable only for non-latency-critical, archival applications rather than high-performance RAG systems. II-B Vector Quantization: The Accuracy-Cost Trade-off Vector quantization (VQ) employs lossy compression, reducing memory footprint by representing float32 values with lower-precision data types (8-bit, 4-bit, or 2-bit integers) [ 12 ] . This technique exhibits a well-characterized compression-fidelity trade-off [ 7 ] . In the low compression regime , compression to approximately 4 bits per dimension generally maintains acceptable recall across diverse embedding models with minimal accuracy degradation [ 7 ] . Conversely, in the aggressive compression regime , compression intensity below 4-bit incurs rapid accuracy degradation and significant recall loss [ 7 ] . Binarization, the extreme quantization case reducing each dimension to a single bit, has historically represented a quantization threshold beyond which accuracy collapse occurs. Traditional binarization methods, such as locality-sensitive hashing (LSH), prioritize computational efficiency over retrieval quality [ 35 ] . Empirical evidence confirms that LSH performance degrades with dataset size, failing to reliably identify nearest neighbors [ 32 ] . This established pattern has created industry consensus that binarization is