A vector search library built from scratch, with every index measured against exact search.
Wintergreen stores things as vectors, long lists of numbers where similar items land near each other, and finds the ones closest to a query. Scanning every vector is exact but slow, so the interesting part is what you give up to go faster. Wintergreen implements the usual approaches side by side and measures each one's recall against the exact answer instead of assuming it.
The core has no third-party dependencies. pybind11 is only for the Python module, Flask and PyTorch only for the demo.
Search a folder of photos by describing them. All six indexes answer the same query, so their latency and accuracy sit side by side.
python -m pip install -r demo/requirements.txt
python demo/download_dataset.py
python demo/generate_embeddings.py
./build.ps1 -RunDemo| Index | Exact | Idea |
|---|---|---|
FlatIndex |
✅ | Compare against every vector. Threads past 32k rows. |
IVFIndex |
❌ | Cluster the vectors, scan the nprobe nearest clusters. |
HNSWIndex |
❌ | Link each vector to its neighbours, walk the graph. |
ProductQuantizer |
❌ | 512 floats down to 8 bytes, distances from a lookup table. |
KMeans |
- | Lloyd iteration with k-means++ seeding. |
FlatIndex always returns the true nearest neighbours, so the rest are scored against it.
5000 vectors, 512 dimensions, k=10, MSVC Release:
| Variant | P95 | QPS | Recall@10 | Memory |
|---|---|---|---|---|
| flat | 1880 µs | 546 | 1.000 | 9.80 MiB |
| ivf | 607 µs | 1888 | 0.350 | 9.89 MiB |
| hnsw | 649 µs | 1687 | 0.435 | 11.02 MiB |
| pq | 219 µs | 5642 | 0.035 | 0.54 MiB |
Recall is the column that matters - the fastest possible index returns the wrong answers instantly. These figures are a floor: the benchmark uses uniformly random vectors, close to the worst case for any approximate method. On the demo's CLIP embeddings HNSW recall is 0.89.
Full grid in benchmarks/results.csv, notes in
docs/benchmark-report.md.
CMake 3.20+ and a C++23 compiler. ./build.ps1 configures, builds Debug and runs both test
suites. Switches: -CoreOnly, -Benchmark, -PrepareData, -RunDemo, -Clean.
cmake -S . -B build -DWINTERGREEN_BUILD_PYTHON=OFF
cmake --build build --config Release --parallel
ctest --test-dir build -C Release --output-on-failure#include "wintergreen.h"
wintergreen::FlatIndex index({.dim = 3, .metric = wintergreen::Metric::Cosine});
index.add(std::vector<long long>{10, 20}, std::vector<float>{1, 0, 0, 0, 1, 0});
for (auto& hit : index.search(std::vector<float>{1, 0, 0}, 1))
std::printf("id %lld scored %f\n", hit.id, hit.score);The approximate indexes take the same Spec plus their own knobs. nprobe and ef_search are
the recall dials - raise either and both recall and latency go up.
wintergreen::IVFIndex ivf(spec, {.nlist = 16, .nprobe = 4});
ivf.train(vectors);
ivf.add(ids, vectors);
wintergreen::HNSWIndex hnsw(spec, {.m = 16, .ef_construction = 200, .ef_search = 64});
hnsw.add(ids, vectors);From Python, with PYTHONPATH pointed at the build output:
import numpy as np, wintergreen
index = wintergreen.FlatIndex(wintergreen.Spec(3))
index.add(np.array([10, 20], dtype=np.int64),
np.array([[1, 0, 0], [0, 1, 0]], dtype=np.float32))
index.search(np.array([1, 0, 0], dtype=np.float32), 2)
# [{'id': 10, 'score': 1.0}, {'id': 20, 'score': 0.0}]Arrays are read straight out of NumPy without copying and the GIL is released around native work.
MIT. See LICENSE.
- Malkov and Yashunin, HNSW, 2016 - https://arxiv.org/abs/1603.09320
- Jégou, Douze and Schmid, Product Quantization, TPAMI 2011 - https://inria.hal.science/inria-00514462
- Arthur and Vassilvitskii, k-means++, SODA 2007 - https://theory.stanford.edu/~sergei/papers/kMeansPP-soda.pdf
- Radford et al., CLIP, 2021 - https://arxiv.org/abs/2103.00020
- https://github.com/facebookresearch/faiss
- https://ann-benchmarks.com/