Vector Lookup

Last time, we calculated the similarity between a query and every movie in the database.

Today’s Question: Can we find the nearest movies without examining every vector?

Let’s use the same 1,000 sentence-transformer embeddings already stored in MySQL. This time, we’ll load them into FAISS (Facebook AI Similarity Search) and compare two new indexes:

  1. Flat Search: exact nearest neighbors, but still exhaustive
  2. IVF (inverted flat file): divide vectors into clusters, then search only certain clusters.
  3. (there are more, like HNSW, etc)

Reminder: why is search so expensive:

for movie in movies:
    similarity = 0
    for j in range(384):
        similarity += query[j] * movie[j]

T(N,d) = O(Nd)

With a fixed embedding size, d=384, this is O(N)… which is not what we want for a large database.

Could a B-Tree help?

FAISS: Faster Code, same algorithm

Let’s start with the following:

import faiss

index = faiss.IndexFlatIP(384)
index.add(movie_vectors)

scores, ids = index.search(query_vector, 5)

IndexFlatIP uses Inner Product similarity. Because our vectors are all normalized unit length, inner product is equivalent to cosine similarity.

This is still O(n). Its a faster implementation, but not better asymptotically.

How do we avoid scanning every vector?

Partitioning!

If our query is near cluster B do we need to evaluate cluster A and C?

So next: How do we identify clusters? One way is K-means clustering

If K=3 clusters then, rather than 18 (or however many) comparisons, we only need 3 centroid comparisons plus the actual 6 vectors.

Inverted File Index (IVF)

Centroid A → [movie 1, movie 4, movie 7, ...]
Centroid B → [movie 2, movie 3, movie 9, ...]
Centroid C → [movie 5, movie 6, movie 8, ...]

So it works like this:

  1. Find closest centroids
  2. Identify the corresponding inverted lists
  3. Compare the query only against those vectors in those lists
  4. Return the top K results from there

The number of lists we look at is called nprobe.

With one probe, we may miss a close vector assigned to a neighboring cluster. With three probes, we examine all clusters and recover exhaustive search behavior for IVF-Flat.

This introduces the fundamental tradeoff:

  1. Fewer probes: fewer comparisons/faster, maybe you miss some.
  2. More probes: more comparisons/slower, miss fewer.

Computational cost:

Suppose a database contains 1,000,000 vectors, each with 384 dimensions. We construct an IVF index with 100 equally sized clusters.

A. How many dot-product coordinate multiplications are required for an exhaustive search?

B. If nprobe = 5, approximately how many vectors must be compared with the query?

C. Approximately how many coordinate multiplications does the IVF search require, including comparisons with all 100 centroids?

D. Approximately what percentage of the exhaustive-search multiplications have we eliminated?

  • A: $1,000,000\times 384=384,000,000$
  • B: $5\times (1,000,000/100)=50,000$ vectors
  • C: $(50,000+100)\times 384=19,238,400$ multiplications
  • D: $1-19,238,400/384,000,000\approx 94.99\%$ eliminated

Lets try this on the server now:

python -m pip install numpy faiss-cpu mysql-connector-python sentence-transformers

Let’s try an exact search with a flat index:

python faiss_movie_lookup.py flat "animated adventure with toys"

Now lets try the ivf:

python faiss_movie_lookup.py ivf 
  "animated adventure with toys" 
  --lists 10 --probes 1

Note the code:

quantizer = faiss.IndexFlatIP(384)

index = faiss.IndexIVFFlat(
    quantizer,
    384,
    40, #clusters
    faiss.METRIC_INNER_PRODUCT
)

index.train(movie_vectors)
index.add(movie_vectors)

index.nprobe = 1
scores, ids = index.search(query_vector, 5)

How much accuracy do we sacrafice?

python faiss_movie_lookup.py benchmark --lists 40 --k 5

How LLMs (next-token) prediction works

  1. Input embeddings: Each input token is converted into a high-dimensional vector.
  2. Transformer: The neural network processes these vectors through multiple layers of attention and other transformations.
  3. Output vector: The transformer produces a hidden-state vector representing the context at the next-token position.
  4. Vocabulary projection: That vector is multiplied by a learned matrix to produce a score (logit) for every possible next token.
  5. Token selection: The scores are converted into probabilities, and a token is selected. The process repeats.