PaperlayerView exact revision on arXiv

Source-linked AI summary

Redundancy Meets Synergy: Dependency-aware Expert Selection for MoE via Submodular Optimization

Zheng Lin, Shaoke Fang, Yuxin Zhang, Jinfeng Xu, Zihan Fang, Zhe Chen, Wei Ni, Jun Luo, Symeon Chatzinotas

arXiv:2610.00558v1cs.LGcs.DC

TL;DR

Existing expert-selection heuristics score experts independently, overlooking inter-expert dependencies. DS-MoE uses second-order Hessian information in a difference-of-submodular objective; the paper reports consistent outperformance over state-of-the-art baselines and a superior accuracy-efficiency trade-off.

  • Problem

    Existing expert-selection heuristics evaluate experts in isolation, overlooking inter-expert dependencies such as redundancy and synergy.

    Source: §1 · pp. 1–2

  • Method

    DS-MoE uses a second-order Taylor expansion and a difference-of-submodular objective to balance redundancy penalties with synergy gains when selecting experts.

    Source: §1 · p. 2

  • Results

    DS-MoE consistently outperforms state-of-the-art baselines and achieves a superior accuracy-efficiency trade-off, as reported by the paper.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The selection objective should optimize inter-expert synergy while mitigating redundancy without succumbing to combinatorial explosion.

    Source: §1 · p. 2

    The current analysis models combinatorial dependencies only within layers; cross-layer expert dynamics remain a direction for future work.

    Source: E LIMITATIONS AND FUTURE WORK · p. 26

Abstract

from arXiv · show

While Mixture-of-Experts (MoE) models effectively scale model capacity through sparse activation, their deployment is often bottlenecked by prohibitive memory requirements. Extracting a compact subset of experts presents a promising solution. However, existing expert selection heuristics predominantly rely on Top-k ranking, which isolates the evaluation of individual experts and ignores the intricate inter-expert dependencies introduced by the MoE gating network. In this paper, we propose DS-MoE, a theoretically grounded framework that redefines expert selection via difference-of-submodular (DS) optimization. By analyzing the second-order Taylor expansion of the loss degradation, we reveal functional duality within expert combinations: redundancy (where experts encode overlapping representations) and synergy (where experts provide complementary error cancellation). To navigate this duality, we mathematically decouple redundancy reduction from synergy maximization by formulating the selection objective as a DS function. Furthermore, we devise a tailored majorization-minimization (MM) algorithm with provable monotonicity guarantees to efficiently identify the optimal expert subset. Extensive experiments demonstrate that DS-MoE effectively preserves indispensable expert combinations, achieving superior performance compared to the state-of-the-art baselines.

1 INTRODUCTION

MoE scales model capacity through sparse activation, but existing expert-selection heuristics assess experts independently and miss dependencies between them. DS-MoE frames selection as difference-of-submodular optimization to balance redundancy and synergy, and the paper reports consistent outperformance over state-of-the-art baselines.

1 INTRODUCTION

  • MoE uses a gating mechanism to route each input token to a sparse subset of experts, decoupling model capacity from computational cost and supporting trillion-parameter scale.The paper situates this shift within the pursuit of scaling laws in large language models.Source: §1 · p. 1
  • Prior selection heuristics evaluate experts in isolation, overlooking redundancy between overlapping representations and synergy from combinations that provide complementary error cancellation.This can cause redundant experts to monopolize capacity and individually negligible but indispensable synergistic experts to be discarded.Source: §1 · pp. 1–2
  • DS-MoE casts expert selection as difference-of-submodular optimization, separating redundancy reduction from synergy maximization and using a tailored MM algorithm with guaranteed monotonic convergence.The paper reports that experiments show consistent outperformance over state-of-the-art baselines and a superior accuracy-efficiency trade-off.Source: §1 · p. 2

2 METHODOLOGY

The methodology defines expert selection as a cardinality-constrained loss-degradation problem, then uses Hessian interactions to model dependencies and separate synergy gains from redundancy costs. A majorization-minimization procedure optimizes a modular surrogate at each update.

2.1 PRELIMINARIES & PROBLEM FORMULATION

  • Top-k routing scores experts independently, while DS-MoE selects a binary expert vector minimizing expected loss degradation relative to the fully active model under a cardinality constraint.The discrete search is NP-hard, motivating an analytical proxy based on a second-order Taylor expansion.Source: §2.1 · p. 3

2.2 HESSIAN-AWARE INTERDEPENDENCE EXTRACTION

  • At convergence, first-order gradients can vanish and miss removal penalties; the Hessian captures curvature, while Gauss-Newton estimates it using first-order Jacobian information.The illustrative landscape assigns removal penalties of 100 for expert 1 and 1 for expert 2; co-activation and signed output-gradient projections distinguish redundancy from synergy.Source: §2.2 · pp. 4–5

2.3 DIFFERENCE-OF-SUBMODULAR DECOMPOSITION

  • Because the Hessian mixes redundancy and synergy, the objective separates positive utility from synergy into a gain function and overlapping-functionality penalties into a cost function, forming a DS objective.The paper characterizes the gain and cost functions as monotonically non-decreasing and strictly supermodular.Source: §2.3 · p. 5

2.4 MAJORIZATION-MINIMIZATION OPTIMIZATION.

  • MM constructs a tight lower-bound surrogate for the objective by bounding its gain and cost components, then reduces each update to cardinality-constrained linear maximization.The surrogate is optimized at the current selection vector to produce the next expert-selection vector.Source: §2.4 · pp. 5–6

Appendix C.5):

The procedure ranks experts by a score balancing synergy gain against redundancy penalty, and its objective is guaranteed not to decrease across iterations. The accompanying table covers test accuracy and convergence rounds across three MoE architectures.

Appendix C.5):

  • Each expert's importance score trades off synergy gain against redundancy penalty, and selecting the highest-scoring k experts turns the update into Top-k sorting.This linear update replaces the intractable combinatorial optimization step.Source: Appendix C.5 · p. 6
  • The MM algorithm's objective is monotonically non-decreasing at every iteration and converges in a finite number of iterations over the finite feasible region.The stated guarantee is U(m(t+1)) ≥ U(m(t)) for all t ≥ 0.Source: Appendix C.5 · p. 6
  • Table 1 reports test accuracy and convergence rounds for DS-MoE and four baselines on Switch-Base-32, Switch-Base-64, and DeepSeek-MoE-16B.The caption marks test accuracy as higher-is-better and convergence rounds as lower-is-better.Source: Table 1 · p. 7

3 EXPERIMENTS

The experiments evaluate DS-MoE across three MoE architectures and language tasks, then test its robustness, scalability, and component choices. Results favor DS-MoE over the reported baselines, while the ablations support using second-order interactions, both DS components, and the MM optimizer.

3.1 EXPERIMENTAL SETUP

  • Experiments cover AGNews, PIQA, HellaSwag, and MMLU on Switch-Base-32, Switch-Base-64, and DeepSeek-MoE-16B, comparing four selection baselines.The baselines are SEER-MoE, DiEP, standard MoE, and random MoE.Source: §3.1 · p. 7

3.2 MAIN RESULTS

  • DS-MoE outperforms the reported baselines on AGNews, PIQA, HellaSwag, and MMLU.AGNews accuracies exceed 94% across the three architectures; on Switch-Base-32, PIQA and HellaSwag accuracies are 78.6% and 75.6%, respectively. MMLU accuracies are 51.8%, 52.4%, and 45.1% across the three architectures, with convergence in 11, 10, and 14 rounds.Source: §3.2 · pp. 7–8

3.3 MICRO-BENCHMARKING

  • At k = 1, DS-MoE reaches 73.3% average accuracy, versus 68.3%, 69.8%, and 70.5% for S-MoE, SEER-MoE, and DiEP; at k = 3, it reaches 74.9%.At k = 3, average convergence time is 18.3 rounds, compared with 27.8 for DiEP, 30.8 for SEER-MoE, and 32.5 for S-MoE.Source: §3.3 · p. 8
  • At N = 64, DS-MoE averages 74.6% accuracy and converges in 21.0 rounds, versus 30.3 rounds for DiEP and 32.3 for SEER-MoE.The reported average accuracy rises from 73.6% to 74.6% as the expert pool expands from N = 32 to 64 at k = 2.Source: §3.3 · p. 8

3.4 ABLATION STUDY

  • Ablations favor the second-order Hessian over first-order proxies, the combined DS decomposition over either component alone, and MM over greedy search.The MM comparison reports superior accuracy and fewer training rounds; the passage attributes these empirical gains to the framework's monotonic convergence guarantees.Source: Figure 3 · p. 9, §3.4 · p. 9

4 CONCLUSION

  • The conclusion presents Hessian-based dependency quantification, DS optimization, and a tailored MM algorithm with a convergence guarantee as DS-MoE's core components.It points to Appendix E for limitations and future directions and Appendix F for practical impact.Source: §4 · p. 9

B RELATED WORK AND RESEARCH GAP

  • Related work covers token-level and expert-level routing methods alongside structural refinements to MoE execution.Examples include FastMoE, MegaBlocks, ST-MoE, SEER-MoE, and DeepSeek-MoE.Source: B RELATED WORK AND RESEARCH GAP · p. 14

C.1 DERIVATION OF THE RETAINED UTILITY FUNCTION

The derivation turns the Taylor loss-degradation approximation into a retained-utility maximization. It expands the objective and removes a decision-independent constant without changing the optimizer.

C.1 DERIVATION OF THE RETAINED UTILITY FUNCTION

  • The derivation treats minimizing expected loss degradation as maximizing retained utility, then expands the vector-matrix expression into scalar sums.The retained utility is U(m) = −∆L(m).Source: §C.1 · pp. 14–16
  • Expanding the quadratic product separates quadratic, linear, and constant terms; Hessian symmetry lets the row and column sums consolidate the linear terms.The derivation then factors out each binary variable to separate terms dependent on m from data-independent constants.Source: §C.1 · p. 15
  • Because C is independent of the decision vector m, discarding it leaves the maximizing m unchanged; each expert's utility includes standalone and pairwise coupling effects.The individual utility d_i is defined to encapsulate those contributions.Source: §C.1 · p. 16

C.2 PROOF OF NP-HARDNESS FOR CARDINALITY-CONSTRAINED QBO

The proof reduces Maximum k-Clique to cardinality-constrained QBO by mapping graph vertices to candidate experts and showing that attaining the utility bound is equivalent to a k-clique.

C.2 PROOF OF NP-HARDNESS FOR CARDINALITY-CONSTRAINED QBO

  • The construction maps each graph vertex to a candidate expert and uses the cardinality constraint k to select the corresponding induced subgraph.A binary selection variable indicates whether its associated vertex is included.Source: §C.2 · p. 16
  • The constructed utility reduces to counting edges among selected vertices, with the maximum attained exactly when they form a k-clique.The objective exhausts the cardinality budget, and its upper bound is saturated if and only if the selected induced subgraph is complete.Source: §C.2 · p. 17
  • The cardinality-constrained QBO problem is NP-hard because solving it exactly is equivalent to deciding whether a graph contains a k-clique.The proof uses a polynomial-time reduction from Maximum k-Clique.Source: §C.2 · pp. 16–17

C.3 PROOF OF SUPERMODULARITY FOR DECOMPOSED FUNCTIONS

The appendix establishes supermodularity of the decomposed gain and cost functions, derives an upper bound for the cost, and turns MM updates into a cardinality-constrained linear maximization.

C.3 PROOF OF SUPERMODULARITY FOR DECOMPOSED FUNCTIONS

  • Both decomposed functions are shown to be monotonically non-decreasing and supermodular, establishing the properties used in the DS optimization analysis.For the cost function, adding an expert to a larger selected set incurs a greater or equal redundancy penalty.Source: §C.3 · pp. 17–18
  • The gain function is strictly supermodular: its standalone expert capability cancels when comparing marginal gains, leaving cross-synergy terms.The proof isolates those terms after subtracting marginal gains for nested selection sets.Source: §C.3 · p. 19

C.4 DERIVATION OF THE COST FUNCTION UPPER BOUND

  • The binary identity m_i m_j = 1/2(m_i + m_j) − 1/2(m_i − m_j)^2 separates the cost into a linear component and a concave residual.A first-order Taylor expansion of the concave residual gives a tight upper bound.Source: §C.4 · pp. 19–20

C.5 PROOF OF CARDINALITY-CONSTRAINED LINEAR MAXIMIZATION PROBLEM

  • The MM surrogate subtracts an upper bound on cost from a lower bound on gain, producing a tractable objective under the expert-capacity constraint.The bounds are formed around the current selection state.Source: §C.5 · pp. 20–21
  • Each expert's importance score trades off marginal synergy gain against context-aware redundancy penalty; selecting the top-k scores solves the surrogate maximization.The surrogate reduces to an affine form whose maximization is equivalent to a Top-k sorting operation.Source: §C.5 · p. 22

C.6 PROOF OF CONVERGENCE FOR THE MM ALGORITHM

The MM proof shows that the retained utility is monotonically non-decreasing, while the complete algorithm repeatedly updates expert scores and stops when its selection stabilizes.

C.6 PROOF OF CONVERGENCE FOR THE MM ALGORITHM

  • The MM updates guarantee a monotonically non-decreasing sequence of retained utility values.The surrogate lower-bounds the objective and is tight at the current state; maximizing it cannot decrease its value.Source: §C.6 · pp. 22–23

D.1 THE COMPLETE MAJORIZATION-MINIMIZATION ALGORITHM

  • The algorithm initializes with no selected experts, decomposes the Hessian, then iteratively scores candidates by marginal synergy minus context-aware redundancy penalty.A Top-k projection updates the subset, and the loop stops when consecutive selections match.Source: §D.1 · p. 24

D.2 DATASETS AND EVALUATION METRICS

The evaluation setup spans four language benchmarks, specifies two evaluation metrics, and describes the tested model architectures and fine-tuning configurations.

D.2 DATASETS AND EVALUATION METRICS

  • The evaluation covers AGNews, PIQA, HellaSwag, and MMLU, spanning classification, commonsense and predictive reasoning, and knowledge-intensive reasoning.MMLU covers 57 academic and professional disciplines.Source: §D.2 · p. 24
  • The study measures test accuracy on unseen splits and convergence efficiency in training iterations until validation accuracy reaches a stationary threshold.Higher test accuracy is identified as the primary proxy for generalization efficacy.Source: §D.2 · pp. 24–25

D.3 MODEL ARCHITECTURES AND HYPERPARAMETER SETTINGS

  • The tested architectures are Switch-Base-32, Switch-Base-64, and DeepSeek-MoE-16B, with 32 or 64 experts in the described MoE variants.The Switch-Base models use encoder-decoder layers, while DeepSeek-MoE-16B is decoder-only.Source: §D.3 · p. 25, Model Architectures · p. 25

Experimental Configurations

  • Fine-tuning uses bfloat16, 8-bit AdamW, learning rate 1 × 10−4, and batch size 16; the dense backbone is frozen while experts, routers, and task heads are updated.The MM defaults are Tmax = 10 iterations and active expert capacity k = 2.Source: Experimental Configurations · p. 25
  • Maximum sequence lengths are 128 tokens for AGNews, 256 for PIQA, and 512 for HellaSwag and MMLU; experiments use NVIDIA GeForce RTX 4090 GPUs.Source: Experimental Configurations · p. 25

E LIMITATIONS AND FUTURE WORK

The analysis models combinatorial dependencies only within layers; future work points to cross-layer routing and distributed settings as extensions.

E LIMITATIONS AND FUTURE WORK

  • Current analysis models combinatorial dependencies only within layers, leaving cross-layer expert dynamics outside the framework.The authors identify cross-layer expert synergies as a future direction.Source: E LIMITATIONS AND FUTURE WORK · p. 26
  • A global, block-diagonal Hessian proxy is proposed to investigate cross-layer synergies and enable holistic network-wide routing.Source: E LIMITATIONS AND FUTURE WORK · p. 26
  • The framework could be extended to federated or split learning, jointly optimizing expert selection with communication and computation constraints.Source: E LIMITATIONS AND FUTURE WORK · p. 26

F PRACTICAL IMPACT

DS-MoE is presented as an MM-based routing approach for training stability, a cardinality-constrained way to lower deployment resource demands, and a means of reducing training overhead and energy use.

F PRACTICAL IMPACT

  • Guaranteed monotonic-convergence MM is presented as avoiding standard Top-k routing's heuristic unpredictability and enhancing training performance.The passage frames this as addressing routing collapse and optimization instabilities.Source: F PRACTICAL IMPACT · p. 26
  • Under a predefined expert budget k, DS-MoE is said to reduce memory and computing requirements for training and deployment without compromising performance.Source: F PRACTICAL IMPACT · p. 26
  • Decoupling redundancy from synergy is reported to resolve gradient conflicts and expedite convergence, reducing computing overhead and energy consumption.The passage presents these reductions as supporting resource-efficient, economically viable large-scale MoE training.Source: F PRACTICAL IMPACT · p. 26
Loading 2610.00558v1…