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

Die Arbeit stellt CRAFT vor, ein effizientes Framework zur feinkörnigen, schichtweisen Replikation von Experten in Mixture-of-Experts-Modellen, das die Lastverteilung unter Einhaltung eines Speicherbudgets optimiert und so die End-to-End-Durchsatzrate im Vergleich zu bestehenden Techniken um durchschnittlich 1,14-fach steigert.

Das Wesentliche

Stellen Sie sich vor, Sie betreiben eine riesige, hochmoderne Bibliothek, in der Tausende von Lesern gleichzeitig nach Informationen suchen. Diese Bibliothek ist ein Künstliches Intelligenz-Modell (ein sogenanntes "Large Language Model" oder LLM), das aus vielen kleinen Spezialisten besteht, den sogenannten Experten.

In einer solchen Bibliothek gibt es ein Problem: Nicht alle Bücher (oder Themen) sind gleich beliebt.

• Manche Themen sind Super-Hits (z. B. "Wie backe ich einen Kuchen?"). Tausende Leute fragen das gleichzeitig.
• Andere Themen sind Nischensachen (z. B. "Wie funktioniert ein 19. Jahrhundert Uhrwerk?"). Nur wenige fragen danach.

Das Problem: Der Stau an der Theke

In der herkömmlichen Bibliothek (dem alten System) wird jeder Experte einer bestimmten Theke zugewiesen.

• Der Experte für "Kuchen" sitzt an Theke 1. Da alle dort anfragen, ist Theke 1 total überlastet. Der Experte schwitzt, die Warteschlange wird lang, und die Antwortzeit ist langsam.
• Der Experte für "Uhrwerke" sitzt an Theke 5. Da kaum jemand fragt, steht er nur herum und langweilt sich.

Das nennt man Lastungleichgewicht. Das System ist ineffizient: Während Theke 1 kollabiert, stehen Theke 5 bis 8 leer.

Die alte Lösung: Alles kopieren (EPLB)

Um das zu lösen, haben die Bibliothekare eine einfache Idee gehabt: "Kopiere die beliebten Experten!"
Wenn Theke 1 überlastet ist, stellen sie einfach 64 Kopien des "Kuchen-Experten" auf 64 verschiedene Tische im Raum. Jetzt können alle Kunden gleichzeitig bedient werden.

Aber: Das kostet enorm viel Platz!
Jede Kopie braucht einen eigenen Stuhl, einen eigenen Schreibtisch und eigene Bücher. In einer vollen Bibliothek (mit begrenztem Speicherplatz auf den Grafikkarten) führt das dazu, dass für die eigentlichen Bücher (den "KV-Cache", also den Kontext, den die KI gerade liest) kein Platz mehr bleibt.

• Ergebnis: Die Experten sind zwar gut verteilt, aber die Bibliothek ist so vollgestopft mit Kopien, dass sie kaum noch Kunden aufnehmen kann. Es ist wie ein überfülltes Restaurant, in dem jeder Tisch einen zweiten Kellner hat, aber keine Stühle mehr für die Gäste übrig sind.

Die neue Lösung: CRAFT (Der clevere Bibliothekar)

Die Autoren des Papers haben CRAFT entwickelt. CRAFT ist wie ein extrem schlauer Bibliothekar, der nicht blind kopiert, sondern genau hinsieht.

CRAFT macht drei Dinge anders:

1. Fein-granulare Analyse (Der genaue Blick):
   CRAFT schaut sich jede einzelne Abteilung (jedes "Layer" im Modell) an.

   • Abteilung A (Kuchen): Hier ist es chaotisch. Wir brauchen dringend Kopien!
   • Abteilung B (Uhrwerke): Hier ist es ruhig. Die Theke ist schon fast leer. Warum dort Kopien hinstellen? Das wäre Verschwendung!
   • Abteilung C (Mittelmäßig): Hier ist es okay, aber ein bisschen mehr Platz wäre gut.

2. Kostenbewusste Zuteilung (Nur das Nötigste):
   Statt für jede Abteilung 64 Kopien zu machen, sagt CRAFT:

   • "Für die hitzige Abteilung A machen wir 16 Kopien."
   • "Für die ruhige Abteilung B machen wir gar keine Kopien."
   • "Für die mittlere Abteilung C machen wir 4 Kopien."
     So sparen sie massiv Platz (Speicher), ohne dass die Warteschlangen zu lang werden.

3. Der "Schachbrett"-Effekt (Intelligente Verteilung):
   Wenn die Kopien verteilt werden, sorgt CRAFT dafür, dass sie nicht alle auf denselben Tischen landen, sondern clever über den ganzen Raum verteilt sind, damit keine neue Theke überlastet wird.

Das Ergebnis: Mehr Gäste, weniger Stau

Dank CRAFT passiert Folgendes:

• Platzsparend: Weil nicht überall unnötige Kopien herumstehen, bleibt viel mehr Platz für die "Gäste" (die eigentlichen Daten und den Kontext der Unterhaltung).
• Schneller: Die Warteschlangen an den überlasteten Theken sind weg, aber die Bibliothek ist nicht überfüllt.
• Effizient: Die Bibliothek kann 1,14-mal mehr Kunden pro Stunde bedienen als mit der alten Methode, bei gleicher Hardware.

Zusammenfassung in einem Satz

Statt blindlings jeden beliebigen Experten 64-mal zu kopieren (was den Speicherplatz verstopft), schaut CRAFT genau hin, kopiert nur dort, wo es wirklich brennt, und spart so wertvollen Platz, um mehr Anfragen gleichzeitig zu bearbeiten.

CRAFT ist also der clevere Bibliothekar, der weiß, wann er einen Kopierer braucht und wann er besser spart.

Technische Zusammenfassung

1. Problemstellung

Mixture-of-Experts (MoE)-Modelle sind der Standard für effizientes Skalieren großer Sprachmodelle (LLMs), da sie die Rechenkosten pro Token konstant halten, während die Gesamtzahl der Parameter wächst. Bei der Verteilung dieser Modelle über mehrere Geräte mittels Expert Parallelism (EP) entsteht jedoch ein kritisches Problem: Lastungleichgewicht (Load Imbalance).

• Ursache: Der Router in MoE-Modellen weist Tokens basierend auf der Eingabeverteilung dynamisch zu. Da natürliche Sprache einer Zipf-Verteilung folgt, werden einige Experten („Hot Experts") extrem häufig aktiviert, während andere („Cold Experts") kaum genutzt werden.
• Folgen: Dies führt zu Ineffizienzen: GPUs mit Hot Experts werden zu Engpässen, während andere GPUs untätig warten. Zudem entstehen Netzwerkengpässe durch ungleichmäßigen Datenverkehr beim All-to-All-Kommunikationsmuster.
• Bestehende Lösungen & deren Mängel:
  • Expert Placement: Versucht, Hot und Cold Experten auf Geräten zu mischen. Scheitert jedoch bei stark schiefen Lastverteilungen, bei denen ein paar Experten den Großteil der Last tragen.
  • Expert Replication (z. B. EPLB): Kopiert Hot Experten auf mehrere Geräte, um die Last zu teilen. Das Problem hierbei ist der hohe Speicherverbrauch. Bestehende Ansätze wie EPLB replizieren oft uniform (z. B. einen Replikat pro Layer pro GPU), was zu einer massiven Überreplikation führt. Viele dieser Replikate bringen nur marginale Verbesserungen der Lastbalance, verbrauchen aber wertvollen GPU-Speicher (VRAM), der für den KV-Cache (wichtig für lange Kontexte) fehlt. Dies führt zu einer Verschlechterung des Durchsatzes.

2. Methodik: CRAFT

CRAFT ist ein Framework, das die Experten-Replikation kostenbewusst und feingranular auf Layer-Ebene optimiert. Das Ziel ist es, das Lastungleichgewicht unter einem gegebenen Speicherbudget zu minimieren.

Kernidee: Nicht alle Schichten (Layers) profitieren gleich stark von Replikation. CRAFT weist Replikate selektiv nur den Schichten zu, die einen hohen Nutzen (Benefit) bieten, und vermeidet Replikation in bereits ausgeglichenen Schichten.

Der Workflow von CRAFT besteht aus drei Schritten:

1. Schätzung des Replikationsnutzens (Benefit Estimation):

   • CRAFT analysiert offline die Experten-Lastverteilung (basierend auf Profiling-Daten).
   • Für jede Schicht wird geschätzt, wie viel Lastbalance-Gewinn (Balancedness Gain) bei unterschiedlichen Anzahlen von Replikaten (z. B. 1, 2, 4, 8...) erzielt wird.
   • Es wird festgestellt, dass der Gewinn sublinear mit der Anzahl der Replikate abnimmt (abnehmende Grenzerträge).

2. Optimale Allokation (Dynamic Programming):

   • Das Problem wird als Multiple-Choice Knapsack Problem (MCKP) formuliert: Wie viele Replikate werden pro Schicht zugewiesen, um den Gesamtgewinn unter der Speicherbeschränkung (Gesamtzahl der Replikate) zu maximieren?
   • CRAFT löst dies effizient mittels dynamischer Programmierung. Das Ergebnis ist ein Plan, in dem stark schief gelastete Schichten viele Replikate erhalten, während ausgeglichene Schichten keine oder wenige erhalten.

3. Kapazitätsbewusste Zuweisung (Capacity-Aware Assignment):

   • Da die Anzahl der Replikate pro Layer nun variiert, muss sichergestellt werden, dass der Speicherbedarf auf allen GPUs gleich bleibt (um Fragmentierung des KV-Caches zu vermeiden).
   • CRAFT verwendet einen greedy-Algorithmus mit zwei Zielen:
     • Primär: Jeder GPU wird so oft ein Experte zugewiesen, bis die Kapazität ausgeglichen ist.
     • Sekundär: Experten werden interleaved (verschachtelt) über Knoten verteilt, um die Lastbalance auf Node-Ebene zu verbessern.

3. Wichtige Beiträge

• Erste detaillierte Charakterisierung: Die Autoren zeigen erstmals, dass der Durchsatz und die Lastbalance nicht linear mit der Anzahl der Replikate skalieren. Sie identifizieren, dass Layer-spezifisches Verhalten entscheidend ist.
• CRAFT Framework: Ein End-to-End-Framework, das in bestehende Serving-Frameworks (wie SGLang) integriert werden kann, ohne das Modell neu zu trainieren oder zu ändern.
• Kosten-Nutzen-Optimierung: CRAFT erreicht eine fast optimale Lastbalance mit deutlich weniger Speicheroverhead als uniforme Replikationsstrategien.

4. Ergebnisse

Die Evaluation erfolgte auf einem Cluster mit 64 GPUs (AWS p4de.24xlarge) mit Modellen wie DeepSeek-R1-671B und Kimi-K2-1000B.

• Durchsatzsteigerung: CRAFT steigert den End-to-End-Durchsatz (Goodput) im Durchschnitt um 1,14-fach (bis zu 1,2-fach) im Vergleich zu bestehenden Techniken wie EPLB.
• Speichereffizienz: CRAFT benötigt deutlich weniger Replikate als EPLB (z. B. 7,25-fach weniger bei DeepSeek-R1), um einen ähnlichen Balance-Gewinn zu erzielen. Dies ermöglicht einen größeren KV-Cache und damit die Verarbeitung längerer Kontexte oder höherer Parallelität.
• Robustheit: CRAFT funktioniert konsistent gut über verschiedene Datensätze hinweg, unabhängig davon, ob diese stark schief (hohe Lastungleichgewichte) oder eher ausgeglichen sind.
• Skalierbarkeit: Bei größeren Cluster-Größen (z. B. 12 Nodes) zeigt CRAFT eine bessere Skalierung als reine Platzierungsstrategien oder uniforme Replikation, da es die Lastungleichgewichte effizienter ausgleicht, ohne den Speicher zu überlasten.
• Overhead: Der initiale Overhead zur Berechnung des Replikationsplans liegt bei ca. 10 Sekunden und ist vernachlässigbar. Während des Betriebs (Inference) entstehen keine zusätzlichen Latenzen.

5. Bedeutung

CRAFT adressiert ein fundamentales Problem beim Betrieb von großen MoE-Modellen: den Trade-off zwischen Lastbalance und Speicherverbrauch.

• Kosteneffizienz: Durch die Reduzierung des Speicheroverheads für Replikate können mehr Anfragen parallel verarbeitet werden, was die Betriebskosten pro Token senkt.
• Praktische Anwendbarkeit: Da CRAFT keine Modelländerungen erfordert und nahtlos in bestehende Frameworks integriert werden kann, ist es sofort einsatzbereit für Produktionssysteme.
• Paradigmenwechsel: Das Paper beweist, dass „mehr Replikate" nicht automatisch „besser" bedeutet. Eine intelligente, datengetriebene Allokation ist entscheidend für die Leistungsfähigkeit von MoE-Systemen im großen Maßstab.

Zusammenfassend bietet CRAFT eine elegante Lösung, um die Skalierbarkeit von MoE-Modellen zu maximieren, indem es die Ressourcenallokation präzise an die tatsächlichen Lastmuster der einzelnen Schichten anpasst.