Comprehensive Guide to Facebook AI Similarity Search

(FAISS)
From Video Transcripts

Contents
1 Introduction to FAISS 2
1.1 What is FAISS? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Key Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Basic Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Core Concepts 3
2.1 Vector Similarity Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.1 L2 Distance (Euclidean Distance) . . . . . . . . . . . . . . . . . . . . 3
2.1.2 Inner Product (IP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Curse of Dimensionality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

3 Flat Indexes 3
3.1 FlatL2 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.1.1 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.1.2 Code Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.1.3 Performance Characteristics . . . . . . . . . . . . . . . . . . . . . . . 4
3.2 FlatIP Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

4 Inverted File (IVF) Index 4

4.1 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
4.1.1 Search Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.1.2 nprobe Parameter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.2 Code Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.3 Performance Trade-offs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

5 Product Quantization (PQ) 6

5.1 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
5.1.1 Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
5.2 Code Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
5.3 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1
6 Locality Sensitive Hashing (LSH) 7
6.1 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6.1.1 Search Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6.2 Code Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.3 Performance Characteristics . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.4 nbits Tuning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

7 Hierarchical Navigable Small World (HNSW) 8

7.1 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
7.1.1 Key Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
7.1.2 Search Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7.2 Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7.3 Code Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7.4 Performance Characteristics . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

8 Practical Implementation Guide 10

8.1 Data Preparation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
8.2 Performance Benchmarking . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
8.3 Accuracy Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

9 Index Selection Guidelines 11

9.1 Decision Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
9.2 Parameter Tuning Recommendations . . . . . . . . . . . . . . . . . . . . . . 11
9.2.1 IVF Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
9.2.2 HNSW Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
9.2.3 PQ Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

10 Advanced Topics 12
10.1 GPU Acceleration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
10.2 Composite Indexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
10.3 Batch Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

11 Conclusion 13

1 Introduction to FAISS
1.1 What is FAISS?
Facebook AI Similarity Search (FAISS) is a library developed by Facebook AI that enables
efficient similarity search and clustering of dense vectors. It can scale to handle datasets
with billions of vectors while maintaining high performance.

1.2 Key Features

• High-efficiency vector comparison

2
 • Scalability from thousands to billions of vectors

• Multiple indexing methods for different use cases

• Optimized for both CPU and GPU

• Balance between search quality and speed

1.3 Basic Problem Statement

Given a set of vectors V = {v1 , v2 , ..., vn } and a query vector q, find the k most similar
vectors from V to q.

2 Core Concepts
2.1 Vector Similarity Metrics
2.1.1 L2 Distance (Euclidean Distance)
v
u n
uX
dL2 (p, q) = t (pi − qi )2 (1)
i=1

2.1.2 Inner Product (IP)

n
X
dIP (p, q) = pi · q i (2)
i=1

2.2 Curse of Dimensionality

As the number of dimensions increases, the volume of space grows exponentially, making
exhaustive search increasingly expensive. FAISS provides approximate methods to handle
high-dimensional spaces efficiently.

3 Flat Indexes
3.1 FlatL2 Index
3.1.1 Theory
The FlatL2 index performs exhaustive search using Euclidean distance. It compares the
query vector against every vector in the database.

3
 v1

q v3 vn

v2

3.1.2 Code Implementation

Listing 1: FlatL2 Index Implementation

import f a i s s
import numpy as np

# I n i t i a l i z e index
d = 768 # d i m e n s i o n a l i t y
i n d e x = f a i s s . IndexFlatL2 ( d )

# Add v e c t o r s
i n d e x . add ( s e n t e n c e e m b e d d i n g s )

# Search
k = 4 # number o f n e a r e s t n e i g h b o r s
D, I = i n d e x . s e a r c h ( xq , k )

3.1.3 Performance Characteristics

• Accuracy: 100% (exhaustive search)

• Speed: O(n · d) where n is number of vectors, d is dimensionality

• Memory: Stores all vectors in full precision

3.2 FlatIP Index

Similar to FlatL2 but uses inner product instead of Euclidean distance.
index = f a i s s . IndexFlatIP (d)

4 Inverted File (IVF) Index

4.1 Theory
IVF index uses Voronoi partitioning to divide the vector space into cells. Each cell contains
vectors closest to a particular centroid.

4
 q

4.1.1 Search Process

1. Compare query vector against all centroids

2. Identify the nearest centroid(s)

3. Search only within the corresponding Voronoi cell(s)

4. Return k-nearest neighbors from that cell

4.1.2 nprobe Parameter

The nprobe parameter controls how many Voronoi cells to search:

• nprobe=1: Search only the closest cell

• nprobe>1: Search multiple closest cells

• Higher nprobe → better accuracy but slower search

4.2 Code Implementation

# Define parameters
n l i s t = 50 # number o f Voronoi c e l l s
d = 768

# Create q u a n t i z e r and IVF i n d e x

q u a n t i z e r = f a i s s . IndexFlatL2 ( d )
i n d e x = f a i s s . IndexIVFFlat ( q u a n t i z e r , d , n l i s t )

# Train t h e i n d e x ( r e q u i r e d f o r IVF)
index . t r a i n ( sentence embeddings )

# Add v e c t o r s

5
i n d e x . add ( s e n t e n c e e m b e d d i n g s )

# S e t nprobe f o r s e a r c h
i n d e x . nprobe = 4 # s e a r c h 4 c l o s e s t c e l l s

# Perform s e a r c h
D, I = i n d e x . s e a r c h ( xq , k )

4.3 Performance Trade-offs

• Speed: Much faster than flat indexes for large datasets

• Accuracy: Approximate (depends on nprobe)

• Memory: Additional storage for centroids

5 Product Quantization (PQ)

5.1 Theory
Product quantization reduces vector storage requirements by splitting vectors into subvectors
and quantizing each subvector separately.

5.1.1 Process
1. Split each vector into m subvectors: v = [v1 , v2 , ..., vm ]

2. For each subvector space, create a codebook via clustering

3. Replace each subvector with its nearest centroid ID

4. Store only centroid IDs instead of full vectors

v0 v1 v2 v3 v4 v5 v6 v7

Subvector 1 Subvector m

C1 C2 C3 Ck

Final: [2, 3, ..., k]

6
5.2 Code Implementation
# D e f i n e PQ p a r a m e t e r s
m = 8 # number o f s u b v e c t o r s ( must d i v i d e d )
b i t s = 8 # b i t s per s u b v e c t o r
n l i s t = 50 # number o f IVF c e l l s

# Create IVF−PQ i n d e x
q u a n t i z e r = f a i s s . IndexFlatL2 ( d )
i n d e x = f a i s s . IndexIVFPQ ( q u a n t i z e r , d , n l i s t , m, b i t s )

# Train and add v e c t o r s

index . t r a i n ( sentence embeddings )
i n d e x . add ( s e n t e n c e e m b e d d i n g s )

# Search
i n d e x . nprobe = 4
D, I = i n d e x . s e a r c h ( xq , k )

5.3 Constraints
• m must divide dimensionality d evenly

• Typical values: m = 8, bits = 8 for 768-dimensional vectors

6 Locality Sensitive Hashing (LSH)

6.1 Theory
LSH hashes similar vectors into the same ”buckets” with high probability, unlike traditional
hashing that minimizes collisions.

Bucket A Bucket B Bucket C

6.1.1 Search Process

1. Hash query vector to find its bucket

2. Search only within that bucket (and possibly nearby buckets)

7
 3. Use Hamming distance for comparison in bucket space

6.2 Code Implementation

# Define parameters
d = 128
n b i t s = d ∗ 4 # number o f b i t s f o r h a s h i n g

# Create LSH i n d e x
i n d e x = f a i s s . IndexLSH ( d , n b i t s )

# Add v e c t o r s and s e a r c h
i n d e x . add (wb)
D, I = i n d e x . s e a r c h ( xq , k )

6.3 Performance Characteristics

• Speed: Fast for low-dimensional data

• Accuracy: Good recall with proper nbits tuning

• Memory: Compact storage due to hashing

• Limitation: Suffers from curse of dimensionality

6.4 nbits Tuning

• Lower nbits → faster but less accurate

• Higher nbits → more accurate but slower

• Rule of thumb: nbits = d × 2 to d × 8

7 Hierarchical Navigable Small World (HNSW)

7.1 Theory
HNSW constructs a hierarchical graph where each level is a navigable small world graph.
The graph has the property that the average number of hops between any two nodes is small.

7.1.1 Key Properties

• Small World: Low average path length between any two nodes

• Hierarchical: Multiple layers with different densities

8
 • Navigable: Easy to find shortest paths

7.1.2 Search Process

1. Start search at top layer

2. Move to lower layers while refining search

3. Use greedy algorithm to find nearest neighbors at each level

7.2 Parameters
• M: Number of connections per node (higher = better connectivity)

• efConstruction: Search depth during graph construction

• efSearch: Search depth during querying

7.3 Code Implementation

# D e f i n e HNSW p a r a m e t e r s
M = 16 # number o f c o n n e c t i o n s
e f C o n s t r u c t i o n = 64 # c o n s t r u c t i o n time s e a r c h d e p t h
e f S e a r c h = 32 # q u e r y time s e a r c h d e p t h

# Create HNSW i n d e x
i n d e x = f a i s s . IndexHNSWFlat ( d , M)

# Set parameters
i n d e x . hnsw . e f C o n s t r u c t i o n = e f C o n s t r u c t i o n
i n d e x . hnsw . e f S e a r c h = e f S e a r c h

# Add v e c t o r s ( t a k e s l o n g e r t o b u i l d )
i n d e x . add (wb)

# Search
D, I = i n d e x . s e a r c h ( xq , k )

9
7.4 Performance Characteristics
• Speed: Very fast query times

• Accuracy: Excellent with proper parameter tuning

• Memory: Large index size due to graph structure

• Build Time: Longer construction time

8 Practical Implementation Guide

8.1 Data Preparation
import numpy as np
from s e n t e n c e t r a n s f o r m e r s import S e n t e n c e T r a n s f o r m e r

# Load s e n t e n c e embeddings
model = S e n t e n c e T r a n s f o r m e r ( ’ b e r t −base−n l i −mean−t o k e n s ’ )

# Example : Encoding t e x t
s e n t e n c e s = [ ” H e l l o world ” , ”Someone s p r i n t s with a f o o t b a l l ” ]
embeddings = model . encode ( s e n t e n c e s )

# For l a r g e r d a t a s e t s , use b a t c h p r o c e s s i n g
with open ( ’ s e n t e n c e s . t x t ’ , ’ r ’ ) as f p :
l i n e s = f p . read ( ) . s p l i t ( ’ \n ’ )

# P r o c e s s i n b a t c h e s i f needed
b a t c h s i z e = 32
all embeddings = [ ]
for i in range ( 0 , len ( l i n e s ) , b a t c h s i z e ) :
batch = l i n e s [ i : i+b a t c h s i z e ]
batch embeddings = model . encode ( batch )
a l l e m b e d d i n g s . append ( batch embeddings )

s e n t e n c e e m b e d d i n g s = np . v s t a c k ( a l l e m b e d d i n g s )

8.2 Performance Benchmarking

import time

def benchmark index ( index , q u e r y v e c t o r s , k=10 , i t e r a t i o n s =100):

times = [ ]
for in range ( i t e r a t i o n s ) :

10
 s t a r t t i m e = time . time ( )
D, I = i n d e x . s e a r c h ( q u e r y v e c t o r s , k )
e n d t i m e = time . time ( )
t i m e s . append ( ( e n d t i m e − s t a r t t i m e ) ∗ 1000) # c o n v e r t t o ms

return np . mean ( t i m e s ) , np . s t d ( t i m e s )

# Compare d i f f e r e n t i n d e x e s
mean time , s t d t i m e = benchmark index ( index , xq )
print ( f ” Average s e a r c h time : { mean time : . 2 f }ms { s t d t i m e : . 2 f }ms” )

8.3 Accuracy Evaluation

def e v a l u a t e a c c u r a c y ( index , q u e r y v e c t o r s , b a s e l i n e r e s u l t s , k =10):
# Get r e s u l t s from c u r r e n t i n d e x
D, I = i n d e x . s e a r c h ( q u e r y v e c t o r s , k )

# Compare w i t h b a s e l i n e ( f l a t i n d e x r e s u l t s )
a c c u r a c y = np . mean ( [ len ( np . i n t e r s e c t 1 d ( I [ i ] , b a s e l i n e r e s u l t s [ i ] ) ) / k
for i in range ( len ( q u e r y v e c t o r s ) ) ] )

return a c c u r a c y

# B a s e l i n e from f l a t i n d e x
b a s e l i n e i n d e x = f a i s s . IndexFlatL2 ( d )
b a s e l i n e i n d e x . add (wb)
D b a s e l i n e , I b a s e l i n e = b a s e l i n e i n d e x . s e a r c h ( xq , k )

# Evaluate other indexes

a c c u r a c y = e v a l u a t e a c c u r a c y ( index , xq , I b a s e l i n e )
print ( f ” R e c a l l a c c u r a c y : { a c c u r a c y :.2%} ” )

9 Index Selection Guidelines

9.1 Decision Matrix
9.2 Parameter Tuning Recommendations
9.2.1 IVF Index
√
• nlist: Start with n where n is number of vectors

• nprobe: Balance between speed and accuracy (2-16 typical)

11
 Index Type Best Use Case Speed Accuracy Memory
FlatL2/IP Small datasets (¡100K) Slow 100% High
IVFFlat Medium-large datasets Fast High Medium
IVFPQ Very large datasets Very Fast Medium Low
LSH Low-dimensional data Fast Medium Low
HNSW High accuracy required Very Fast Very High High

Table 1: Index Selection Guide

9.2.2 HNSW Index

• M: 16-48 (higher for better recall)

• efConstruction: 40-200 (higher for better graph quality)

• efSearch: 16-128 (higher for better accuracy)

9.2.3 PQ Index
• m: Choose so that d/m is integer (8, 16 typical)

• bits: 8 bits provides good quality/size trade-off

10 Advanced Topics
10.1 GPU Acceleration
FAISS supports GPU acceleration for faster indexing and search:
# Move i n d e x t o GPU
r e s = f a i s s . StandardGpuResources ( )
gpu index = f a i s s . index cpu to gpu ( res , 0 , index )

# Use GPU i n d e x f o r s e a r c h
D, I = g p u i n d e x . s e a r c h ( xq , k )

10.2 Composite Indexes

Combine multiple techniques for optimal performance:
# IVF + HNSW + PQ c o m p o s i t e i n d e x
q u a n t i z e r = f a i s s . IndexHNSWFlat ( d , 32 )
i n d e x = f a i s s . IndexIVFPQ ( q u a n t i z e r , d , n l i s t , m, b i t s )

12
10.3 Batch Processing
For multiple queries, process in batches:
def b a t c h s e a r c h ( index , q u e r i e s , k=10 , b a t c h s i z e =1000):
all results = []
for i in range ( 0 , len ( q u e r i e s ) , b a t c h s i z e ) :
batch = q u e r i e s [ i : i+b a t c h s i z e ]
D, I = i n d e x . s e a r c h ( batch , k )
a l l r e s u l t s . append ( I )
return np . v s t a c k ( a l l r e s u l t s )

11 Conclusion
FAISS provides a comprehensive toolkit for efficient similarity search across various scales
and requirements. Key takeaways:

• Flat indexes provide exact results but scale poorly

• IVF indexes offer good speed/accuracy trade-off for medium datasets

• PQ indexes enable handling of very large datasets with reduced memory

• LSH works well for low-dimensional data

• HNSW provides state-of-the-art performance for high-accuracy requirements

The choice of index and parameters depends on your specific requirements for accuracy,
speed, memory, and dataset size. Always benchmark with your actual data and queries to
find the optimal configuration.

13