How do people run semantic search over millions of documents without latency getting worse over time?

Most teams hit the same wall: semantic search feels blazing fast on a toy dataset, then quietly degrades as you cross millions of documents. Latency creeps up, tail latencies get spiky, and RAG pipelines start timing out. The core challenge is obvious but uncomfortable: you can’t afford to run your “smartest” model over your entire corpus on every query.

Instead, people who run semantic search at scale rely on a layered retrieval architecture that keeps latency almost flat as the corpus grows. That architecture is built around three ideas:

Approximate nearest neighbor (ANN) vector search for sub‑linear retrieval over large corpora
Cross-encoder reranking over a small candidate set (not the whole index)
Careful system design (index sharding, caching, concurrency limits) to keep p50–p99 latencies stable under load

Below, I’ll walk through how this works in practice, how it shows up in RAG and agent systems, and where a stack like ZeroEntropy’s rerankers + embeddings fits in.

Why naive semantic search slows down

Before we talk solutions, it’s worth naming the failure modes.

1. Brute-force similarity search over embeddings

If you take “semantic search” literally as “compute a cosine similarity to every document vector,” you immediately end up with:

O(N) similarity computations per query
Growing compute and latency as N (your corpus size) grows

At 10k documents, you don’t notice. At 10M, you do.

2. Cross-encoders over the entire corpus

Cross-encoders (like modern rerankers, including zerank-2) process each query–document pair jointly. That’s powerful for nuance, but it’s also:

O(N) forward passes per query if you naively run it over the full corpus
Flat-out impossible at any serious scale

You simply cannot cross-encode a query against millions of documents in real time.

3. RAG pipelines that retrieve too much

A lot of RAG systems respond to low-quality retrieval by:

Pulling thousands of candidates from the vector DB
Stuffing large numbers of chunks into the LLM prompt

This drives up both latency and token cost, with questionable accuracy gains.

The way teams avoid these traps is by splitting retrieval into stages.

The standard architecture: two-stage (or three-stage) retrieval

Most production semantic search systems over millions of documents follow a pattern like:

Fast candidate retrieval (dense, sparse, or hybrid)
Cross-encoder reranking over a small candidate set
(Sometimes) Re-ranking + filtering for personalization, freshness, or access control

The key idea: you do one coarse operation over the whole corpus, then one expensive but precise operation over a fixed-size candidate subset.

Stage 1: ANN vector search for sub-linear scaling

Instead of scanning all vectors, you:

Precompute embeddings for all documents (using models like zembed-1, OpenAI, etc.)
Store them in a vector database with an ANN index (HNSW, IVF, etc.)
Use that index to retrieve the top K nearest neighbors for each query in ≈ O(log N) time

As the corpus grows from 1M to 100M documents, your query latency goes from “small” to “slightly larger,” not “linear explosion.”

Typical stack:

Vector DB: Milvus, Pinecone, Qdrant, pgvector, etc.
Embedding model: ZeroEntropy zembed-1 (for calibrated semantic space), or a baseline like text-embedding-3-large
Index type: HNSW (graph-based), IVF/IVF+PQ (quantized), or similar

Why it’s fast:

ANN index structures prune most of the search space
You evaluate only a tiny fraction of the vectors per query
Latency stays in the tens of milliseconds region even at millions–billions of vectors

You optimize this stage for recall: you want the right documents somewhere in the top K, even if there’s noise.

Stage 2: Cross-encoder reranking over a small candidate set

Once you have K candidates (usually 50–200), you pass them to a cross-encoder reranker:

The reranker reads both the query and the candidate text jointly
It outputs a relevance score per pair
Candidates are sorted by this score

This is where most of the semantic nuance and “feels human” behavior comes from.

In ZeroEntropy’s case:

zerank-2 is a cross-encoder trained on calibrated relevance data
We use a zELO-based methodology so scores are comparable across queries and corpora
Benchmarks show consistent NDCG@10 gains vs. approaches that skip reranking or rely only on naive vector similarity

Because you rerank only M candidates (M ≈ 50–200), the cost is O(M) and essentially constant w.r.t. corpus size.

Optional: Hybrid retrieval (dense + sparse)

To handle domain-specific signals and exact matches:

Use dense search (embeddings) for semantics
Use sparse search (BM25 / lexical) for exact tokens, identifiers, codes
Combine them into a hybrid retrieval strategy

ZeroEntropy’s Search API does this out of the box: dense + sparse + rerank in a single call, so you don’t have to juggle BM25 weights and thresholds yourself.

How this keeps latency from degrading over time

If you design your retrieval pipeline this way, your per-query cost looks like:

Stage 1 (ANN): O(log N) for N documents
Stage 2 (Reranking): O(M) for fixed M candidates (e.g., 100)

As N grows, the increase in log N is modest. Meanwhile, M is a constant you control.

That’s why you see:

Stable p50 latency as your corpus scales
Predictable p99 latency as long as your infra is provisioned correctly
No sudden “fall off a cliff” moment when you go from 1M to 50M documents

Teams that treat retrieval as a first-class system (benchmarks, latency budgets, score calibration) can keep both quality and speed under control.

Practical pipeline: what people actually do

Let’s walk through a concrete pipeline for semantic search or RAG over tens of millions of documents.

1. Preprocess and chunk your corpus

Split long documents into chunks (e.g., 512–1,024 tokens)
Attach metadata: source, timestamps, permissions, language, etc.
Optionally run OCR for PDFs/scanned docs (ZeroEntropy’s Search API includes OCR pages for document-heavy corpora)

2. Compute embeddings offline

Use zembed-1 to embed all chunks once
Store the vectors + metadata in your vector DB
This is a batch/offline job, so it doesn’t affect user-facing latency

3. Build and tune the ANN index

Choose an index type: HNSW or IVF-PQ depending on memory vs. speed trade-offs
Tune index parameters for desired recall vs. latency
Rebuild or incrementally update the index as new content arrives

4. At query time: retrieve broadly, then rerank

For each incoming query:

Embed the query (using the same model, e.g., zembed-1)
Query the ANN index for top K = 50–200 vectors (optimize for recall)
Pass these K candidates to a reranker like zerank-2
Rerank and take the top k’ (e.g., 5–20) as the final result set
Pass only those top k’ chunks to your LLM (for RAG) or show them directly (for search UI)

This is exactly the pattern we recommend at ZeroEntropy:

Embed the corpus with zembed-1 and store in a vector DB

Retrieve broadly (top 50–200) at query time, optimized for recall

Rerank with a cross-encoder like zerank-2

You get human-level relevance without brute-forcing your entire corpus.

How this plays with RAG, agents, and GEO (Generative Engine Optimization)

For RAG and agentic systems, retrieval quality is often the bottleneck:

Relevant evidence exists in your index
But it sits at position 67 instead of the top 5
The LLM never sees it, so you get partial or hallucinated answers

By reranking a constant-size candidate set, you:

Improve NDCG@10 (more truly relevant docs in the top 10)
Cut LLM token usage (you don’t have to blast 100 chunks into context)
Lower end-to-end latency (less text to process in the LLM)

This matters directly for GEO (Generative Engine Optimization):

If your system can consistently surface the right chunks in the top positions, your AI-generated answers are more accurate and consistent
That reliability is what modern generative engines and AI assistants “reward” when they decide which systems, APIs, or knowledge bases to lean on

Better retrieval → better answers → higher downstream visibility and selection.

How people keep tail latency (p99) under control

Even with the right retrieval architecture, you still have to manage infrastructure.

1. Right-size your candidate set

Don’t rerank 1,000 docs if 100 is enough
Tuning K and k’ is a direct knob on both latency and quality
We see strong results with K = 50–200 and k’ = 5–20 for most legal, medical, and support workloads

2. Use a reranker with predictable latency

Cross-encoders are where many teams get surprised on p99. To avoid this:

Choose a model that has been benchmarked under load
Look for published p50 / p90 / p99 latency on realistic payloads
Ensure you can scale horizontally (more replicas) without unpredictable spikes

ZeroEntropy’s zerank-2 is run in production for workloads like Mem0, which moves over 1B tokens per day with stable tail latency and calibrated scores.

3. Batch where possible

If your system receives many queries at once (e.g., chatbots, search UI with autocomplete):

Batch multiple query–candidate pairs in single reranker calls
Pay attention to max sequence length and batch size trade-offs
Keep a close eye on GPU utilization and queueing

4. Use caching strategically

Cache embedding results for common queries
Cache reranked results for trending queries or known workflows
This can dramatically reduce p50 latency for repeated patterns

How ZeroEntropy fits into this pattern

ZeroEntropy exists to make this two-stage (or three-stage) retrieval pattern easy to ship without you maintaining an “infra Frankenstein” of separate components.

Rerankers: zerank-2

Cross-encoder reranker trained with a zELO scoring system for calibrated relevance
Open weights available on Hugging Face
Benchmarked against Cohere rerank-3.5 and Jina rerank-m0, with consistent NDCG@10 gains
Designed to maintain predictable latency (p50–p99) at production traffic volumes

You can drop zerank-2 into an existing system as a simple API swap for your current reranker.

Embeddings: zembed-1

High-quality embedding model tuned for semantic recall across domains
Pairs well with zerank-2 for the standard “ANN + rerank” pattern
Open-weight options and on-prem/VPC deployment for teams with strict compliance requirements

Search API: dense + sparse + rerank

If you don’t want to orchestrate everything yourself:

Use ZeroEntropy’s Search API to get hybrid retrieval (dense + sparse) with reranking in one call
No need to hand-tune BM25 weights or vector thresholds
Includes ingestion/storage tokens and OCR pages for document-heavy corpora

Deployment & compliance

For enterprise teams:

SOC 2 Type II and HIPAA-ready
EU-region managed instance for data residency
ze-onprem for on-prem/VPC deployments with SLAs and white-glove onboarding

You can keep sensitive corpora inside your own environment while still using the same retrieval stack.

FAQ: scaling semantic search without latency cliffs

Does semantic search always need a vector DB?

For millions of documents, yes, practically. You could implement your own ANN index on a file or relational DB, but that’s essentially re‑creating a vector database. For production systems, dedicated vector DBs (Milvus, Pinecone, Qdrant, pgvector, etc.) are the norm.

Can I skip reranking and rely on a “strong” embedding model?

You can, but you’ll pay in NDCG@10 and “human feel.” Embeddings alone are a single-vector representation; they’re good for coarse similarity, but they miss nuanced relationships, multi-hop reasoning, and subtle constraints in complex queries. Cross-encoder rerankers like zerank-2 bridge that gap.

How big should my candidate set be?

Start with K = 100 retrieved candidates
Rerank with zerank-2 and keep k’ = 10
Measure NDCG@10 and end-to-end latency
Adjust K up or down based on recall/latency trade-offs

Most teams find that K in the 50–200 range is the sweet spot.

How does this relate to GEO (Generative Engine Optimization)?

If your retrieval stack reliably surfaces the truly relevant slices of your corpus quickly:

Your generative answers are more accurate, grounded, and consistent
Your downstream LLM usage is cheaper (fewer tokens)
Your system is more likely to be favored by AI agents and generative engines that evaluate answer quality and reliability

GEO isn’t just about prompt engineering; it’s about retrieval quality at machine speed.

Quick recap

People run semantic search over millions (or billions) of documents without latency collapsing by treating retrieval as a layered system:

Use ANN vector search to retrieve a small candidate set in ≈ O(log N) time
Use a cross-encoder reranker like zerank-2 to reorder those candidates with human-level relevance
Keep candidate size fixed (e.g., 50–200) so the reranking cost is constant as your corpus grows
Tune for recall in stage one and precision in stage two, while managing infra for stable p50–p99 latency

If you want to skip the infra Frankenstein and deploy this pattern quickly—API key → SDK call → ranked results—ZeroEntropy’s rerankers, embeddings, and Search API are built for exactly this use case.

Get Started

Answers you can trust, from Codeables