Menala Kompromi Recall dan Latensi

Indeks ANN yang sama dapat disetel untuk berjalan cepat dengan recall rendah atau lebih lambat dengan recall tinggi, dan pergeseran itu terjadi melalui parameter pencarian. Topik ini membahas parameter yang tersedia pada IVF, HNSW, dan kuantisasi, menghitung efek tiga pengaturan nprobe pada simulasi yang sama, lalu menutupnya dengan pengaturan setara pada pgvector serta cara membaca hasilnya dengan recall@k.

Parameter pencarian dan efeknya#

Setiap keluarga indeks menawarkan parameter yang arah efeknya konsisten: memperbesarnya menaikkan recall dengan biaya yang lebih besar, sedangkan memperkecilnya sebaliknya. Tabel berikut merangkum parameter utamanya beserta tempat pengaturannya.

Parameter pencarian pada IVF dan HNSW dapat diubah per sesi tanpa membangun ulang indeks, sedangkan pilihan kuantisasi terkunci pada saat indeks dibangun. IVF dipilih sebagai bahan pengukuran pada bagian berikut karena setiap klaster yang disapu terhitung dengan tepat, sehingga biaya pengaturannya dapat dinyatakan sebagai jumlah titik, bukan perkiraan.

Mengukur efek tiga pengaturan nprobe#

Simulasi berikut menggunakan dataset 1000 vektor berdimensi 8 yang berasal dari empat kelompok berjauhan, dibagi k-means menjadi empat klaster. Tiga query ditempatkan di perbatasan kelompok agar jawabannya melintasi klaster. Untuk setiap query, jawaban eksak top-10 dihitung melalui pemindaian penuh, kemudian pencarian IVF dijalankan dengan $n_{\text{probe}} = 1$, $2$, dan $4$. recall@10 dirata-ratakan atas tiga query, dan biayanya dinyatakan sebagai total titik yang dipindai.

"""Tiga pengaturan nprobe pada IVF: recall@10 naik seiring jumlah titik yang dipindai."""
import numpy as np
from sklearn.cluster import KMeans

rng = np.random.default_rng(31)

# Empat kelompok data pada ruang 8 dimensi, dijadikan satu dataset 1.000 vektor
pusat = np.array([
    [0, 0, 0, 0, 0, 0, 0, 0],
    [5, 0, 5, 0, 5, 0, 5, 0],
    [0, 5, 0, 5, 0, 5, 0, 5],
    [5, 5, 5, 5, 5, 5, 5, 5],
], dtype=float)
X = np.vstack([rng.standard_normal((250, 8)) + c for c in pusat])

# Tahap pembangunan IVF: seluruh vektor dibagi ke dalam empat klaster
kmeans = KMeans(n_clusters=4, n_init=10, random_state=42).fit(X)
label = kmeans.labels_
centroid = kmeans.cluster_centers_

# Tiga query di perbatasan antar kelompok, sehingga jawabannya melintasi klaster
Q = np.vstack([
    (pusat[0] + pusat[1]) / 2 + rng.normal(0, 1.0, 8),
    (pusat[0] + pusat[2]) / 2 + rng.normal(0, 1.0, 8),
    (pusat[0] + pusat[3]) / 2 + rng.normal(0, 1.0, 8),
])
k = 10

# Jawaban eksak: pemindaian penuh untuk setiap query
eksak = []
for q in Q:
    jarak = np.linalg.norm(X - q, axis=1)
    eksak.append(set(map(int, np.argsort(jarak)[:k])))

# Tiga pengaturan pencarian: jumlah klaster yang disapu per query
print("nprobe | dipindai | recall@10")
for nprobe in (1, 2, 4):
    dipindai = 0
    recall_total = 0.0
    for qi, q in enumerate(Q):
        jarak_centroid = np.linalg.norm(centroid - q, axis=1)
        terpilih = np.argsort(jarak_centroid)[:nprobe]
        kandidat = np.flatnonzero(np.isin(label, terpilih))
        dipindai += kandidat.size
        jarak_kandidat = np.linalg.norm(X[kandidat] - q, axis=1)
        hasil = set(map(int, kandidat[np.argsort(jarak_kandidat)[:k]]))
        recall_total += len(hasil & eksak[qi]) / k
    rata = recall_total / len(Q)
    print(f"{nprobe:>6} | {dipindai:>8} | {rata:>9.2f}")

nprobe | dipindai | recall@10
     1 |      750 |      0.70
     2 |     1500 |      0.90
     4 |     3000 |      1.00

Pola pada keluaran berjalan seperti dugaan. Dengan satu klaster, recall@10 hanya 0,70 sementara 750 titik dipindai untuk tiga query. Menaikkan nprobe menjadi dua klaster menggandakan pemindaian menjadi 1500 titik dan menaikkan recall ke 0,90. Pada empat klaster, seluruh 3000 titik dipindai dan recall mencapai 1,00 karena keempat klaster ikut disapu. Kenaikan recall berhenti di 1,00, sehingga kenaikan parameter lebih lanjut setelah recall mencapai 1,00 hanya menambah biaya tanpa efek pada hasil.

Penyebab recall yang turun pada pengaturan hemat adalah tetangga terbaik yang berada di klaster yang belum disapu. Query di perbatasan sengaja memunculkan kasus ini, tetapi prinsipnya berlaku umum: risiko kehilangan tetangga ada setiap kali jawaban tersebar di lebih banyak klaster daripada yang dipilih. Pada data nyata yang batas-batas antarklasternya saling menembus, kenaikan recall per kenaikan parameter biasanya lebih landai daripada simulasi ini.

Membaca hasil pengukuran dengan recall@k#

Pengukuran yang sama dapat dilakukan tanpa memahami isi indeks. Prosedurnya berurutan: pilih sekumpulan query uji, jalankan pencarian eksak untuk setiap query guna mendapatkan jawaban acuan yang dalam literatur disebut ground truth, jalankan pencarian ANN dengan satu pengaturan, hitung recall@k per query lalu rata-ratakan, dan ulangi untuk pengaturan berikutnya. Setiap pengaturan dipasangkan dengan biayanya, baik jumlah pemindaian maupun waktu yang terukur di lingkungan masing-masing, agar pergeseran recall dan biayanya terlihat utuh.

Bentuk kurva yang dihasilkan biasanya menaik cepat di awal dan melandai saat mendekati 1,00, sebagaimana terlihat pada simulasi. Pola melandai itu berguna saat menentukan titik kerja: kenaikan parameter terakhir yang hanya menaikkan recall sedikit biasanya tidak sebanding dengan biaya pemindaiannya. Proyek ANN-Benchmarks menyajikan pengukuran jenis ini untuk banyak algoritma dengan sumbu recall terhadap queries per second, sehingga pemilihan titik kerja dapat dibandingkan lintas keluarga indeks pada dataset yang sama.

Pengaturan setara pada pgvector#

pgvector mengekspos parameter pencarian yang sama melalui perintah SET. Nilai default hnsw.ef_search adalah 40, sedangkan default ivfflat.probes adalah 1, yang berarti IVFFlat pada kondisi awal hanya memindai satu klaster per query. Mengubah nilai parameter hanya memengaruhi sesi koneksi tempat perintahnya dijalankan, sehingga aplikasi yang menggunakan banyak koneksi perlu mengatur nilainya pada setiap koneksi.

-- tidak-dijalankan
SET hnsw.ef_search = 100;
SET ivfflat.probes = 10;

Kedua perintah di atas menggambarkan kompromi yang sama seperti simulasi: ivfflat.probes = 10 menyapu sepuluh klaster dari jumlah lists yang tersedia, sedangkan hnsw.ef_search = 100 memperluas kumpulan kandidat HNSW melebihi default 40. Nilai yang tepat tidak diwariskan dari satu penerapan ke penerapan lain, melainkan diukur dengan prosedur recall@k pada query dan data masing-masing.

Kesalahan umum#

Kesalahan pertama adalah mengukur recall@k dengan nilai k yang berbeda dari k yang digunakan aplikasi. Indeks yang disetel untuk recall@10 tidak otomatis setia pada recall@1, karena urutan di dalam hasil tidak dijamin oleh rumus recall, sehingga nilai k pengukurannya harus sama dengan nilai k pencarian sebenarnya.

Kesalahan kedua adalah melaporkan recall tanpa pasangan biayanya. Angka recall@10 sebesar 1,00 pada simulasi diperoleh dengan memindai seluruh 3000 titik, sehingga tanpa kolom biaya, pengaturan tersebut terlihat unggul padahal perilakunya sama dengan pemindaian penuh. Setiap angka recall dalam perbandingan sebaiknya menyertakan jumlah pemindaian atau waktu yang setara.

Ringkasan#

• Parameter pencarian menentukan kompromi antara recall dan biaya: nprobe pada IVF, ef_search pada HNSW, dan jenis kode kuantisasi pada kompresi.
• Simulasi tiga pengaturan nprobe menunjukkan recall@10 naik dari 0,70 ke 0,90 lalu 1,00, seiring jumlah titik yang dipindai naik dari 750 ke 1500 lalu 3000.
• recall@k diukur terhadap jawaban eksak pada sekumpulan query uji, dan kenaikannya melandai mendekati 1,00 sehingga kenaikan terakhir jarang sebanding dengan biayanya.

Referensi#

• pgvector — GitHub — Dokumentasi pgvector yang mencantumkan parameter hnsw.ef_search, ivfflat.probes, serta nilai defaultnya.
• ANN-Benchmarks — GitHub — Proyek benchmark yang menyajikan kurva recall terhadap kecepatan query untuk berbagai algoritma ANN.