Sparsity Saves Compute, Not Samples: Oracle Inequalities for Dense and Sparse Mixture of Experts

Sagar Ghosh; Huy Nguyen; Alessandro Rinaldo

cs.LGOct 10, 2026

Sparsity Saves Compute, Not Samples: Oracle Inequalities for Dense and Sparse Mixture of Experts

Authors: Sagar Ghosh, Huy Nguyen, Alessandro Rinaldo

Organizations: The University of Texas at Austin

Abstract

Mixture-of-Experts (MoE) models combine specialized experts through an input-dependent routing mechanism, and their sparse variants underpin many modern large-scale systems. Yet the statistical cost of adaptive routing remains only partially understood. We study the estimation error of least-squares MoE estimators when both the experts and the gating network are Lipschitz in their parameters. We represent each MoE as a gate--expert pair in a Gated Hilbert Space, whose norm $\|\cdot\|_Δ$ separates the contributions of routing and expert discrepancies. Using its empirical representation, we derive an oracle inequality with a fast rate of order $\tilde{\mathcal O}\big((Kd_{\mathrm{pr},e}+d_{\mathrm{pr},g})/n\big)$ for dense MoEs with $K$ experts. For sparse Top- $k$ and Top- $p$ routing, the selection map is discontinuous in the gating parameters. We handle this by partitioning the gating class according to the selection patterns it induces on the sample. The resulting bounds match the dense rate up to an additive routing cost governed by the Natarajan dimension of the selector. We show that such a routing-complexity condition cannot be dropped: Lipschitz continuity in the parameters alone does not suffice. For linear softmax gating, the routing cost is of the same order as the gating term. Finally, for linear experts, we establish a matching minimax lower bound of order $Kd_{\mathrm{pr},e}/n$ , showing that the rates are optimal up to logarithmic factors.

Figures & tables

Figure 1: Excess test MSE versus $n$ (log–log) for the General, Top $-k$ and Top- $p$ cases for $2$ $(d_{\textrm{in}},d_{\textrm{out}})$ combinations.

$d_{\mathrm{in}}$	$d_{\mathrm{out}}$
	$\qquad 8$	$\qquad 16$	$\qquad 32$
$4$	$0.020$ / $1.03$	$0.032$ / $1.05$	$0.073$ / $1.11$
$8$	$0.037$ / $1.06$	$0.052$ / $1.08$	$0.032$ / $1.05$
$16$	$0.043$ / $1.07$	$0.070$ / $1.11$	$0.108$ / $1.17$
$32$	$0.026$ / $1.04$	$0.062$ / $1.09$	$0.166$ / $1.12$

Table 1: Top-

p

MoE (

K=4

p=0.7

), final models (

n=8\times 10^{5}

), test set: Shannon entropy of the gate distribution / average number of active experts

\bar{k}_{x}

Figure 2: Average number of experts selected by Top- $p$ routing ( $K=4$ , $p=0.7$ ) on the test set versus training size, for $(d_{\mathrm{in}},d_{\mathrm{out}})=(4,8)\&(16,8)$ . Dotted: hard routing ( $k_{x}=1$ ); dashed: worst-case count $\lceil Kp\rceil=3$ used in the bound.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

$d_{\mathrm{in}}$	$d_{\mathrm{out}}$	$D$	$n_{\max}/D$	empirical slope	bound-shape slope
4	8	1988	402	$-1.03$	$-0.84$
4	16	3044	263	$-1.07$	$-0.83$
4	32	5156	155	$-1.42$	$-0.82$
8	8	2628	304	$-0.99$	$-0.84$
8	16	3684	217	$-0.90$	$-0.83$
8	32	5796	138	$-0.96$	$-0.81$

Appendix

Table 2: General MoE (

K=4

, dense routing): parameter count

D

, the ratio

n_{\max}/D

with

n_{\max}=8\times 10^{5}

, the fitted log-log slope of the excess test MSE, and the slope of the bound shape

B(n)

over the same range of

n

Figure 3: Excess test MSE versus $n$ (log-log) for the general (dense) MoE ( $K=4$ ) in all twelve configurations. Points: excess test MSE $\mathrm{MSE}(n)-\hat{a}$ ; solid: least-squares fit (slope in legend); dashed: bound shape $B(n)$ of Theorem 4.3 , rescaled to the first point; dotted: reference slope $-1$ .

$d_{\mathrm{in}}$	$d_{\mathrm{out}}$	$D$	$n_{\max}/D$	empirical slope	bound-shape slope
4	8	1988	402	$-0.88$	$-0.85$
4	16	3044	263	$-0.92$	$-0.84$
4	32	5156	155	$-1.09$	$-0.83$
8	8	2628	304	$-0.95$	$-0.84$
8	16	3684	217	$-0.81$	$-0.84$
8	32	5796	138	$-0.76$	$-0.83$

Appendix

Table 3: Top-

k

MoE (

K=4

k=2

): parameter count

D

, the ratio

n_{\max}/D

with

n_{\max}=8\times 10^{5}

, the fitted log–log slope of the excess test MSE, and the slope of the bound shape

B(n)

over the same range of

n

Figure 4: Excess test MSE versus $n$ (log–log) for the Top- $k$ MoE ( $K=4$ , $k=2$ ) in all twelve configurations $(d_{\mathrm{in}},d_{\mathrm{out}})\in\{4,8,16,32\}\times\{8,16,32\}$ . Points: excess test MSE $\mathrm{MSE}(n)-\hat{a}$ ; solid: least-squares fit (slope in legend); dashed: bound shape $B(n)$ of Theorem 4.6 , rescaled to the first point; dotted: reference slope $-1$ .

$d_{\mathrm{in}}$	$d_{\mathrm{out}}$	$D$	$n_{\max}/D$	empirical slope	bound-shape slope
4	8	1988	402	$-0.83$	$-0.83$
4	16	3044	263	$-0.97$	$-0.82$
4	32	5156	155	$-1.10$	$-0.81$
8	8	2628	304	$-0.79$	$-0.82$
8	16	3684	217	$-0.74$	$-0.81$
8	32	5796	138	$-0.76$	$-0.81$

Appendix

Table 4: Top-

p

MoE (

K=4

p=0.7

\kappa=3

d_{h}=32

): parameter count

D

, the ratio

n_{\max}/D

with

n_{\max}=8\times 10^{5}

, the fitted log–log slope of the excess test MSE, and the slope of the bound shape

B_{p}(n)

over the same range of

n

Figure 5: Excess test MSE versus $n$ (log–log) for the Top- $p$ MoE ( $K=4$ , $p=0.7$ ) in all twelve configurations $(d_{\mathrm{in}},d_{\mathrm{out}})\in\{4,8,16,32\}\times\{8,16,32\}$ . Points: excess test MSE $\mathrm{MSE}(n)-\hat{a}$ ; solid: least-squares fit (slope in legend); dashed: bound shape $B_{p}(n)$ of Theorem 4.8 , rescaled to the first point; dotted: reference slope $-1$ .

Figure 6: Average number of experts $\bar{k}_{x}$ selected by Top- $p$ routing ( $K=4$ , $p=0.7$ ) on the test set versus training size $n$ , for all twelve configurations $(d_{\mathrm{in}},d_{\mathrm{out}})\in\{4,8,16,32\}\times\{8,16,32\}$ . Dotted: hard routing ( $k_{x}=1$ ); dashed: worst-case count $\lceil Kp\rceil=3$ used in the bound.

Sparse Mixture-of-Experts

Sparse mixture-of-experts models route each input to a small subset of specialized networks to increase capacity while limiting computation.

See all 117 papers

Towards a Statistical Understanding of Mixture-of-Experts
Sep 3, 2026Siyuan He, Bokai Yang, Jie Hu +2Mixture of Experts Sparse Mixture-of-Experts
Qiuzhen College, Tsinghua University, Beijing, China. · KLATASDS-MOE, School of Statistics, East China Normal University, Shanghai, China. · Yau Mathematical Sciences Center, Tsinghua University, Beijing, China. +1
Expert Routing for Communication-Efficient MoE via Finite Expert Banks
May 6, 2026Mohammad Reza Deylam Salehi, Ali KhalesiMixture of Experts Information-Theoretic Generalization Bounds
IEEE Graduate Member · Nice, France · Institut Polytechnique des Sciences Avancées (IPSA) +1
Grassmannian Mixture-of-Experts: Concentration-Controlled Routing on Subspace Manifolds
Feb 19, 2026Ibne Farabi Shihab, Sanjeda Akter, Anuj SharmaExpert Routing Mixture-of-Experts Language Models
Department of Computer Science, Iowa State University · Department of Civil, Construction and Environmental Engineering, Iowa State University

Sep 3, 2026J/K move · Enter open · S save

Towards a Statistical Understanding of Mixture-of-Experts

Siyuan He, Bokai Yang, Jie Hu, Ziwen Gao+1

Qiuzhen College, Tsinghua University, Beijing, China. · KLATASDS-MOE, School of Statistics, East China Normal University, Shanghai, China. · Yau Mathematical Sciences Center, Tsinghua University, Beijing, China.+1

Mixture of Experts Sparse Mixture-of-Experts Mixture-of-Experts Models Statistical Learning Theory

Open paper AskPDF arXiv

Mixture-of-experts (MoE) architectures increase model capacity by combining a collection of expert predictors through input-dependent routing, while often activating only a small subset of experts for each input. Despite their growing importance in modern large-scale models, the statistical roles of their design choices, especially routing, sparse activation, and shared experts, remain only partially understood, as existing theory has largely focused on parametric or correctly specified MoE models. In this paper, we view MoE as a form of localized aggregation and show how this localization reshapes the approximation-estimation-computation tradeoff. We derive oracle risk bounds for learning dense and sparse routing with evolving experts, separating approximation, expert-learning, and router-estimation errors, and characterize how sparse Top-K routing can retain the benefits of localized aggregation while controlling per-input computation. We also interpret gating through the geometry of input space, relating routing performance to regions of local expert advantage, and show how shared experts, as adopted in architectures such as DeepSeekMoE, can extract common predictive structure so that routed experts focus on residual local variation. Together, these results provide a unified statistical framework for understanding MoE through input-dependent expert aggregation, in which expert specialization and computational tradeoffs are governed by local predictive structure.

Abstract

Sparse Mixture-of-Experts

Explore similar work

Towards a Statistical Understanding of Mixture-of-Experts

Expert Routing for Communication-Efficient MoE via Finite Expert Banks

Grassmannian Mixture-of-Experts: Concentration-Controlled Routing on Subspace Manifolds