28 · Approximate-index recall, candidates, and latency
Index acceleration works by examining fewer documents, potentially discarding correct documents before scoring. Reuse the recommendation course's kmeans/partition_retrieval instead of creating a separate vector engine.
Predict first: Must probing 2/12 clusters be six times faster than 12/12? Are exact-neighbor agreement and task Recall the same metric?
Use 40 fixed, already inspected test queries and all 5,183 documents for mechanism diagnosis. Parameter sweeps reveal tradeoffs, not replacements for the formal run's settings.
Navigation: Previous · Next · Integrated experiment
English companion. All instructional Markdown is translated. Experiment code, Chinese language examples, execution counts, and saved outputs remain as in the source edition; historical output text may therefore be Chinese. The initial setup cell anchors the working directory and Python import path for this companion's deeper folder; it does not change the experiment. Saved outputs are historical evidence, not a new run. Run from the top after preparing the required data and models.
# English companions live one directory deeper; keep the original experiment code unchanged.
from pathlib import Path as _TranslationPath
import os as _translation_os
import sys as _translation_sys
_translation_root = next((p for p in [_TranslationPath.cwd(), *_TranslationPath.cwd().parents]
if (p / "reclab").is_dir()), None)
if _translation_root is None:
raise RuntimeError("Open this notebook from inside the Search Recommendation Ads Lab checkout.")
_translation_os.chdir(_translation_root)
if str(_translation_root) not in _translation_sys.path:
_translation_sys.path.insert(0, str(_translation_root))
from pathlib import Path
import os, sys
root = Path.cwd()
if not (root / 'reclab').exists(): root = root.parent
os.chdir(root); sys.path.insert(0, str(root))
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from reclab.search_lessons import context, query_vectors, score_query, labels
from reclab.search import BM25, rrf
from reclab.retrieval import topk, metrics
ctx = context()
print('Shared search run:', ctx['receipt']['run_id'])Saved notebook output · not executed on this page
Shared search run: 20261030T124927-d1467622
1. Establish exact retrieval as the reference
Exact retrieval computes every document–query dot product. With normalized vectors, Euclidean distance can route to clusters before candidate scoring. This teaching coarse index is not FAISS, HNSW, or PQ and does not represent production ANN performance.
Clustering produces 12×384 centers and 5,183 labels. Check that every document belongs to exactly one cluster, then inspect balance.
from reclab.learning.retrieval import kmeans, partition_retrieval
from threadpoolctl import threadpool_limits
with threadpool_limits(limits=4): centers,assignment=kmeans(ctx['vectors'],clusters=12,seed=42)
counts=np.bincount(assignment,minlength=12)
assert counts.sum()==len(ctx['corpus'])
print('centers / assignment:',centers.shape,assignment.shape)
pd.Series(counts).plot.bar(title='Documents per coarse partition',ylabel='documents');plt.show()Saved notebook output · not executed on this page
centers / assignment: (12, 384) (5183,)
<Figure size 640x480 with 1 Axes>
2. Change only the number of probes
Fix vectors, centers, queries, and sorting; vary probes=1/2/4/12. Report two kinds of recall: overlap with exact top 10 measures approximation error; qrels Recall@10 measures task quality. Neither replaces the other.
Timing covers routing, candidate scoring, and sorting only. It excludes query encoding, model loading, index construction, and HTTP, so it cannot simply be subtracted from chapter 17's end-to-end latency.
from reclab.search_lessons import coarse_sweep
qids=sorted(ctx['truth']['test'])[:40]
sweep=pd.DataFrame(coarse_sweep(qids)).set_index('probes')
display(sweep.round(4))
assert np.isclose(sweep.loc[12,'agreement'],1.)
assert sweep.loc[12,'candidates']==5183Saved notebook output · not executed on this page
| recall@10 | ndcg@10 | mrr@10 | hit_rate@10 | agreement | candidates | index_p50_ms | |
|---|---|---|---|---|---|---|---|
| probes | |||||||
| 1 | 0.5375 | 0.4448 | 0.4179 | 0.55 | 0.625 | 456.575 | 0.2072 |
| 2 | 0.6750 | 0.5445 | 0.5071 | 0.70 | 0.800 | 871.625 | 0.3660 |
| 4 | 0.7750 | 0.6157 | 0.5683 | 0.80 | 0.930 | 1709.425 | 0.6093 |
| 12 | 0.8250 | 0.6440 | 0.5892 | 0.85 | 1.000 | 5183.000 | 1.2815 |
3. Candidate budgets and actual end-to-end gains
Plot candidate count, neighbor agreement, and index time to inspect nonlinear relationships. NumPy matrix operations and small-corpus cache locality mean fewer documents need not reduce total time. Real retrieval also has fixed query-encoding cost. A constructed fixed overhead below illustrates Amdahl's law, explicitly not a measurement.
fig,axes=plt.subplots(1,2,figsize=(10,3))
sweep[['agreement','recall@10']].plot(marker='o',ax=axes[0],ylim=(0,1.05),title='Approximation vs relevance')
sweep[['index_p50_ms']].plot(marker='o',ax=axes[1],title='Measured index-only latency (ms)')
plt.tight_layout();plt.show()
fixed_ms=12.; original_index_ms=2.; improved_index_ms=.5
print('Constructed speedup:',(fixed_ms+original_index_ms)/(fixed_ms+improved_index_ms))Saved notebook output · not executed on this page
<Figure size 1000x300 with 2 Axes>
Constructed speedup: 1.12
4. All-cluster equivalence is an executable invariant
Probing every cluster must cover the corpus and reproduce exact ranking. This catches ID offsets, dropped candidates, and inconsistent tie rules. Equal average NDCG alone does not prove document-by-document agreement.
for q,v in zip(qids[:8],query_vectors(qids[:8])):
ids,count=partition_retrieval(ctx['vectors'],v,centers,assignment,probes=12,k=10)
exact=topk(np.r_[-np.inf,ctx['vectors']@v],10)
assert (ids+1).tolist()==exact and count==5183
print('8 queries: full-probe document-level equivalence verified')Saved notebook output · not executed on this page
/Users/lynnlee/Documents/Codex/2026-10-30/task/soutui-lab/.venv/lib/python3.12/site-packages/tqdm/auto.py:21: TqdmWarning: IProgress not found. Please update jupyter and ipywidgets. See https://ipywidgets.readthedocs.io/en/stable/user_install.html from .autonotebook import tqdm as notebook_tqdm
8 queries: full-probe document-level equivalence verified
Exercise: Fix probes=2, change only clustering seed, and inspect candidate-count and qrels-Recall variation. Do not report the best test seed as a final result. Choose index parameters on training/select queries and reserve independent audit. Next, combine lexical and semantic channels.