User-Schedulable Approximations for Quantized Tensor Programs
Organizations: Adobe Research, USA
Abstract
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.
Figures & tables
| Directive | The per-block dot | Step (rule) |
|---|---|---|
| eager_inline | the decoded product, in f32 | |
| hoist_invariants | , | scales outside the reduction ( Hoist ) |
| change_type(Int(32)) | , in i32 | an integer dot ( Widen , Retype ) |
| cast back, exact for this block | ||
| instruction selection | by sdot ( smmla with i8mm) | 8-bit products into 32-bit lanes |
| How | Guarantees |
|---|---|
| Checked when a pipeline is built | Types, dimensions and component names; the chain of declared ranges (C2); derived-component matching (symbolic) and which components may declare a bound (§ 6.2 ); change_type ’s interval proof (conservative: it may reject a safe program, with a compile error); hoist_invariants ’ invariance and empty-domain guard (built conservatively for float sums, as the target is not yet known). |
| Tested, on sampled or exhaustive inputs | The round-trip law, losslessness, bounds, ranges, derived components, and closed() , which catches a decoder that reads the original tensor instead of its encoding (the seven grid formats skip it, as their embedded tables count as foreign buffers; Appendix M ); bytes against GGML’s and KleidiAI’s; kernels against an f64 oracle (§ 7.3 ). |
| Assumed: user obligations | Supported inputs (§ 3.1 ); sever ’s buffers; the encoders given to TrustedInverse ; derived components’ (also tested); unsafe accumulation; the multiples of 16 that the scaled q4_0 variant needs (§ B.1 ; checked by byte comparison). |
| Extension | Ours | GGML |
|---|---|---|
| format sharing units (q5_1, given q5_0) | 5 format-definition lines, 2 rows | 264 |
| K-quant sharing a quantizer (q5_K, given q4_K) | 15 format-definition lines, 3 rows, 3 knobs | 1297 (697 repack) |
| format with new units (mxfp4) | 68 format-definition lines, 3 rows | 469 |
| format with a new quantizer (q2_0) | 32 format-definition lines, 3 rows | 225 |
| weight layout (q4_0 ) | 1 row | 558 + 58 shared |
| K-quant layout (q6_K , given q4_K’s) | 8 format-definition lines, 1 row, 1 knob | 373 |
| Apple M3 Max | Xeon w5-2455X | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Neon | Accelerate | Metal | x86 | |||||||||
| Cases | Med. | Cases | Med. | Cases | Med. | Cases | Med. | |||||
| Format-specific | 311 | 1.10 | 96.8% | 311 | 1.07 | 86.5% | 392 | 1.13 | 86.5% | 789 | 1.11 | 73.9% |
| Blocked-dot | 1338 | 1.94 | 99.3% | 1338 | 1.73 | 87.0% | — | — | — | 831 | 1.64 | 92.7% |
| All | 1649 | 1.77 | 98.8% | 1649 | 1.49 | 86.9% | 392 | 1.13 | 86.5% | 1620 | 1.23 | 83.5% |
Appendix figures & tables20 assets
Supplementary material from the paper’s appendix.
Appendix
| Area | Change |
|---|---|
| Approximation library | Func::approximate_by replaces a Func’s uses by the decoding of its encoding. Combinators Compose , Parallel , Choose , Pointwise (with Pointwise::affine for affine code maps), Identity and TrustedInverse ; derived components ( Derive ). Lossless layout units: BlockReshape (also over index tiles), StructLayout (with port_field ), BitFields and its shorthand PlanarFieldPack , SplitBits , Permute , LittleEndianScalarPack . Named, typed components with declared value ranges, component tags, signatures, and static checks of types and ranges. encode_funcs / decode_funcs expose each stage’s Funcs for scheduling. |
| Types | Struct types: records of mixed-type fields, loaded and stored whole, which StructLayout uses for block records. |
| Pipelines | Pipeline::sever replaces the computation of given Funcs by fresh inputs of the same shape, so that work such as encoding static weights moves out of the kernel. Func::precompute evaluates a constant Func at compile time and embeds the result as a constant buffer. |
| Directives | eager_inline inlines Funcs at schedule time, so that later directives see the inlined expression. hoist_invariants factors loop-invariant multiplicands out of a semiring reduction; invariance is decided modulo the reduction variables’ bounds, through shifts of bit fields, exact widenings and inlined masks. change_type retypes a reduction after checking that the new type cannot overflow; its unsafe form fuses a float sum of products into multiply-adds. vectorize(v, n, VectorizeIn::SWAR) vectorizes within a general-purpose register. |
| Queries and helpers | Func::is_precomputed , Stage::is_order_independent , Stage::value / values . Schedule helpers vectorize_all_stages , unroll_all_stages , eager_inline_all , in_callers and clone_in_callers . |
| Lowering | rfactor : no split-tail guard on the merge stage; tail clamps partitioned out of the steady state. Simplifier rules for divisions of scaled sums; a promise’s likely tag is dropped with the promise. Dense canonical forms and alignment-aware division of multi-dimensional ramps. Bounds of select . A store no longer clobbers a store of another type. Prefetches of struct-typed buffers. |
| Format | bpw | Composition (encode order, after BlockReshape ) | Layouts |
| Legacy, block of 32 | |||
| q4_0 | 4.5 | Type0 (4); integers: affine (offset 8) or twos (4); PlanarFieldPack (4) & fp16 | soa, , , , |
| q4_1 | 5 | Type1 (4); affine (unsigned); PlanarFieldPack (4) & fp16 & fp16 | , |
| q5_0 | 5.5 | Type0 (5); integers: SplitBits (4); PlanarFieldPack (4) & [ affine ; PlanarFieldPack (1), tabulated ] & fp16 | |
| q5_1 | 6 | as q5_0 with Type1 (5), plus fp16 for the minimum | |
| q8_0 | 8.5 | Q8_0 ; fp16 | soa, , , |
| Combinators, reshaping, layout and bit packing | Quantizers, then value maps | ||
|---|---|---|---|
| Unit | Meaning | Unit | Meaning |
| Compose | sequential composition; decode runs the stages’ decodes in reverse | Type0 | , the signed extreme, ; integers rounded half up |
| Parallel | a codec per component, side by side (not parallel execution) | Type1 | affine: , and the minimum |
| TrustedInverse | an external encoder paired with a decoder; nothing declared relates them | Q8_0 | , integers rounded |
| Inverse | a unit with its encode and decode swapped | KAffine , Q3K , Q6K | K-quant search: sub-block scales (and mins) fitted, then quantized against super-block scales |
| Derive | appends a component computed from other components; decode drops it | Q8K | (as in f32), integers rounded |
| Estimator | all | CPU | Metal | format- | blocked | median | below | Metal |
| (2041) | (1649) | (392) | specific (703) | dot (1338) | 0.95 | per sample | ||
| per-case fastest layout: | ||||||||
| first run | 96.5% | 98.8% | 86.5% | 91.3% | 99.2% | 1.56 | 72 | 82.9% |
| minimum time (reported) | 96.7% | 99.2% | 86.5% | 91.5% | 99.5% | 1.57 | 67 | 84.9% |
| median time | 96.7% | 99.1% | 86.7% | 91.7% | 99.3% | 1.56 | 67 | 85.5% |
| held-out-shape layout (the headline): | ||||||||
| Column | cases | per-sample | 0.95 | matched | 0.95 |
|---|---|---|---|---|---|
| GEMV | 72 | 0.86–1.72 (1.17) | 8 | 0.71–1.63 (1.00) | 28 |
| 18 | 1.02–1.32 (1.22) | 0 | 0.71–1.01 (0.78) | 16 | |
| 72 | 0.49–3.48 (1.01) | 30 | 0.68–3.76 (1.23) | 22 | |
| 124 | 0.91–2.60 (1.13) | 9 | 1.01–2.34 (1.30) | 0 | |
| 124 | 0.79–1.16 (1.00) | 12 | 0.78–1.21 (1.10) | 3 |
| Weights | T1 | T10 | T1 | T10 |
|---|---|---|---|---|
| legacy | 0.50–1.23 (0.61) 16 | 1.99–6.17 (3.22) | 0.08–0.19 (0.10) 20 | 0.60–1.53 (0.81) 12 |
| K-quants | 0.49–1.48 (0.61) 16 | 1.93–4.51 (3.08) | 0.08–0.18 (0.10) 20 | 0.56–1.12 (0.73) 16 |
| grid IQ | 0.27–0.68 (0.54) 28 | 1.17–2.31 (1.64) | 0.05–0.09 (0.06) 28 | 0.34–0.58 (0.43) 28 |
| codebook | 0.76–2.06 (1.33) 8 | 1.79–5.73 (3.33) | 0.08–0.24 (0.15) 16 | 0.43–1.43 (0.88) 8 |
| low-bit | 0.62–1.10 (0.75) 12 | 2.18–4.94 (3.54) | 0.09–0.15 (0.12) 16 | 0.69–1.25 (0.93) 10 |
| f16, bf16 | 0.15–0.69 (0.38) 8 | 1.00–2.52 (1.67) | 0.03–0.09 (0.06) 8 | 0.30–0.59 (0.44) 8 |
| f32 accumulation | f16 accumulation | all | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Mutant | fam. | runs | T | S | runs | T | G | S | runs | T | any |
| drop last block | 6 | 72 | 72/72 | 48/48 | 12 | 4/12 | 12/12 | 8/8 | 84 | 76/84 | 84/84 |
| row shift | 6 | 72 | 72/72 | 48/48 | 12 | 9/12 | 12/12 | 8/8 | 84 | 81/84 | 84/84 |
| tail row ( ) | 6 | 72 | 72/72 | 48/48 | 12 | 7/12 | 12/12 | 8/8 | 84 | 79/84 | 84/84 |
| tail column ( ) | 6 | 54 | 48/54 | 36/36 | 9 | 4/9 | 9/9 | 6/6 | 63 | 52/63 | 63/63 |
| sign flip | 6 | 72 | 72/72 | 48/48 | 12 | 6/12 | 12/12 | 8/8 | 84 | 78/84 | 84/84 |
| Formats | Properties | Checks | Trials | Values/trial |
|---|---|---|---|---|
| q4_0, q4_1, q5_0, q5_1 , q8_0, q8_1 | bound, ranges, closure | 180 | 1440 | 32768 |
| q8_1; 5 interleaved layouts | law, derived block sum, closure; the law | 13 | 44 | 32768+ |
| mxfp4, nvfp4 | bound, ranges, closure, law | 71 | 562 | 32768+ |
| iq4_nl, iq4_xs | bound, ranges, closure | 12 | 36 | 65536 |
| q8_K, q2_K–q6_K | bound, ranges, closure | 54 | 162 | 65536 |
| tq1_0, tq2_0, q1_0, q2_0 | bound, ranges, closure; q1_0 also the law | 29 | 84 | 65536 |
| Formats | Law | Where, or why not | Evidence |
|---|---|---|---|
| f16, bf16 | exact | every f32 | exhaustive |
| q4_0, q5_0, q8_0, q8_1 | on domain | f16 scale finite, nonzero | exhaustive |
| q4_1, q5_1 | on domain | finite f16 , ; not where f32 absorbs integers | exhaustive |
| tq1_0, tq2_0, q2_0 | on domain | f16 scale finite, nonzero | exhaustive |
| q1_0 | on domain | not where a negative value’s scale underflows | exhaustive |
| mxfp4 | on domain | exhaustive |
| family | reduction | fixed by the stored fields because | tested: for |
|---|---|---|---|
| q4_0, q5_0 | signed max; | code (value ) present; exact, so | all rotations of |
| q8_0 | present; exact | all 1020 rotations of with a | |
| q8_1 | q8_0; | as q8_0; is a function of , both restored for every | as q8_0, compared on a second round trip |
| q4_1, q5_1 | , | codes present; is monotone: , | all all finite rotations of ; |
| tq1_0, tq2_0, q2_0 | present; | all 3 rotations of | |
| q1_0 | none: for every code, and the sum is exact | all both alternations of |
| Kernel | cases | default matches | speedup of tuned over default (median) |
|---|---|---|---|
| vec_dot | 14 | 8 | 1.06 |
| GEMV (T1, T10) | 56 | 41 | 1.02 |
| GEMM ( , 512) | 56 | 54 | 1.01 |
| all | 126 | 103 | 1.02 |
| (a) Single row: vec_dot and GEMV | |||||
|---|---|---|---|---|---|
| Weights | Activations | GGML | vec_dot | GEMV T1 | GEMV T10 |
| legacy | paired | C | 0.99–1.04 (1.01) | 1.00–2.13 (1.74) | 0.95–2.65 (1.49) |
| f32 | C, R, K | n/a | 0.99–2.13 (1.08) | 1.01–2.28 (1.11) | |
| K-quants | paired | C | 1.01–1.24 (1.07) | 1.02–1.45 (1.15) | 1.01–2.04 (1.21) |
| f32 | R, C | n/a | 1.02–1.25 (1.10) | 0.88–1.75 (1.13) 3 | |
| grid IQ | paired | C | 0.99–1.29 (1.19) | 0.99–1.30 (1.15) | 0.97–1.35 (1.13) |
| Weights | Activations | GEMV | |||
|---|---|---|---|---|---|
| legacy | f32 | 0.72–1.63 (1.04) 6 | 0.74–1.25 (0.96) 9 | 1.06–2.29 (1.33) | 1.01–1.21 (1.12) |
| f16 | n/a | n/a | 1.07–2.34 (1.32) | 1.02–1.20 (1.09) | |
| K-quants | f32 | 0.76–1.38 (0.93) 11 | 0.68–3.76 (0.87) 12 | 1.02–2.30 (1.27) | 1.05–1.20 (1.13) |
| f16 | n/a | n/a | 1.04–2.34 (1.28) | 1.04–1.19 (1.12) | |
| codebook | f32 | 0.81–1.34 (1.23) 3 | 1.19–3.12 (2.49) | 1.02–2.29 (1.28) | 1.01–1.14 (1.07) |
| f16 | n/a | n/a | 1.06–2.29 (1.30) | 1.03–1.13 (1.06) |
| T12 | T1 | ||||||
|---|---|---|---|---|---|---|---|
| Stratum | GGML’s path | Cases | Median | Cases | Median | ||
| format-specific | AMX | 101 | 1.21 | 80.2% | 91 | 0.95 | 49.5% |
| repacked | 38 | 1.80 | 71.1% | 30 | 1.77 | 66.7% | |
| tiled VNNI | 273 | 1.14 | 79.1% | 202 | 1.12 | 76.2% | |
| all GEMM/GEMV | 412 | 1.16 | 78.6% | 323 | 1.07 | 67.8% | |
| vec_dot | – | – | – | 54 | 1.00 | 74.1% | |
| format-specific | blocked-dot | ||||||
|---|---|---|---|---|---|---|---|
| Threads | Cases | Median | Cases | Median | |||
| T12 | 1 | 28 | 1.10 | 53.6% | 188 | 1.08 | 86.2% |
| 8 | 128 | 1.33 | 92.2% | 88 | 2.51 | 93.2% | |
| 32 | 128 | 1.23 | 93.8% | 88 | 3.42 | 100.0% | |
| 512 | 128 | 0.97 | 55.5% | 88 | 5.08 | 100.0% | |
| T1 | 1 | 35 | 0.94 | 48.6% | 181 | 1.09 | 87.8% |
| Directive | Preserves | Obligation (who) |
|---|---|---|
| Halide’s other directives, eager_inline | the f32 program | none |
| sever | the f32 program | the substituted buffers hold the cut computation’s values, or an encoding meeting the codec’s contracts (user; unchecked) |
| rfactor , hoist_invariants | value over ; f32 rounding, overflow, underflow and NaNs may change | bound-based hoists guarded by require() ; write-backs not preserving the identity guarded by a nonempty domain, for float sums only under strict floats (compiler) |
| change_type , safe | value over , computed exactly; rounds once back | exact-integer terms, no overflow (interval proof; run-time check for symbolic extents) |
| change_type , unsafe ( Accumulate only) | nothing: an approximation | Accumulate ’s bound (§ L.2 ); no overflow, normal range (user, unchecked) |
| approximate_by(codec) | nothing: values become | the codec’s declared contracts (user; tested) |
| \begin{array}[]{@{}l@{\quad}l@{}}\textsc{Hoist}\hfil\hskip 8.50012pt&f(\bar{v})\oplus\!\!=s\otimes t\;\leadsto\;g(\bar{v})=1_{\oplus};\ \ g(\bar{v})\oplus\!\!=t;\ \ f(\bar{v})=f(\bar{v})\oplus(s\otimes g(\bar{v}))\\ \text{\emph{over} }\mathbb{R}\hfil\hskip 8.50012pt&\text{if }s\text{ is free of }R\text{ and }(\oplus,\otimes)\in\{(+,\times),(\min,+),(\max,+),(\vee,\wedge),(\wedge,\vee)\}\\ \hfil\hskip 8.50012pt&\text{write-back only where }R\neq\emptyset,\text{ unless }s\otimes 1_{\oplus}=1_{\oplus};\ \min,\max\text{ only where }{+}\text{ cannot wrap}\\[4.0pt] \textsc{Field}\hfil\hskip 8.50012pt&\textstyle\sum_{R}t\bigl[(x\gg s)\,\&\,m\bigr]\;\leadsto\;\bigl(\sum_{R}t\bigl[(x\gg(s-\delta))\,\&\,(m\ll\delta)\bigr]\bigr)\gg\delta\\ \text{\emph{exact}}\hfil\hskip 8.50012pt&\delta=\mathrm{select}(0\leq s\leq k,\,s,\,0),\text{ if }s\text{ is free of }R\text{ and }|R|\text{ is constant}\\ \hfil\hskip 8.50012pt&\text{and }k\text{ is the largest shift with }[0,|R|]\cdot\mathcal{I}\bigl(t[(x\gg(s-k))\,\&\,(m\ll k)]\bigr)\subseteq L_{\mathrm{type}(t)}\\[4.0pt] \textsc{Split}\hfil\hskip 8.50012pt&\mathrm{cast}_{W}(a+b)\;\leadsto\;\mathrm{cast}_{W}(a)+\mathrm{cast}_{W}(b)\\ \text{\emph{exact}}\hfil\hskip 8.50012pt&\text{if }W\text{ represents }T=\mathrm{type}(a+b)\text{ and }\mathcal{I}(a)+\mathcal{I}(b)\subseteq T\\[2.0pt] \hline\cr\hfil\hskip 8.50012pt\\[-8.0pt] \textsc{Widen}\hfil\hskip 8.50012pt&\mathrm{cast}_{F}(a)\odot\mathrm{cast}_{F}(b)\;\leadsto\;\mathrm{cast}_{F}(\mathrm{widening}_{\odot}(a,b))\\ \text{\emph{exact}}\hfil\hskip 8.50012pt&\text{if }a,b:T\text{ integer},\ F\text{ represents }T\text{ and }\odot\in\{+,-,\times\}\\[4.0pt] \textsc{Retype}\hfil\hskip 8.50012pt&f(\bar{v})=i;\ f(\bar{v})\oplus\!\!=x\;\leadsto\;f^{\prime}(\bar{v})=\mathrm{cast}_{t}(i);\ f^{\prime}(\bar{v})\oplus\!\!=x^{\prime};\ f=\mathrm{cast}(f^{\prime})\\ \text{\emph{over} }\mathbb{R}\hfil\hskip 8.50012pt&\text{if }\mathcal{I}(i),\,\mathcal{I}(x)\subseteq L_{t}\text{, float leaves of }i,x\text{ are whole-number constants or int casts,}\\ \hfil\hskip 8.50012pt&\text{and every float }{+},{-},{\times}\text{ in them stays within its type's exact integers}\\ \hfil\hskip 8.50012pt&\text{and, for }\oplus\in\{+,-\},\ \mathcal{I}(i)\pm[0,|R|]\cdot\mathcal{I}(x)\subseteq L_{t}\ \text{(symbolic }|R|\text{: checked at run time)}\end{array} |
| Quantizer | formats | decoded value | sensitivities |
|---|---|---|---|
| Type0 , Q8_0 , Sign , | q4_0, q5_0, q8_0, q8_1, | ||
| Ternary , Q2 , IQ4 (32) | q1_0, tq1_0, tq2_0, q2_0, iq4_nl | ||
| Type1 | q4_1, q5_1 | , | |
| KAffine | q2_K, q4_K, q5_K | , | |
| Q3K , Q6K , IQ4 (256) | q3_K, q6_K, iq4_xs | ||
| ScaledCodes | grid IQ (7) | (no bound declared) |
| Check | Law | When |
| types, dimensions, component names | a stage’s components are what the next stage expects | build |
| check_ranges | each lossless stage’s declared input range contains the declared output range of the stage before it (C2) | build |
| derived-component match | a term equals a component’s definition over (§ 6.2 ) | build |
| idempotent_requantize(tol) | for , the round-trip law; integer components exactly, float components within tol | sampled |
| lossless() | , bit for bit | sampled |
| within_declared_bound() | sampled |
LLM Inference Acceleration
LLM inference acceleration develops algorithms and systems that reduce language-model latency, memory use, and serving cost while preserving output quality.
See all 1,228 papers