MAESTRO: Directing MoE Model Expert Downsizing with Markov Chains
An Awkward Reality
2025 has been 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 troops sending just 3.7 billion into battle. Qwen3-30B and GPT-OSS-20B followed suit, making MoE the standard recipe for "large parameters, low compute."
But there's an awkward catch: even though only ~5% of experts are activated per inference, 100% of them must reside in GPU memory.
Imagine a military command with 100 generals: each campaign deploys 5, but the other 95 still draw salaries, occupy barracks, and require supplies. Likewise, a 671B-parameter model needs enough VRAM to hold all 671B parameters, even if only 37B are active per token.
This is MoE deployment's core bottleneck: computation is cheap, but space is expensive.
The most direct fix is pruning—cutting the "less useful" experts. But how do you judge which experts are less useful?
In July 2026, a team 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 techniques from dense transformers: count how often each expert is invoked; cut the infrequent ones.
This sounds reasonable but ignores a key fact: MoE routing is coupled across layers.
Consider a 32-layer MoE with 64 experts per layer, activating 6 per token. A token's expert choice at layer 1 can influence its choice at layer 2, forming a cross-layer "routing path." Traditional methods only look at per-expert invocation counts—a local heuristic, like a downsizing officer who fires soldiers purely by attendance. Some soldiers are rarely present but called at critical moments; firing them breaks the whole routing chain.
Concretely, traditional methods make two kinds of mistakes:
1. Cutting "bridge experts": some experts are invoked rarely but act as transfer hubs connecting high-frequency experts. Removing them severs downstream routing paths. 2. Keeping "redundant experts": some frequently invoked experts overlap heavily in function—one can cover for the other. Frequency-based methods can't see this redundancy.
The Markov Chain Perspective
MAESTRO's core innovation: model MoE routing as a Markov chain.
A Markov chain describes systems moving between states via transition probabilities, with the key "memoryless" property—the next state depends only on the current state.
In MAESTRO, the "state" is "which experts are activated at the current layer," and the "transition" is "which experts get activated at the next layer." A transition matrix captures this: entry (i, j) is the probability that layer ℓ's expert i is followed by layer ℓ+1's expert j.
By counting transitions across many inference samples, MAESTRO estimates this matrix. Then comes the crucial step: computing the chain's stationary distribution.
The stationary distribution gives the long-run frequency of each state if the chain runs long enough. In the MoE context, it tells you each expert's global importance after accounting for all cross-layer dependencies.
This far outperforms simple local frequency counts. An expert with high stationary probability isn't just frequently invoked—it sits on a "transportation artery" that many other experts' routing paths pass through. Cutting such an expert sends ripples down the entire chain.
From Math to Engineering
MAESTRO's pipeline has five steps:
Step 1: Routing data collection. Run a batch of inference samples (e.g., 100k texts) through every layer, logging which experts each token activates—like installing cameras on a highway to count traffic.
Step 2: Transition matrix estimation. Aggregate adjacent-layer expert co-activations into transition matrices: for expert i at layer ℓ and expert j at layer ℓ+1, count joint activations and normalize to probabilities.
Step 3: Global transition matrix and stationary distribution. Aggregate all layers' matrices into a global one, then solve for its stationary distribution—yielding a global importance score per expert.
Step 4: Expert selection. Given a target compression ratio (e.g., 50% of experts removed), rank experts by stationary distribution and keep the top-scoring ones.
Step 5: Recovery fine-tuning. Pruning causes some performance loss. A light fine-tune (~1B tokens in the paper) lets the remaining experts adapt to the new routing.
A notable detail: MAESTRO assumes routing is "first-order Markov"—the next layer's choice depends only on the current layer. It's a simplifying assumption (real routing may have longer dependencies), but it makes the math tractable, and experiments show it works well.
Experimental Results: A 10.61% Improvement
The team tested MAESTRO on two mainstream MoE models: GPT-OSS-20B (OpenAI's open-source 20B MoE) and Qwen3-30B (Alibaba's 30B MoE).
Evaluation covered five domains: general ability, math, code, safety, bias, and ethics—chosen deliberately diverse to test post-pruning generalization.
Under a strict 50% compression rate (half the experts removed):
- Average performance retention is 10.61% higher than SOTA. A significant gain—traditional methods degrade noticeably at 50% compression, while MAESTRO nearly preserves the original model.
- Cross-task variance is substantially lower. Pruned models behave more consistently across tasks—no "great at math but safety collapses" scenarios. This consistency matters more than the average score, because deployment requires predictable behavior.
An Analogy: Transit Network Pruning
Imagine downsizing a city's bus network. Each route has stops with varying daily ridership.
Traditional approach: count each stop's daily ridership; cancel low-ridership stops.
MAESTRO approach: model the whole network as a Markov chain—stops are states, passenger flows are transitions. The stationary distribution reveals that some stops with modest ridership are transfer hubs: many passengers pass through them to reach other lines. Closing them disrupts travel across an entire district.
MAESTRO keeps exactly these "globally important" hubs, even when their own ridership isn't the highest. That's the difference between global and local views.
Limitations and Honest Assessment
The paper candidly discusses several limitations:
1. First-order Markov assumption: routing may have longer-range dependencies (e.g., layer 5 depending on layer 3). Higher-order Markov chains are future work. 2. Whole-expert granularity: MAESTRO keeps or drops entire experts, with no "partial pruning" option. Halving an expert's width might sometimes beat removing it entirely; combining with width pruning is a natural direction. 3. Recovery fine-tuning cost: pruning requires ~1B tokens of fine-tuning data—far less than pretraining, but not free. This could be a barrier for extremely resource-constrained settings. 4. Limited model scale: experiments cover only 20B and 30B models. Whether MAESTRO holds at 100B+ MoEs remains to be verified.
The Bigger Picture: MoE Deployment Economics
MAESTRO's significance goes beyond technique. It points to an emerging trend: post-training compression of MoE models is becoming its own research field.
Pretraining an MoE costs millions of dollars, but deployment scenarios have wildly different resource constraints—cloud can run the full model, edge devices might fit only a quarter of the experts. Methods like MAESTRO enable train once, prune to fit.
This changes MoE economics: previously "big models too expensive, small models insufficient"; now "train one big model, carve out different sizes per scenario." MAESTRO's global routing view ensures pruned models stay reliable across diverse tasks.
More deeply, MAESTRO reminds us: 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—just like "critical nodes" on the internet, where some routers carry little traffic yet partition the whole network if severed.
The Markov chain is a mathematical tool over a century old. Applying it to MoE pruning isn't profound novelty—it's a demonstration of "using the right tool." Sometimes the best research isn't inventing something new, but 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