CRAFT: Cost-aware Expert Replica Allocation with Fine-Grained Layerwise Estimations

CRAFT is a cost-aware expert replica allocation framework that utilizes fine-grained, layerwise benefit estimations to maximize load balancing and serving throughput under memory constraints, achieving up to a 1.2x performance improvement over existing techniques without requiring model retraining.

The Gist

Imagine you run a massive, high-speed restaurant called "The MoE Kitchen."

The Problem: The "Hot Chef" Bottleneck

In this kitchen, instead of having one giant chef who does everything, you have hundreds of specialized chefs (called Experts).

• The Setup: When a customer orders a dish (a token of text), a smart waiter (the Router) looks at the order and sends it to the specific chefs who are best at making that dish.
• The Issue: In the real world, some dishes are ordered all the time (like "Spicy Noodles"), while others are rare (like "Deep-Fried Clouds").
• The Result: The chefs who make "Spicy Noodles" are running around frantically, sweating, and burning out. The chefs who make "Deep-Fried Clouds" are standing around doing nothing, checking their phones.
• The Consequence: The whole restaurant slows down because the busy chefs are the bottleneck. The kitchen is unbalanced.

The Old Solution: "Copy-Paste" Chefs

To fix this, the restaurant owners tried a simple idea: Replication.
If "Chef A" is too busy, let's hire a clone of Chef A (a Replica) to help out.

• The Old Way (EPLB): The old system was like a strict manager who said, "We will hire one clone for every single chef, no matter what."
• The Flaw: This is incredibly expensive! You now need twice as many chefs, which means you need twice as much kitchen space (GPU Memory).
  • For the rare dishes, you hired a clone who just stood there doing nothing.
  • For the super busy dishes, one clone wasn't enough, but you were forced to stop hiring because you ran out of space.
  • The Cost: You spent a fortune on space, but the kitchen is still a bit chaotic.

The New Solution: CRAFT (The Smart Manager)

The authors of this paper created CRAFT. Think of CRAFT as a brilliant, cost-conscious manager who uses data to make smart decisions.

1. The "Fine-Grained" Inspection
Instead of guessing, CRAFT looks at the menu history. It asks: "Which specific dishes are actually causing the rush?"

• It realizes that for "Spicy Noodles," we need 4 clones.
• For "Deep-Fried Clouds," we need 0 clones (the original chef is fine).
• For "Grilled Cheese," maybe we need 1 clone.

2. The "Cost-Aware" Budget
CRAFT knows the kitchen has a limited amount of space (Memory Budget). It doesn't just hire clones willy-nilly. It calculates: "If I hire a clone for this specific dish, how much faster will the whole kitchen get?"

• If a clone helps a lot, CRAFT hires them.
• If a clone helps very little (because the dish isn't that popular), CRAFT says, "No thanks, let's save that space."

3. The Result

• Better Balance: The busy chefs get the help they actually need. The slow chefs don't get wasted clones.
• More Space: Because CRAFT doesn't hire unnecessary clones, it saves a huge amount of kitchen space.
• Faster Service: With more space saved, the restaurant can handle more customers at once (larger "KV Cache" or waiting list) without slowing down.

The Analogy in Action

Imagine you are organizing a party with 64 guests (GPUs).

• The Old Way: You give every single guest a backup microphone, just in case they need to speak. This is expensive, and most guests never use their mics.
• CRAFT's Way: You look at the schedule. You see that Guest #5 is going to give a 20-minute speech, so you give them 4 backup mics. Guest #12 is just going to say "Happy Birthday," so they get 0 backups. Guest #30 is a singer, so they get 2 backups.
• The Outcome: You used fewer mics total, but the people who actually needed to speak had plenty of help. The party runs smoother, and you saved money on equipment.

Why This Matters

In the world of AI (Large Language Models), "kitchen space" is GPU Memory, which is incredibly expensive and hard to get.

• CRAFT allows companies to run these massive AI models faster and cheaper.
• It doesn't require retraining the AI (no new recipes).
• It just rearranges the existing staff smarter.

The Bottom Line: CRAFT stops us from wasting money on "useless clones" and puts our resources exactly where they are needed, making AI faster and more efficient.

Technical Summary

1. Problem Statement

Mixture-of-Experts (MoE) models have become the standard for scaling Large Language Models (LLMs) efficiently. However, deploying MoE models introduces a critical system bottleneck: Expert Load Imbalance.

• The Issue: Due to the dynamic routing of tokens (often following a Zipfian distribution), a few "hot" experts receive a disproportionate number of tokens, while "cold" experts remain underutilized.
• Consequences: This leads to GPU idleness on devices hosting cold experts and network congestion (all-to-all traffic) on devices hosting hot experts, severely degrading inference throughput.
• Existing Solutions & Limitations:
  • Expert Placement: Co-locating hot and cold experts helps but fails when load skew is extreme (a few experts dominate a layer).
  • Expert Replication (e.g., EPLB): Replicating hot experts across devices balances the load. However, existing schemes (like EPLB) use uniform replication (allocating one replica per layer per GPU). This approach is memory-inefficient:
    1. It over-replicates in layers where load is already balanced (diminishing returns).
    2. It under-allocates in highly skewed layers.
    3. The massive memory overhead reduces the available KV cache, limiting batch sizes and causing throughput degradation, especially in large-scale deployments.

2. Methodology: CRAFT

The authors propose CRAFT, a cost-aware framework that performs fine-grained, per-layer expert replication to maximize load balance under a strict memory budget.

Key Design Principles

1. Layer-Specific Benefit Estimation: The authors observe that different MoE layers benefit differently from replication.
   • High-skew layers: Benefit substantially from replication.
   • Low-skew layers: Benefit little; replication here is a waste of memory.
2. Sublinear Scaling: Load balancedness scales sublinearly with the number of replicas. Doubling replicas beyond a certain point yields negligible balancedness gains but doubles memory cost.

Workflow

CRAFT operates in three main steps:

1. Offline Profiling & Benefit Estimation:
   • Analyzes offline expert load distributions.
   • Estimates the "replication benefit" (balancedness gain) for each layer at various replica counts (using a geometric progression of replica numbers).
   • Generates a benefit matrix quantifying the gain per layer per replica count.
2. Optimal Allocation (Solving the Knapsack Problem):
   • Formulates the allocation as a Multiple-Choice Knapsack Problem (MCKP).
   • Goal: Maximize total balancedness gain subject to a total replica budget ($R \times D$, where $R$ is replicas per GPU and $D$ is the number of GPUs).
   • Solution: Uses dynamic programming to select the optimal number of replicas for each specific layer. Some layers get many replicas; others get none.
3. Capacity-Aware Assignment:
   • Challenge: Uneven replica counts per layer can cause memory imbalance across GPUs.
   • Solution: Employs a greedy, interleaved assignment algorithm. It assigns experts to GPUs to ensure:
     • Each GPU holds a nearly identical number of experts (minimizing capacity skew).
     • Replicas are distributed evenly across nodes to maintain uniform KV cache sizes (preventing memory fragmentation).

3. Key Contributions

• First Detailed Characterization: The paper provides the first analysis of how throughput and load balancedness scale with replication, identifying the "diminishing returns" curve and the critical importance of layer-specific behavior.
• CRAFT Framework: An end-to-end system that integrates seamlessly into existing serving frameworks (like SGLang) without requiring model retraining or architectural changes.
• Cost-Aware Optimization: Unlike previous uniform replication, CRAFT dynamically allocates memory only where it yields high performance gains, significantly reducing the memory overhead.

4. Experimental Results

The framework was evaluated on state-of-the-art models (DeepSeek-R1-671B and Kimi-K2-1000B) across various datasets and cluster sizes (6 to 12 nodes, 8 A100 GPUs per node).

• Throughput Improvement:
  • CRAFT achieves an average 1.14× increase in end-to-end throughput compared to the existing uniform replication technique (EPLB).
  • In optimal configurations, gains reach up to 1.2×.
  • On highly skewed datasets, CRAFT improves throughput by 1.42× over the baseline (no replication), whereas EPLB only achieves 1.24× (due to memory overhead).
• Memory Efficiency:
  • CRAFT achieves near-optimal load balance using significantly fewer replicas than EPLB (e.g., 7.25× fewer replicas on DeepSeek-R1).
  • This preserves a larger KV cache, allowing for larger batch sizes and preventing the throughput degradation seen in EPLB when the KV cache is shrunk.
• Scalability:
  • CRAFT scales efficiently with cluster size. As the cluster grows, the baseline (placement-only) suffers from increased imbalance, while CRAFT maintains high throughput.
  • EPLB often performs worse than the baseline in smaller clusters because its excessive memory usage drastically reduces the KV cache size.
• Overhead:
  • Zero runtime overhead: CRAFT requires no additional computation during inference.
  • Negligible initialization overhead: The offline profiling and optimization take ~10 seconds, which is negligible compared to framework startup times.

5. Significance

CRAFT addresses a fundamental inefficiency in MoE serving: the trade-off between load balancing and memory usage. By moving from uniform to fine-grained, cost-aware replication, it enables:

1. Higher Throughput: Maximizing resource utilization by eliminating GPU idleness without sacrificing batch size.
2. Cost Reduction: Allowing large-scale MoE models to run on fewer GPUs or with larger context windows (due to preserved KV cache) for the same hardware budget.
3. Practical Deployment: It is a drop-in replacement for existing load balancers in frameworks like SGLang, making it immediately applicable to production LLM serving without model retraining.

In summary, CRAFT demonstrates that intelligent, sparse replication is far superior to uniform, heavy replication, solving the load imbalance problem while respecting the strict memory constraints of modern LLM inference.