Semantic Search in Machine Learning

The Problem with Keywords

Classical information retrieval systems rely on sparse lexical representations: a query is decomposed into tokens, each token is matched against an inverted index, and documents are scored by term-frequency statistics.

BM25 — the dominant algorithm for three decades — is fast, interpretable, and requires no training data. That's pretty great, right?

BUT here's the fundamental limitation: BM25 is structurally incapable of bridging the vocabulary mismatch between how users phrase questions and how authors write answers.

Consider this: the query "affordable sedan with good mileage" and the passage "budget-friendly compact car offering excellent fuel economy" are semantically equivalent — but they share zero lexical overlap. BM25 would score this match at zero. A Swiggy user searching for "chiken biriyani" would miss perfectly relevant results listed as "Hyderabadi chicken biryani" because the spelling doesn't match.

Early Attempts (and Why They Fell Short)

Early approaches to close this gap — query expansion, synonym dictionaries, latent semantic analysis — offered marginal improvements at considerable engineering cost. You'd spend weeks building synonym dictionaries only to discover that language is far too creative to capture in static mappings.

The Breakthrough: Neural Encoders

The real breakthrough came with transformer-based encoders trained with contrastive objectives that learn to project semantically similar text into proximate regions of a continuous vector space.

Karpukhin et al. (EMNLP 2020) demonstrated with Dense Passage Retrieval (DPR) that a dual-encoder trained on question-answer pairs outperformed BM25 by 9-19 points of top-20 retrieval accuracy on multiple open-domain QA benchmarks — without any term-matching heuristics.

Why This Matters for Production Systems

Semantic search exists because production systems need meaning-level retrieval at scale:

• Search engines must understand intent, not just keywords
• RAG systems must ground LLMs in contextually relevant passages, not merely string-matched fragments
• E-commerce platforms like Flipkart and Amazon must surface items that satisfy latent user preferences even when the query is vague ("something cozy for winter evenings")
• Food delivery apps like Swiggy and Zomato must handle multilingual, misspelled, transliterated queries across 500+ Indian cities

Dense retrieval, powered by learned representations and efficient ANN indexing, is the enabling technology for all of these capabilities.

The Geometric Insight

The core intuition behind semantic search is beautifully geometric: if you train a neural network to place semantically similar texts near each other in a high-dimensional space, retrieval reduces to finding the nearest points to the query vector.

That's it. That's the entire idea.

How the Model Learns This

Training uses contrastive learning — the model sees triplets of (query, positive passage, negative passages) and adjusts its parameters so that:

• Positive pairs have high cosine similarity
• Negative pairs are pushed apart

After training, the encoder produces a fixed-length vector for any text input, and all the semantic understanding the model has learned is compressed into the distances between these vectors.

The Offline-Online Trick

Here's the architectural insight that makes semantic search practical at scale: we decouple document encoding from query encoding.

• Document encoding happens offline, once per corpus update. You can take your time — run it on a batch of GPUs overnight.
• Query encoding happens online, per request. This is a single encoder forward pass — typically 5-20ms on a GPU.
• ANN lookup finds the nearest neighbors in the pre-built index — another 1-10ms.

Total online cost per query? Under 50 milliseconds, irrespective of corpus size. Whether you have 10,000 documents or 10 billion, the query-time cost stays roughly the same. That was pretty simple, wasn't it?

Key Insight: This offline-online decoupling is what separates bi-encoder semantic search from cross-encoder approaches. A cross-encoder scores each query-document pair jointly — accurate, but $O(N)$ per query. A bi-encoder does the heavy lifting offline.

What Determines Quality?

The quality of semantic search is bounded by two independent factors:

1. Embedding model quality — its ability to capture nuanced meaning (determined by architecture, training data, and objective function)
2. ANN index quality — its ability to find true nearest neighbors efficiently (determined by index type, parameters, and the recall-throughput tradeoff)

Improving either factor independently improves the end-to-end system. This modularity is one of the reasons semantic search is such a popular architecture.

Let's build up the math step by step. I'll explain the intuition first, then give the formal notation.

The Retrieval Problem

We want to find the $k$ most relevant documents for a given query. Semantic search formalizes this as a maximum inner product search (MIPS) or nearest neighbor search in a learned embedding space.

Let $f_\theta : \mathcal{T} \rightarrow \mathbb{R}^d$ be an encoder parameterized by $\theta$ that maps a text input from token space $\mathcal{T}$ to a $d$-dimensional real-valued vector.

Given a query $q$ and a corpus $\mathcal{C} = \{d_1, d_2, \ldots, d_N\}$, semantic search retrieves the top-$k$ documents:

$\text{Retrieve}(q, k) = \underset{k}{\arg\max} \; \{ \text{sim}(f_\theta(q), f_\theta(d_i)) \mid d_i \in \mathcal{C} \}$

where $\text{sim}(\cdot, \cdot)$ is typically cosine similarity:

$\text{sim}(\mathbf{a}, \mathbf{b}) = \frac{\mathbf{a} \cdot \mathbf{b}}{\|\mathbf{a}\| \cdot \|\mathbf{b}\|}$

The Training Objective

How does the encoder learn to place similar texts nearby? Through the InfoNCE loss — a contrastive objective.

Given a batch of queries $\{q_j\}$ with corresponding positive passages $\{d_j^+\}$ and negative passages $\{d_{j,i}^-\}$:

$\mathcal{L} = -\frac{1}{B} \sum_j \log \frac{\exp(\text{sim}(f_\theta(q_j), f_\theta(d_j^+)) / \tau)}{\exp(\text{sim}(f_\theta(q_j), f_\theta(d_j^+)) / \tau) + \sum_i \exp(\text{sim}(f_\theta(q_j), f_\theta(d_{j,i}^-)) / \tau)}$

where $\tau$ is a temperature hyperparameter (controls how sharply the model discriminates) and $B$ is the batch size.

Intuitively, this loss says: "Make the positive pair's similarity high relative to all the negative pairs." It's essentially a softmax classification where the model must pick the correct passage out of a crowd of distractors.

Variants

• DPR (Karpukhin et al., 2020) uses separate encoders for queries and passages with in-batch negatives.
• ColBERT (Khattab & Zaharia, 2020) refines this with token-level late interaction:

$\text{sim}_{\text{ColBERT}}(q, d) = \sum_{i=1}^{|q|} \max_{j=1}^{|d|} \mathbf{E}_{q_i} \cdot \mathbf{E}_{d_j}^T$

where $\mathbf{E}_q$ and $\mathbf{E}_d$ are per-token embeddings. This enables finer-grained matching while retaining the ability to pre-compute document representations.

Complexity

At inference, exact search over $N$ documents requires $O(N \cdot d)$ operations per query — impractical for large corpora. Approximate nearest neighbor algorithms reduce this to:

• $O(\log N)$ for graph-based methods like HNSW (Malkov & Yashunin, 2018)
• $O(\sqrt{N})$ for partition-based methods like IVF

For a corpus of 100 million documents, that's the difference between 100,000,000 comparisons and roughly 17 comparisons (HNSW). That's a 1,000,000x speedup.

Let me wrap up everything we've covered about semantic search.

• Semantic search retrieves documents based on meaning, not keyword overlap. Neural encoders map queries and documents into a shared dense vector space where similarity is computed geometrically — $\text{sim}(\mathbf{q}, \mathbf{d}) = \frac{\mathbf{q} \cdot \mathbf{d}}{\|\mathbf{q}\| \cdot \|\mathbf{d}\|}$

• The offline-online split is the key architectural insight: documents are encoded once during ingestion; only the query encoding ($5$-$20$ms on GPU) and ANN lookup ($1$-$10$ms) happen per request. This makes query latency independent of corpus size.

• Three seminal works established the field: Sentence-BERT (Reimers & Gurevych, EMNLP 2019) provided the bi-encoder training framework, DPR (Karpukhin et al., EMNLP 2020) established the dual-encoder paradigm, and ColBERT (Khattab & Zaharia, SIGIR 2020) introduced fine-grained late interaction.

• Hard negative mining is essential — training with BM25-retrieved or ANCE-style dynamically mined negatives produces encoders that make fine-grained semantic distinctions, not just coarse topic-level groupings.

• HNSW dominates production deployments: recall@10 > 0.95 at <5ms per query. IVF+PQ provides 8-16x memory savings when RAM is constrained.

• Hybrid search is the recommended default — combining dense retrieval with BM25 via reciprocal rank fusion consistently outperforms either method alone. Pure dense retrieval can underperform BM25 on out-of-domain queries (BEIR benchmark).

• Production essentials: recall monitoring against golden evaluation sets, embedding model versioning with blue-green re-indexing, metadata filtering for access control, and cost-aware choices between API-based (OpenAI at $0.02-0.13/million tokens, ~INR 1.7-11/million tokens) and self-hosted encoders.

Semantic search is the retrieval backbone of modern RAG systems, knowledge-base search, and content discovery. Its quality ceiling is jointly determined by the embedding model's representational fidelity and the ANN index's recall-throughput characteristics — improving either factor independently lifts the entire system. Moving on from here, the natural next steps are understanding re-ranking (downstream) and hybrid search (a complementary pattern).