MAESTRO: Commanding MoE Expert Pruning with Markov Chains
The Awkward Reality
2025 has been a breakout year for Mixture-of-Experts (MoE) models. DeepSeek-V3 packs 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 reality: although only ~5% of experts are activated per inference, 100% of experts must reside in GPU memory. It's like a military command with 100 generals who send 5 to each battle yet must house and pay all 100. Computation is cheap, but memory is expensive.
The most direct fix is pruning — removing less useful experts. The question is: how do you decide which experts to cut? 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 from dense transformer pruning: count how often each expert is invoked; cut the infrequent ones.
This ignores a key fact: MoE routing is coupled across layers. A token's expert choice at layer 1 can influence its choice at layer 2, forming a "routing path." Frequency-based pruning is a *local heuristic* — like an officer who dismisses soldiers based on attendance alone, even when low-attendance soldiers are called at critical moments.
Traditional methods make two kinds of mistakes:
1. Cutting "bridge experts": rarely invoked experts that connect high-frequency experts; removing them breaks downstream routing paths. 2. Keeping "redundant experts": frequently invoked experts whose functions overlap heavily, where one can substitute for the other.
The Markov Chain Perspective
MAESTRO's core innovation: model MoE routing as a Markov chain. The "state" is the set of experts activated at the current layer; the "transition" is which experts are activated at the next layer, described by a transition matrix whose (i, j) entry is the probability that expert j at layer ℓ+1 activates given expert i at layer ℓ.
After estimating this matrix from routing statistics over many inference samples, the key step is computing the chain's stationary distribution — the long-run frequency of visiting each state. In the MoE context, this yields each expert's global importance, accounting for all cross-layer dependencies. A high-stationary-probability expert sits on a "transport hub" — many routing paths pass through it — and removing it propagates impact along the whole chain.
From Math to Engineering
The MAESTRO pipeline has five steps:
1. Routing data collection: run a batch of inference samples through the model, logging which experts each token activates per layer. 2. Transition matrix estimation: aggregate expert co-activation between adjacent layers into normalized transition probabilities. 3. Global transition matrix and stationary distribution: merge per-layer matrices into a global one and solve for its stationary distribution, giving each expert a global importance score. 4. Expert selection: rank by stationary distribution and keep the top experts for a target compression ratio (e.g., removing 50%). 5. Recovery fine-tuning: lightly fine-tune with limited data (1 billion tokens) so remaining experts adapt to the new routing.
A notable detail: MAESTRO assumes routing is *first-order Markov* — the next layer depends only on the current layer. This is a simplifying assumption, but 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 five domains: general ability, math, code, safety, bias, and ethics.
At a strict 50% compression rate:
- Average performance retention is 10.61% higher than SOTA. Traditional methods degrade noticeably at 50% compression; MAESTRO nearly maintains the original model's level.
- Cross-task variance is significantly lower — pruned models behave consistently, without scenarios like "math is fine but safety collapses." Consistency matters more than average score for deployment, because you need predictable behavior.
An Analogy: Transit Network Pruning
Imagine trimming a city's bus routes. The traditional approach removes stops with low daily ridership. MAESTRO instead models the whole network as a Markov chain — each stop is a state, and passenger flows between stops are transition probabilities. The stationary distribution reveals "transfer hubs": stops with modest own-ridership but critical for connecting many routes. Removing them disrupts an entire area's mobility. MAESTRO preserves globally important hubs even when their own usage isn't highest — the difference between global and local perspective.
Limitations and an Honest Assessment
1. First-order Markov assumption: real routing may have longer-range dependencies; higher-order chains are future work. 2. Whole-expert granularity: no partial 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–30B models; 100B+ MoE validation remains open.
The Bigger Picture: MoE Deployment Economics
MAESTRO points to an emerging trend: post-training compression of MoE models is becoming its own research direction. Pretraining an MoE costs millions of dollars, but deployment scenarios have wildly different resource constraints. Methods like MAESTRO enable train once, prune as needed — carving out different sizes from one large model.
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 its position within the routing network — much like critical nodes on the internet, where a low-traffic router can partition the network if it fails. The Markov chain is a century-old mathematical tool; applying it to MoE pruning isn't deep novelty but a demonstration of "using the right tool." Sometimes the best research isn't inventing something new — it's discovering a new use for an old tool.
---
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