Technische Samenvatting: Sparsiteit is Combinatorische Diepte: Kwantificering van MoE-Expressiviteit via Tropische Geometrie

Probleemstelling

Mixture-of-Experts (MoE)-architecturen zijn de standaard geworden voor het schalen van neurale netwerken door het totale aantal parameters te ontkoppelen van de berekening per invoer (conditionele berekening). Er bestaat echter een theoretische kloof met betrekking tot hun expressieve kracht. Klassieke leertheorie suggereert dat het verminderen van actieve parameters de expressiviteit van een model moet beperken, aangezien expressiviteit traditioneel is gekoppeld aan architecturale breedte en diepte. Waar dichte netwerken worden geanalyseerd met behulp van affiene hypervlakken, slagen bestaande kaders er niet in de topologie van invoerafhankelijke routing in MoE te vangen. Specifiek is het Top-k routing-mechanisme een data-afhankelijke, discrete sorteermethode die expertdomeinen dynamisch afsnijdt tot lokale, niet-convexe polyedrische kegels. Standaard meetkundige telhulpmiddelen storten in wanneer ze geconfronteerd worden met de combinatorische explosie van geneste ongelijkheden die nodig zijn om deze conditionele fragmenten bij te houden. Bijgevolg blijft het onduidelijk hoe sparsere routing de expressiviteit van een neuraal netwerk kwantitatief uitbreidt zonder deze te degraderen.

Methodologie

De auteurs vullen deze kloof door MoE-expressiviteit te analyseren via de lens van tropische geometrie, een algebraïsche structuur over de max-plus halfring ($\mathbb{R} \cup \{-\infty\}$ met operaties $\oplus = \max$ en $\otimes = +$). Dit kader biedt een exacte taal voor het modelleren van maximalisatie, ordening en stuksgewijs-affien gedrag, die inherent zijn aan Top-k routing.

De methodologie verloopt in drie fasen:

1. Algebraïsche Formulering: Het artikel stelt vast dat het Top-k routing-mechanisme algebraïsch isomorf is met het $k$-de elementaire symmetrische tropische polynoom. De beslissingsgrenzen van de router worden afgebeeld op de Normale Veder van een Hypersimplex ($\Delta_{k,N}$), een meetkundig object gerelateerd aan de Tropische Grassmanniaan.
2. Capaciteitsafleiding: Met behulp van de theorie van hypervlakkenarrangementen (specifiek de stelling van Zaslavsky) leiden de auteurs boven- en ondergrenzen af voor het aantal lineaire regio's die door MoE-netwerken worden geïnduceerd. Ze onderscheiden tussen "omgevingscapaciteit" (in de volledige invoerruimte) en "effectieve capaciteit" (beperkt tot laagdimensionale data-manifolds).
3. Architecturale Optimalisatie: De theoretische grenzen worden vertaald naar voorschrijvende ontwerpprincipes. De auteurs formuleren een optimalisatieprobleem om de optimale expertgranulariteit te bepalen en analyseren meetkundige faalmodi, specifiek "Hoekinstorting" (Angular Collapse), waar ongecentreerde data ervoor zorgt dat routingbeslissingen lokaal constant worden.

Belangrijkste Bijdragen

1. Tropische Isomorfie van Routing

Het artikel stelt de eerste algebraïsche isomorfie vast tussen Top-k routing en het $k$-de elementaire symmetrische tropische polynoom. Dit onthult dat het routingmechanisme de invoerruimte partitioneert in de Normale Veder van een Hypersimplex. Deze meetkundige karakterisering bewijst dat sparsiteit combinatorische diepte is: het routingmechanisme schaalt de meetkundige capaciteit met de binomiaalcoëfficiënt $\binom{N}{k}$, waardoor de polynoom-schaalgrenzen van dichte breedte effectief worden omzeild.

2. De Combinatorische Splitsstelling

De auteurs leiden overeenkomstige boven- en ondergrenzen af voor het aantal lineaire regio's voor MoE-netwerken. Ze bewijzen dat de meetkundige capaciteit schaalt als:
$$\Theta\left( \binom{N}{k} (kH)^{d_{in}} \right)$$
waarbij $N$ het totale aantal experts is, $k$ het aantal actieve experts, $H$ de expertbreedte, en $d_{in}$ de invoerdimensie. Dit vestigt de eerste strakke expressiviteitsgrens voor MoE-architecturen, en toont aan dat de combinatorische term $\binom{N}{k}$ fungeert als een meetkundige vermenigvuldiger.

3. Combinatorische Weerbaarheid op Manifolds

Onder de Manifold-hypothese (waar data ligt op een laagdimensionale manifold met intrinsieke dimensie $d_{eff} \ll d_{in}$) bewijst het artikel dat dichte netwerken lijden aan meetkundige capaciteitsinstorting, waarbij de effectieve capaciteit slechts schaalt als $O(H^{d_{eff}})$. Daarentegen vertonen MoE-architecturen Combinatorische Weerbaarheid. De combinatorische winst van sparsere routing blijft bestaan op de manifold, en behoudt hoge expressiviteit via de transversaliteit van routingkegels. De verhouding van effectieve capaciteit tussen MoE en dichte netwerken schaalt als $O\left(\binom{N}{k} k^{d_{eff}}\right)$.

4. Architecturale Wetten voor Optimale Sparsiteit

Door theorie om te zetten in ontwerpprincipes, leidt het artikel het volgende af:

• Fijnkorrelige Experts: Het splitsen van experts in fijnere granulariteiten (verhogen van $N$ terwijl $H$ wordt verlaagd) levert superlineaire winsten in capaciteit op, mits de expertbreedte boven een kritieke limiet blijft ($H \geq d_{eff}$) om Tropische Rangdeficiëntie te voorkomen.
• Gedeelde Experts als Affiene Rectificatoren: Het artikel identificeert Hoekinstorting als een meetkundige faalmodus waarbij ongecentreerde data de router doet verzadigen, waardoor een vaste subset van experts wordt geselecteerd. Het bewijst dat Gedeelde Experts meetkundig noodzakelijk zijn om te fungeren als "Affiene Rectificatoren". Door de globale affiene drager (gemiddelde bias) te isoleren van de gerouteerde residual, centreren gedeelde experts de datamanifold ten opzichte van de projectieve kegels van de router, voorkomen ze routinginstorting en zorgen ze ervoor dat de beslissingsgrenzen regio's met hoge data-variatie snijden.

Resultaten

• Iso-Berekening Vergelijking: Onder een strikte beperking van gelijke actieve parameters (FLOPs) bereikt een Top-4 MoE-model (4 experts selecteren uit 16) een capaciteitsvermenigvuldiger van 1820$\times$ ten opzichte van een dichte baseline, terwijl een Top-1 MoE slechts een 16$\times$ lineaire uitbreiding bereikt.
• Schaalwetten: De bovengrens van de capaciteit vertoont polynoomgroei in $N$ van graad $(m-1)k$ onder granulariteitstransformatie, waarbij de combinatorische winst de logaritmische breedteboete domineert, mits de intrinsieke dimensie $d_{eff}$ klein is.
• Meetkundige Faalmodi: De analyse kwantificeert hoe ongecentreerde data leidt tot een verdwijnende ruimtelijke hoek op de eenheidsbol, waardoor de router een toestand van "Tropische Verzadiging" binnengaat waarbij routingbeslissingen lokaal constant worden, waardoor de combinatorische capaciteit onbereikbaar wordt.

Betekenis

Het artikel claimt het eerste theoretische kader te bieden dat verklaart waarom sparsere conditionele berekening in MoE-architecturen expressief efficiënt is in plaats van beperkend. Door sparsiteit te herformuleren als combinatorische diepte via tropische geometrie, doet het werk het volgende:

1. Het lost de spanning op tussen sparsere routing en hoge expressiviteit, en toont aan dat het routingmechanisme zelf een laag van topologische complexiteit toevoegt die onafhankelijk is van het aantal parameters.
2. Het biedt een rigoureuze meetkundige rechtvaardiging voor de ontwerpkiezen in state-of-the-art architecturen (bijv. DeepSeek-MoE, Mixtral), specifiek de verschuiving naar fijnkorrelige experts en de opname van gedeelde experts.
3. Het vestigt dat de "Combinatorische Weerbaarheid" van MoE het toelaat om hoge expressiviteit te behouden op laagdimensionale datamanifolds waar dichte netwerken lijden aan capaciteitsinstorting.

De auteurs positioneren dit werk niet louter als een beschrijvende analyse, maar als een algebraïsche noodzaak voor het begrijpen van conditionele berekening, en bieden een fundament voor toekomstige architecturale optimalisatie gebaseerd op meetkundige principes in plaats van heuristische efficiëntie.