Flat Indexing: When is Brute Force better?
Flat indexing means no approximate index at all: you store vectors in a list and, for each query, compute the distance (or similarity) to every vector. That’s brute force—exact nearest neighbor search. It gives perfect recall and is often the best choice when the dataset is small enough that scanning all vectors is cheaper than building and querying an IVF or HNSW index.
Summary
- For small N (e.g. under tens of thousands), one pass over all vectors can be faster than graph/cluster traversal; you get exact results. Benefits from SIMD and cache-friendly access.
- Use flat when N is small, when you need exact results, or to avoid build/tuning. For large scale use search space reduction and optionally quantization.
- Pipeline: store vectors in a contiguous list; each query scans all, computes distance, returns top-k. No build step; add vectors by appending.
- Trade-off: flat gives perfect recall and simple ops; ANN indexes reduce work per query at the cost of build time and approximate results.
- Search space reduction techniques and comparing graph-based vs. cluster-based indexes describe when to move from flat to IVF or HNSW.
Why flat can win for small N
Approximate indexes (IVF, HNSW, etc.) have build cost and per-query overhead. For small N (e.g. under tens of thousands of vectors, depending on dimension and hardware), a single pass over all vectors can be faster than traversing a graph or probing clusters, and you get exact results. Flat search also benefits heavily from SIMD and cache-friendly sequential access, so it scales well on modern CPUs for moderate sizes. Many systems use flat as the default for small collections and only switch to IVF or HNSW when the dataset grows.
When to switch to ANN
So “when is brute force better?”—when N is small, when you need guaranteed exact results, or when you want to avoid index build time and tuning (e.g. nlist/nprobe, efSearch). For large-scale ANN, flat becomes impractical and you need search space reduction via indexes and optionally quantization.
Practical tip: benchmark flat vs. HNSW/IVF on your (N, d) and hardware; the crossover depends on dimension, SIMD, and target latency. Measuring index build time and measuring latency (p50, p99) help decide; what is IVF and what is HNSW describe the main alternatives when you outgrow flat.
Frequently Asked Questions
What is “small” for flat?
Roughly < 10k–100k vectors depending on dimension and hardware. With SIMD, flat can handle 100k+ 384-d vectors in a few ms per query.
Does flat support all distance metrics?
Yes. You’re just looping over vectors; any metric (L2, cosine, dot product) works. ANN indexes may optimize only a subset.
Can I combine flat with quantization?
Yes. Store quantized vectors (e.g. INT8) and compute distance on quantized values; still brute force but faster and less memory. See scalar quantization.
When does HNSW beat flat?
When N is large enough that the flat scan cost exceeds HNSW’s O(log n) traversal. The crossover depends on dimension, efSearch, and implementation.