Phase 0: Development Environment & Mathematical Foundations · 65 min · Python · NumPy
The Concept
The Retrieval Problem
Given a query and a collection of documents, find the most relevant documents. This sounds simple, but it is the core of every search engine, every RAG system, and every recommendation engine. The challenge is defining "relevant" in a way a computer can compute.
There are two fundamental approaches, and they capture different kinds of relevance:
- Lexical search — match words in the query to words in the documents (TF-IDF, BM25). If the query says "vector search" and a document contains "vector search," it's probably relevant. This is fast, requires no model, and is still the backbone of Elasticsearch and Lucene.
- Semantic search — match meaning using dense vector embeddings. If the query says "similarity lookup" and a document contains "vector search," semantic search can connect them even though no words overlap, because the embedding model learned that these phrases mean similar things.
In production RAG, you combine both (hybrid search) because each catches what the other misses: lexical search is precise for exact terms, names, and IDs; semantic search handles paraphrasing, synonyms, and conceptual matching.
TF-IDF: Why Rare Words Matter More
The intuition behind TF-IDF is something you already understand intuitively: if someone searches for "the," every document matches — it's useless. If someone searches for "quantization," only a few documents match — it's highly informative. TF-IDF turns this intuition into a score by combining two factors:
- Term Frequency (TF): how many times the word appears in this document. A document that mentions "search" five times is probably more about search than one that mentions it once.
- Inverse Document Frequency (IDF): how rare the word is across the entire collection. A word that appears in 2 out of 100 documents is distinctive — it carries more information about which documents are relevant. A word that appears in 80 out of 100 documents is nearly useless for distinguishing between them.
The product TF × IDF gives a weight for each word in each document. Common words get low weights; rare, distinctive words get high weights. When you compute cosine similarity between a query vector and document vectors in this weighted space, you're measuring how much they overlap in the informative words — not just the raw word counts.
TF(t, d) = count of term t in document d / total terms in d
IDF(t) = log(N / df(t)) where N = total docs, df(t) = docs containing t
TF-IDF = TF × IDF
A word appears in 2 out of 100 documents. Another word appears in 80 out of 100. Which has a higher IDF score?
IDF = log(N / df). A word in 2 docs: IDF = log(100/2) ≈ 3.9. A word in 80 docs: IDF = log(100/80) ≈ 0.22. Rare words are more distinctive, so they get higher IDF — this is the core idea behind TF-IDF.
Common words ("the", "is") have low IDF. Rare words ("quantization", "reranking") have high IDF.
import numpy as np
from typing import list
class TfidfVectorizer:
"""TF-IDF vectorizer from scratch."""
def fit(self, documents: list[str]) -> None:
# Build vocabulary
self.vocab: dict[str, int] = {}
for doc in documents:
for word in doc.lower().split():
if word not in self.vocab:
self.vocab[word] = len(self.vocab)
# Compute document frequency (df) for each term
N = len(documents)
df = np.zeros(len(self.vocab))
for doc in documents:
words = set(doc.lower().split())
for word in words:
df[self.vocab[word]] += 1
# IDF: log(N / df). Add 1 to avoid division by zero
self.idf = np.log((N + 1) / (df + 1)) + 1 # smoothed IDF
# Precompute document vectors
self.doc_vectors = np.array([self._vectorize(doc) for doc in documents])
def _vectorize(self, text: str) -> np.ndarray:
vec = np.zeros(len(self.vocab))
words = text.lower().split()
for word in words:
if word in self.vocab:
vec[self.vocab[word]] += 1
# TF (raw count / total terms)
total = len(words) if words else 1
tf = vec / total
# TF-IDF
return tf * self.idf
def search(self, query: str, top_k: int = 5) -> list[tuple[int, float]]:
"""Return top-k document indices and cosine similarities."""
query_vec = self._vectorize(query)
# Cosine similarity = dot product / (norm * norm)
query_norm = np.linalg.norm(query_vec) + 1e-8
doc_norms = np.linalg.norm(self.doc_vectors, axis=1) + 1e-8
similarities = (self.doc_vectors @ query_vec) / (doc_norms * query_norm)
# Top-k
top_idx = np.argsort(similarities)[::-1][:top_k]
return [(i, similarities[i]) for i in top_idx]
# Usage
docs = [
"machine learning models for classification",
"deep learning neural networks",
"vector search and retrieval augmented generation",
"gradient descent optimization algorithm",
"transformer attention mechanism for nlp",
"rag systems with vector databases",
]
vectorizer = TfidfVectorizer()
vectorizer.fit(docs)
results = vectorizer.search("vector search retrieval", top_k=3)
for idx, score in results:
print(f" [{score:.4f}] {docs[idx]}")
Here's the semantic-search half of the picture, stripped down to plain lists of floats — no numpy, no real embedding model, just cosine similarity and a nearest-neighbor scan:
import math
def cosine_similarity(a: list[float], b: list[float]) -> float:
dot = sum(x * y for x, y in zip(a, b))
norm_a = math.sqrt(sum(x * x for x in a))
norm_b = math.sqrt(sum(y * y for y in b))
if norm_a == 0 or norm_b == 0:
return 0.0
return dot / (norm_a * norm_b)
# Toy 3-dim "embeddings" standing in for real 768-dim vectors
embeddings = {
"cat sat on mat": [0.9, 0.1, 0.0],
"dog ran in park": [0.8, 0.2, 0.1],
"stock market crashed": [0.0, 0.1, 0.9],
"puppy played fetch": [0.7, 0.3, 0.1],
}
query_vec = [0.85, 0.15, 0.05] # pretend embedding for "small dog playing"
scores = [(text, cosine_similarity(query_vec, vec)) for text, vec in embeddings.items()]
scores.sort(key=lambda pair: pair[1], reverse=True)
print("Nearest neighbors to the query:")
for text, score in scores:
print(f" [{score:.4f}] {text}")
# Try it: change query_vec to be closer to [0.0, 0.1, 0.9] and rerun —
# watch "stock market crashed" jump to the top of the ranking.
BM25: The Industry Standard Lexical Ranker
TF-IDF has two weaknesses that BM25 fixes. First, term frequency scales linearly — a document mentioning a word 10 times gets 10x the score of one mentioning it once. But in practice, the 10th mention adds less information than the 1st. BM25 introduces term frequency saturation: after a few mentions, additional occurrences contribute less and less (controlled by parameter $k_1$, typically 1.5).
Second, TF-IDF doesn't account for document length. A 5000-word document naturally mentions any given word more than a 100-word document, but that doesn't mean it's more relevant. BM25 introduces document length normalization (controlled by parameter $b$, typically 0.75): longer documents are penalized so that a short, focused document can outrank a long, rambling one.
These two improvements make BM25 the default ranking algorithm in Elasticsearch, Lucene, and most search infrastructure. It has been the lexical search standard for decades and remains a critical component of hybrid RAG pipelines.
import numpy as np
class BM25:
"""BM25 ranking algorithm from scratch."""
def __init__(self, k1: float = 1.5, b: float = 0.75):
self.k1 = k1 # term frequency saturation
self.b = b # document length normalization
def fit(self, documents: list[list[str]]) -> None:
self.documents = documents
self.N = len(documents)
self.doc_len = np.array([len(doc) for doc in documents])
self.avgdl = self.doc_len.mean()
# Build vocabulary and document frequency
self.vocab: dict[str, int] = {}
df: dict[str, int] = {}
for doc in documents:
unique = set(doc)
for word in unique:
df[word] = df.get(word, 0) + 1
if word not in self.vocab:
self.vocab[word] = len(self.vocab)
# IDF: log((N - df + 0.5) / (df + 0.5) + 1)
self.idf: dict[str, float] = {}
for word, freq in df.items():
self.idf[word] = np.log((self.N - freq + 0.5) / (freq + 0.5) + 1)
# Build term frequency index
self.tf: list[dict[str, int]] = []
for doc in documents:
tf: dict[str, int] = {}
for word in doc:
tf[word] = tf.get(word, 0) + 1
self.tf.append(tf)
def score(self, query: list[str], doc_idx: int) -> float:
"""Compute BM25 score for a query-document pair."""
score = 0.0
doc_tf = self.tf[doc_idx]
dl = self.doc_len[doc_idx]
for term in query:
if term not in self.idf:
continue
tf = doc_tf.get(term, 0)
idf = self.idf[term]
# BM25 formula
numerator = tf * (self.k1 + 1)
denominator = tf + self.k1 * (1 - self.b + self.b * dl / self.avgdl)
score += idf * (numerator / denominator) if denominator > 0 else 0
return score
def search(self, query: list[str], top_k: int = 5) -> list[tuple[int, float]]:
scores = [(i, self.score(query, i)) for i in range(self.N)]
scores.sort(key=lambda x: x[1], reverse=True)
return scores[:top_k]
# Usage
docs_tokenized = [doc.split() for doc in [
"machine learning models for classification tasks",
"deep learning neural networks and backpropagation",
"vector search retrieval augmented generation rag",
"gradient descent optimization for machine learning",
"transformer attention mechanism natural language processing",
"rag systems vector databases embedding search",
]]
bm25 = BM25()
bm25.fit(docs_tokenized)
results = bm25.search("vector search rag".split(), top_k=3)
for idx, score in results:
print(f" [{score:.4f}] {' '.join(docs_tokenized[idx])}")
Inverted Index: The Data Structure Behind Search
from collections import defaultdict
class InvertedIndex:
"""Maps terms to the documents that contain them."""
def __init__(self):
self.index: dict[str, list[tuple[int, int]]] = defaultdict(list) # term -> [(doc_id, tf)]
self.doc_count = 0
def add_document(self, doc_id: int, tokens: list[str]) -> None:
self.doc_count += 1
tf: dict[str, int] = {}
for token in tokens:
tf[token] = tf.get(token, 0) + 1
for token, freq in tf.items():
self.index[token].append((doc_id, freq))
def search(self, term: str) -> list[tuple[int, int]]:
"""Return (doc_id, term_frequency) for documents containing term."""
return self.index.get(term, [])
# This is what Elasticsearch and Lucene use under the hood.
# For a query, you look up each term in the index, merge the postings,
# and rank by TF-IDF or BM25.
Lexical vs Semantic Search
Lexical (TF-IDF, BM25):
- Matches exact words
- Fast, no model needed
- Fails on synonyms ("car" vs "automobile")
- Good for keyword queries
Semantic (Embeddings):
- Matches meaning via dense vectors
- Requires an embedding model
- Handles synonyms and paraphrasing
- Good for natural language queries
Hybrid (Best of both):
- Combine BM25 + embedding scores
- Reciprocal Rank Fusion: score = 1/(k+rank_bm25) + 1/(k+rank_semantic)
- This is what production RAG systems use