Metan Faiss 1.16.0 tuo e-means-menetelmän suurten aineistojen nopeampaan klusterointiin

Metan Faiss-ylläpitäjät julkaisivat version 1.16.0 10. marraskuuta 2026. Se sisältää FAIR at Metan e-means-klusterointialgoritmin CPU-, GPU- ja hajautettuina toteutuksina. Tutkijoiden mukaan menetelmä saavuttaa Lloydin k-meansin virhetason 25 kierroksen jälkeen jo 1,4–2,6 kierroksessa. GPU:n suoritusajat ovat 10–45 kertaa lyhyemmät kuin vertailussa mukana olleilla toteutuksilla.

Ohjelmistojulkaisua edelsi tutkimuksen esijulkaisun lähettäminen arXiviin 6. marraskuuta 2026, joten kyse ei ollut algoritmin ensimmäisestä julkisesta esittelystä. Työn tekivät FAIR at Metan ja École Nationale des Ponts et Chaussées’n tutkijat.

Versio 1.16.0 sisältää e-meansin vertailutoteutukset, hajautetun ja sentroideihin jaetun koulutuksen, Triton- ja CuTe-osoitusrajapinnat, pienemmän tarkkuuden osoituksen sekä vertailutestit tutkimustulosten toistamiseen. Mukana on myös DINO-esimerkkejä, joissa data pidetään muistissa tai suoratoistetaan SSD-levyiltä.

Näin e-means päivittää sentroideja

K-means pyrkii löytämään sentroidit, jotka minimoivat vektorien ja niitä lähimpien sentroidien välisen neliöityjen etäisyyksien keskiarvon. Menetelmää käytetään tiedonhakuun, kvantisointiin ja datan kuratointiin. Lloydin algoritmi sijoittaa jokaisen pisteen lähimpään sentroidiin ja laskee kunkin klusterin summan ja pisteiden määrän uudelleen koko aineistosta. E-means sen sijaan päivittää eksponentiaalisesti vaimenevia summia ja lukumääriä minieristä, jolloin aiempien sijoitusten vaikutus vähenee vähitellen. Jokainen sentroidi on edelleen juoksevan vektorisummansa ja juoksevan lukumääränsä suhde. Kun koko aineisto käsitellään yhtenä eränä ja askelpituus on 1, tuloksena on yksi Lloyd-iteraatio.

Kaksi aineistoon sovitettua skaalautumislakia määrittää eräkoon ja alkuperäisen askelpituuden aineiston koon, klusterien määrän ja kierrosbudjetin perusteella. Näin vältytään erilliseltä hyperparametrien hakuajolta, jota aiemmat minieriin perustuvat menetelmät edellyttivät. Kosinusaikataulu pienentää askelpituuden kymmenesosaan sen alkuarvosta. Julkaistun luokan oletusarvona on viisi koulutuskierrosta, ja se hyväksyy myös kierrosten murto-osat.

Tutkijat sovittivat skaalautumislait 75 000 optimointiajolla DEEP-kokoonpanoilla. He raportoivat, että pidätetyllä aineistolla mitatun katumuksen mediaani eli parhaan ruudukkoasetuksen ylittävä virhe oli askelpituuslain kohdalla 0,07 % ja oletuseräkokolain kohdalla 0,19 %. Menetelmä herättää lisäksi liian vähän käytetyt klusterit uudelleen jakamalla luovuttajaklusterin. Lopuksi kunkin klusterin keskiarvo lasketaan täsmällisesti viimeisen kierroksen sijoitusten perusteella. Erillinen, hitaasti muuttuvaan keskiarvoon perustuva viimeistely pyrkii sen sijaan pienentämään otoksen ulkopuolista virhettä.

Vertailutestit ulottuvat kymmeneen miljardiin vektoriin

Koko artikkelissa kuvataan testejä upotus- ja synteettisillä aineistoilla. Tärkeimmät GPU-vertailut tehtiin H100-näytönohjaimilla, joissa on 80 Gt muistia, ja CPU-kokeet 64-ytimisellä Xeon Platinum 8462Y+ -prosessorilla. Tutkijoiden mukaan e-means saavutti 11 VIBE-upotustestissä Lloydin 25 kierroksen virhetason 1,6–2,6 kierroksessa. Nopeutus oli 8,0–22,8-kertainen Flash-KMeansiin verrattuna yhdellä H100:lla ja 9,0–15,0-kertainen Faissiin verrattuna 64 CPU-ytimellä. Jokaisessa testissä käytettiin 20 siementä.

Suurimmassa mittakaavassa tutkijat ryhmittelivät DINO10B-aineiston, joka sisältää 10 miljardia 1 024-ulotteista DINO-kuvalaikutusupotusta, noin 16,7 miljoonaan klusteriin 2,5 kierroksessa käyttäen täsmällistä osoitusta. Testivirhe oli hieman pienempi kuin Lloydin 25 kierroksen vertailutasolla. Ajo käytti 779 GPU-tuntia 32 koneella. Erillisessä ajossa käytettiin käänteistiedostoindeksin (IVF) kautta tehtävää likimääräistä lähimmän sentroidin hakua. Se alitti vertailutason kolmen kierroksen jälkeen käyttäen 23,2 GPU-tuntia yhdellä kahdeksan näytönohjaimen koneella. IVF-menetelmä hakee valituista sentroidiämpäreistä sen sijaan, että se vertaisi jokaista pistettä jokaiseen sentroidiin.

Artikkelin mukaan IVF-osoitus on kymmenen miljardin vektorin mittakaavassa 34 kertaa edullisempaa kuin täsmällinen osoitus, mutta sadan miljoonan vektorin aineistossa siitä ei ole hyötyä. Tämä ero osoittaa, ettei pelkkä kierrosten määrä määritä infrastruktuuritarvetta: tarvittavan laitteiston määrään vaikuttavat toteutus ja osoitusmenetelmä.

Saatavuus ja dokumentoidut rajoitukset

Virallisessa käyttöoppaassa annetaan ohjeet NumpyEmeans NumPy-dataa varten ja Emeans PyTorch-tensoreita varten. Faiss yksinään tukee suorittamista suorittimella; GPU-suoritus edellyttää CUDA-yhteensopivaa PyTorchia. CuTe-ytimet ovat käytettävissä H100- ja H200-näytönohjaimilla ja Triton muilla tuetuilla uudemmilla NVIDIA-näytönohjaimilla. GPU:lla pienempää tarkkuutta käytetään vain lähimmän sentroidin osoituksessa, kun taas sentroidit, juoksevat summat ja palautettavat etäisyydet säilyvät FP32-tarkkuudella. Replikoidut ja osioidut sentroidiluokat tukevat koulutusta usealla GPU:lla. Artikkelissa todetaan, että 16 miljoonan sentroidin FP32-summat vievät 64 GiB muistia, mikä tekee osioinnista perusteltua tässä mittakaavassa.

Skaalautumislait on viritetty suhteellisen moniulotteiselle datalle, eivätkä ne ole optimaalisia hyvin pieniulotteisille tai pienille aineistoille. Julkaistussa oletusasetuksessa käytetään siksi laatua painottavaa eräkokolakia, kun ulottuvuuksia on enintään 16, ja klusterien elvytys poistetaan käytöstä, kun niitä on enintään kaksi. Käyttöoppaassa huomautetaan myös, että palautetut koulutustunnisteet ovat viimeiseltä kierrokselta eivätkä välttämättä vastaa lopullisia sentroideja. Lisäksi GPU-toteutus ei tarkista, sisältävätkö syötteet NaN- tai ääretönarvoja.

Suuria upotuskokoelmia klusteroiville tekoälyputkille julkaisu konkretisoi kompromissin: ylläpidetyssä kirjastossa voidaan käyttää aiempaa vähemmän koulutuskierroksia, mutta suurimmat GPU-kulutuksen vähennykset riippuvat aineiston mittakaavasta, laitteistosta ja siitä, sopiiko likimääräinen osoitus kyseiseen käyttötapaukseen.