Skip to main content
Back to timeline
arXivSource publication:

Quantized tensor kernels stop being hand-written per format: one algorithm and one schedule library generate 347 kernels, including 38 weight–activation pairs GGML lacks

Synopsis

Tensor libraries such as GGML hand-write a kernel for every weight format, activation format and instruction set; on the Arm CPU the authors tested, only 8 of the 54 weight–activation pairs GGML runs have a tiled matrix-multiplication kernel. The authors extend Halide's separation of algorithm and schedule to the representation of values: a codec describes a quantized format, and a new approximate_by directive turns its encoder and decoder into ordinary schedulable stages. One matrix-product algorithm and one schedule library generate 347 kernels covering 31 GGML and KleidiAI formats, including 38 weight–activation pairs for which GGML has no kernel.

Source-provided article image: User-Schedulable Approximations for Quantized Tensor Programs
arXiv

Interpretation

Encoding and decoding a quantized format can now be scheduled as ordinary computation instead of hand-written per format. GGML writes these combinations by hand, which the authors count at 16111 nonblank, noncomment lines for the formats studied, KleidiAI kernels included; even so, only 8 of its 54 CPU weight–activation pairs have tiled kernels, and the rest compute one block dot product at a time. One matrix-product algorithm plus one schedule library generate 347 kernels for 31 formats, covering 38 weight–activation pairs for which GGML has no kernel, with no additional schedule code.

A format is decomposed into reusable codec units, and the encoder and decoder come from one composition, so the two halves need not be kept in sync by hand. A codec composes units such as quantizers, integer representations, bit packers and layouts; the new approximate_by directive inserts a codec in front of a computation stage and returns its encoder and decoder as ordinary stages, so weights are encoded offline, activations inside the kernel, and both decoders are fused into the register tile of a matrix product. On an Apple M3 Max, against GGML's format-specific kernels, these kernels reach at least 95% of GGML's speed in 91.0% of the cases that have one, with a median speedup of 1.13; counting GGML's path through Accelerate as part of GGML, 86.9% of CPU cases still reach that threshold.

An optional round-trip law turns format consistency into a testable property, and it exposed an inconsistency in q8_1's block sum. The law requires that re-encoding decoded values reproduces their encoding; under it, 25–27% of GGML's q8_1 blocks of normally distributed inputs changed on decode and re-encode, and two blocks with the same integers and scale had different sums. The cause is that GGML computes the sum from the scale before rounding the scale to f16 for storage; the new composition rounds the scale first and derives the sum from the stored scale and integers, the one deliberate departure from GGML's bytes.

Perspective

The demonstrated scope is matrix-multiplication kernels on Arm CPUs and Apple GPUs, plus one x86 port using Intel AMX; the measurements time kernels rather than end-to-end inference, on one M3 Max and one x86 workstation. The authors note that for larger f32 matrix products GGML can instead dequantize the weights and call Apple's BLAS library Accelerate, which is usually faster than these kernels.

The round-trip law is optional, the K-quant search encoders fail it, and q8_K and qai8dx round-trip their scales only within 1–2 ulp; error bounds are derived by hand and tested, and the compiler neither infers nor checks them. The authors also list cases that remain below GGML's speed, attributing them to schedules, Halide code generation or its runtime rather than to the representation.