🤖 machine learning

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

FairyFuse is a CPU-based inference system that achieves multiplication-free execution and a 29.6x kernel speedup by fusing ternary weight operations into a single AVX-512 loop, enabling high-throughput, near-lossless LLM generation on commodity hardware without floating-point multiplications.

Original authors: Fei Zuo, Xiaoyan Xi, Quanyi Zeng, Feiyu Wang, Ho Fai Leung

Published 2026-04-24

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: Fei Zuo, Xiaoyan Xi, Quanyi Zeng, Feiyu Wang, Ho Fai Leung

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Traffic Jam" in Your Computer

Imagine you are trying to drive a massive truck (a Large Language Model) through a city. The truck is full of heavy cargo (the model's "weights" or knowledge).

In most computers, the engine (the CPU) is powerful, but the roads (the memory bandwidth) are narrow and crowded. Every time the truck needs to make a decision (generate a word), it has to stop at a warehouse, unload a heavy box, carry it to the engine, do some math, and put it back.

The problem is that the math is too heavy. The truck spends more time waiting for the cargo to arrive than actually driving. This is why running AI on a regular laptop or server is often slow; the computer is stuck in a traffic jam caused by moving too much data.

The Old Solution: "Dequantization" (Unpacking the Boxes)

Previously, to make these models smaller, researchers used quantization. Think of this as packing the heavy cargo into smaller, lighter boxes.

The Catch: Even though the boxes are smaller, the computer still has to unpack them into their original heavy form before it can do the math. It's like buying a flat-pack bookshelf: you save space shipping it, but you still have to spend time assembling it before you can use it.
The Result: You save space, but you don't save much time because the "assembly" (unpacking and multiplying numbers) still takes forever.

The New Idea: "Ternary" Weights (The Magic Switch)

The paper introduces a model called Fairy2i that uses Ternary Weights.
Instead of having numbers like 3.14 or -2.5, these weights are only three things: +1, -1, or 0.

The Analogy: Imagine you are cooking.
- Normal Math: You have to measure exactly 3.14 cups of flour. This requires a scale and a calculator (Multiplication).
- Ternary Math: You only have three options: "Add a cup," "Subtract a cup," or "Do nothing."
- The Benefit: You don't need a scale or a calculator anymore. You just flip a switch. If it's +1, you add. If it's -1, you subtract. If it's 0, you ignore it. You have eliminated the need for multiplication entirely.

The Innovation: "FairyFuse" (The Assembly Line)

Here is the tricky part. The model uses a complex "widely-linear" structure, which means for every single math operation, the computer actually has to do eight tiny sub-operations.

If you just told the computer to do these eight steps one by one, it would be slow because it would keep running back and forth to the warehouse to grab the same ingredients (data) over and over again.

FairyFuse is the genius assembly line that fixes this.

Fusion: Instead of sending the truck out 8 times, it loads the truck once and does all 8 operations in a single, super-fast loop.
Masked Operations: It uses special CPU instructions (like a master key) to tell the computer: "Only add the ingredients where the switch is ON, and subtract where the switch is OFF."
No Unpacking: It never unpacks the boxes. It keeps them in their tiny, compressed state and processes them directly.

The Results: Why This Changes Everything

The authors tested this on a standard Intel server (a "commodity CPU," meaning a regular computer, not a super-expensive AI chip).

Speed: It is 30 times faster than the old way of doing math on a CPU.
Comparison: It beats the current industry standard (llama.cpp) by 1.24x, even though it uses less memory.
Quality: The AI is just as smart as the full-size version. It didn't get "dumber" because of the compression.
The Twist: Surprisingly, this works better on CPUs than on GPUs.
- Why? GPUs are like super-highways with massive bandwidth. They don't care about the traffic jam as much. But CPUs are like narrow city streets. By making the "boxes" so small and removing the "assembly" step, FairyFuse clears the traffic jam on the CPU perfectly. On a GPU, the highway is already so wide that making the boxes smaller doesn't help much, and the special "switch-flipping" instructions aren't as efficient there.

Summary

FairyFuse is a new way to run AI on regular computers. It takes a model, shrinks the math down to simple "Add, Subtract, or Ignore" steps, and builds a super-efficient assembly line to process them without ever doing complex multiplication.

The Metaphor:

Old Way: A delivery driver who stops at every house to weigh the package, calculate the tax, and then deliver it. (Slow, heavy math).
FairyFuse: A delivery driver who knows exactly which houses need a package, which need a return, and which need nothing. They drive through the neighborhood at top speed, dropping off or picking up based on a simple list, never stopping to do math.

This allows us to run powerful AI assistants on our laptops and private servers without needing massive, expensive supercomputers.

1. Problem Statement

Large Language Models (LLMs) are increasingly deployed on CPU-only platforms (e.g., edge devices, privacy-sensitive servers) where memory bandwidth is the primary bottleneck for autoregressive token generation, rather than compute power.

Current Limitations: While weight quantization (e.g., 4-bit) reduces memory pressure, existing inference systems (like llama.cpp) still dequantize weights back to floating-point formats and perform standard floating-point multiplications. This wastes the potential savings of low-bit representations.
The Ternary Opportunity: Ternary weights $\{-1, 0, +1\}$ offer a 16× compression ratio over FP32. Theoretically, multiplying by these values requires only conditional addition, subtraction, or a no-op, eliminating multiplications entirely.
The Gap: Previous work (e.g., Fairy2i) demonstrated that complex-valued ternary models can match FP16 quality, but their reference runtimes still used standard floating-point routines, failing to exploit the multiplication-free nature of the weights at the hardware level. Furthermore, naive implementations of complex-valued linear layers (which decompose into 8 real-valued sub-GEMVs) introduce significant overhead due to redundant memory accesses and synchronization.

2. Methodology

The authors present FairyFuse, a specialized inference engine designed to execute ternary-weight LLMs on commodity x86 CPUs without any floating-point multiplications.

A. Multiplication-Free Ternary GEMV

Instead of dequantizing weights or using lookup tables (LUTs), FairyFuse processes packed ternary weights directly:

Packing: Sixteen ternary weights ( $\{-1, 0, +1\}$ ) are packed into a single 32-bit integer (2 bits per weight).
Decoding: Using the BMI2 instruction _pext_u32 (Parallel Bits Extract), the system extracts two 16-bit masks in a single cycle: one for positive weights ( $+1$ ) and one for negative weights ($-1$).
Execution: The system uses AVX-512 masked instructions (_mm512_mask_add_ps and _mm512_mask_sub_ps) to accumulate the activation vector based on the extracted masks.
- If the mask bit is set for $+1$ , it adds the activation.
- If the mask bit is set for $-1$, it subtracts the activation.
- If the weight is $0$, no operation occurs.
Result: The inner loop contains zero floating-point multiplication instructions and zero table lookups, avoiding the cache pressure associated with LUT-based approaches (like T-MAC).

B. Fused Widely-Linear Kernel

Complex-valued LLMs (like those from Fairy2i) use a "widely-linear" transformation that decomposes into eight coupled real-valued GEMVs. A naive approach would run these as eight separate kernels, causing:

Redundant loading of activation vectors.
Repeated decoding of mask patterns.
Intermediate spills to DRAM.
High synchronization overhead.

FairyFuse solves this by fusing all eight sub-GEMVs into a single row-parallel AVX-512 loop using four key optimizations:

Mask Reuse (O1): A single decoded mask pair is applied to both real and imaginary activation paths, amortizing the decode cost.
Input Reuse (O2): Activation vectors are loaded once into registers and shared across all eight sub-GEMVs, halving memory traffic.
Sign-Swap Aliasing (O3): Complex conjugation (flipping the sign of the imaginary part) is handled by precomputing a negated activation vector and swapping pointers, avoiding per-lane negation instructions.
Register-Resident Accumulation (O4): All eight partial sums are kept in AVX-512 registers throughout the loop, eliminating intermediate DRAM writes until the final horizontal reduction.

3. Key Contributions

First Multiplication-Free Ternary Kernel on x86: Implementation of a GEMV kernel that uses only masked AVX-512 additions/subtractions and BMI2 bit-extraction, verified via assembly inspection to contain zero multiplications.
Fused Widely-Linear Execution: A novel kernel design that consolidates the eight sub-GEMVs of complex-valued layers into a single SIMD loop, achieving a 1.55× speedup over unfused execution.
System-Level Validation: Full-stack evaluation on a 7B parameter model demonstrating that extreme quantization (2-bit storage) is most effective on CPUs, not GPUs, due to architectural differences in memory bandwidth and instruction sets.

4. Results

Evaluated on an Intel Xeon 8558P (48 cores, ~200 GB/s bandwidth) against llama.cpp baselines:

Throughput:
- 32.4 tokens/second (tok/s).
- 1.24× faster than llama.cpp Q4_K_M (26.15 tok/s).
- 1.61× faster than llama.cpp Q2_K (20.1 tok/s), despite Q2_K having a slightly smaller memory footprint.
Quality:
- WikiText-2 Perplexity: 5.52 (vs. 5.47 for FP16; Q4_K_M is 5.68).
- Downstream Accuracy: 66.0% (vs. 67.3% for FP16; Q4_K_M is 65.1%).
- The quality is near-lossless, preserving the benefits of the Fairy2i training method.
Kernel Speedup:
- Achieved a 29.6× speedup over FP32 single-threaded execution and up to 54.4× on 48 threads for specific matrix sizes.
- Assembly analysis confirmed zero vmulps or vfmadd instructions in the critical path.
Roofline Analysis (CPU vs. GPU):
- CPUs: Ternary packing shifts the Arithmetic Intensity (AI) from 0.25 (memory-bound) to 8.0, moving the workload closer to the CPU compute ridge, unlocking massive speedups.
- GPUs: Ternary packing actually degrades performance by ~130× on NVIDIA H200 GPUs. GPUs lack efficient equivalents to _pext_u32 (forcing multiple shifts/masks) and have such high memory bandwidth (4.8 TB/s) that the compression offers negligible benefit compared to the overhead of decoding.

5. Significance

Redefining Hardware Targets: The paper challenges the assumption that GPUs are always superior for LLM inference. It demonstrates that for extreme quantization (2-bit/ternary), CPUs are the natural target due to their efficient bitwise instruction sets (BMI2) and the fact that they are memory-bandwidth constrained.
Practical Edge Deployment: By achieving high throughput on commodity CPUs with near-lossless quality, FairyFuse enables the deployment of billion-parameter LLMs on laptops, desktops, and edge servers without discrete GPUs, addressing privacy and latency requirements.
Efficiency Paradigm: It proves that eliminating multiplications entirely (rather than just reducing precision) is a viable path for inference, provided the hardware architecture supports the specific bitwise operations required to decode the weights.

In summary, FairyFuse bridges the gap between algorithmic ternary quantization and hardware execution, delivering a multiplication-free inference engine that outperforms state-of-the-art 4-bit CPU implementations while maintaining high model fidelity.