How do I do nearest-neighbor search on millions of vectors quickly?

For millions of vectors, brute-force nearest-neighbor search is usually too slow, so you want an Approximate Nearest Neighbor (ANN) method. The best choice depends on your data size, latency target, update rate, and whether you need exact results.

Common fast approaches

1) HNSW (Hierarchical Navigable Small World)

• Very popular for fast search with high recall.
• Great for:
  • low latency
  • high-dimensional embeddings
  • mostly read-heavy workloads
• Pros:
  • excellent query speed
  • strong accuracy
  • simple to use in libraries like hnswlib, FAISS, Milvus, Weaviate, Qdrant
• Cons:
  • memory-heavy
  • slower to build than some alternatives
  • updates are okay, but not ideal for extremely high churn

2) IVF / inverted file indexes

• Used in FAISS and vector databases.
• Idea: cluster vectors into buckets, search only a few buckets.
• Often combined with:
  • PQ (Product Quantization) for compression
  • OPQ for better quantization quality
• Pros:
  • scales well to very large collections
  • memory-efficient with PQ
• Cons:
  • tuning required (nlist, nprobe)
  • may have lower recall than HNSW if not tuned well

3) PQ / compressed search

• Best when memory is tight.
• Compress vectors into small codes and search approximately.
• Often used with IVF.
• Pros:
  • much lower RAM usage
• Cons:
  • more approximation, can reduce recall

4) Tree-based methods / KD-trees / Ball trees

• Only good for low dimensions.
• For modern embeddings (e.g., 128–1536 dims), they usually don’t scale well.

5) Brute force with GPU

• If you have a GPU and can batch queries, brute-force can actually be very fast up to surprisingly large scales.
• Good when:
  • exact results matter
  • index-building complexity should be avoided
  • you can use large batched queries
• Tools:
  • FAISS GPU
• Cons:
  • expensive memory/compute for large datasets
  • not always ideal for low-latency online queries

---

Practical recommendation

If you want a good default:

• Use HNSW if you want:

  • easy setup
  • high recall
  • fast query performance
  • enough RAM

• Use FAISS IVF-PQ if you want:

  • better memory efficiency
  • large-scale indexing
  • tunable tradeoff between speed and accuracy

• Use FAISS GPU brute force if:

  • exact search is required
  • you have GPUs
  • queries are batched

---

Key tuning knobs

HNSW

• M: graph degree / connectivity
  • higher = better recall, more memory
• efConstruction: build quality
  • higher = slower build, better index
• efSearch: query accuracy/speed tradeoff
  • higher = better recall, slower search

Typical starting point:

• M = 16 or 32
• efConstruction = 100–400
• efSearch = 50–200

IVF / FAISS

• nlist: number of clusters
• nprobe: number of clusters searched per query
  • higher = better recall, slower
• With PQ:
  • more compression = less memory, lower accuracy

Rule of thumb:

• nlist often around sqrt(N) or tuned experimentally
• nprobe start around 5–20 and adjust

---

Architecture tips

To keep search fast at scale:

• Normalize vectors if using cosine similarity, and then use inner product search.
• Batch queries whenever possible.
• Keep vectors in contiguous memory.
• Filter candidates if you have metadata constraints before or during ANN search.
• Sharding helps if dataset is too large for one machine.
• Use SSD-backed vector DBs only if RAM is insufficient, but expect slower performance.

---

If you’re building this yourself

A simple path:

1. Choose similarity metric:
   • cosine
   • inner product
   • L2
2. Pick an ANN library:
   • hnswlib for simple HNSW
   • FAISS for many scalable options
3. Build index
4. Tune recall vs latency using a validation set
5. Benchmark with your real queries

---

What to choose by scenario

• Fast, accurate, memory OK → HNSW
• Huge dataset, memory constrained → IVF-PQ
• Exact search on GPU → FAISS GPU
• Managed production vector search → Qdrant / Milvus / Weaviate / Pinecone / Elasticsearch kNN depending on ecosystem

---

If you want, I can give you:

1. a Python example with FAISS,
2. a Python example with hnswlib, or
3. a decision guide based on your vector dimension and dataset size.