Résumé Technique : La Sparsité est une Profondeur Combinatoire : Quantification de l'Expressivité des MoE via la Géométrie Tropicale

Énoncé du Problème

Les architectures de type Mélange d'Experts (MoE) sont devenues la norme pour mettre à l'échelle les réseaux de neurones en découplant le nombre total de paramètres du calcul par entrée (calcul conditionnel). Cependant, un écart théorique persiste concernant leur pouvoir expressif. La théorie classique de l'apprentissage suggère que la réduction des paramètres actifs devrait limiter l'expressivité d'un modèle, car celle-ci est traditionnellement liée à la largeur et à la profondeur architecturales. Alors que les réseaux denses sont analysés à l'aide d'arrangements d'hyperplans affines, les cadres existants échouent à capturer la topologie du routage dépendant de l'entrée dans les MoE. Plus précisément, le mécanisme de routage Top-k est une opération de tri discrète dépendante des données qui tronque dynamiquement les domaines d'experts en cônes polyédriques locaux non convexes. Les outils géométriques de comptage standards s'effondrent face à l'explosion combinatoire des inégalités imbriquées requises pour suivre ces fragments conditionnels. Par conséquent, il reste flou comment le routage sparse étend quantitativement l'expressivité d'un réseau de neurones sans la dégrader.

Méthodologie

Les auteurs comblent cet écart en analysant l'expressivité des MoE à travers le prisme de la géométrie tropicale, une structure algébrique sur le demi-anneau max-plus ($\mathbb{R} \cup \{-\infty\}$ avec les opérations $\oplus = \max$ et $\otimes = +$). Ce cadre fournit un langage exact pour modéliser la maximisation, le classement et le comportement affine par morceaux, qui sont inhérents au routage Top-k.

La méthodologie se déroule en trois étapes :

1. Formulation Algébrique : L'article établit que le mécanisme de routage Top-k est algébriquement isomorphe au $k$-ième polynôme tropical symétrique élémentaire. Les frontières de décision du routeur sont mappées sur le Vent Normal d'un Hypersimplexe ($\Delta_{k,N}$), un objet géométrique lié à la Grassmannienne Tropicale.
2. Dérivation de la Capacité : En utilisant la théorie des arrangements d'hyperplans (spécifiquement le théorème de Zaslavsky), les auteurs dérivent des bornes supérieures et inférieures sur le nombre de régions linéaires induites par les réseaux MoE. Ils distinguent entre la "capacité ambiante" (dans l'espace d'entrée complet) et la "capacité effective" (restreinte aux variétés de données de basse dimension).
3. Optimisation Architecturale : Les bornes théoriques sont traduites en principes de conception prescriptifs. Les auteurs formulent un problème d'optimisation pour déterminer la granularité optimale des experts et analysent les modes de défaillance géométriques, spécifiquement l'"Effondrement Angulaire", où des données non centrées provoquent des décisions de routage localement constantes.

Contributions Clés

1. Isomorphisme Tropical du Routage

L'article établit le premier isomorphisme algébrique entre le routage Top-k et le $k$-ième polynôme tropical symétrique élémentaire. Cela révèle que le mécanisme de routage partitionne l'espace d'entrée selon le Vent Normal d'un Hypersimplexe. Cette caractérisation géométrique prouve que la sparsité est une profondeur combinatoire : le mécanisme de routage multiplie la capacité géométrique par le coefficient binomial $\binom{N}{k}$, contournant efficacement les limites de mise à l'échelle polynomiale de la largeur dense.

2. Le Théorème de Tranchage Combinatoire

Les auteurs dérivent des bornes supérieures et inférieures correspondantes sur le nombre de régions linéaires pour les réseaux MoE. Ils prouvent que la capacité géométrique évolue selon :
$$\Theta\left( \binom{N}{k} (kH)^{d_{in}} \right)$$
où $N$ est le nombre total d'experts, $k$ le nombre d'experts actifs, $H$ la largeur de l'expert, et $d_{in}$ la dimension d'entrée. Cela établit la première borne d'expressivité serrée pour les architectures MoE, démontrant que le terme combinatoire $\binom{N}{k}$ agit comme un multiplicateur géométrique.

3. Résilience Combinatoire sur les Variétés

Sous l'Hypothèse de Variété (où les données résident sur une variété de basse dimension de dimension intrinsèque $d_{eff} \ll d_{in}$), l'article prouve que les réseaux denses souffrent d'un effondrement de capacité géométrique, où la capacité effective évolue uniquement selon $O(H^{d_{eff}})$. En revanche, les architectures MoE présentent une Résilience Combinatoire. Le gain combinatoire issu du routage sparse persiste sur la variété, maintenant une expressivité élevée via la transversalité des cônes de routage. Le ratio de capacité effective entre les MoE et les réseaux denses évolue selon $O\left(\binom{N}{k} k^{d_{eff}}\right)$.

4. Lois Architecturales pour une Sparsité Optimale

Traduisant la théorie en principes de conception, l'article dérive :

• Experts à Granularité Fine : Diviser les experts en granularités plus fines (augmentant $N$ tout en diminuant $H$) produit des gains super-linéaires en capacité, à condition que la largeur de l'expert reste au-dessus d'une limite critique ($H \geq d_{eff}$) pour prévenir la Déficience de Rang Tropical.
• Experts Partagés comme Rectificateurs Affines : L'article identifie l'Effondrement Angulaire comme un mode de défaillance géométrique où des données non centrées provoquent la saturation du routeur, sélectionnant un sous-ensemble fixe d'experts. Il prouve que les Experts Partagés sont géométriquement nécessaires pour agir comme des "Rectificateurs Affines". En isolant le porteur affine global (biais moyen) du résidu routé, les experts partagés centrent la variété de données par rapport aux cônes projectifs du routeur, empêchant l'effondrement du routage et assurant que les frontières de décision intersectent les régions de données à forte variance.

Résultats

• Comparaison Iso-Compute : Sous une contrainte stricte de paramètres actifs égaux (FLOPs), un modèle MoE Top-4 (sélectionnant 4 experts parmi 16) atteint un multiplicateur de capacité de 1820$\times$ par rapport à une base dense, tandis qu'un MoE Top-1 n'atteint qu'une expansion linéaire de 16$\times$.
• Lois de Mise à l'Échelle : La borne supérieure de capacité présente une croissance polynomiale en $N$ de degré $(m-1)k$ sous transformation de granularité, où le gain combinatoire domine la pénalité logarithmique de largeur, à condition que la dimension intrinsèque $d_{eff}$ soit faible.
• Modes de Défaillance Géométriques : L'analyse quantifie comment des données non centrées conduisent à un angle solide vanishing sur la sphère unité, provoquant l'entrée du routeur dans un état de "Saturation Tropicale" où les décisions de routage deviennent localement constantes, rendant la capacité combinatoire inaccessible.

Importance

L'article prétend fournir le premier cadre théorique expliquant pourquoi le calcul conditionnel sparse dans les architectures MoE est expressivement efficace plutôt que limitant. En reformulant la sparsité comme une profondeur combinatoire via la géométrie tropicale, ce travail :

1. Résout la tension entre le routage sparse et la haute expressivité, montrant que le mécanisme de routage lui-même ajoute une couche de complexité topologique indépendante du nombre de paramètres.
2. Offre une justification géométrique rigoureuse pour les choix de conception dans les architectures de pointe (par exemple, DeepSeek-MoE, Mixtral), spécifiquement le passage vers des experts à granularité fine et l'inclusion d'experts partagés.
3. Établit que la "Résilience Combinatoire" des MoE leur permet de maintenir une haute expressivité sur des variétés de données de basse dimension là où les réseaux denses souffrent d'un effondrement de capacité.

Les auteurs positionnent ce travail non pas simplement comme une analyse descriptive, mais comme une nécessité algébrique pour comprendre le calcul conditionnel, fournissant une fondation pour l'optimisation architecturale future basée sur des principes géométriques plutôt que sur une efficacité heuristique.