FairyFuse: Multiplication-Free LLM Inference on CPUs via Fused Ternary Kernels

1. Problemstellung

Die Bereitstellung von Large Language Models (LLMs) auf reinen CPU-Plattformen (z. B. für On-Device-Assistenten oder Edge-Server) stößt auf ein fundamentales Problem: Der Autoregressive Decoding-Prozess ist durch die Speicherbandbreite limitiert, nicht durch die Rechenleistung.

• Herausforderung: Selbst bei Quantisierung der Gewichte auf 4 Bit oder weniger (z. B. Q4_K_M) müssen die komprimierten Gewichte zur Inferenzzeit oft wieder in Gleitkomma-Zahlen dequantisiert werden, um herkömmliche Multiplikationen (FMA) durchzuführen. Dies nutzt das Potenzial der Bit-Einsparung nicht vollständig aus.
• Spezifisches Szenario: Ternäre Gewichte (Werte in $\{-1, 0, +1\}$) bieten eine 16-fache Komprimierung gegenüber FP32. Theoretisch kann jedes Produkt aus Gewicht und Aktivierung durch eine bedingte Addition, Subtraktion oder eine „No-Op" ersetzt werden, was Multiplikationen vollständig eliminiert.
• Lücke: Bisherige Systeme (wie das Referenz-System von Fairy2i oder llama.cpp) nutzen diese ternäre Struktur auf Hardware-Ebene nicht aus. Sie dequantisieren die Gewichte oder nutzen Lookup-Tabellen (LUT), was entweder Rechenzeit kostet oder den Cache-Druck erhöht. Zudem ist die Architektur von Fairy2i komplex-valued (komplexwertig), was eine lineare Transformation in acht reelle Teil-Operationen (GEMVs) zerlegt, was bei naiver Implementierung zu ineffizienter Datenwiederverwendung führt.

2. Methodik: FairyFuse

FairyFuse ist ein Inferenzsystem, das die theoretischen Vorteile ternärer Gewichte auf handelsüblichen x86-CPUs in die Praxis umsetzt.

A. Ternäre GEMV-Logik (Multiplikationsfrei)

Statt Gewichte zu dequantisieren, werden sie direkt verarbeitet:

• Packing: 16 ternäre Gewichte ($\{-1, 0, +1\}$) werden in einem einzigen 32-Bit-Wort gepackt (2 Bit pro Gewicht).
• Decoding: Anstatt Multiplikationen durchzuführen, werden die positiven und negativen Masken mittels der BMI2-Intrinsics (_pext_u32) in einem Zyklus extrahiert.
• Akumulation: Die Berechnung erfolgt ausschließlich über maskierte Additionen und Subtraktionen mittels AVX-512 (_mm512_mask_add_ps, _mm512_mask_sub_ps).
• Ergebnis: Der innere Schleifenkern enthält null Gleitkomma-Multiplikationsanweisungen und keine Lookup-Tabellen.

B. Fusionierter Widely-Linear Kernel

Da Fairy2i-Modelle komplexwertig sind, zerfällt jede Schicht in acht gekoppelte reelle GEMV-Operationen (General Matrix-Vector Multiplications). Eine naive Ausführung würde acht separate Schleifen erfordern, was zu redundanter Datenladung und Synchronisations-Overhead führt. FairyFuse löst dies durch einen fusionierten Kernel:

1. Masken-Wiederverwendung (O1): Ein decodiertes Maskenpaar wird für sowohl reelle als auch imaginäre Akkumulationspfade genutzt.
2. Eingabe-Wiederverwendung (O2): Aktivierungsvektoren werden nur einmal geladen und für alle acht Teil-GEMVs geteilt.
3. Vorzeichen-Tausch-Trick (O3): Die Konjugation komplexer Zahlen (Vorzeichenwechsel der imaginären Komponente) wird durch einen vorab berechneten Alias (neg_x_im) realisiert, was per-Lane-Negationen eliminiert.
4. Register-residente Akkumulatoren (O4): Alle acht Teilergebnisse bleiben während der gesamten inneren Schleife in AVX-512-Registern, was Zwischenspeicherungen im DRAM (Spills) verhindert.

3. Schlüsselbeiträge

1. Erster ternärer GEMV-Kernel auf x86: Implementierung eines Kernels, der ausschließlich maskierte AVX-512-Additionen und -Subtraktionen verwendet, ohne Multiplikationen oder Tabellen-Lookups im kritischen Pfad.
2. Fusion komplexer Schichten: Konsolidierung der acht Sub-GEMVs einer komplexwertigen Schicht in eine einzige SIMD-freundliche Schleife durch intelligente Masken- und Eingabewiederverwendung. Dies führt zu einem 1,55-fachen Geschwindigkeitsgewinn gegenüber einer unfusionierten Ausführung.
3. Architektonische Erkenntnis: Die Arbeit zeigt, dass extreme Quantisierung (Ternär) CPUs als primäres Zielplattform begünstigt, nicht GPUs. Während GPUs durch hohe Bandbreite (HBM) von Kompression kaum profitieren, verschiebt die 16-fache Kompression die Rechenintensität auf CPUs von einem speichergebundenen in einen rechenintensiven Bereich.

4. Ergebnisse

Die Evaluation erfolgte auf einem Intel Xeon 8558P (48 Kerne, ~200 GB/s Speicherbandbreite) mit einem 7-Milliarden-Parameter-Modell (LLaMA-2-7B, Fairy2i-W2).

• Durchsatz: FairyFuse erreicht 32,4 Tokens pro Sekunde.
  • Das ist 1,24-mal schneller als llama.cpp im Q4_K_M-Format (26,15 tok/s).
  • Es ist schneller als llama.cpp Q2_K (20,1 tok/s), obwohl Q2_K weniger Speicher benötigt, da der Multiplikations-freie Pfad die Rechenlatenz senkt.
• Qualität: Die Modellqualität bleibt nahezu verlustfrei:
  • WikiText-2 Perplexity: 5,52 (Vergleich: FP16 = 5,47; Q4_K_M = 5,68).
  • Durchschnittliche Downstream-Accuracy: 66,0% (Vergleich: FP16 = 67,3%).
• Kernel-Performance:
  • Bei 48 Threads erreicht der ternäre Kernel einen 29,6-fachen bis 54,4-fachen Speedup gegenüber FP32.
  • Die Roofline-Analyse zeigt, dass die ternäre Packung die arithmetische Intensität von 0,25 auf 8,0 OP/Byte erhöht, was den Kernel näher an die Rechengrenze (Compute Ridge) der CPU bringt.
• GPU-Vergleich: Auf einer NVIDIA H200 GPU führt die ternäre Implementierung zu einer 130-fachen Verschlechterung gegenüber FP16, da GPUs keine effizienten pext-ähnlichen Anweisungen für das schnelle Decodieren besitzen und die hohe Bandbreite die Kompression nicht ausnutzen kann.

5. Bedeutung und Fazit

FairyFuse demonstriert, dass die Kombination aus ternärer Quantisierung und spezialisierten CPU-Instruktionen (AVX-512, BMI2) einen praktikablen Weg für die Inferenz von Milliarden-Parameter-Modellen auf Standard-Hardware eröffnet.

• Privatsphäre & Kosten: Es ermöglicht hochperformante, datenschutzkonforme Inferenz auf Geräten ohne dedizierte GPUs.
• Paradigmenwechsel: Die Arbeit widerlegt die Annahme, dass extreme Quantisierung (unter 4 Bit) nur für GPUs oder spezialisierte Hardware geeignet ist. Stattdessen zeigt sie, dass CPUs aufgrund ihrer Speicherbandbreiten-Beschränkungen und effizienten Bit-Manipulations-Instruktionen die ideale Plattform für ternäre Modelle sind.
• Zukunft: Das System bietet eine Blaupause für die Entwicklung von Multiplikations-freien Inferenzengines, die die Lücke zwischen algorithmischer Quantisierung und hardware-effizienter Ausführung schließen.