Week 10, Day 1: Exact Flat kNN, RAM/Bandwidth Math & The Curse of Dimensionality

1. Why Brute-Force Exact kNN (IndexFlatIP) Breaks at Scale

In Exact kNN (Flat Index), every query vector $\mathbf{q} \in \mathbb{R}^D$ must be compared against all $N$ vectors in the corpus:

• Time Complexity: $O(N \cdot D)$ floating-point operations per query.
• Memory Footprint Formula (Raw FP32): $\text{RAM}_{\text{raw}} = N \times D \times 4\text{ bytes}$

Concrete Back-of-the-Envelope Capacity Math

Suppose $N = 10,000,000$ chunks and $D = 1,536$ (OpenAI text-embedding-3-small): $\text{RAM}_{\text{raw}} = 10^7 \times 1,536 \times 4\text{ B} = 61,440,000,000\text{ B} \approx \mathbf{57.22\text{ GiB}} \text{ (or } 61.44\text{ GB)}$ Because CPU DDR5 memory bandwidth is ~60 GB/s, scanning 61.44 GB of vectors from RAM for a single user query takes ~1,000 ms (1 full second)—meaning a 64-core server can only handle 1 query per second (1 QPS)!

2. The Curse of Dimensionality in High-Dimensional Spaces

In low dimensions ($D = 2$ or $D = 3$), space is cozy and spatial trees (KD-Trees) easily prune branches. As dimension $D \to \infty$ (e.g., $D = 1536$), two counter-intuitive mathematical phenomena occur for uniform/Gaussian random points:

1. Concentration of Measure: The ratio between the distance to the farthest point $D_{\max}$ and the distance to the nearest point $D_{\min}$ converges to $1$: $\lim_{D \to \infty} \frac{D_{\max} - D_{\min}}{D_{\min}} \to 0$
2. Near-Orthogonality of Random Vectors: Two random unit vectors in $\mathbb{R}^{D}$ have expected dot product $0$and standard deviation$\frac{1}{\sqrt{D}}$. At$D = 1536$,$\frac{1}{\sqrt{1536}} \approx 0.0255—almost all random vectors are nearly \90^\circ$ orthogonal to each other! Fortunately, real text embeddings lie on a lower-dimensional semantic manifold, which enables Approximate Nearest Neighbor (ANN) indexes (IVF and HNSW) to search in sub-linear time!

In Simple English: Why Searching 10 Million Vectors Needs Smart Indexes

Look at the memory formula: $\text{RAM} = N \times D \times 4\text{ bytes}$:

• Suppose $N = 10,000,000$ documents, each stored as $D = 1,536$ decimal numbers (float32 = 4 bytes each).
• Size: $10^7 \times 1,536 \times 4 \approx \mathbf{61.4\text{ GB of pure RAM}}$ just to hold raw vectors!
• Speed Problem (Flat k-NN): Checking every single one of those 10 million vectors for every user question forces the CPU to read 61.4 GB per query (~several seconds!). That is why engineers compress vectors and build Approximate Nearest Neighbor (ANN) shortcuts!