Approximate retrieval under latency
Approximate retrieval is an explicit recall–latency contract, not a transparent substitute for exact search.
Novel equipment failures appear before reliable labels exist.
This chapter moves from freeze an exact reference to guard freshness and compatibility. We will make the idea concrete in a small code example before placing it back inside a production system with a declared latency, cost, and operator-capacity budget.
Publish encoder and index as one versioned bundle, track unindexed inventory, and rebuild or incrementally update before freshness breaches the contract.
Verify the behavior illustrated in ann_recall_audit.py, then measure decision utility, slice reliability, and system latency.
A stale ANN index never retrieves new inventory; a reranker cannot recover what retrieval omitted. An unsafe release must degrade to a named baseline or the last known-good version.
Build the idea one layer at a time.
Exact nearest-neighbor search is a trustworthy ruler but an expensive serving strategy at large scale. Approximate indexes trade some candidate recall for lower latency, and that trade sets a hard ceiling on everything downstream.
Graph indexes such as HNSW navigate through a hierarchy of neighbor links instead of scoring every item. A larger search effort explores more candidates and usually raises recall, but costs CPU time and tail latency. Index construction parameters make a similar memory-versus-connectivity tradeoff.
Approximation must be measured against exact top-k results on representative queries. A reranker can reorder retrieved candidates but cannot recover an omitted item, so operate the index with recall, p95/p99 latency, memory, build age, and encoder/index version as first-class metrics.
- HNSW
- recall-latency tradeoff
Follow the reasoning before touching the code.
- 01
Freeze an exact reference
Sample real queries and compute their top-k neighbors by exhaustive scoring under the deployed encoder and similarity function.
- 02
Sweep search effort
Benchmark approximate settings at fixed concurrency, recording overlap with exact results alongside median and tail latency.
- 03
Guard freshness and compatibility
Publish encoder and index as one versioned bundle, track unindexed inventory, and rebuild or incrementally update before freshness breaches the contract.
exact = {
'q1': ['a', 'b', 'c', 'd'],
'q2': ['m', 'n', 'o', 'p'],
}
approx = {
'q1': ['a', 'c', 'x', 'b'],
'q2': ['n', 'o', 'y', 'z'],
}
recalls = [len(set(exact[q]) & set(approx[q])) / 4 for q in exact]
print('recall@4', sum(recalls) / len(recalls))Audit candidate recall by overlap with an exact top-k reference.
What to notice
- The audit counts membership overlap, not rank order; ranking quality should be measured separately after candidate generation.
- The two queries have different recall, so the mean should be accompanied by slice and tail-query analysis.
YOUR TURN Pause and predict before revealing the answer.
Suppose increasing search effort changes approximate q2 to [m, n, o, z] but adds 8 ms at p99. What are the new mean recall and the release decision?
Need a hint?
Compute each query recall first; the decision also needs a declared latency SLO.
Check your reasoning
Mean recall rises from 0.625 to 0.75. Whether to release depends on whether the 8 ms increase fits the latency budget and whether that recall gain matters on valuable slices.
Lessons 1, 2, 3, 4 in this course.
Connect the chapter to the course’s quantitative spine.
Approximate retrieval is an explicit recall–latency contract, not a transparent substitute for exact search. The cosine similarity below is the shared course-level lens that helps quantify the surrounding system. Name each symbol, check its units or shape, and use only values that were available at the production cutoff.
Cosine similarity
| Symbol | Meaning / shape / unit |
|---|---|
u, v | embedding vectors |
uᵀv | dot product |
∥·∥₂ | vector magnitude |
Open derivation and numerical substitution
Start from the production quantity being optimized, substitute the observed values with their declared units, then isolate the model-controlled term. Preserve shape annotations at each step so broadcasting or aggregation cannot silently change the result.
- Write the named inputs: u, v, uᵀv, ∥·∥₂.
- Substitute one small, hand-checkable batch before vectorizing.
- Calculate an independent reference value and compare within a declared tolerance.
# equation → code contract
inputs = validate_shapes_and_units(batch)
value = compute_c06(inputs)
assert is_finite(value)Change one assumption and make the tradeoff visible.
Use the worked chapter as your prediction, then change one input in the lab and explain why the output moves. The lab runs predefined TypeScript and never executes learner code, so the focus stays on the concept rather than setup.
ANN recall–latency lab
Increase search effort and expose the recall/latency frontier.
Assumption: HNSW-like curve for a fixed one-million-vector index.
Open nonvisual data table
| Item | Computed state | Interpretation |
|---|---|---|
| query 1 | 82.7% | 4.7 ms |
| query 2 | 82.0% | 4.9 ms |
| query 3 | 81.2% | 5.1 ms |
| query 4 | 80.4% | 5.3 ms |
| query 5 | 79.5% | 5.5 ms |
Trace the complete operating path.
Carry the chapter’s central idea into the system: Approximate retrieval is an explicit recall–latency contract, not a transparent substitute for exact search. The path below shows where that reasoning needs an artifact, a test, an owner, or a fallback.
- 01
Turn “Freeze an exact reference” into a written invariant and a failing test.
- 02
Promote ann_recall_audit.py from illustration to a versioned implementation with representative fixtures.
- 03
Use “Guard freshness and compatibility” as the release checkpoint: Publish encoder and index as one versioned bundle, track unindexed inventory, and rebuild or incrementally update before freshness breaches the contract.
- 04
Serve or materialize behind explicit a declared latency, cost, and operator-capacity budget.
- 05
Join telemetry to mature outcomes and retain a rollback path.
Observability
Join service health, input quality, prediction distributions, slice behavior, and mature outcomes by exact version.
Cost
Measure storage, preprocessing, compute, queueing, and human review under a representative arrival pattern.
Failure modes
A stale ANN index never retrieves new inventory; a reranker cannot recover what retrieval omitted. Add a detector, owner, mitigation, and stop condition for this class of failure.
Alternatives
Compare a rule, a simpler statistical baseline, and a different system boundary before adding model complexity.
Explain the contract, not just the vocabulary.
Incident discovery and retrieval system
Combine PCA, clustering, anomaly triage, embeddings, and ANN search with human review.
- Representation analysis
- Cluster/anomaly validation
- Embedding evaluation
- ANN recall/latency audit
Read primary material with a purpose.
Return to the opening failure.
Version encoder and index together; monitor cluster stability, alert yield, exact-sample recall, latency, and freshness.
For this lesson, the release evidence is the worked code example, a hand-checked formal result, deterministic simulation output, a ≥80% checkpoint, the production rubric, and a named fallback. The course resolves when the system can produce a pca, clustering, anomaly, and nearest-neighbor retrieval investigation.