07. IR - Dense Retrieval

Dense Retrieval (DR) replaces traditional inverted index-based retrieval (e.g., BM25) with neural embeddings.

Differences from BM25:

• Uses vector representations instead of exact term matching.

• Improves retrieval for semantic similarity rather than keyword overlap.

Neural methods for document expansion & indexing:

• Doc2Query → Expands documents with queries that match them semantically (BERT/T5 variants).

• DeepCT → Assigns term weights using BERT output during indexing.

• COIL → Fuses contextual vectors into an inverted index structure for faster lookup.

Neural Re-Ranking:

• Reorders a pre-selected list of documents.

• Uses score(q,d) interface (like classical ranking).

Dense Retrieval:

• Replaces the traditional first stage.

• Uses neural encoder & nearest neighbor vector indexto rank documents.

If dense retrieval is effective enough, it can be used alone without a re-ranking step.

Benefits:

• Faster retrieval (removes additional ranking stage).

• Lower complexity in production search systems.

Training process:

• Triplet-based training → Uses (query, relevant document, non-relevant document).

• Generate embeddings → Generate dense vector representations for queries and documents (from triplet).

• Loss function → Maximize margin between relevant & non-relevant docs.

Batch formation:

• Sample as many triplets as allowed by GPU memory.

• Common batch sizes: 16-128.

• Batches mix different queries for better generalization.

Selection process:

1. Run BM25 to get the top 1000 results for each training query.

2. Randomly select some of those as negative (non-relevant) passages.

3. The non-relevant selections provide some signal (There must be at least some lexical overlap)

4. These negatives add realism to training but may contain noise (which is useful)

Two main loss functions:

1. Plain Margin Loss → Maximizes separation between relevant & non-relevant docs. loss = max(0, s_nonrel - s_rel +1)

2. RankNet Loss → A pairwise ranking loss assuming binary relevance. -> loss = BinaryCrossEntropy(s_rel - s_nonrel)

Both assume binary relevance

-> Aim to maximize margin between relevant & non-relevant documents

1. Step 1 - Model Training → Learn query/document embeddings.

2. Step 2 - Indexing → Encode all passages into dense vectors and store them.

3. Step 3 - Searching → Use nearest neighbor search to find relevant passages.

BERT_dot compresses query & passages into a single vector:

• Each passage is encoded only once during indexing.

• At query time, only the query embedding needs to be computed.

• Relevance is scored using a dot-product between query & passage vectors.

✅ This allows fast lookup using a nearest neighbor index.

Process:

1. Encode all passages in the collection

2. Save them in a nearest neighbor index.

3. At query time/search, encode query on the fly and retrieve the nearest neighbot vectors from passage index.

GPU-based search can efficiently compute the top 1000 results from 9 million vectors using fast dot-product calculations.

✅ Advantage: Extremely fast for smaller datasets.

🚫 Limitation: Becomes costly for very large-scale retrieval.

1. Flat Index → Brute force search over all embeddings (best accuracy but slowest).

2. Inverted File Index → Clusters documents, reducing search space.

3. Product Quantization → Compresses vectors into lower-dimensional integer representations.

4. Graph-Based Indices → Builds a graph where similar vectors are linked for fast traversal. Search space is split into hierarchical layers

5. Approximate Nearest Neighbor search -> Get a good nearest neighbor but maybe not the neares (Tadeoff between latency and effectiveness)

USe the raw vector embeddings and brute force search

• + Exaustive search -> best accurecy

• - Calculate distance for each pair -> slow

Partition the data set into clusters using clustering algo (like k-means) and compute centroids of each cluster.

Compute similarity between query and centroids and select top n clusters and compute similarity to all vectors of the cluster

• + Large reduction of search space

• - More overhead

Replace original vectors of floats with lower dimensional vector of integers

• + Memory efficient & fast

• - Results are approximate & Quality depends of split and clustering parameters

Proximity graph, vectors are linked with similar “friends”

Search starts at predefined entry points and vsit friends until no nearer vertex is found. Then go one layer down and continue search

• +Scalse much better to huge data sets

• - Need additional pre-processing & memory

Search for a close neighbor (but not the optimum) -> Tradeoff between Latency and effectiveness

• + Faster than brute force search, Scales better to massive datasets. -> Necessary for low-latency CPU serving

• - Adds a lot of complexity to search system

ANN trades off accuracy for speed by reducing search complexity.

Advantages:

• Faster than brute force search.

• Scales better to massive datasets.

Disadvantage:

• Retrieval quality depends on index structure and approximation method.