SCHUR-A*: Layer-wise Optimal Expert Pruning for MoEs via Schur-Complement Guided A* Search

Sparse Mixture-of-Experts (MoE) language models enable conditional computation but face deployment challenges due to the memory wall: while few experts are activated per token, the entire model must reside in memory. Existing expert pruning methods primarily rely on independent ranking, failing to account for the complex inter-dependencies and redundancies between experts. In this paper, we formulate post-training MoE pruning as a reconstruction-driven subset selection problem, aiming to minimize layer-output distortion under a cardinality constraint. We introduce SCHUR-A*, an algorithm that leverages A* search to achieve globally optimal expert selection within each layer. To maintain computational tractability, we derive a novel, admissible heuristic upper bound using a Schur-complement-based relaxation of the reconstruction objective. This tight bound allows for aggressive pruning of the search space while mathematically guaranteeing optimality. Furthermore, we propose an automated strategy to balance fidelity and memory reduction across heterogeneous layers via knee-point detection. Extensive experiments on Qwen3-30B-A3B demonstrate that SCHUR-A* significantly outperforms greedy and ranking-based baselines, maintaining comparable performance even under aggressive pruning ratios.

Large language models are powerful, but they are also expensive to run because they require a large amount of GPU memory. Some modern models are built from many specialized components and only use a few of them for each input. Even so, all components usually need to be stored in memory, which makes these models difficult to deploy on affordable hardware. This paper presents SCHUR-A*, a method for reducing the memory needed by such models after they have already been trained. The method identifies which components can be safely removed while preserving the behavior of the original model. A key feature is that it does not judge each component in isolation. Instead, it considers how components work together, because some may look unimportant on their own but become useful when combined with others. Our experiments show that SCHUR-A* can remove a substantial portion of the model while keeping strong performance on language understanding and reasoning tasks. This can make large language models cheaper and easier to deploy, although careful testing is still needed before using compressed models in specialized or high-stakes settings.