Finding the Needle in a Haystack: Comparing Multi-Vector Search Strategies

In the development of advanced search and retrieval systems, moving from keyword matching to semantic understanding is a critical step. However, a key distinction exists between finding a relevant document and locating a specific piece of information within that document with precision. While there are techniques that perform well for retrieving documents, most of them work by extracting summarized semantic meaning of the document. This can be seen as these models trying to understand the “gist” of the documents. Both single-vector search and late-interaction approaches work well for these conditions with various tradeoffs involved. But there’s another type of problem where the goal is not just to understand the overall topic of a document in general, but to also specifically account for the requested detail within the document. This “needle in a haystack” problem is a significant challenge, and addressing it is essential for building high-precision retrieval systems.

This guide provides a technical analysis of multi-vector search for high-precision information retrieval. We will examine various optimization strategies and analyze their performance. This guide should be seen as complementary to resources like the Answer.AI blog on ColBERT pooling , which explains how pooling strategies can be effective for document-level retrieval. Here, we will demonstrate why those same techniques can be counterproductive when precision at an intra-document, token level is the primary objective.

Find reproducible code here

The Dataset

To properly test these strategies, we need a task where precision is not just a feature, but the entire goal.

The Task: The Document Haystack Dataset

Our benchmark is built on the AmazonScience/document-haystack dataset, which contains 25 visually complex source documents (e.g., financial reports, academic papers). To create a rigorous test, our evaluation follows a per-document methodology:

• We process each of the 25 source documents independently.
• Table Creation: For a single source document (e.g., “AIG”), we ingest all pages from all of its page-length variants (from 5 to 200 pages long). This creates a temporary LanceDB table containing approximately 1,230 pages.
• The Task: We then query this table using a set of “needle” questions, where the goal is to retrieve the exact page number containing the answer. A successful retrieval means the correct page number is within the top K results.
• Measurement: We measure both retrieval accuracy (Hit@K) and the average search latency for each query against this table.
• Iteration: Once the evaluation for one document is complete, the table is discarded, and the process repeats for the next source document.

Dataset example The documents contain “text needles” like these

During evaluation, the queries processed are somewhat like this:

What is the secret currency in the document?
What is the secret object #3 in the document?

The intention of this task is to find the page which has the text needle that answers this questions

Models and Architectures

Our testbed includes a baseline single-vector model and a family of advanced multi-vector models.

Single-Vector (Bi-Encoder) Baseline: openai/clip-vit-base-patch32

A bi-encoder maps an entire piece of content (a query, a document page) to a single vector. The search process is simple: pre-compute one vector for every page, and at query time, find the page vector closest to the query vector.

• Strength: Speed and simplicity.
• Weakness: This creates an information bottleneck. All the nuanced details, keywords, and semantic relationships on a page must be compressed into a single, fixed-size vector. For finding a needle, this is like trying to describe a specific person’s face using only one word.

Multi-Vector (Late-Interaction) Models

Multi-vector models, pioneered by ColBERT, take a different approach. Instead of one vector per page, they generate a set of vectors for each page—one for every token (or image patch).

• Mechanism (MaxSim): The search process is more sophisticated. For each token in the query, the system finds the most similar token on the page. These maximum similarity scores are then summed up to get the final relevance score. This “late-interaction” preserves fine-grained, token-level details.
• The Models: We used several vision-language models adapted for this architecture, including ColPali, ColQwen2, and ColSmol. While their underlying transformer backbones differ, they all share the ColBERT philosophy of representing documents as a bag of contextualized token embeddings.

Different Retrieval Strategies Used

A full multi-vector search is powerful but computationally intensive. Here are five strategies for managing it, complete with LanceDB implementation details.

1. base: The Gold Standard (Full Multi-Vector Search)

This is the pure, baseline late-interaction search. It offers the highest potential for accuracy by considering every token.

LanceDB also integrates with ConteXtualized Token Retriever (XTR) , an advanced retrieval model that prioritizes the most semantically important document tokens during search. This integration enhances the quality of search results by focusing on the most relevant token matches. LanceDB Implementation:

import lancedb
import pyarrow as pa

# Schema for multi-vector data
# Assumes embeddings are 128-dimensional
schema = pa.schema([
    pa.field("page_num", pa.int32()),
    pa.field("vector", pa.list_(pa.list_(pa.float32(), 128)))
])

db = lancedb.connect("./lancedb")
tbl = db.create_table("document_pages_base", schema=schema)

# Ingesting multi-token embeddings for a page
# multi_token_embeddings is a NumPy array of shape (num_tokens, 128)
tbl.add([{"page_num": 1, "vector": multi_token_embeddings.tolist()}])

# Searching with a multi-token query
# query_multi_vector is also shape (num_query_tokens, 128)
results = tbl.search(query_multi_vector).limit(5).to_list()

2. flatten: Mean Pooling

This strategy “flattens” the set of token vectors into a single vector by averaging them. This transforms the search into a standard, fast approximate nearest neighbor (ANN) search.

LanceDB Implementation:

# Schema for single-vector data
schema_flat = pa.schema([
    pa.field("page_num", pa.int32()),
    pa.field("vector", pa.list_(pa.float32(), 128))
])
tbl_flat = db.create_table("document_pages_flat", schema=schema_flat)

# Ingesting the mean-pooled vector
mean_vector = multi_token_embeddings.mean(axis=0)
tbl_flat.add([{"page_num": 1, "vector": mean_vector.tolist()}])

# Searching with a single averaged query vector
query_mean_vector = query_multi_vector.mean(axis=0)
results = tbl_flat.search(query_mean_vector).limit(5).to_list()

3. max_pooling & 4. cls_pooling

These are variations of flatten. max_pooling takes the element-wise max across all token vectors, while cls_pooling simply uses the first vector in the sequence (corresponding to the [CLS] token). The implementation is identical to flatten, just with a different aggregation method (.max(axis=0) or [0]).

5. rerank: The Hybrid “Optimization”

This two-stage strategy aims for the best of both worlds. First, use a fast, pooled-vector search to find a set of promising candidates. Then, run the full, accurate multi-vector search on only those candidates.

LanceDB Implementation: This requires a table with two vector columns.

# Schema with both flat and multi-vector columns
schema_rerank = pa.schema([
    pa.field("page_num", pa.int32()),
    pa.field("vector_flat", pa.list_(pa.float32(), 128)),
    pa.field("vector_multi", pa.list_(pa.list_(pa.float32(), 128)))
])
tbl_rerank = db.create_table("document_pages_rerank", schema=schema_rerank)

# Ingest both vectors
tbl_rerank.add([
    {
        "page_num": 1,
        "vector_flat": multi_token_embeddings.mean(axis=0).tolist(),
        "vector_multi": multi_token_embeddings.tolist()
    }
])

# --- Two-Stage Search ---
# Stage 1: Fast search on the flat vector
query_flat = query_multi_vector.mean(axis=0)
candidates = tbl_rerank.search(query_flat, vector_column_name="vector_flat") \
                       .limit(100) \
                       .with_row_id(True) \
                       .to_pandas()

# Stage 2: Precise multi-vector search on candidates
candidate_ids = tuple(candidates["_rowid"].to_list())
final_results = tbl_rerank.search(query_multi_vector, vector_column_name="vector_multi") \
                          .where(f"_rowid IN {candidate_ids}") \
                          .limit(5) \
                          .to_list()

The Results

For a “needle in a haystack” task, retrieval accuracy is the primary metric of success. The benchmark results reveal a significant performance gap between the full multi-vector search strategy and common optimization techniques.

Baseline Performance: Single-Vector Bi-Encoder

First, we establish a baseline using a standard single-vector bi-encoder model, openai/clip-vit-base-patch32. This represents a common approach to semantic search but, as the data shows, is ill-suited for this task’s precision requirements.

With a Hit@20 rate of just under 12%, the baseline model struggles to reliably locate the correct page. This performance level is insufficient for applications requiring high precision.

Multi-Vector Model Performance

We now examine the performance of multi-vector models using different strategies. The following table compares the base (full multi-vector), flatten (mean pooling), and rerank (hybrid) strategies across several late-interaction models.

The data shows a consistent pattern: the base strategy outperforms both flatten and rerank across all models, achieving a Hit@20 rate of over 90% in some cases. The pooling and reranking strategies perform no better than the single-vector baseline.

In-Depth Analysis of Pooling Strategies

To further understand the failure of optimization techniques, we compared different methods for pooling token vectors into a single vector: mean (flatten), max, and cls.

All pooling methods perform poorly, confirming that the aggregation of token vectors into a single representation loses the fine-grained detail required for this task.

Analysis: Why “Optimizations” are Ineffective Here

The strategies that seem like clever optimizations for general retrieval are, in fact, counterproductive for high-precision tasks.

1. The Failure of Pooling: The flatten (mean pooling) strategy, along with max_pooling and cls_pooling, fails to improve upon the baseline. As explained in the Answer.AI blog on ColBERT pooling, pooling is a form of compression. For document-level retrieval, this compression creates a useful “summary.” For our task, however, this averaging process destroys the essential localization signal. The subtle but critical differences between the token embeddings on one page and the next are smoothed over and lost. The resulting single vector represents the topic of the page, not the specific needle on it.

2. The Failure of rerank: The rerank strategy, often presented as a hybrid solution, is the worst-performing strategy. Its Hit@20 is consistently below 10%. The reason is a fundamental flaw in its two-stage design for this task: the first stage uses a pooled vector to retrieve candidates. Since pooling eliminates the localization signal, the initial candidate set is effectively random. The powerful second-stage multi-vector search is then applied to a list of pages that is highly unlikely to contain the correct page, exemplifying the “garbage in, garbage out” principle.

3. The Superior Performance of base Search: In our evaluation, the full, un-optimized base multi-vector search was the only strategy that demonstrated high performance. With a Hit@20 of over 95% for the best model, it shows that preserving every token vector is the most reliable way we observed to find the needle. We did not identify an effective shortcut for this class of problem.

Latency

The “optimizations” are fast but do not produce correct results. The only effective strategy has a clear and understandable computational cost.

(Latency measured on NVIDIA H100 GPUs)

Practical Considerations: Latency, Complexity, and Scalability

While the accuracy of base multi-vector search is impressive, it’s crucial to understand the practical limitations that come with its computational intensity. These models are not a universal replacement for traditional single-vector search but rather a specialized tool for specific problems.

Search Latency and Computational Complexity

As the benchmark data shows, the search latency for base multi-vector search is orders of magnitude higher than for single-vector (or pooled-vector) search. It’s important to note that the reported ~670ms latency is an average from per-document evaluations. In this benchmark, each of the 25 documents is processed independently. All pages from a single document’s variants (ranging from 5 to 200 pages) are ingested into a temporary table, resulting in a table size of approximately 1,230 rows (pages) per evaluation. The search is performed on this table, and then the table is discarded. This highlights a significant performance cost even on a relatively small, per-document scale. This stems from a fundamental difference in computational complexity:

• Modern ANN Search (for single vectors): Algorithms like HNSW (Hierarchical Navigable Small World) provide sub-linear search times, often close to O(log N), where N is the number of items in the index. This allows them to scale to billions of vectors with millisecond-level latency.
• Late-Interaction Search (Multi-Vector): The search process is far more intensive. For each query, it must compute similarity scores between query tokens and the tokens of many candidate documents. The complexity is closer to O(M * Q * D), where M is the number of candidate documents to score, Q is the number of query tokens, and D is the average number of tokens per document. While optimizations exist to reduce M, the core calculation is fundamentally more expensive than a single vector distance calculation.

When to Use Multi-Vector Search

Given these constraints, full multi-vector search is not a drop-in replacement for single-vector ANN search. It is best suited for:

• Small-Scale, High-Precision Tasks: When the corpus of documents is manageable (thousands to tens of thousands, not billions) and the value of finding the exact piece of information is extremely high.
• Specialized Applications: In domains like legal discovery, compliance, or scientific research, the cost of a slower, more computationally expensive search is easily justified by the need for precision. For example, finding a specific clause in one of 10,000 contracts is a perfect use case.
• Post-Retrieval Re-ranking: While our rerank strategy showed that a poor first stage fails, multi-vector models can be used effectively as a re-ranking step if the initial retrieval stage is highly capable of recalling the correct document. However, this adds complexity to the system architecture.

For general-purpose, large-scale document retrieval where understanding the “gist” is sufficient, single-vector search remains the more practical and scalable solution.

Conclusion

This benchmark highlights the critical importance of matching your retrieval strategy to your objective. Pooling and reranking remain valid techniques for document-level retrieval, where the goal is to find a relevant document. However, if the goal is to find specific information within a document, the detail provided by full multi-vector representations is essential.

In conclusion, building precise retrieval systems requires preserving the fine-grained detail of the source data. For needle-in-a-haystack problems, this means utilizing the full capabilities of late-interaction, multi-vector search.

Appendix: Full Benchmark Results