E-means: 10x faster k-means at equal loss

Re:E-means: 10x faster k-means at equal loss by gilfyole on Tuesday November 10, 2026 @06:29AM (#50438828)

Thanks for this. I tried experimenting with e-means in retrieval engine im building, for that I had to port the CPU version from faiss to Rust

https://crates.io/crates/emeans

https://pypi.org/project/emeans

We use k-means to build the cells of our vector index, which today runs 5 Lloyd iterations on a sample of the data. So I ran a quick test on 500k LAION embeddings (768 dimensions, 4,096 cells) against our current code:

- Current setup of 5 iterations: about 4x faster, with slightly better recall at every probe count (for example 0.9518 vs 0.9473 at 32 probes) and fewer rows scanned per query

- Cells came out much more even. The biggest cell went from 6.6x the average size to 4.75x, and there were no empty cells (we had 7)

- With only 2 iterations it was about 10x faster and recall stayed close to what we have today

These numbers are from my mac. I'm rerunning on a Linux box with AVX-512 now. If it holds up, we'll try it in our index build

Some notes here: https://github.com/infino-ai/infino/issues/1279

[ Parent | on HN ]

Re:E-means: 10x faster k-means at equal loss by swann_bessa on Tuesday November 10, 2026 @06:56AM (#50439052)

Hi, I’m the author of the paper.

Thank you for trying e-means and detailing your results. This kind of results of e-means at 2 epochs compared with Lloyd is the typical kind of acceleration we want people to know about.

If you have any questions, I’ll be happy to answer.

[ Parent | on HN ]