ENID
Lensa ML

Vector Search dan HNSW

Langkah 1 dari 6: Nearest Neighbour

Brute force membandingkan query dengan setiap vector

Vector dalam indeks (N)120
Tetangga yang dikembalikan (k)5
Ketuk plot untuk memindahkan query; contoh embedding 2Dtiap garis abu-abu = satu jarak dihitung; 5 terdekat berwarna hijau
Jarak dihitung
120
Multiply-add pada d = 768
92.2K
Jarak ke tetangga 5
0.097

Menggandakan N menggandakan pekerjaan: 120 vector berarti 120 perhitungan jarak per query, masing-masing seharga d multiply-add. 5 titik hijau adalah jawaban eksaknya.

Geser Vector dalam indeks (N) dari 20 ke 200 dan Tetangga yang dikembalikan (k) dari 1 ke 10, atau ketuk plot untuk memindahkan query. Ini pencarian k-nearest neighbours yang sama seperti pada classifier kNN, tetapi diterapkan pada embedding. Exact search berbiaya O(N · d) per query, dan pengurutan penuh tidak perlu: heap berukuran k menyimpan yang terbaik sejauh ini dalam O(N log k). Di GPU, brute force pada beberapa juta vector sering kali cukup cepat, dan exact search tetap menjadi baseline untuk mengukur setiap indeks aproksimasi.

Langkah 2 dari 6: Cosine, Dot, L2

Tiga skor, dan kapan hasilnya berbeda

Arah query60°
Panjang query1.0
Vector dokumen
contoh vector (ilustrasi)ABCDEFqlingkaran putus-putus: panjang 1cosineB0.98C0.94A0.71D0.17F-0.50E-0.91dotC1.22A1.20B0.59D0.33F-0.70E-0.73L2B0.43C0.50A1.22E1.76D1.99F2.09peringkat 1 di atas; kuning ≠ cosine
Teratas cosine
B
Teratas dot
C
Teratas L2
B
Peringkat berbeda
6

Cosine memilih B hanya dari sudut. Dot product menghargai panjang dan memilih C, sedangkan L2 sepakat dengan cosine. 6 posisi peringkat berbeda dari cosine.

Geser Arah query dan Panjang query, lalu ganti Vector dokumen antara Panjang asli dan Dinormalisasi. Cosine similarity adalah a · b / (‖a‖ ‖b‖), jadi panjang diabaikan. Pada unit vector, ‖a − b‖² = 2 − 2 · cos. Karena itu banyak sistem menormalisasi sekali saat indexing, lalu menjalankan pencarian inner product yang cepat. Sesuaikan metrik dengan model embedding: model yang dilatih dengan objektif cosine mengharapkan cosine, sedangkan retriever dot product seperti DPR bisa menyimpan sinyal berguna pada panjang vector.

Langkah 3 dari 6: Approximate Search

Menukar sedikit recall dengan kecepatan yang jauh lebih tinggi

Lebar pencarian (ef)32
Recall@10 vs latensi, 1M vector (ilustrasi)0.1 ms1 ms10 ms100 ms00.50.91recall@10brute forceef = 32top-10 eksak, per peringkat: hijau = didapat, merah muda = terlewat12345678910
Recall@10
0.706
Latensi
0.53 ms
Lebih cepat dari brute force
56×

ef = 32 menemukan 7 dari 10 tetangga eksak dalam 0,53 ms, sekitar 56 kali lebih cepat daripada memindai seluruh 1M vector. Kurva ini ilustrasi, tetapi bentuknya lazim.

Geser Lebar pencarian (ef) dari 1 ke 512 dan ikuti titik di sepanjang kurva. Indeks aproksimasi melepaskan jaminan jawaban eksak demi kecepatan. Benchmark publik seperti ann-benchmarks menggambar kurva yang sama, query per detik terhadap recall, untuk setiap library dan pengaturan parameter. Sistem produksi sering menargetkan recall@10 antara 0,9 dan 0,99, karena retriever yang memasok reranker atau LLM jarang membutuhkan top 10 yang sempurna. Angka brute force 30 ms dan kurvanya bersifat ilustrasi, bukan hasil pengukuran.

Langkah 4 dari 6: Graph HNSW

Link panjang dan jarang di atas, link lokal dan rapat di bawah

Link per node (M)3
Layer
Layer 0: 80 dari 80 node; dibangun dengan insersi HNSW pada data contohentry pointnode per layer, atas ke bawah: 2 → 3 → 8 → 27 → 80
Node di layer ini
80
Link di layer ini
163
Rata-rata link per node
4.1
Layer
5

Layer 0 memuat semua 80 titik, masing-masing terhubung ke paling banyak 6 tetangga dekat. Link pendek ini membuat bagian akhir pencarian, yang bersifat lokal, menjadi akurat.

Geser Link per node (M) dari 2 ke 8 dan klik tombol Layer satu per satu. Setiap node menarik layer teratasnya sekali, yaitu floor(−ln(u) · m_L) dengan u seragam dan m_L = 1/ln M, sehingga peluangnya mencapai layer l adalah M^−l. Link dipilih dengan heuristik dari paper-nya: kandidat hanya disimpan kalau lebih dekat ke node baru daripada ke tetangga mana pun yang sudah disimpan, dan ini menjaga link antar-cluster. Desain berlapis ini memperluas skip list ke proximity graph, dan paper-nya menyarankan M antara 5 dan 48.

Langkah 5 dari 6: Greedy Search

Dari entry point turun ke layer 0

Query
Lebar pencarian (ef)5
Layer 4: hop greedyjalurdiperluasjarak dihitungterlewat
Layer
4
Jarak dihitung
1
Brute force
80
Recall@5 (akhir)
2/5

Di layer 4, pencarian pindah ke tetangga yang lebih dekat ke query dan berhenti kalau tidak ada lagi yang lebih dekat. Node itu menjadi titik awal di satu layer di bawahnya.

Pilih Query A, B, atau C, atur Lebar pencarian (ef) antara 5 dan 40, lalu tekan Putar atau Langkah. Query A pada ef = 5 menunjukkan pola kegagalannya: beam berhenti di antara titik-titik dekat jalur masuk, dan tiga tetangga sebenarnya tidak pernah tercapai. Biaya pencarian tumbuh kira-kira seiring log N, karena setiap layer atas memangkas sisa jarak ke target. Insersi menjalankan pencarian yang sama dengan lebar konstruksi, efConstruction (16 di sini), jadi membangun indeks jauh lebih mahal daripada satu query.

Langkah 6 dari 6: Skala Besar

List IVF, product quantization, memori

List IVF yang diperiksa (nprobe)1 dari 8
IVF: 8 list k-means pada 120 titik contoh; hanya list terpilih dipindaikotak: centroid list; cincin: top 5 eksak (merah muda = terlewat)
Vector tersimpan (N)100M
Dimensi (d)768
Byte kode PQ (m)
Memori untuk 100M vector pada d = 768vector float32307.2 GBkode PQ, 64 B/vector6.4 GBlink HNSW, M = 1612.8 GB
Vector dipindai (IVF contoh)
18 dari 120
Recall@5 (IVF contoh)
3/5
Memori float32
307.2 GB
Memori PQ
6.4 GB

Memeriksa 1 dari 8 list berarti memindai 18 titik, tetapi melewatkan 2 tetangga sebenarnya yang berada tepat di seberang batas list. Vector mentah pada d = 768 memakan 307,2 GB; kode PQ 64 byte memampatkannya 48× menjadi 6,4 GB, dengan pengorbanan pada akurasi jarak.

Geser List IVF yang diperiksa, lalu atur Vector tersimpan, Dimensi, dan Byte kode PQ. IVF, atau inverted file index, menjalankan k-means sekali dan menetapkan setiap vector ke centroid terdekatnya, lalu query hanya memindai nprobe list terdekat. Product quantization (Jégou dkk., 2011) membagi setiap vector menjadi m sub-vector dan mengganti masing-masing dengan indeks dari salah satu 256 centroid yang dipelajari, satu byte per sub-vector. Codebook-nya hanya menambah 256 × d × 4 byte. FAISS menggabungkan keduanya sebagai IVF-PQ, dan vector database menambahkan penyimpanan, filtering, dan pembaruan di sekitar indeks semacam ini.

Apa itu vector search dan bagaimana cara kerja HNSW?

Vector search mencari vector tersimpan yang paling dekat dengan vector query menurut ukuran kemiripan seperti cosine similarity, dot product, atau jarak Euclidean (L2). Vector-nya biasanya berupa embedding, jadi "terdekat" berarti "paling mirip maknanya". Exact search membandingkan query dengan setiap vector tersimpan, dan ini terlalu lambat untuk jutaan item, sehingga sistem nyata memakai indeks approximate nearest neighbour (ANN) seperti HNSW, IVF, dan product quantization.

Vector search adalah tahap retrieval dalam retrieval-augmented generation (RAG): pertanyaan diubah menjadi embedding, chunk dokumen terdekat diambil, lalu LLM menjawab berdasarkan chunk itu. Operasi yang sama menjadi dasar semantic search, sistem rekomendasi, pencarian gambar, deduplikasi, dan anomaly detection. Library seperti FAISS dan hnswlib, serta vector database yang dibangun di atasnya, mengembalikan hasil teratas dari ratusan juta vector dalam hitungan milidetik karena hanya mencari di sebagian sangat kecil data.

Ide utama

  • Vector search mengembalikan k vector tersimpan yang paling mirip dengan query, biasanya embedding yang dibandingkan dengan cosine, dot product, atau jarak L2.
  • Exact search menghitung satu jarak per vector tersimpan, jadi biayanya tumbuh linear dengan ukuran koleksi.
  • Pada vector yang dinormalisasi, cosine similarity, dot product, dan jarak L2 menghasilkan peringkat yang sama.
  • Indeks aproksimasi mengorbankan sedikit recall@k demi pencarian yang puluhan hingga ribuan kali lebih cepat.
  • HNSW membangun proximity graph berlapis dan mencarinya secara greedy dari layer atas yang jarang sampai layer bawah yang rapat, dengan ef mengatur lebar beam.
  • IVF membatasi pencarian pada beberapa cluster k-means, dan product quantization memampatkan setiap vector menjadi beberapa byte sehingga miliaran vector muat di memori.

Ulasan singkat tentang topik ini

Pertanyaan umum

Apa itu vector database?

Vector database menyimpan embedding bersama data sumbernya dan melayani query nearest neighbour lewat indeks ANN, biasanya HNSW atau IVF. Di sekitar indeks itu ada fitur database: insert dan delete, filter metadata, persistensi, replikasi, dan kontrol akses. Banyak mesin relasional dan pencarian, seperti PostgreSQL dengan pgvector dan Elasticsearch, kini juga menyediakan indeks vector.

Apakah HNSW lebih baik daripada IVF?

HNSW biasanya memberi recall lebih tinggi pada latensi yang sama dan tidak butuh tahap training, tetapi menyimpan seluruh vector dan link graph di memori. IVF butuh satu tahap training k-means dan sering digabung dengan product quantization, sehingga jauh lebih hemat memori pada skala miliaran. Pilihan yang tepat bergantung pada ukuran koleksi, anggaran memori, dan seberapa sering datanya berubah.

Bagaimana memilih ef dan M untuk HNSW?

M menentukan jumlah link yang disimpan setiap node, jadi M yang lebih besar menaikkan recall sekaligus pemakaian memori. efConstruction mengatur kualitas pembangunan indeks, dan ef saat query mengatur trade-off recall dan latensi. Pendekatan yang umum: tetapkan M dan efConstruction, lalu naikkan ef sampai recall@k pada held-out set berisi query dengan jawaban eksak mencapai target.

Bisakah hasil vector search difilter berdasarkan metadata?

Bisa, tetapi filtering berinteraksi dengan indeks. Post-filtering mencari dulu, lalu membuang hasil yang tidak cocok, sehingga bisa mengembalikan kurang dari k item kalau filternya ketat. Pre-filtering atau penelusuran graph yang memperhitungkan filter membatasi pencarian pada item yang cocok, dan sebagian besar vector database menerapkan salah satu strategi ini.

Penjelasan terkait

Referensi

  1. Malkov & Yashunin (2016), "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs"
  2. Jégou, Douze & Schmid (2011), "Product Quantization for Nearest Neighbor Search"
  3. Johnson, Douze & Jégou (2017), "Billion-scale similarity search with GPUs"
  4. Douze et al. (2024), "The Faiss library"

Terakhir diperbarui