{"id":"b300ba32-efc1-4600-bce6-3361542ba752","arxiv_id":"2505.06839","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For MoE layers with equal active parameters, increasing the number of active experts from k' to k yields an exponential separation in L2 approximation error whenever the binomial coefficient binom(m,k) dominates binom(m',k').","lead":"This paper proves that Mixture-of-Experts models activating many small experts per token are exponentially more expressive than models activating few large experts, at equal active parameter counts. The proof covers constant, linear, and ReLU expert networks and is backed by small-scale training experiments.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.5 (Appendix B.10) is not proven as written: it uses a rank-κ decomposition of the conditional covariance that fails even for full-space U; the linear-activation separation in Theorem 3.4 is therefore unsupported until a correct proof is supplied.","rationale":"The reader's weakest-assumption pick, Lemma 3.2, is the foundation of the routing construction, and I find that lemma largely plausible after checking the second-moment calculation; the apparent sign errors in Appendix A.2 look repairable. The clearest load-bearing defect is in Lemma 3.5/B.10, which the reader noted as an appendix gap but did not make the central concern. The proof of B.10 contains a matrix decomposition that is simply false in general, and because B.10 is the step that converts the expert construction's Frobenius separation into an L2 approximation lower bound for the linear-activation theorem, Theorem 3.4 is not proven as written. This does not necessarily falsify the paper's main conclusion—the lemma statement looks true and a rearrangement argument should repair it—but the paper currently lacks that argument. Therefore the verdict should remain CONDITIONAL: accept only after the B.10 proof is corrected, since the central expressivity claim for linear activations currently rests on an invalid line. The constant-activation theorem and the high-level narrative are not threatened by this particular gap, but a careful reader cannot certify Theorem 3.4 from the text as it stands.","tokens_in":30286,"tokens_out":42770,"duration_ms":438656,"concrete_test":"Independently re-derive Lemma 3.5: for C = (A1−A2)^T(A1−A2) and any Σ_U satisfying λ_{d−κ+1}(Σ_U) ≥ c/d, prove tr(CΣ_U) ≥ (c/d)∑_{i>κ} σ_i^2(A1−A2) using only the Ky Fan rearrangement inequalities. If this derivation succeeds, patch Section B.3 by replacing the rank-κ decomposition with it. If it fails, search for a counterexample: take U with μ(U)=1/2, κ just above C(1+log(1/μ(U))), and A1−A2 with σ_1^2=⋯=σ_κ^2=0 and σ_{κ+1}^2=⋯=1, and verify numerically whether the stated inequality holds. Either outcome settles whether Theorem 3.4 needs a substantive new idea or only a proof repair.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"All three separation theorems go through the LP/matching framework, and for linear activations the key separation input is Lemma 3.5/B.10: for large-measure U, E_{μ|U}||A1x−A2x||^2 ≥ (c/d)·min_{rank B≤κ}||A1−A2−B||_F^2. The proof uses Lemma B.5 to assert that Σ_U = (c/d)I + V with rank(V)≤κ and ||V||≤c/d. This decomposition is false whenever Σ_U has more than κ eigenvalues above c/d—for instance, U of full measure in the Gaussian case gives Σ_U = I/d, so I/d − (c/d)I has rank d. The subsequent Von Neumann bound −⟨(A1−A2)^T(A1−A2), V⟩ ≥ −(c/d)∑_{i=1}^κ σ_i^2 is therefore not justified by the stated decomposition. A correct proof could likely be obtained by a rearrangement/Ky Fan argument after separating the positive part of Σ_U − (c/d)I, but that argument is absent. Since Lemma 3.5 is the mechanism that gives expert separation in the linear case, Theorem 3.4 is unproven as written. The ReLU proof uses the related Lemma B.5 and Lemma C.2 rather than B.10, and the constant-activation case is unaffected; this is a proof gap rather than a demonstrated false conclusion.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the expressivity of linearly-routed Mixture-of-Experts (MoE) layers as a function of granularity k (the number of active experts), comparing architectures with equal active parameter counts. It states three separation theorems for constant, linear, and ReLU activations: under dimension/width conditions and the combinatorial dominance of binom(m,k) over binom(m',k'), a randomly constructed (m,k)-MoE cannot be approximated in L2 by any (m',k')-MoE with substantially fewer expert configurations. The proof strategy combines a randomized routing construction (balanced top-k regions via a second-moment argument), random expert constructions satisfying boundedness and separation properties, and LP/hypergraph matching lower bounds that abstract away the adversary's routing. Section 4 reports experiments where student MoEs trained to fit teacher MoEs succeed only when their granularity matches or exceeds that of the teacher.","tokens_in":30605,"tokens_out":21830,"duration_ms":208432,"significance":"The central claim—that fine-grained experts provide an exponential expressivity advantage at equal active parameter count—is interesting, plausible, and directly relevant to current MoE architecture debates. The paper contributes a reusable technical framework: a routing lemma with a second-moment analysis, random packing constructions of expert functions, and a linear-programming/matching lower-bound technique that targets the number of routing regions rather than the details of the competitor's routing. The paper is also candid about its limitations, explicitly flagging the kw <= 0.99d regime and the non-explicit constants in the DeepSeek heuristic. If all three separation theorems are fully established, this would be a notable theoretical result. However, two load-bearing proof gaps, detailed in the major comments, mean that the linear and ReLU separations are not yet proven as written; the constant-activation separation and the routing construction appear sound. The experimental section is supportive but does not by itself compensate for the proof gaps.","major_comments":[{"comment":"The proof of Lemma B.10 asserts, after invoking Lemma B.5, that Sigma_U = (c/d)I + V with rank(V) <= kappa and ||V|| <= c/d. Lemma B.5 only lower-bounds the d-kappa+1 largest eigenvalues of Sigma_U and does not imply a rank-kappa decomposition of the deviation from (c/d)I. For a full-measure set U in the Gaussian case, Sigma_U = I/d, so the required V = (1-c/d)I has rank d, which contradicts rank(V) <= kappa for kappa < d. Consequently, the subsequent Von Neumann trace bound, which relies on rank(V) <= kappa, is not justified. Since Lemma 3.5 is the mechanism that gives expert separation in the linear case, Theorem 3.4 is not proven as written. The gap appears repairable by splitting V into its negative part (rank at most kappa, norm at most c/d, handled by Von Neumann) and its positive part (handled by positivity of the trace), but this argument must be supplied.","section":"Appendix B.3, Lemma B.10 (Lemma 3.5)"},{"comment":"The greedy construction in Claim C.10 does not account for previously used vertices, and its final arithmetic is incorrect. With R = 10^6, the displayed inequality 'TR >= 0.0001Rk = 1000k' uses 0.0001 x 10^6 = 100, not 1000, so the greedy argument only guarantees TR >= 100k, not the required 750k. Even after correcting R to 10^7, the step 'by the pigeonhole principle there is j_{s+1}' requires the number of unused vertices to exceed the instantaneous bad-set size, i.e. l - s > binom(750k,k)binom(m, floor(0.0001k)) for each s; this is not implied by the stated assumption l > binom(750k,k)binom(m, floor(0.0001k)). Since Lemma C.9's maximal fractional matching bound, and hence Theorem 3.6, depends on Claim C.10, the ReLU separation is not proven as written. The gap can likely be fixed by taking R to be a sufficiently large universal constant and adding R to the non-saturation threshold, which is dominated by binom(m,k) in the intended regime, but the correction should be made explicit.","section":"Appendix C.3, Claim C.10"}],"minor_comments":[{"comment":"The informal Theorem 1.1 and the abstract frame the result as a comparison at equal active parameter counts, but the formal statements of Theorems 3.1 and 3.4 do not impose k'w' = kw (only Theorem 3.6 does). Please clarify whether the formal results are intentionally stronger (they appear to hold for all (m',k',w',d')) or whether the equal-parameter condition is missing.","section":"Section 3, Theorems 3.1 and 3.4"},{"comment":"The final probability bound contains the expression '1/m - Omega(sqrt(C))k + exp(-C'd)', which as written can be negative; this is presumably a typo for a sum of positive failure probabilities and should be corrected.","section":"Appendix A.1, proof of Lemma A.5"},{"comment":"The caption says 'test loss of a teacher MoE trained to learn a student MoE', while the text says students are trained to learn teacher models; the roles should be made consistent.","section":"Section 4, Figure 2 caption"},{"comment":"The statement of (C.5) uses sigma_i^2((sum_{l in S_j} M_l) Pi^T) where Pi is a projection; the proof and Lemma C.3 require the complementary projection Pi^perp. Please correct the projection notation so that the statement matches the proof.","section":"Appendix C.2, Lemma C.6"},{"comment":"The assumptions list 'm >= Ck' and later 'm >= C'k' redundantly; since C and C' are used elsewhere as different universal constants, this duplication can confuse. Please consolidate the lower bound on m.","section":"Appendix C, Theorem C.1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript contains two localized but load-bearing proof gaps in the linear and ReLU separation theorems. Both appear repairable without changing the paper's scope: the Lemma B.10 issue can be fixed by a positive-part/negative-part split of the conditional covariance, and the Claim C.10 issue can be fixed by adjusting the universal constant R and the non-saturation threshold. I would not recommend rejection; the routing construction and the constant-activation theorem appear sound, and the experimental section is honest and reproducible. I recommend asking the authors to supply the corrected arguments in a revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear [Colleague],\n\nQuick take: this is a serious theory paper that gives the first careful expressivity separation based on MoE granularity, but the linear-activation theorem is not proven as written. The constant-activation case looks solid, and the overall technique — random routing vectors with balanced regions, random packing of experts, LP/hypergraph matching — is genuinely worth knowing.\n\nThe counting intuition binom(m,k) is the core, and they turn it into a real theorem for constant activations: random Gaussian routing vectors give roughly balanced regions, random constant experts give separated sums, and the LP argument converts that into an inapproximability bound. That part holds up and is the cleanest contribution.\n\nThe trouble is Lemma 3.5 (Appendix B.10), which is load-bearing for the linear case. The proof uses a decomposition Σ_U = (c/d)I + V with rank(V) ≤ κ and ||V|| ≤ c/d. That is false: for U of full measure, Σ_U = I/d, so the difference has rank d. The subsequent Von Neumann trace bound is therefore unjustified. The stress-test note suggests a correct proof might be recoverable via a rearrangement/Ky Fan argument, but as written, Theorem 3.4 is unsupported. This is a genuine gap, not a manufactured one. The ReLU proof uses different lemmas (B.5 and C.2) and may escape the specific issue, but it inherits similar machinery, so it needs a careful check too. I also had trouble verifying Claim C.10's arithmetic in the hypergraph matching step; it is probably repairable, but the writing is too terse for me to confirm.\n\nThe experiments are a nice sanity check but limited: small d, and they confirm the intuitive direction (matching granularity matters) without testing the asymptotic separation regime. The citation pattern is fine.\n\nWho is this for? Researchers working on MoE architecture theory, or anyone who wants to understand whether fine-grained experts give provable expressivity gains. It deserves a serious referee, but the referee should insist on a corrected Lemma 3.5 and a cleaner proof of the ReLU step. I would send it to peer review, with the expectation of a revised version. The constant-activation theorem can be accepted as is; the rest needs work.\n\nBest,\n[You]","headline":"The constant-activation separation for MoE granularity is solid and interesting, but the linear-activation theorem rests on a false covariance decomposition and needs a corrected proof before it can be trusted.","tokens_in":31099,"tokens_out":3010,"would_cite":true,"duration_ms":29830,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"Increasing the granularity of a mixture-of-experts layer — the number of experts active on each input — exponentially increases what the layer can represent, even when the number of active parameters is held fixed.","keywords":["mixture of experts","granularity","expressivity","top-k routing","active parameters","random routing construction","L2 approximation lower bounds","fine-grained MoE scaling laws"],"falsifier":"Compute, by Monte Carlo or exact integration, the second moment $\\mathbb{E}[\\mu(U_S)^2]$ for i.i.d. Gaussian routing vectors $r_1,\\dots,r_m$ with $d = C k (\\log m)^2$; Lemma A.7's proof requires it to be at most $3/\\binom{m}{k}^2$ for standard Gaussian $\\mu$. If the observed value exceeds that, the routing construction that all three separation theorems depend on is false. Alternatively, train an $(m',k')$-MoE with $\\binom{m'}{k'}$ just below $c\\binom{m}{k}^{0.99}$ against the hard teacher $f$ and check whether the $L^2$ error falls below the theorem's constant; the theorem predicts it cannot.","tokens_in":30081,"feed_emoji":"🧠","tokens_out":11038,"duration_ms":94541,"temperature":0.7,"pith_summary":"The paper establishes a theoretical advantage for fine-grained mixture-of-experts (MoE) layers: when two MoEs have the same number of active parameters, the one that activates more experts per token can represent functions that the coarser one cannot approximate, and the gap is exponential in the granularity. Concretely, if $\\binom{m'}{k'} < c \\binom{m}{k}^{0.99}$ with $m \\ge C k$, there is an $(m,k)$-MoE $f$ such that every $(m',k')$-MoE $f'$ with equal active parameters satisfies $\\mathbb{E}\\|f-f'\\|^2 > c\\,\\mathbb{E}\\|f\\|^2$. The proof works for constant, linear, and ReLU activations and for Gaussian or uniform-on-ball input distributions, so the phenomenon is not tied to one nonlinearity. A sympathetic reader would care because this gives the first theoretical rationale for the design split seen in frontier models, where DeepSeek-V3 uses eight active experts per token and Llama-4 uses one.","feed_headline":"Fine-grained experts win exponentially at equal parameter cost","feed_subtitle":"A proof shows that more active experts per token expand what the layer can represent, at zero extra active-parameter cost.","key_machinery":"The load-bearing object is the randomized routing construction (Lemma 3.2): Gaussian routing vectors in dimension $d \\ge C k (\\log m)^2$ partition a rotationally invariant input distribution into at least $(1/9)\\binom{m}{k}$ regions $U_S$, each with probability at least $1/(2\\binom{m}{k})$, proved by a first- and second-moment argument on the random vectors. On top of this partition, the paper places separated local functions: random expert vectors for the constant case, random low-rank matrices for the linear case, and random sparse matrices for the ReLU case, all engineered so that different active-expert sums are far apart. The final inapproximability argument is a linear program (or hypergraph matching, for ReLU) that shows any approximating MoE with too few regions must leave a constant fraction of the input mass badly approximated; a key supporting lemma states that high-probability subsets of a Gaussian or uniform-ball distribution have high-rank conditional covariance.","core_discovery":"On the paper's own terms, the central discovery is the identification of the configuration count $\\binom{m}{k}$ — the number of possible sets of $k$ active experts among $m$ — as the quantity that controls MoE expressivity. The Informal Theorem 1.1 states that if $m \\ge C k$ and $\\binom{m'}{k'} < c \\binom{m}{k}^{0.99}$, then a carefully constructed $(m,k)$-MoE cannot be approximated by any $(m',k')$-MoE with the same number of active parameters, in the sense that the $L^2$ error is at least a constant times the energy of the target function. Because $\\binom{m}{k}$ grows like $\\Theta(m^k)$ when $k$ is fixed, this yields an exponential separation in granularity. The same style of separation is proven for constant, linear, and ReLU activations (Theorems 3.1, 3.4, and 3.6), with the technical condition $w \\gtrsim \\log m$ on expert width for the nontrivial activations.","pith_inferences":["The configuration count $\\binom{m}{k}$ looks like the right general currency for conditional computation: any architecture that reuses parameters across more input regions should inherit a similar exponential expressivity advantage, so analogous separations may hold for learned routing, softmax routing, or branchy layers.","The theorem's 0.99 exponent is slack; a natural sharpening would replace it by the full condition $\\binom{m'}{k'} \\le c \\binom{m}{k}$, or even a polynomial gap, and the paper's techniques seem pointed in that direction.","The high-rank conditional-covariance lemma is a transferable tool: any low-dimensional function class approximating a target over many large-volume cells of a high-dimensional isotropic distribution should suffer the same separation, which could give lower bounds for other sparse or structured models.","A direct empirical test outside the paper's setup: in real language-model pretraining, the loss gap between a granularity-$k$ and granularity-1 model at fixed active parameters should persist as total parameters grow, not close with scale."],"forward_implications":["A coarse MoE cannot be rescued simply by scaling total parameters: with the same active parameter count, the fine-grained model expresses functions the coarse model misses by a constant relative $L^2$ error.","For fixed granularity $k$, the separation grows exponentially in $k$, so the benefit of moving from 1 to 8 active experts, as in Llama-4 versus DeepSeek-V3, is much larger than a constant-factor gain.","The heuristic bound for DeepSeek-V3's configuration count, $\\binom{256}{8} \\ge 4\\times 10^{14}$, suggests a granularity-1 MoE would need on the order of $10^{14}$ experts to match it at equal active parameters.","Experiments on random teacher-student MoEs show that a student must match the teacher's granularity to learn it; a lower-granularity student fails even with 16 times more total parameters.","The proven advantage is for expressivity and ignores routing or communication costs, so the practical recommendation to increase granularity is conditional on hardware and routing schemes that keep those costs low."],"supporting_citations":[{"why":"supplies the chi-squared tail bounds (Proposition A.2) used to control both the random routing regions and the random expert constructions.","marker":"[LM00]"},{"why":"supplies the random-matrix operator-norm bound used in the construction of well-separated linear experts.","marker":"[Ver18]"},{"why":"supplies the Hanson-Wright inequality used to concentrate the Frobenius norm of products of random expert matrices.","marker":"[RV13]"},{"why":"supplies the Eckart-Young-Mirsky theorem used to turn rank-constrained approximation into tail singular-value sums.","marker":"[Hog06]"},{"why":"supplies the von Neumann trace inequality used in Lemma 3.5 to lower-bound approximation error over large-volume sets.","marker":"[VN37]"}],"fun_headline_variants":["Granularity yields exponential MoE expressivity boost","More active experts per token, exponentially more power","Fine-grained MoE: exponential expressivity at same cost","MoE expressivity scales exponentially with granularity","Active expert count drives exponential MoE gains"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The separation relies on Lemma 3.2's claim that random Gaussian routing vectors in dimension $d \\ge C k (\\log m)^2$ split any rotationally invariant input distribution into at least one ninth of all $\\binom{m}{k}$ possible active-expert regions, each carrying at least $1/(2\\binom{m}{k})$ of the probability; if that randomized construction fails, the linear-programming lower bounds in Theorems 3.1, 3.4, and 3.6 collapse.","fun_headline_variants_meta":{"raw":{"variants":["Granularity yields exponential MoE expressivity boost","More active experts per token, exponentially more power","Fine-grained MoE: exponential expressivity at same cost","MoE expressivity scales exponentially with granularity","Active expert count drives exponential MoE gains"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000577,"raw_usage":{"total_tokens":2685,"prompt_tokens":871,"completion_tokens":1814,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":487,"completion_tokens_details":{"reasoning_tokens":1741}},"tokens_in":487,"tokens_out":1814,"duration_ms":13121,"temperature":1.0,"reasoning_tokens":1741,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:33:21.663891+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute, by Monte Carlo or exact integration, the second moment $\\mathbb{E}[\\mu(U_S)^2]$ for i.i.d. Gaussian routing vectors $r_1,\\dots,r_m$ with $d = C k (\\log m)^2$; Lemma A.7's proof requires it to be at most $3/\\binom{m}{k}^2$ for standard Gaussian $\\mu$. If the observed value exceeds that, the routing construction that all three separation theorems depend on is false. Alternatively, train an $(m',k')$-MoE with $\\binom{m'}{k'}$ just below $c\\binom{m}{k}^{0.99}$ against the hard teacher $f$ and check whether the $L^2$ error falls below the theorem's constant; the theorem predicts it cannot.","supporting_citations":[],"review_version":1}