[FEA] Kmeans to support massive k
Open
@HowardHuang1 is already working on this.
Since Apr 14, 2026.
feature request
- Dominant language
- Cuda
- Stars
- 854
- Forks
- 236
- Avg merge
- 3d 3h
- Merged PRs (30d)
- 62
Description
GPUs have become widely used for coarse quantization in IVFs, but the fundamental kmeans algorithm becomes very limited as k increases, since it computes a 1-nn for expectation step which boils down to an exhaustive matrix multiplication.
We should investigate the potential of using a high recall ANN inside kmeans for thr 1-nn step to speed up the expectation step when k is massive. For example, in a single IVF with 100B ot 1T vectors, it's not uncommon to have a global index with 1-10B centroids.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Assessment
This issue has not been assessed yet.