How Precomputed Tables Let Meta's FAISS Scan Billion-Scale Vectors Without Decompressing Them

On March 29, 2017, Meta's engineering team published a library that quietly solved a hard physical limit in machine learning. Before that date, searching a billion high-dimensional vectors required either a supercomputer's memory array or days of disk thrashing. The release of FAISS introduced a mathematical bypass that allowed massive similarity searches to run entirely in standard RAM.[1]

The breakthrough was not a faster processor, but a method of avoiding processing altogether. FAISS demonstrated how to scan compressed data without ever decompressing it. By precomputing the answers to partial distance calculations, the system replaced billions of floating-point multiplications with simple table lookups.[1][3]

This architecture shifted the bottleneck of similarity search from raw compute power to memory bandwidth. It allowed a single server to search a billion images, texts, or user profiles in milliseconds. Today, this specific mechanism underpins the retrieval systems of nearly every major artificial intelligence platform.[3][9]

The memory bandwidth bottleneck

To understand the bypass, one must first measure the roadblock. In machine learning, objects like images or paragraphs are represented as dense arrays of numbers called vectors. A standard vector might contain 128 floating-point dimensions, requiring 512 bytes of memory to store.[3]

Scaling that standard size to a billion items creates an immediate hardware crisis. A billion 128-dimensional vectors consume 512 gigabytes of random access memory. Merely reading that much data from memory to the processor takes seconds, regardless of how fast the processor can perform the distance math.[3][9]

"The main bottleneck in similarity search is memory bandwidth," the original FAISS research team noted in their 2017 arXiv paper. When a user submits a query vector, the system must find the closest matches among the billion stored vectors. Exact nearest neighbor search requires comparing the query against every single stored item.[3]

That exact comparison demands 128 floating-point subtractions and multiplications per vector. Across a billion vectors, that is 128 billion operations, all waiting on 512 gigabytes of data to travel across the motherboard. The physical limits of the Von Neumann architecture make this brute-force approach useless for real-time applications.[3][4]

Product quantization and sub-vectors

The solution begins with a compression technique called Product Quantization, originally detailed in a 2010 IEEE paper by researchers at INRIA. Instead of treating a 128-dimension vector as a single monolithic coordinate, the algorithm slices it into shorter segments. A common configuration splits the vector into eight sub-vectors of 16 dimensions each.[2][7]

Each of these 16-dimension slices is then compared against a predefined dictionary of 256 standard shapes, known as centroids. The system finds the closest matching centroid for that specific slice and throws away the original floating-point numbers. It only records the 8-bit integer ID of the chosen centroid.[6][8]

Because there are eight slices, the entire 512-byte vector is reduced to just eight 8-bit integers. The storage requirement plummets from 512 bytes to exactly 8 bytes. A billion vectors now fit comfortably inside 8 gigabytes of RAM, easily residing on a single consumer-grade graphics card.[3][6]

However, compression usually introduces a new penalty: decompression time. In a standard system, to compare a new query vector against these compressed records, the CPU would have to reconstruct the approximate original vectors first. That decompression step would consume all the time saved by the smaller memory footprint.[4][8]

The precomputed lookup table

This is where the FAISS architecture introduces its defining trick, known as Asymmetric Distance Computation. When a new query vector arrives, the system does not decompress the database to match the query. Instead, it processes the query to match the compressed database.[2][5]

The query vector is sliced into the same eight segments. For each of those eight segments, the system calculates the exact distance to all 256 possible centroids in the dictionary. This creates a small, temporary grid: eight columns by 256 rows, containing 2,048 highly precise distance measurements.[6][8]

This grid is the precomputed query-to-centroid table. It takes a fraction of a millisecond to generate because it only involves the single query vector and the fixed dictionary. Once this table is built, the heavy floating-point mathematics for the entire search operation are permanently finished.[3][5]

The system then begins scanning the 8-gigabyte compressed database. When it looks at a stored vector, it sees only eight integer IDs. To find the distance between the query and this stored vector, it simply uses those eight IDs as coordinates to look up the precomputed distances in the temporary table.[4][6]

Scanning without decompressing

The inner loop of the search algorithm is stripped of all complex arithmetic. It reads the first centroid ID, fetches the precomputed distance from the table, reads the second ID, fetches the next distance, and adds them together. Eight memory lookups and seven integer additions yield the total approximate distance.[3][5]

"The distance is computed using only table lookups and additions," the Qdrant engineering team explains in their technical documentation on product quantization. The stored vectors remain fully compressed as 8-byte arrays throughout the entire process. The decompression step is entirely bypassed.[8]

This mechanism converts a compute-bound problem into a cache-bound problem. The 2,048-value lookup table is so small that it fits entirely within the L1 cache of a CPU or the shared memory of a GPU multiprocessor. The processor never has to wait for main memory to deliver the distance calculations.[3][9]

By keeping the lookup table in the fastest possible memory tier, FAISS achieves scan rates that approach the theoretical maximum bandwidth of the hardware. The system can evaluate millions of vectors per millisecond, simply because it is only reading 8 bytes per vector and performing zero multiplications.[1][3]

Inverted files and Voronoi cells

Even at 8 bytes per vector, scanning a billion items linearly still takes noticeable time. To push query latencies down to the single-digit milliseconds required by production systems, FAISS layers the precomputed tables over an indexing structure called an Inverted File.[3][5]

During the initial database construction, the entire billion-vector space is partitioned into thousands of coarse clusters, often called Voronoi cells. Every vector is assigned to the cell that represents its general neighborhood in the high-dimensional space. The vectors within each cell are then compressed using Product Quantization.[2][6]

When a query arrives, FAISS first determines which few Voronoi cells the query falls nearest to. It completely ignores the rest of the database. If the system is configured to probe only 32 out of 32,000 cells, it immediately skips 99.9 percent of the stored vectors.[3][4]

The precomputed query-to-centroid table is then used to rapidly scan only the vectors inside those selected cells. This combination—macro-level pruning via inverted files and micro-level acceleration via precomputed tables—is what allows the library to claim billion-scale search capabilities on single-node hardware.[1][5]

The accuracy trade-off

This extreme efficiency requires a compromise on precision. Because the stored vectors are approximated by centroids, the distances calculated via the lookup table are not perfectly exact. The system might occasionally rank the true second-closest vector as the closest, or miss a marginal neighbor entirely.[2][8]

In practice, machine learning embeddings are already noisy representations of semantic concepts. The slight quantization error introduced by the centroid approximation rarely degrades the actual user experience. A visually similar image or a semantically relevant paragraph is still retrieved, even if its mathematical distance is slightly fuzzed.[6][8]

For applications demanding perfect precision, engineers use the compressed scan as a first pass. The precomputed tables rapidly identify the top 100 approximate matches. The system then fetches only those 100 specific vectors from a slower, uncompressed storage tier to calculate their exact floating-point distances for a final reranking.[4][6]

This architecture—where compressed vectors are scanned via lookup tables without decompression—has become the industry standard. It transitioned similarity search from an academic curiosity into the foundational infrastructure that powers modern retrieval-augmented generation and semantic search.[1][8]