Исследователи из Meta FAIR предложили алгоритм e-means, который, по их утверждениям, достигает качества классического k-means за 1,4–2,6 эпохи вместо множества полных проходов по данным. Против оптимизированного под GPU Flash-KMeans авторы заявляют ускорение от 9,5 до 45,5 раза. k-means остаётся базовым инструментом кластеризации: его применяют для векторного поиска и RAG, работы с эмбеддингами, балансировки датасетов, квантизации весов и KV-кэша, построения кодбуков для токенов изображений и аудио, а также для поиска аномалий. На миллиардах векторов каждый проход по данным обходится дорого, поэтому индустрия давно ищет способы удешевить вычисления. Мини-батч-варианты k-means обновляют центры по небольшим порциям данных и работают быстрее, но сходятся к заметно худшему качеству. Авторы e-means предлагают пересчитывать центры через экспоненциальное скользящее среднее по батчам: для каждого кластера хранится число точек и их сумма, а с каждым новым батчем свежие данные получают больший вес, тогда как старые постепенно забываются. Сам центр остаётся обычным средним — суммой, делённой на количество. Благодаря этому центры начинают смещаться уже после первых батчей, а не после полного прохода. Размер батча и шаг обновления вычисляются по готовым формулам, так что подбирать гиперпараметры вручную не требуется. На самом крупном тесте — 10 млрд эмбеддингов и 16 млн кластеров — алгоритму понадобилось почти в 9 раз меньше GPU-часов, а лосс оказался немного ниже, чем у классического k-means. Для RAG-систем на больших базах, где построение индексов занимает тысячи часов работы видеокарт, это может дать заметную экономию. Авторы опубликовали статью, код и страницу проекта.