IVF — truy vấn hai tầng

IVF — truy vấn hai tầng A workflow diagram generated by Archify. 01 / Offline — train + assign 02 / Tầng 1 — chọn cụm 03 / Tầng 2 — quét trong cụm EX / Bẫy biên cụm Đầu vào Tầng 1 — O(nlist) Tầng 2 — O(nprobe·N/nlist) Corpus 1M vector · 1536 chiều, float32 · Offline — train + assign › Đầu vào Corpus 1M vector 1536 chiều, float32 k-means · nlist = 4.000 centroid · Offline — train + assign › Tầng 1 — O(nlist) · train: 120k–1M vector k-means nlist = 4.000 centroid train: 120k–1M vector Bảng centroid · 24 MB trong RAM · Offline — train + assign › Tầng 1 — O(nlist) Bảng centroid 24 MB trong RAM 4.000 inverted list · ~250 vector mỗi list · Offline — train + assign › Tầng 2 — O(nprobe·N/nlist) 4.000 inverted list ~250 vector mỗi list Truy vấn q · vector 1536 chiều · Tầng 1 — chọn cụm › Đầu vào Truy vấn q vector 1536 chiều Chấm điểm centroid · 4.000 × 1536 ≈ 6,1M phép · Tầng 1 — chọn cụm › Tầng 1 — O(nlist) Chấm điểm centroid 4.000 × 1536 ≈ 6,1M phép Chọn nprobe = 16 cụm · Tầng 1 — chọn cụm › Tầng 1 — O(nlist) · núm runtime Chọn nprobe = 16 cụm núm runtime Quét đầy đủ 16 list · 16 × 250 = 4.000 vector · Tầng 2 — quét trong cụm › Tầng 2 — O(nprobe·N/nlist) Quét đầy đủ 16 list 16 × 250 = 4.000 vector Top-k · ít hơn brute force ~125× · Tầng 2 — quét trong cụm › Tầng 2 — O(nprobe·N/nlist) Top-k ít hơn brute force ~125× q sát biên cụm · NN thật ở cụm không probe · Bẫy biên cụm › Tầng 1 — O(nlist) q sát biên cụm NN thật ở cụm không probe Ba cách chữa · nprobe↑ · spilling · balanced · Bẫy biên cụm › Tầng 2 — O(nprobe·N/nlist) Ba cách chữa nprobe↑ · spilling · balanced gán vào cụm gần nhất chỉ 16/4.000 cụm đọc centroid đọc vector trong list 16 list id mẫu train Legend Kết quả Bước tính toán Bẫy / rủi ro Cách chữa Dữ liệu đã dựng Đầu vào

Chi phí hai tầng, tính bằng tay

  • • Tầng 1: nlist = 4.000 phép so sánh centroid ≈ 6,1M
  • • Tầng 2: nprobe × N/nlist = 16 × 250 = 4.000 vector ≈ 6,1M
  • • Tổng ~12,3M so với 1.536M của brute force
  • • Bảng centroid ≈ 24 MB; corpus float32 ≈ 6,1 GB

Vì sao nlist ≈ 4√N

  • • Tổng chi phí = nlist + nprobe · N/nlist
  • • Cực tiểu tại nlist = √(nprobe × N)
  • • nprobe = 16, N = 1M → nlist = 4.000 = 4√N

Ba điều phải nhớ

  • • IVF cần train trước — không dựng được từ index rỗng
  • • nlist bất biến sau train; nprobe mới là núm runtime
  • • Ứng viên sát biên cụm bị bỏ, không có cảnh báo nào