User-Schedulable Approximations for Quantized Tensor Programs
Quantization lets language models run on edge devices, but it sharply increases the number of tensor kernels a library must maintain: every weight format must be paired with every activation format on every instruction set and GPU, with an encoder and a decoder that agree on the stored bytes. In GGML, the tensor library used by llama.cpp, these kernels are written by hand, and only 8 of the 54 weight-activation pairs it runs on our Arm CPU have a tiled matrix-multiplication kernel.
We extend Halide's separation of algorithm and schedule to the representation of
values. Each approximation is a codec, an encoder paired with a decoder,
composed from reusable units: quantizers, integer representations, bit packers
and layouts. A new directive, approximate_by, applies a codec to one stage of
a program and returns the encoder and decoder as ordinary stages that Halide can
schedule, so both decoders fuse into the register tiles of a matrix product.
Optional contracts, such as a round-trip law, are checked by property tests; the
law exposed an inconsistent block sum in GGML's q8_1.
One algorithm and one schedule library generate 347 kernels for 31 of GGML's and
KleidiAI's formats on Arm CPUs and Apple GPUs, covering 38 weight-activation
pairs for which GGML has no kernel, in 3.7x less code than GGML and KleidiAI. On
an Apple M3 Max, our kernels reach at least 95% of the speed of GGML's
format-specific kernels in 91.0% of the cases that have one, with a median
speedup of 1.13x, and are faster still where GGML falls back to blocked dot
products. Counting Apple's BLAS library, which is usually faster for larger
f32 products, we still reach that threshold in 86.9% of CPU cases. A port to
x86 with Intel's AMX adds 793 lines of code and matches GGML in 83.5% of its
cases.