Skip to content
Blog

Brute-Force Scans: When Linear Search Is Actually the Fastest Option

Why exhaustive vector scans still beat ANN indexes for small to medium corpora, and how SIMD makes brute force surprisingly competitive.

Published on • November 22, 2026

AI Assistant

Introduction

Every vector search tutorial starts with ANN indexes — HNSW, IVF, PQ. Yet a large share of production workloads are still best served by the dumbest possible method: compare the query against every vector and keep the best ones. Brute force is exact, tunable-free, and often faster than you expect.

How a Brute-Force Scan Works

best = min-heap of size k
for each vector v in corpus:
    score = distance(query, v)
    push (score, v) into best
return best
  • Build time: zero (store vectors as-is)
  • Memory: just the raw vectors — no graph, no centroids, no codebooks
  • Query time: O(n · d) — linear in corpus size and dimension

There is no index to tune, no recall knob to calibrate, and no rebuild after inserts. Correctness is trivially guaranteed: you always get the true top-k.

Why It Is Faster Than It Sounds

Three factors make linear scan surprisingly competitive:

  1. SIMD instructions. Modern CPUs compute 8–16 float operations per cycle with AVX2/AVX-512. A dot product over 768 floats is a handful of vectorized instructions.
  2. Memory bandwidth, not FLOPs. For in-memory corpora the bottleneck is streaming the vectors; contiguous float32 arrays stream at near-peak bandwidth.
  3. No random access. ANN graph traversal jumps around memory, causing cache misses. A linear scan is perfectly sequential — hardware prefetchers love it.

Numbers from the ANN-benchmarking world repeatedly show: for corpora up to a few hundred thousand vectors, a well-optimised brute-force scan answers in single-digit milliseconds and often matches or beats HNSW on latency while being exact.

When Brute Force Wins

  • Small/medium corpora — roughly < 100k–1M vectors depending on dimension and hardware
  • High QPS with small k — SIMD scans parallelise trivially across cores
  • Frequently changing data — no index rebuild or incremental-insert cost
  • Ground truth — you need exact results to benchmark ANN recall against
  • Cold, one-off queries — building an index for a batch job is pure overhead

When It Loses

  • Large corpora — cost grows linearly; 100M vectors × every query is unaffordable
  • High dimensions + large k — work per query balloons
  • Memory-tight deployments — no way to shrink the index with quantisation and still keep exactness (PQ codes need a scan too, but over much smaller data)

Practical Advice

Start with brute force as your baseline. Measure p95 latency at realistic corpus size and QPS. If it meets your budget, ship it — you have skipped index tuning entirely. Only move to HNSW/IVF when measurements, not assumptions, say you must. Keep the brute-force path around as your exact ground truth for recall evaluation.

Conclusion

Brute force is not the enemy of good search — it is the yardstick. Exact, simple, and SIMD-friendly, it wins outright for a huge class of workloads. Earn the right to add an index by first proving you need one.

References