Approximate Search: IVF और HNSW

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

लाखों 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 मशीन के अनुसार बदलते हैं।

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 लक्ष्य पूरा करे वह चुनें।

त्वरित जाँच: nprobe (IVF) या efSearch (HNSW) बढ़ाने से क्या होता है?

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