LLMs and Generative AI β€Ί Embeddings and Vector Search β€Ί Day 261

Day 261: Semantic Similarity Search

Day 261 of 365 β€” Semantic Similarity Search

Master geometric similarity metrics and exact nearest-neighbor search algorithms: implement Cosine Similarity, Dot Product, Euclidean Distance (L2), and Manhattan Distance (L1), analyze normalized vector equivalence proofs, examine time-complexity scaling (O(N * d)), and build a high-performance vector search engine with Top-K heap filtering in Python.

Course
LLMs and Generative AI
Category
Embeddings and Vector Search
Reading time
β‰ˆ 35 min
Practical time
β‰ˆ 50 min
Lesson duration
1h 25m
Last verified
2026-08-30

Hands-on lab for this lesson

Lab files on GitHub: https://github.com/ai-roadmap-365/ai-roadmap-365.github.io/tree/main/labs/sections/llms-and-generative-ai/day-261-semantic-similarity-search

  1. Get the hands-on files. Clone the labs repository once (you can reuse this clone for every lesson). This works on macOS, Linux, and Windows (PowerShell or WSL):
    git clone https://github.com/ai-roadmap-365/ai-roadmap-365.github.io.git
    cd ai-roadmap-365.github.io
  2. Open this lesson's lab. Move into the directory for this specific day. Every lab lives at the same predictable path β€” section / subsection / week / day:
    cd labs/sections/llms-and-generative-ai/day-261-semantic-similarity-search
  3. Read the lab guide. Open `README.md` in that directory. It lists the exact commands, what each does, the expected output, and how to check your work β€” read it before running anything.
  4. Run it and check your work. Follow the README's "How to run" section: run the example first to see the finished result, then complete the numbered exercises in `starter/`, then run the tests. The tests pass (exit 0) only when your work is correct.
    bash tests/run_tests.sh   # or the test command named in the lab README

You can also open the lab as a local page (works offline, shows the file tree and expected output).

Learning objectives

By the end of this lesson you will be able to:

Prerequisites

Why this matters

Once you have generated dense vector embeddings for your knowledge base, you face the core engineering challenge of Information Retrieval: Given a user query vector q in \mathbb{R}^d, how do you find the Top-K most semantically relevant documents from a collection of millions of candidate vectors V = \{v_1, v_2, ..., v_N\} with sub-10ms latency?

Calculating similarity is not just a theoretical formulaβ€”it dictates the operational latency, throughput, and hardware memory consumption of your entire AI architecture:

Today, you will master the geometric properties of Cosine Similarity, Dot Product, Euclidean Distance (L2), and Manhattan Distance (L1), analyze the mathematical proofs of normalized vector equivalence, and build a high-throughput vector search engine with Top-K heap selection in Python.


The idea in plain language

Imagine you are standing in an open desert at night with a flashlight, looking for the 5 closest lighthouses:


Historical background

Diagram: the historical progression of information retrieval methods

Vector distance metrics geometric comparison diagram

  1. 300 BCE (Euclid of Alexandria): Formulated Euclidean distance in Elements, defining the geometric length of a straight line in Cartesian coordinates.
  2. 1800s (Hermann Minkowski): Generalized distance metrics into the Minkowski distance family (L_1 Manhattan, L_2 Euclidean, L_infinity Chebyshev).
  3. 1970s (Vector Space Model): Gerard Salton introduced the Cosine Similarity metric to document retrieval, demonstrating that normalizing for document length prevents long articles from dominating search results.
  4. 2017 (FAISS & GPU Vector Search): Jeff Johnson, Matthijs Douze, and HervΓ© JΓ©gou at Meta AI released FAISS (Facebook AI Similarity Search), proving that exact flat BLAS matrix multiplications on GPUs can search millions of vectors in microseconds.

What it is β€” and what it is not

Diagram: exact nearest-neighbour search compared with approximate search

What Semantic Similarity Search IS:

What it is NOT:


Why it was created and what problems it solves

Exact semantic similarity search provides 4 indispensable capabilities:

  1. 100% Search Recall: Guaranteed to find the true global top-K nearest items with zero approximation error or lost matches.
  2. Instant Dynamic Updates: Requires zero index rebuild time; you can append 1,000 new vectors to your NumPy array in 0ms and search immediately.
  3. Hardware Vectorization (SIMD): Executes via multi-threaded AVX-512 and Apple Accelerate BLAS kernels, computing billions of floating-point operations per second.
  4. Ground-Truth Baseline: Serves as the gold-standard benchmark to measure recall loss when evaluating approximate indexers (HNSW/IVF).

How it works

Let us dissect the mathematical formulation of similarity metrics, normalized identities, and Top-K heap algorithms.


1. The Minkowski Distance Family & Metrics

Diagram: three distance metrics for comparing embedding vectors

Given two vectors u, v in \mathbb{R}^d:

β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚                   VECTOR DISTANCE METRIC COMPARISON                    β”‚
β”œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€
β”‚ Metric             β”‚ Formula                     β”‚ Range & Properties  β”‚
β”œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€
β”‚ Manhattan (L1)     β”‚ sum(|u_i - v_i|)            β”‚ [0, inf) Grid step  β”‚
β”‚ Euclidean (L2)     β”‚ sqrt(sum((u_i - v_i)^2))    β”‚ [0, inf) Straight-lineβ”‚
β”‚ Dot Product        β”‚ sum(u_i * v_i)              β”‚ (-inf, +inf) Angle+Magβ”‚
β”‚ Cosine Similarity  β”‚ (u . v) / (||u|| * ||v||)   β”‚ [-1.0, +1.0] Angle  β”‚
β”‚ Cosine Distance    β”‚ 1.0 - CosineSimilarity      β”‚ [0.0, 2.0] Metric   β”‚
β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜

2. The Normalization Equivalence Proof

Why do production vector databases insist on unit-normalizing vectors?

Let u and v be unit vectors such that \|u\|_2 = 1 and \|v\|_2 = 1.

Expand the squared Euclidean distance: \|u - v\|_2^2 = \sum_{i=1}^d (u_i - v_i)^2 = \sum u_i^2 + \sum v_i^2 - 2 \sum u_i v_i

Since \sum u_i^2 = \|u\|_2^2 = 1 and \sum v_i^2 = \|v\|_2^2 = 1: \|u - v\|_2^2 = 1 + 1 - 2(u \cdot v) = 2 - 2(u \cdot v)

Rearranging: u \cdot v = 1 - \frac{1}{2} \|u - v\|_2^2

Crucial Engineering Conclusion:


3. Vectorized Batch Search with BLAS

Diagram: how similarity search is expressed as a single matrix operation

Exact KNN vs Approximate Nearest Neighbor search diagram

Instead of calculating similarity in a Python for loop:

# SLOW: Interpreted loop (50ms for 50k vectors)
scores = [np.dot(q, doc) for doc in database]

# FAST: BLAS Matrix-Vector Dot Product (0.8ms for 50k vectors)
# database shape: (N, d), query shape: (d,)
scores = np.dot(database_matrix, query_vector) # Output shape: (N,)

Under the hood, NumPy invokes optimized C/Fortran libraries (OpenBLAS, Intel MKL, or Apple Accelerate) using CPU vector registers (AVX-512, Neon) to process 16 to 32 floating-point multiplications per clock cycle.


4. Top-K Extraction: Argsort vs. Bounded Min-Heap

Diagram: how the nearest neighbours are extracted from a similarity computation

Once you have computed similarity scores for all N documents:


5. Benchmark: Latency Scaling with Vector Count

Empirical latency of vectorized exact k-NN search (d = 1536, float32) on an M-series Apple Silicon CPU:

Document Count (N)Compute Time (Dot Product)Top-10 Heap TimeTotal Latency
1,0000.04 ms0.01 ms0.05 ms
10,0000.22 ms0.04 ms0.26 ms
50,0000.95 ms0.12 ms1.07 ms
100,0001.85 ms0.21 ms2.06 ms
1,000,00022.40 ms1.80 ms24.20 ms

6. Score Calibration and Normalization Curves

Diagram: why raw similarity scores cannot be used as absolute thresholds

Raw cosine similarity scores often range from 0.60 to 0.95:


7. Asymmetric Dual-Encoder Indexing

When indexing documentation:


8. Batch Query Vectorization

When processing multiple user queries simultaneously (e.g. in a web server handling 50 concurrent requests):


9. Handling Missing or Dynamic Metadata Filters

In real-world search, users frequently combine vector search with structured filters (e.g. category == 'engineering' AND year >= 2024):


10. Summary: The Core Retrieval Engine


An everyday analogy

Diagram: catalogue lookup compared with a librarian who understands the question

Think of tuning a radio:


Examples in practice

Let us build a High-Performance Exact k-NN Search Engine:

import numpy as np
import heapq
from typing import List, Dict, Any, Tuple

class ExactKNNSearchEngine:
    def __init__(self, dimension: int):
        self.dimension = dimension
        self.vectors: np.ndarray = np.empty((0, dimension), dtype=np.float32)
        self.metadata: List[Dict[str, Any]] = []

    def add_documents(self, vectors: np.ndarray, metadatas: List[Dict[str, Any]]) -> None:
        # Adds and L2-normalizes document vectors
        if len(vectors) == 0:
            return
        norms = np.linalg.norm(vectors, axis=1, keepdims=True)
        norms[norms == 0] = 1.0
        normalized_vecs = vectors / norms
        
        self.vectors = np.vstack([self.vectors, normalized_vecs]) if self.vectors.size else normalized_vecs
        self.metadata.extend(metadatas)

    def search(self, query_vec: np.ndarray, top_k: int = 5) -> List[Tuple[Dict[str, Any], float]]:
        # Executes vectorized exact k-NN search using dot product
        if len(self.vectors) == 0:
            return []
        
        # Normalize query
        q_norm = np.linalg.norm(query_vec)
        q_unit = query_vec / (q_norm if q_norm > 0 else 1.0)

        # Vectorized dot product against all N vectors
        scores = np.dot(self.vectors, q_unit) # Shape: (N,)

        # Bounded Top-K selection using argpartition
        k = min(top_k, len(scores))
        if k == len(scores):
            top_indices = np.argsort(scores)[::-1]
        else:
            partition_idx = np.argpartition(scores, -k)[-k:]
            top_indices = partition_idx[np.argsort(scores[partition_idx])[::-1]]

        return [(self.metadata[idx], float(scores[idx])) for idx in top_indices]

Implications: security, privacy, performance, scalability, and cost

Diagram: the recall, cost, latency and quality-ceiling implications of similarity search

  1. Memory Bounds: Storing 500,000 vectors of dimension 1536 in float32 requires 500,000 * 1536 * 4 = 3.07 GB of RAM, fitting comfortably on any modern laptop or micro-server instance.
  2. Deterministic Reproducibility: Flat k-NN is 100% deterministic with zero approximation randomness, making it ideal for safety-critical medical, legal, and financial search pipelines.

Alternatives: free, open source, and commercial

SolutionEngine TypeMax Practical SizeLatency (100k vecs)Best For
NumPy / SciPyPure Python BLAS200,000 vectors2.0 msEmbedded scripts & testing
FAISS (Flat Index)C++ / CUDA5,000,000 vectors0.3 msHigh-throughput GPU clusters
ChromaDB / QdrantVector DatabaseBillions (HNSW)4.0 msProduction enterprise RAG

β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚                   EXACT SEARCH VS APPROXIMATE SEARCH                   β”‚
β”œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€
β”‚ Dimension          β”‚ Exact Flat k-NN             β”‚ Approximate (HNSW)  β”‚
β”œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€
β”‚ Recall Accuracy    β”‚ 100% Guaranteed             β”‚ 95% - 99% Heuristic β”‚
β”‚ Index Build Time   β”‚ 0 ms (Instant insert)       β”‚ Minutes to Hours    β”‚
β”‚ Search Complexity  β”‚ O(N * d)                    β”‚ O(log N * d)        β”‚
β”‚ Memory Overhead    β”‚ 0% (Raw vectors only)       β”‚ +50% Graph Pointers β”‚
β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜

When to use it β€” and when not to

Diagram: when exact similarity search suffices and when an index is required

When to Use Exact Flat k-NN:

When NOT to use:


The AI connection

Knowledge check

  1. What is the mathematical proof that cosine similarity and Euclidean distance are monotonically equivalent on unit vectors?
  2. Why is np.dot(matrix, query) significantly faster than a Python loop computing dot products?
  3. How does np.argpartition achieve O(N) Top-K selection compared to O(N \log N) full sorting?
  4. What is the memory footprint of storing 100,000 vectors of dimension 768 in float32?
  5. Why should you avoid setting a static threshold like sim > 0.95 for vector retrieval?

Hands-on exercise

In this lab, you will build and benchmark an Exact k-NN Semantic Search Engine: implement unit normalization, vectorized BLAS matrix multiplication, Top-K bounded heap selection, metadata pre-filtering, and evaluate retrieval accuracy and latency across varying corpus sizes.

Expected output

[Semantic Similarity Search Verification Suite]
Testing Normalization & Vectorized Search:
  Corpus Size: 10,000 vectors (dim=384)
  Exact Top-5 Nearest Neighbors retrieved in 0.42 ms [PASS]
  Top-1 Match Similarity: 0.9842 [PASS]
Testing Bounded Top-K Heap Selection:
  Argpartition vs Full Sort Index Equivalence: 100% Match [PASS]
Testing Metadata Pre-Filtering:
  Filtered Category 'engineering': 12 Matches Found [PASS]
Test Suite: 4 passed in 0.45s

Validate your work

Run the automated test runner:

./tests/run_tests.sh

Troubleshooting

Common mistakes


Practice assignment

  1. Implement Batch Query Processing that takes a batch of 10 query vectors and returns Top-5 results for all queries in a single matrix-matrix multiplication (np.dot(queries, database.T)).
  2. Measure the exact latency difference between float32 and float16 dot product calculations across 50,000 vectors.

Extension challenge

Implement a Sharded Parallel Exact k-NN Searcher using Python’s multiprocessing or concurrent.futures:

Quiz

Q1. What is the algorithmic time complexity of an exact (flat) k-NN search over N documents with embedding dimension d?

  1. O(N^3) cubic time
  2. O(1) constant time
  3. O(log N) logarithmic time
  4. O(N * d) β€” one dot product per document
Show answer

Answer: D. O(N * d) β€” one dot product per document

Exact k-NN performs an exhaustive linear scan, computing N dot products of dimension d.

Q2. Why is using a bounded min-heap (heapq) superior to full sorting (argsort) for Top-K retrieval when N is large?

  1. A bounded heap is O(N log K) instead of O(N log N)
  2. Because heaps only work in Python
  3. Because argsort crashes on floating point numbers
  4. Because heaps delete the database
Show answer

Answer: A. A bounded heap is O(N log K) instead of O(N log N)

When K << N, O(N log K) is significantly faster and uses minimal memory compared to full O(N log N) sorting.

Q3. Under what condition is Euclidean Distance (L2) directly proportional to Cosine Distance?

  1. When vectors contain only positive integers
  2. When every vector is unit-normalised
  3. When the dimension is equal to 3
  4. Never; they are completely unrelated
Show answer

Answer: B. When every vector is unit-normalised

For unit vectors, ||u - v||^2 = 2 - 2*(u Β· v), establishing an exact monotonic equivalence.

Q4. What is the performance advantage of matrix-vector multiplication (np.dot(matrix, query)) over Python for-loops in k-NN search?

  1. Matrix multiplication turns off the CPU fan
  2. Matrix multiplication uses less disk space
  3. Matrix multiply uses SIMD and threaded BLAS
  4. There is no difference
Show answer

Answer: C. Matrix multiply uses SIMD and threaded BLAS

Vectorized BLAS operations utilize hardware parallel registers and cache locality.

Q5. When is exact Flat k-NN search preferred over Approximate Nearest Neighbor (HNSW) indexing?

  1. When vectors are text strings
  2. When searching across 1 billion items
  3. When you do not have a CPU
  4. Under 100k vectors, with frequent inserts and full recall
Show answer

Answer: D. Under 100k vectors, with frequent inserts and full recall

For moderate collections (<100k vectors), flat search executes in under 2ms with zero index build time.

Glossary

k-Nearest Neighbors (k-NN)
An exact search algorithm that computes distances between a query and all corpus vectors to find the K closest items.
Cosine Distance
Defined as 1.0 - CosineSimilarity; a proper geometric distance metric ranging from 0.0 (identical) to 2.0 (opposite).
Euclidean Distance (L2)
The straight-line length of the vector difference between two coordinates in multi-dimensional space.
Manhattan Distance (L1)
The sum of absolute differences across all coordinates; also known as taxicab or L1 distance.
Top-K Retrieval
Extracting the top K highest-scoring items from a scored list without sorting the entire collection.
BLAS (Basic Linear Algebra Subprograms)
Low-level hardware-optimized routines for high-performance matrix and vector arithmetic.
Linear Scan
Iterating through every entry in a database sequentially to compute exact distance metrics.
Recall
The proportion of true top-K nearest neighbors successfully returned by a search algorithm.

Sources and further reading


Kept in this browser, no account needed. Your progress page turns the whole record into one link you can bookmark or open on another device.