# Exact k-Nearest Neighbours — Embeddings & Vector Search

Source: https://www.geekswithgeeks.com/en/embeddings/s-knn

> Search by comparing the query with every vector.

## 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.

![Four tools: brute force, IVF, HNSW, compression.](assets/figures/embeddings/section-3-map.svg) — Figure 3.1 — Brute force, IVF, HNSW and compression.

## 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.

```python
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.

**Quiz:** Why start with brute force?

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

*Answer:* It is exact and gives ground truth to judge approximate methods. You cannot measure recall without exact answers to compare against.