Exact k-Nearest Neighbours

Simple, exact, and often enough

k-nearest neighbours (kNN) search returns the k vectors closest to the query. The exact method, brute force or a flat index, computes the distance to every stored vector and keeps the best k. Its cost is N × dimensions operations per query, which is trivial for thousands of vectors and still fine for a few hundred thousand on a modern CPU or GPU with batching. Brute force is exact (no missed neighbours), needs no training or tuning, and supports any filter. Always start here: it gives you the ground truth against which you will judge every approximate method, and it is often fast enough that you never need more.

Find the nearest without checking everything

Brute force is exact; indexes such as IVF and HNSW trade a little recall for much more speed.

Brute force against a library, run

I ran this in a Python virtual environment with numpy 2.5.3, scikit-learn 1.9.1 and faiss-cpu 1.15.1, with fixed random seeds so the numbers repeat. A numpy brute-force search and scikit-learn's brute-force NearestNeighbors return exactly the same five neighbours for the query.

import numpy as np
from sklearn.neighbors import NearestNeighbors

rng = np.random.default_rng(1)
data = rng.normal(size=(500, 16)); q = rng.normal(size=(1, 16))
brute = np.argsort(np.linalg.norm(data - q, axis=1))[:5]
nn = NearestNeighbors(n_neighbors=5, algorithm="brute").fit(data)
lib = nn.kneighbors(q, return_distance=False)[0]
print("numpy brute force:", brute.tolist())
print("sklearn           :", lib.tolist(), "| identical:", brute.tolist() == lib.tolist())

Output:

numpy brute force: [109, 179, 258, 325, 168]
sklearn           : [109, 179, 258, 325, 168] | identical: True

GPUs make brute force go further

Batched matrix multiplication on a GPU can brute-force millions of vectors quickly, which often removes the need for an ANN index.

Quick check: Why start with brute force?

• It needs a GPU
• It is always the fastest at any size
• It is exact and gives ground truth to judge approximate methods
• It cannot filter