MAESTRO: Commanding MoE Expert Pruning with Markov Chains
An Awkward Reality
2025 was a breakout year for Mixture-of-Experts (MoE) large language models. DeepSeek-V3 packs 671 billion parameters but activates only 37 billion per token—like an army of 67.1 billion that sends only 3.7 billion into each battle. Qwen3-30B, GPT-OSS-20B, and others followed, making MoE the standard recipe for "large parameters, low compute."
But here's the awkward truth: although only ~5% of experts are activated per inference, 100% of them must sit in GPU memory.
Imagine a military command with 100 generals: each campaign deploys 5, yet the other 95 still draw salaries, occupy barracks, and consume supplies. A 671B-parameter model requires memory for all 671B parameters even if only 37B are active per token.
This is the core MoE deployment bottleneck: computation is cheap, but space is expensive.
The most direct fix is pruning—removing the "less useful" experts. But how do you decide which ones? In July 2026, researchers from IIT Delhi and NVIDIA proposed a new answer: use a Markov chain to direct the 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 directly from dense transformer pruning: count how often each expert is invoked, and cut the infrequent ones.
Sounds reasonable, but it ignores a key fact: MoE routing is coupled across layers.
A token traveling from layer 1 to layer 32 does not choose experts independently at each layer—its choice at layer 1 can influence layer 2, forming a "routing path."
Traditional frequency-based pruning is a local heuristic—like a裁军 officer judging soldiers purely by attendance. Some rarely-activated experts are summoned at critical moments; removing them breaks the entire routing chain. Concretely, traditional methods make two classes of errors:
1. Pruning "bridge experts": low-frequency experts that serve as transit hubs connecting high-frequency ones. Cutting them severs downstream routing paths. 2. Keeping "redundant experts": high-frequency experts whose functions heavily overlap, where one can substitute for the other.
The Markov Chain Perspective
MAESTRO's core innovation: model MoE routing as a Markov chain.
A Markov chain describes state transitions: the next state depends only on the current one. Here, the "state" is which experts are active at layer ℓ, and the "transition" is which experts activate at layer ℓ+1. A transition matrix records the probability that expert j activates at layer ℓ+1 given expert i activated at layer ℓ.
MAESTRO estimates these matrices from routing statistics over many inference samples, then computes the chain's stationary distribution—the long-term frequency with which each state is visited. In the MoE context, this yields each expert's global importance after accounting for all cross-layer dependencies.
This is far more informative than local frequency counts. An expert with high stationary probability isn't just frequently invoked—it sits on a "main thoroughfare" that many routing paths pass through. Pruning such an expert propagates impact across the whole chain.
From Math to Engineering
MAESTRO's pipeline has five steps:
1. Routing data collection: Run a batch of inference samples (e.g., 100k texts) through every layer, recording which experts each token activates per layer—like installing traffic cameras on a highway. 2. Transition matrix estimation: Aggregate adjacent-layer expert co-occurrences into transition matrices, normalized into probabilities. 3. Global transition matrix and stationary distribution: Merge per-layer matrices into one global matrix and solve for its stationary distribution, yielding each expert's global importance score. 4. Expert selection: Rank experts by stationary distribution and keep the top fraction for a target compression ratio (e.g., 50%). 5. Recovery fine-tuning: Pruning causes some performance loss; lightweight fine-tuning on ~1 billion tokens lets remaining experts adapt to the changed routing.
One notable detail: MAESTRO assumes routing is first-order Markov—the next layer's choice depends only on the current layer. It's a simplification (real routing may have longer dependencies), 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 (OpenAI's open-source 20B MoE) and Qwen3-30B (Alibaba's 30B MoE), across general ability, math, code, safety, bias, and ethics benchmarks—deliberately diverse tasks to test generalization after pruning.
At a strict 50% compression rate (half the experts removed):
- Average performance retention beat SOTA by 10.61%. Under 50% compression, traditional methods degrade noticeably, while MAESTRO nearly preserves the original model.
- Cross-task variance is significantly lower. Pruned models perform consistently across tasks—no "great at math but safety collapses" scenarios. This consistency matters more than average score, because deployment demands predictable behavior.
- Traditional approach: rank stops by daily ridership and eliminate the quiet ones.
- MAESTRO approach: model the whole network as a Markov chain—each stop is a state, with transition probabilities between stops. The stationary distribution reveals that some stops, though individually quiet, are transfer hubs. Closing them disrupts an entire district's travel.
The low variance validates MAESTRO's core hypothesis: global routing information avoids pruning decisions that are locally optimal but globally catastrophic. Traditional methods may cut a safety-critical "bridge expert"—crashing safety benchmarks while others remain fine. MAESTRO sees cross-layer dependencies and avoids this.
An Analogy: Transit Network Pruning
Imagine cutting bus routes in a city:
Limitations and an Honest Assessment
The paper candidly discusses several limitations:
1. First-order Markov assumption: real routing may involve longer-range dependencies (e.g., layer 5 depending on layer 3). Higher-order chains are future work. 2. Whole-expert granularity: experts are kept or dropped entirely; partial width pruning could sometimes be better and is a natural extension. 3. Recovery fine-tuning cost: ~1 billion tokens of fine-tuning data is far less than pretraining, but not free—a barrier for extremely resource-constrained settings. 4. Limited model scale: experiments cover only 20B and 30B models; whether results hold for 100B+ MoEs remains to be verified.
The Bigger Picture: MoE Deployment Economics
MAESTRO's significance goes beyond technique. It signals an emerging field: post-training compression of MoE models as a research direction in its own right.
Pretraining an MoE model costs millions of dollars, but deployment scenarios have different constraints—clouds can run the full model, edge devices may fit only a quarter of the experts. Methods like MAESTRO enable train once, prune as needed.
This changes MoE economics: instead of "big models too expensive, small models insufficient," you train one large model and carve out differently sized variants per scenario. MAESTRO's global routing view ensures the pruned variants remain reliable across diverse tasks.
More deeply, MAESTRO reminds us that in complex systems, local information is never enough. An expert's value lies not in how often it's invoked, but in where it sits within the routing network—much like "critical nodes" on the internet, where cutting a low-traffic router can partition the entire network.
The Markov chain is a century-old mathematical tool. Applying it to MoE pruning isn't a profound invention—it's a demonstration of using the right tool. Sometimes the best research isn't inventing something new, but finding a new use for an old idea.
---
Paper: https://arxiv.org/abs/2607.08601
Authors: Palaash Goel (IIT Delhi), Ayush Maheshwari (NVIDIA India), Tanmoy Chakraborty (IIT Delhi)
Models tested: GPT-OSS-20B, Qwen3-30B
Published: July 9, 2026