hn.today

SuperEMeans: Making e-means 3× faster

lkuffo.com54 points0 comments
Screenshot of SuperEMeans: Making e-means 3× faster

SuperEMeans combines e-means, which aims to achieve strong clustering quality in fewer training epochs, with SuperKMeans, which speeds clustering by pruning unnecessary dimension calculations. The evaluation builds IVF vector-search indexes from five million 1,536-dimensional OpenAI embeddings and ten million 1,024-dimensional Cohere embeddings, using a 16-core CPU. With two epochs, SuperEMeans runs in 128 seconds on the OpenAI data and 295 seconds on Cohere, versus 203 and 526 seconds for the tested e-means implementation - up to 1.8 times faster. At five epochs, it is about three times faster: 162 versus 513 seconds for OpenAI, and 436 versus 1,283 seconds for Cohere.

Search quality, measured by recall among the top 100 results while probing 1% of clusters, is essentially unchanged by SuperEMeans relative to e-means. However, e-means’ clusters can be larger in frequently queried regions, so searches scan roughly 8-20% more vectors than with traditional k-means at the same probe rate. This imbalance increases search cost even when recall is similar; the algorithm’s mean-squared-error objective does not prioritize balanced cluster sizes. The author links the problem to mini-batch updates and a conservative cluster-revival threshold. Raising that threshold from 0.1 to 0.3 improves Cohere cluster balance, though it does not fully match k-means. The results argue that vector-search clustering should account for both assignment quality and cluster balance.

Read on lkuffo.com0 comments on Hacker News

Summary generated by AI from the linked article. hn.today is not affiliated with Hacker News or Y Combinator.

More in Programming

Sarasa Gothic Mono

Sarasa Gothic Mono

Sarasa Gothic Mono is a free, open-source monospace typeface built for multilingual programming, combining Source Han Sans and Iosevka. It offers coding ligatures, pixel-friendly hinting, condensed characters, and support for Latin, Cyrillic, Greek, and East Asian scripts. (picaq.github.io)

The daily digest

Today's best Hacker News stories, summarized and screenshotted, one email a day.