# Approximate Search: IVF और HNSW — Embeddings और Vector Search

Source: https://www.geekswithgeeks.com/hi/embeddings/s-ann

> दो सबसे आम index परिवार और उनके recall knobs समझें।

## जानबूझकर अधिकांश डेटा छोड़ें

लाखों vectors के लिए सब कुछ स्कैन करना बहुत धीमा है, इसलिए **approximate nearest neighbour (ANN)** indexes अधिकांश डेटा देखने से बचते हैं। **IVF (inverted file)** vectors को k-means से `nlist` cells में बाँटता है; query सिर्फ़ `nprobe` सबसे पास के cells में देखती है। **HNSW (hierarchical navigable small world)** परतदार graph बनाता है जिसमें हर vector पास के पड़ोसियों से जुड़ता है; query graph पर लालच से लक्ष्य की ओर चलती है, और `efSearch` तय करता है कि चलते समय कितने उम्मीदवार रखे जाएँ। दोनों **100% से कम recall** देते हैं: सच्चा निकटतम पड़ोसी कभी-कभी छूट जाता है। `nprobe` या `efSearch` बढ़ाने से recall और latency साथ बढ़ते हैं, इसलिए आवश्यक recall तक **अपने डेटा पर tune** करें। IVF को **प्रशिक्षण** चरण चाहिए और कम memory लगती है; HNSW में प्रशिक्षण नहीं, बहुत तेज़ और सटीक है, पर ज़्यादा memory लेता है और अद्यतन कम सस्ते में समर्थित करता है।

## Recall बनाम खोज प्रयास, चलाकर

मैंने यह Python virtual environment में numpy 2.5.3, scikit-learn 1.9.1 और faiss-cpu 1.15.1 के साथ चलाया, निश्चित random seeds के साथ ताकि संख्याएँ दोहराई जाएँ। 20,000 clustered 64-आयामी vectors पर 100 cells वाला IVF 1 cell जाँचने पर 0.743 recall@10, 4 पर 0.998 और 16 पर 1.000 पाता है। HNSW efSearch=4 पर 0.643 से 16 पर 0.932 और 64 पर 1.000 जाता है। Recall सटीक flat-index उत्तरों के विरुद्ध मापा गया है। Latency नहीं दिखाई क्योंकि timings मशीन के अनुसार बदलते हैं।

```python
import numpy as np, faiss
rng = np.random.default_rng(0)
d, n, nq = 64, 20000, 200
centers = rng.normal(size=(50, d)) * 3
xb = (centers[rng.integers(0, 50, n)] + rng.normal(size=(n, d))).astype("float32")
xq = (centers[rng.integers(0, 50, nq)] + rng.normal(size=(nq, d))).astype("float32")

flat = faiss.IndexFlatL2(d); flat.add(xb)
_, truth = flat.search(xq, 10)                                   # exact answers

def recall(found): return float(np.mean([len(set(f) & set(t)) / 10 for f, t in zip(found, truth)]))

ivf = faiss.IndexIVFFlat(faiss.IndexFlatL2(d), d, 100); ivf.train(xb); ivf.add(xb)
for nprobe in (1, 4, 16):
    ivf.nprobe = nprobe
    print(f"IVF  nprobe={nprobe:2d} recall@10 = {recall(ivf.search(xq, 10)[1]):.3f}")

hnsw = faiss.IndexHNSWFlat(d, 16); hnsw.hnsw.efConstruction = 100; hnsw.add(xb)
for ef in (4, 16, 64):
    hnsw.hnsw.efSearch = ef
    print(f"HNSW efSearch={ef:2d} recall@10 = {recall(hnsw.search(xq, 10)[1]):.3f}")

```

Output:

```
IVF  nprobe= 1 recall@10 = 0.743
IVF  nprobe= 4 recall@10 = 0.998
IVF  nprobe=16 recall@10 = 1.000
HNSW efSearch= 4 recall@10 = 0.643
HNSW efSearch=16 recall@10 = 0.932
HNSW efSearch=64 recall@10 = 1.000
```

## सटीक उत्तरों के विरुद्ध tune करें

अपने ANN index का recall@k असली queries के नमूने पर flat index के विरुद्ध निकालें। जो सबसे सस्ती setting लक्ष्य पूरा करे वह चुनें।

**Quiz:** nprobe (IVF) या efSearch (HNSW) बढ़ाने से क्या होता है?

- [x] Recall और latency दोनों बढ़ाता है
- [ ] Recall और latency दोनों घटाता है
- [ ] Embedding model बदलता है
- [ ] Vectors हटाता है

*Answer:* Recall और latency दोनों बढ़ाता है. ज़्यादा खोज प्रयास ज़्यादा सच्चे पड़ोसी पाता है पर समय लेता है।