e-means, k-means를 10배 빠르게 대체
원제: E-means: Outperforming k-means in one-tenth the epochs
왜 중요한가
k-means는 벡터 검색, 데이터 압축, VQ-VAE 등 AI 인프라 전반에 쓰이는 핵심 알고리즘으로, 10배 이상의 속도 향상은 대규모 시스템 비용에 직접 영향을 미친다.
Meta FAIR 연구팀이 개발한 클러스터링 알고리즘 'e-means'가 2026년 공개됐다. Lloyd 알고리즘 기반 k-means 대비 epoch 수를 최대 10분의 1로 줄이면서도 더 낮은 손실(loss)을 달성했으며, GPU에서는 최대 45배, CPU에서는 최대 15배의 wall-clock 시간 단축이 측정됐다.
Meta FAIR의 Swann Bessa, Hugo Touvron, Matthijs Douze, Hervé Jégou 등 공동 연구진이 개발한 e-means 알고리즘이 오픈소스로 공개됐다. 논문은 arXiv(2611.09501)에 게재됐으며, 코드는 Faiss 라이브러리(faiss/contrib/e_means)에서 사용할 수 있다.
e-means는 1967년 MacQueen이 제안한 규칙에 머물러 있던 미니배치 k-means 방식을 현대 딥러닝 최적화 기법으로 대체한다. 핵심은 지수 이동 평균(Exponential Moving Average) 기반 미니배치 업데이트다. 기존 Lloyd 알고리즘이 에포크당 1회 센트로이드를 갱신하는 데 비해 e-means는 에포크당 97회 업데이트를 수행한다.
성능 측면에서 e-means는 다양한 규모와 데이터셋에서 Lloyd 알고리즘이 25 에포크 만에 도달하는 test loss를 1.2~3 에포크 만에 달성했다. GPU 환경에서는 최신 Lloyd 구현체인 Flash-KMeans 대비 10~45배, CPU에서는 Faiss 대비 8~15배 빠른 wall-clock 속도를 기록했다.
특히 하이퍼파라미터 튜닝이 불필요하다는 점이 차별점이다. 배치 크기와 스텝 크기를 스케일링 법칙으로 자동 설정하며, 코사인 스케줄 감쇠율, 초기화 개선, 소멸 클러스터 복구 전략, 그리고 훈련 말미에 추가 손실을 줄이는 파이널라이제이션 단계도 포함됐다. 브라우저 기반 플레이그라운드도 제공돼 즉시 체험 가능하다.