AlgoInsight

Free lesson · ML System Design Interviews

Embeddings and Vector Spaces

Easy12 min readmachine-learningml-system-designinterview-prep

What Are Embeddings?

An embedding is a way to turn something (a word, an image, a person, a product) into a list of numbers that computers can understand and compare.

Imagine you're teaching a robot to understand fruits. You can't show it pictures forever. Instead, you'd describe each fruit with a list of properties:

Apple:   [sweetness: 7, size: 5, red: 8, firmness: 8]
Banana:  [sweetness: 8, size: 6, yellow: 9, firmness: 5]
Orange:  [sweetness: 6, size: 6, orange: 9, firmness: 7]
Lemon:   [sweetness: 2, size: 4, yellow: 8, firmness: 7]

Now the robot can compare fruits mathematically. It sees that apples and bananas are similar (both sweet), while lemons are very different (not sweet). That's an embedding - turning raw data into meaningful numbers.

The GPS Analogy

Think of embeddings like GPS coordinates for concepts.

These two cities are geographically close to each other (New York and Boston), so their coordinates are similar. These coordinates let you:

Embeddings work the same way. In "embedding space":

Types of Embeddings

Word Embeddings

Convert words into numbers so the computer understands meaning.

Word: "King"
Embedding: [0.2, -0.5, 0.8, 0.1, -0.3, ...]  # Usually 100-300 dimensions

Word: "Queen"
Embedding: [0.3, -0.48, 0.79, 0.15, -0.28, ...] # Very similar!

💡 Tip: Word embeddings capture semantic meaning. Words with similar meanings (like "king" and "queen") end up with similar numbers.

The famous analogy: "King" - "Man" + "Woman" ≈ "Queen"

This happens because the math of embeddings captures these relationships!

Image Embeddings

Convert images into a list of numbers representing their visual features.

Imagine training a neural network on millions of dog photos. The network learns to describe dogs with numbers like:

"fluffy score": 0.8
"size": 0.6
"brownish color": 0.7
"ear shape": 0.4

A photo of a fluffy golden retriever and a fluffy poodle will have very similar embeddings, even though they look quite different.

User and Item Embeddings

In recommendation systems, represent users and products as embeddings.

User: [likes_action: 0.8, likes_romance: 0.2, watches_late: 0.9, ...]
Movie: [is_action: 0.9, is_romance: 0.1, long_runtime: 0.8, ...]

When embeddings align (both have high "likes_action" and "is_action"), the recommendation system predicts the user will enjoy the movie.

Embedding Space: The Core Idea

Embedding space is an imaginary multidimensional space where each object has a location.

Objects that are semantically similar end up close together in this space.

In embedding space:
- "dog" and "cat" are neighbors (both animals)
- "dog" and "pizza" are far apart (totally different)
- "student" and "teacher" are relatively close (both in education)

How Similarity Search Works

Once you have embeddings, you can measure how similar two things are using math.

Cosine Similarity

Imagine two arrows pointing in different directions. Cosine similarity measures the angle between them.

If arrows point the same direction:     cosine_similarity = 1.0 (identical)
If arrows are perpendicular:             cosine_similarity = 0.0 (completely different)
If arrows point opposite directions:     cosine_similarity = -1.0 (opposite)

Formula:

cosine_similarity = (vector_a · vector_b) / (|vector_a| * |vector_b|)

Where:

Dot Product

A simpler measure that also works well for embeddings that are already normalized:

dot_product = sum of (element_a[i] * element_b[i]) for all i

Python Example: Computing Cosine Similarity

import math

def cosine_similarity(vector_a, vector_b):
    """
    Calculate cosine similarity between two vectors.
    Returns a number between -1 and 1.
    1 means identical, 0 means perpendicular, -1 means opposite.
    """
    # Step 1: Calculate dot product
    dot_product = sum(a * b for a, b in zip(vector_a, vector_b))

    # Step 2: Calculate magnitudes
    magnitude_a = math.sqrt(sum(a ** 2 for a in vector_a))
    magnitude_b = math.sqrt(sum(b ** 2 for b in vector_b))

    # Step 3: Avoid division by zero
    if magnitude_a == 0 or magnitude_b == 0:
        return 0

    # Step 4: Compute cosine similarity
    return dot_product / (magnitude_a * magnitude_b)


# Example: embeddings for fruits
apple = [0.7, 0.3, 0.1, 0.8, 0.2]     # sweet, not sour, small-ish, firm, red
banana = [0.8, 0.2, 0.05, 0.4, 0.1]   # sweet, not sour, thin, soft, yellow
lemon = [0.1, 0.9, 0.8, 0.6, 0.3]     # not sweet, sour, yellow, firm, small

# Compare
print(f"Apple vs Banana: {cosine_similarity(apple, banana):.3f}")  # High (both sweet)
print(f"Apple vs Lemon:  {cosine_similarity(apple, lemon):.3f}")   # Low (different)
print(f"Banana vs Lemon: {cosine_similarity(banana, lemon):.3f}")  # Low (different)

# Output:
# Apple vs Banana: 0.987  (very similar!)
# Apple vs Lemon:  0.623  (somewhat different)
# Banana vs Lemon: 0.524  (quite different)

📝 Note: In real ML systems, you'd use optimized libraries like NumPy or scikit-learn, but this shows the core math.

Finding Similar Items: Nearest Neighbors

Once you have embeddings and a similarity measure, finding similar items is straightforward:

  1. You have an embedding for your query (a user's interests, a product description, etc.)
  2. You compute similarity to ALL items in your database
  3. You sort by similarity and return the top K results
def find_k_nearest_neighbors(query_embedding, database_embeddings, k=5):
    """
    Find k most similar items to the query.

    Args:
        query_embedding: [d1, d2, ..., dn]
        database_embeddings: list of embeddings
        k: number of results to return

    Returns:
        indices of k nearest neighbors
    """
    similarities = []

    for idx, item_embedding in enumerate(database_embeddings):
        sim = cosine_similarity(query_embedding, item_embedding)
        similarities.append((idx, sim))

    # Sort by similarity (descending)
    similarities.sort(key=lambda x: x[1], reverse=True)

    # Return top k
    return [idx for idx, _ in similarities[:k]]

Why Embeddings Are the Backbone of Modern ML

1. Universal Representation

Any data type can be converted to embeddings: text, images, audio, videos, users, products.

2. Geometric Reasoning

Once you have embeddings, you can:

3. Transfer Learning

Use embeddings trained on huge datasets. You don't need to train from scratch for your specific problem.

4. Scalability

With ~300 dimensions per embedding, you can:

5. The Foundation for Modern Systems

The Math Behind Embeddings

To use embeddings effectively, you need to understand three core similarity measures.

Dot Product

The dot product (or inner product) is the simplest similarity measure:

dot_product(A, B) = A[0]*B[0] + A[1]*B[1] + A[2]*B[2] + ... + A[n]*B[n]

Numerical example:

Vector A = [1, 2, 3]
Vector B = [4, 5, 6]

dot_product = (1*4) + (2*5) + (3*6) = 4 + 10 + 18 = 32

Interpretation:

When to use: Fast similarity, especially in embedding spaces (embeddings are typically normalized).

Euclidean Distance

The Euclidean distance is the straight-line distance between two points:

euclidean_distance(A, B) = sqrt((A[0]-B[0])² + (A[1]-B[1])² + ... + (A[n]-B[n])²)

Numerical example:

Vector A = [1, 2, 3]
Vector B = [4, 5, 6]

distance = sqrt((1-4)² + (2-5)² + (3-6)²)
         = sqrt(9 + 9 + 9)
         = sqrt(27)
         = 5.2

Interpretation:

When to use: When you care about actual distances (e.g., clustering).

Cosine Similarity

The cosine similarity measures the angle between vectors (ignores magnitude):

cosine_similarity(A, B) = (A · B) / (|A| * |B|)

Where:
- A · B = dot product
- |A| = magnitude of A = sqrt(A[0]² + A[1]² + ... + A[n]²)
- |B| = magnitude of B

Numerical example:

Vector A = [1, 2, 3]
Vector B = [4, 5, 6]

Dot product = 32 (from above)

|A| = sqrt(1² + 2² + 3²) = sqrt(14) = 3.74
|B| = sqrt(4² + 5² + 6²) = sqrt(77) = 8.77

cosine_similarity = 32 / (3.74 * 8.77) = 32 / 32.8 = 0.976

Interpretation:

When to use: Almost always for embeddings. Best metric for capturing semantic similarity.

📝 Comparison:

  • Dot product: Fast, works for normalized vectors
  • Euclidean distance: Sensitive to magnitude, good for clustering
  • Cosine similarity: Magnitude-invariant, best for embeddings

How Word2Vec Learns Embeddings

Word2Vec is a foundational technique that learns word embeddings automatically from text. Instead of hand-crafting features, it learns meaning from context.

The Core Idea

Words that appear in similar contexts have similar meanings.

"The cat sat on the mat"
"The dog sat on the rug"

The words "cat" and "dog" appear in similar positions → should have similar embeddings

Skip-gram Model

Skip-gram learns embeddings by predicting context words.

Task: Given a word, predict the words around it.

Sentence: "The cat sat on the mat"
Window size: 2

Training examples:
- Input: "cat" → Predict: ["The", "sat"] (words within 2 positions)
- Input: "sat" → Predict: ["cat", "on"]
- Input: "on"  → Predict: ["sat", "the"]
- Input: "the" → Predict: ["on", "mat"]

How it learns:

  1. Random embeddings for each word: "cat" = [0.1, -0.2, 0.8, ...]
  2. Use embeddings to predict context words
  3. If predictions are wrong, adjust embeddings
  4. After seeing millions of examples, embeddings capture meaning

Why it works:

CBOW Model

CBOW (Continuous Bag of Words) is the reverse: predict a word from context.

Sentence: "The cat sat on the mat"

Training examples:
- Input: ["The", "sat"] → Predict: "cat"
- Input: ["cat", "on"] → Predict: "sat"
- Input: ["sat", "the"] → Predict: "on"

Comparison:

Concrete Example: Learning "King" and "Queen"

Start with random embeddings for common words:

king = [0.2, -0.5, 0.8, 0.1]
queen = [0.3, -0.48, 0.79, 0.15]  (initially very different)
man = [0.1, -0.3, 0.6, 0.2]
woman = [0.25, -0.45, 0.75, 0.12]

Skip-gram learns:

After training:

king   ≈ [0.18, -0.52, 0.82, 0.08]  (similar to man + royal)
queen ≈ [0.28, -0.50, 0.80, 0.10]   (similar to woman + royal)
man   ≈ [0.12, -0.32, 0.62, 0.18]
woman ≈ [0.26, -0.47, 0.78, 0.10]

Now: king - man + woman ≈ queen (because embeddings capture semantic relationships!)

🎯 Interviewer's Perspective: Word2Vec was groundbreaking because it showed embeddings can be learned automatically from text, without labeled data. This enabled the modern NLP era.

Embedding Dimensionality

One key question: how many dimensions do you need?

Common Dimensions

Task                          Typical Dimensions    Trade-off
─────────────────────────────────────────────────────────────
Word embeddings (Word2Vec)    50-300                Medium complexity
FastText (char-level)         100-300               Handle typos
GloVe (public embeddings)     100-300               Pre-trained
Sentence embeddings (SBERT)   384-768               Higher quality
Image embeddings (ResNet)     512-2048              Complex visual patterns
Dense retrieval (modern)      384-1536              SOTA retrieval quality

Why Not Just Use 10,000 Dimensions?

More dimensions = more model capacity, but:

  1. Curse of dimensionality: Distances become less meaningful

    • With 10 dimensions: Many points are far apart
    • With 10,000 dimensions: All distances are similar! (neighbors become meaningless)

  2. Storage and memory:

    • 1M embeddings × 100 dims × 4 bytes = 400 MB (fits in RAM)
    • 1M embeddings × 10,000 dims × 4 bytes = 40 GB (costs money)

  3. Computation cost:

    • Dot product in 100 dims: 100 operations
    • Dot product in 10,000 dims: 10,000 operations
    • With 1B items in database: 100B vs 10T operations

  4. Sparsity problem:

    • Low dimensions: Most variance explained
    • High dimensions: Most variance is noise

Optimal Dimension Strategy

# Typical approach:
# Start small, grow if needed

config = {
    "task": "semantic search",
    "corpus_size": 1_000_000,
    "latency_requirement": "50ms per query",

    # Start with 384 (popular sentence embedding size)
    "initial_dim": 384,

    # Measure performance
    "metrics": ["recall@100", "latency_per_query", "memory_usage"],

    # If recall < 95%, increase to 768
    # If latency > 100ms, decrease to 256
    # If memory > budget, decrease dimensions
}

💡 Tip: 384 dimensions is the "sweet spot" for most semantic search tasks. It balances quality, speed, and memory.

Approximate Nearest Neighbor Search

The Naive Approach: Brute Force

To find similar embeddings, you could compare to every item:

def brute_force_search(query_embedding, all_embeddings, k=10):
    """Find k nearest neighbors by comparing to all items."""

    similarities = []
    for i, item_embedding in enumerate(all_embeddings):
        sim = cosine_similarity(query_embedding, item_embedding)
        similarities.append((i, sim))

    # Sort and return top k
    return sorted(similarities, key=lambda x: x[1], reverse=True)[:k]

Performance:

Corpus size: 1,000,000 items
Dimensions: 384
Time per similarity: ~1 microsecond

Total time = 1,000,000 * 1 microsecond = 1 second per query

At 100 queries/second = 100 seconds of CPU time = not acceptable!

Approximate Nearest Neighbors (ANN)

Instead, partition the space so you only check relevant items.

Approach 1: Locality Sensitive Hashing (LSH)

Idea: Hash similar vectors to the same bucket.

Query embedding: [0.5, -0.3, 0.8, ...]

Hash function 1: [round(0.5), round(-0.3), round(0.8)] = [1, 0, 1]
Hash function 2: [round(0.5*2), round(-0.3*2), round(0.8*2)] = [1, 0, 1]
Hash function 3: [round(0.5*3), round(-0.3*3), round(0.8*3)] = [2, -1, 2]

Concatenate: "101101-1 2" → bucket ID

Look up: All items in this bucket are candidates!

Trade-off:

Time improvement: 1 million items → only check ~1000 candidates = 1000x speedup!

Approach 2: Inverted File with Vector Quantization (IVF)

Idea: Cluster embeddings, then search only relevant clusters.

Step 1: Offline (once per week)
  - Run K-means on all embeddings, create 1000 clusters
  - Store which cluster each embedding belongs to

Step 2: Query time (milliseconds)
  - Find the 10 nearest clusters to query
  - Only search embeddings in those clusters
  - Return top results

Time breakdown:

Trade-off:

Approach 3: Hierarchical Navigable Small World (HNSW)

Idea: Build a graph where nearby vectors are connected.

Start at query vector Q

From Q, find nearest neighbor in graph → P1
From P1, find nearest neighbors in P1's neighbors → P2
From P2, find nearest neighbors → P3
... repeat hierarchically

Eventually converge to nearest neighbors!

Why it's fast:

Time: O(log N) for billion items ≈ 30 comparisons instead of 1 billion!

Characteristics:

🎯 Interviewer's Perspective: Know the three approaches. HNSW is state-of-the-art. When someone says "vector database", they typically use HNSW internally.

Python Example: Building a Simple FAISS Index

import numpy as np
import faiss

# Step 1: Generate embeddings (in practice, from a model)
# Imagine we have 100,000 product embeddings
n_samples = 100_000
embedding_dim = 384

embeddings = np.random.randn(n_samples, embedding_dim).astype('float32')

# Step 2: Create FAISS index (IVF + PQ for efficiency)
# IVF = Inverted File (cluster-based)
# PQ = Product Quantization (compress embeddings)

n_clusters = 100  # Number of clusters
quantizer = faiss.IndexFlatL2(embedding_dim)  # Distance metric: L2 (Euclidean)
index = faiss.IndexIVFFlat(quantizer, embedding_dim, n_clusters, faiss.METRIC_L2)

# Step 3: Train and add embeddings
index.train(embeddings)  # Learn cluster centers
index.add(embeddings)    # Add all embeddings to index

print(f"Index contains {index.ntotal} vectors")

# Step 4: Search for nearest neighbors
query_embedding = np.random.randn(1, embedding_dim).astype('float32')
k = 10  # Find top 10 nearest

distances, indices = index.search(query_embedding, k)

print(f"Top {k} nearest neighbors:")
for i, idx in enumerate(indices[0]):
    distance = distances[0][i]
    print(f"  {i+1}. Item {idx} (distance: {distance:.4f})")

# Step 5: Time comparison
import time

# Brute force search
start = time.time()
for _ in range(100):
    # Compare query to all embeddings (slow)
    sims = np.dot(embeddings, query_embedding.T)
    top_k = np.argsort(sims.flatten())[-k:]
brute_force_time = time.time() - start

# FAISS search
start = time.time()
for _ in range(100):
    distances, indices = index.search(query_embedding, k)
faiss_time = time.time() - start

print(f"\nTiming (100 queries):")
print(f"  Brute force: {brute_force_time:.2f}s")
print(f"  FAISS:       {faiss_time:.2f}s")
print(f"  Speedup:     {brute_force_time/faiss_time:.1f}x")

# Output (approximate):
# Brute force: 12.5s
# FAISS:       0.3s
# Speedup:     42x

Key Takeaways

🎯 Interviewer's Perspective: Be ready to explain:

  1. What embeddings are (numbers that represent meaning)
  2. The GPS coordinate analogy (similar things are close)
  3. How to measure similarity (cosine similarity, dot product)
  4. Why embeddings matter in production systems (efficiency, generalization, scalability)

Embeddings are lists of numbers that capture the meaning or characteristics of something. Similar things have similar numbers. This simple idea is the foundation of modern recommendation systems, search, and LLM-based applications.

Back to ML System Design Interviews