MAESTRO: Pruning MoE Experts with Markov Chains
An Awkward Reality
2025 was a breakout year for Mixture-of-Experts (MoE) large models. DeepSeek-V3 has 671 billion parameters but activates only 37 billion per token. Qwen3-30B and GPT-OSS-20B followed suit, making MoE the standard recipe for "large parameters, low compute."
But there's an awkward catch: although each inference activates only about 5% of experts, 100% of them must sit in GPU memory. It's like a military command with 100 generals — only 5 deploy per battle, but all 100 draw salaries and occupy barracks. A 671B-parameter model still needs enough VRAM to hold all 671B parameters.
This is MoE deployment's core bottleneck: computation is cheap, but memory is expensive. The direct fix is pruning — cutting "less useful" experts. But how do you judge usefulness? In July 2026, researchers from IIT Delhi and NVIDIA proposed a new answer: use a Markov chain to direct this downsizing. The method is called MAESTRO (Markov-chain Approximated Expert Sparsification via Transition-based Routing).
The Blind Spot of Existing Methods
Before MAESTRO, mainstream MoE pruning borrowed from dense transformer pruning: count how often each expert is invoked, and cut the infrequent ones. This ignores a key fact: MoE routing is coupled across layers. A token's expert choices at layer 1 influence its choices at layer 2, forming a "routing path."
This local heuristic makes two types of errors:
1. Cutting "bridge experts": experts that are rarely invoked themselves but serve as transit hubs connecting high-frequency experts. Removing them breaks the routing chain. 2. Keeping "redundant experts": frequently invoked experts whose functions overlap heavily; removing one is fine because another covers for it.
The Markov Chain View
MAESTRO's core innovation: model MoE routing as a Markov chain. The "state" is which experts are activated at the current layer; the "transition" is which experts activate at the next layer. Entry (i, j) of the transition matrix gives the probability of expert j at layer ℓ+1 given expert i at layer ℓ.
By counting transitions over many inference samples, MAESTRO estimates this matrix, then computes its stationary distribution — the long-run visitation frequency of each state. In the MoE context, this is each expert's global importance accounting for all cross-layer dependencies. A high-stationary-probability expert isn't just frequently called; it sits on a traffic artery that other experts' routing paths pass through. Cutting it propagates damage along the whole chain.
From Math to Engineering
The pipeline has five steps:
1. Routing data collection: run a batch of inference samples through every layer, recording which experts each token activates. 2. Transition matrix estimation: count co-activations of experts in adjacent layers and normalize into probabilities. 3. Global transition matrix and stationary distribution: aggregate all layers' matrices and solve for the stationary distribution, yielding global importance scores. 4. Expert selection: rank by score and keep the top fraction for a target compression rate (e.g., 50%). 5. Recovery fine-tuning: lightly fine-tune on a small dataset (1 billion tokens) so remaining experts adapt.
Notably, MAESTRO assumes a first-order Markov process — next-layer routing depends only on the current layer. It's a simplification, but it keeps the math tractable and experiments show it works well.
Results: A 10.61% Improvement
The team tested MAESTRO on GPT-OSS-20B and Qwen3-30B across general ability, math, code, safety, bias, and ethics. At 50% expert compression:
- Average performance retention is 10.61% higher than SOTA. Traditional methods degrade noticeably; MAESTRO nearly preserves the original model.
- Cross-task variance is significantly lower — the pruned model behaves consistently, avoiding scenarios like "great at math but safety collapses." This consistency matters more than average score, because deployment needs predictable behavior.
An Analogy: Transit Network Pruning
Imagine cutting city bus routes. The traditional approach cancels stops with low daily ridership. MAESTRO models the whole network as a Markov chain — stops are states, passenger flows are transitions. The stationary distribution reveals transfer hubs: stops with modest ridership through which many passengers pass. Remove those and a whole district's mobility suffers. MAESTRO keeps globally important stops even when their local traffic isn't highest.
Limitations and an Honest Assessment
The paper candidly discusses several limitations:
1. First-order Markov assumption: real routing may have longer-range dependencies (e.g., layer 5 depending on layer 3). Higher-order chains are future work. 2. Whole-expert granularity: no partial (width) pruning; combining with width pruning is a natural direction. 3. Recovery fine-tuning cost: 1 billion tokens is far less than pretraining but not free. 4. Limited model scale: experiments cover only 20B and 30B models; behavior on 100B+ MoEs needs validation.
The Bigger Picture: MoE Deployment Economics
MAESTRO points to an emerging trend: post-training compression of MoE models as a standalone research direction. Pretraining an MoE costs millions of dollars, but deployment scenarios have different resource constraints. Methods like MAESTRO let you train once, prune as needed — carving out different sizes for cloud and edge.
The deeper lesson: in complex systems, local information is never enough. An expert's value lies not in how often it's invoked but in its position within the routing network — much like critical nodes on the internet. The Markov chain is a century-old mathematical tool; applying it here is less a novel invention than a demonstration of "using the right tool." Sometimes the best research isn't inventing something new, but finding a new use for an old one.
---
Paper: https://arxiv.org/abs/2607.08601
Authors: Palaash Goel (IIT Delhi), Ayush Maheshwari (NVIDIA India), Tanmoy Chakraborty (IIT Delhi)
Tested models: GPT-OSS-20B, Qwen3-30B
Published: July 9, 2026