librarylibs/Quant/src/Quant.xtl
Quant: weights in fewer bits: float rounding, integer and ternary quantization, a ternary layer as additions, blockwise 4-bit and NF4 with double quantization
Import it with an alias of your choice: "qz:" u_se< "Quant". Put libs/Quant/src on XETAL_PATH ("just path"); the reference is libs/Quant/docs. Names with l: are exported; h: names are private to this file.
Every format is simulated: the numbers stay Float, rounded as the format would store them, so a network runs unchanged on the rounded weights. A scale or a threshold is a number for the whole array, or an array shaped as the weights (per layer, per row: the caller chooses).
Floats
ˡf̲loats : Float -> Float -> Float
b f̲loats x: each number rounded to b bits after its leading one,
as a float format keeps it (23 for FP32, 10 for FP16, 7 for bfloat16).
"qz:" u̲se< "Quant"
2.0 qz:f̲loats 1.0 1.3 6.2 1.0 1.25 6.0
ˡf̲loats ← { b x → s ← 2.0 ^ (f̲loat f̲loor (l̲og 0.000000001 m̲ax a̲bs x) ÷ l̲og 2.0) − b s × f̲loat f̲loor 0.5 + x ÷ s }
Integers
ˡs̲nap : Float -> Float -> Float
s s̲nap x: each number rounded to the nearest multiple of the step s.
"qz:" u̲se< "Quant"
0.25 qz:s̲nap 0.1 0.2 0.9 0.0 0.25 1.0
ˡs̲nap ← { s x → s × f̲loat f̲loor 0.5 + x ÷ s }
ˡi̲nt : Num a => a -> Float -> Float
b i̲nt x: symmetric b-bit integers for the whole array: the
largest size becomes 2^(b-1) - 1 steps (127 for 8 bits); the values
come back as Float.
"qz:" u̲se< "Quant"
4 qz:i̲nt 0.875 -0.5 0.1 0.875 -0.5 0.125
ˡi̲nt ← { b x → (('m̲ax r̲/ r̲avel a̲bs x) ÷ (2.0 ^ f̲loat b − 1) − 1.0) ˡs̲nap x }
Ternary: 1.58 bits
ˡc̲ut : Num a => a -> a -> Float
s c̲ut x: -1, 0 or +1 for each number: +1 where it passes s, -1
where it is below -s.
"qz:" u̲se< "Quant"
0.5 qz:c̲ut 0.9 0.2 -0.7 -0.1 1.0 0.0 -1.0 0.0
ˡc̲ut ← { s x → (f̲loat x > s) − f̲loat x < n̲eg s }
ˡt̲ernary : Float -> Float -> Float
t t̲ernary x: c_ut at t times the array's mean size.
ˡt̲ernary ← { t x → (t × ('+ r̲/ r̲avel a̲bs x) ÷ f̲loat t̲ally r̲avel x) ˡc̲ut x }
ˡs̲cale : Float -> Float -> Float
x s̲cale q: the mean size of the numbers ternary codes q keep (q
not 0): the one multiply a ternary layer needs (q times it stands
for x).
"qz:" u̲se< "Quant"
0.9 0.2 -0.7 -0.1 qz:s̲cale 1.0 0.0 -1.0 0.0 0.8
ˡs̲cale ← { x q → ('+ r̲/ r̲avel (a̲bs x) × a̲bs q) ÷ 1.0 m̲ax '+ r̲/ r̲avel a̲bs q }
Additions
ˡa̲dds : Float -> Float -> Float
h a̲dds q: a ternary layer without multiplying: for the input
vector h (an item per row of q) and each column of q, the sum of the
inputs under +1 minus the sum of those under -1. Times the scale, it
is h times the ternary weights.
"qz:" u̲se< "Quant"
1.0 2.0 3.0 qz:a̲dds 3 2 r̲eshape 1.0 0.0 -1.0 1.0 0.0 -1.0 -1.0 -1.0
ˡa̲dds ← { h q → H ← h 'l̲eft t̲able o̲ffsets 2 s̲elect s̲hape q ('+ r̲/ H × f̲loat q = 1.0) − '+ r̲/ H × f̲loat q = -1.0 }
Blocks: 4 bits, a scale per block
ˡb̲locks : Int -> a -> a
k b̲locks x: x's numbers (raveled) as rows of k, a block each; the
count must be a multiple of k.
"qz:" u̲se< "Quant"
2 qz:b̲locks 1.0 -4.0 2.0 0.5 1.0 -4.0 2.0 0.5
ˡb̲locks ← { k x → n ← t̲ally r̲avel x 0 ≠ n m̲od k ? ⎕P̲ANIC "qz:b_locks: " c̲at (f̲ormat n) c̲at " numbers are not blocks of " c̲at f̲ormat k ((n d̲iv k) c̲at k) r̲eshape r̲avel x }
ˡa̲bsmax : Num a => Int -> a -> a
k a̲bsmax x: each block's largest size, its scale (absmax).
"qz:" u̲se< "Quant"
2 qz:a̲bsmax 1.0 -4.0 2.0 0.5 4.0 2.0
ˡa̲bsmax ← { k x → 'm̲ax r̲/₂ a̲bs k ˡb̲locks x }
ˡu̲niformCodes : Num a => (a, Int) -> Float -> (Float, Float)
(b, k) u̲niformCodes x: blockwise symmetric b-bit integers: each
block divided by its scale, its absmax over 2^(b-1) - 1 (7 for 4
bits), rounded and clipped to -7 .. 7: (codes, scales), the codes as
Floats a row per block.
"qz:" u̲se< "Quant"
(q, s) ← (4, 2) qz:u̲niformCodes 1.0 -4.0 2.0 0.5
q
2.0 -7.0
7.0 2.0
ˡu̲niformCodes ← { (b, k) x → top ← (2.0 ^ f̲loat b − 1) − 1.0 s ← (k ˡa̲bsmax x) ÷ top B ← k ˡb̲locks x S ← s 'l̲eft t̲able o̲ffsets k (top m̲in (n̲eg top) m̲ax f̲loat f̲loor 0.5 + B ÷ 0.000000000001 m̲ax S, s) }
ˡu̲niform : Num a => (a, Int) -> Float -> Float
(b, k) u̲niform x: x through blockwise b-bit integers and back
(codes times their block's scale), shaped as x: what a uniform 4-bit
base computes with.
"qz:" u̲se< "Quant"
(4, 2) qz:u̲niform 1.0 -4.0 2.0 0.5 1.1428571428571428 -4.0 2.0 0.5714285714285714
ˡu̲niform ← { (b, k) x → (q, s) ← (b, k) ˡu̲niformCodes x (s̲hape x) r̲eshape q × s 'l̲eft t̲able o̲ffsets k }
NF4: 16 levels at the normal's quantiles
nf4 : Float
The NF4 codebook as QLoRA publishes it (Dettmers et al. 2023, appendix E; bitsandbytes' create_normal_map, float32), derived again by c_odebook and checked against it in the tests.
nf4 ← -1.0 -0.6961928009986877 -0.5250730514526367 -0.39491748809814453 -0.28444138169288635 -0.18477343022823334 -0.09105003625154495 0.0 0.07958029955625534 0.16093020141124725 0.24611230194568634 0.33791524171829224 0.44070982933044434 0.5626170039176941 0.7229568362236023 1.0
ʰe̲rf : Float -> Float
erf by its series, 80 terms: 2/sqrt(pi) sum (-1)^n z^(2n+1) / (n! (2n+1)); to 1e-15 for |z| up to about 3.
ʰe̲rf ← { z → (_, _, t) ← 80 '{ (n, a, t) → (n + 1.0, n̲eg a × z × z ÷ n + 1.0, t + a ÷ 1.0 + 2.0 × n) } p̲ower (0.0, z, 0.0) t × 2.0 ÷ s̲qrt 3.141592653589793 }
ʰh̲alf : Float -> (Float, Float) -> (Float, Float)
One halving of (lo, hi) toward the x where Phi(x) is p.
ʰh̲alf ← { p (lo, hi) → m ← 0.5 × lo + hi (ˡp̲hi m) < p ? (m, hi) (lo, m) }
ʰs̲pan : (Float, Float) -> Int -> Float
n points from a to b, both included.
ʰs̲pan ← { (a, b) n → a + (b − a) × (f̲loat (r̲ange n) − 1) ÷ f̲loat n − 1 }
ˡp̲hi : Float -> Float
p̲hi x: the standard normal's cumulative distribution, 1/2 (1 +
erf(x / sqrt 2)), erf by its series.
"qz:" u̲se< "Quant"
qz:p̲hi 1.0 0.8413447460685428
ˡp̲hi ← { x → 0.5 × 1.0 + ʰe̲rf x ÷ s̲qrt 2.0 }
ˡq̲uantile : Float -> Float
q̲uantile p: the normal's inverse, the x with Phi(x) = p, by 60
halvings of -4 .. 4 (to 1e-15 of p in 0.00004 .. 0.99996).
"qz:" u̲se< "Quant"
qz:q̲uantile 0.975 1.959963984540054
ˡq̲uantile ← { p → (lo, hi) ← 60 '{ q → p ʰh̲alf q } p̲ower (-4.0, 4.0) 0.5 × lo + hi }
ˡc̲odebook : Float -> Float
c̲odebook offset: NF4's 16 levels, made as QLoRA makes them: the
normal's quantiles at 9 points from offset to 1/2 (8 positive) and at
8 (7 negative, mirrored), with 0, scaled so the largest is 1. Each
level is as likely as the next for normal weights, and 0 is exact.
QLoRA's offset is 0.9677083, the mean of 1 - 1/(2 15) and 1 - 1/(2 16).
"qz:" u̲se< "Quant"
8 t̲ake qz:c̲odebook 0.9677083 -1.0 -0.6961928906037205 -0.5250730386952299 -0.39491749069931015 -0.2844413576181078 -0.18477343519288897 -0.0910499921442795 0.0
ˡc̲odebook ← { offset → pos ← 'ˡq̲uantile e̲ach -1 d̲rop (offset, 0.5) ʰs̲pan 9 neg ← 'ˡq̲uantile e̲ach -1 d̲rop (offset, 0.5) ʰs̲pan 8 v ← s̲ort pos c̲at 0.0 c̲at n̲eg neg v ÷ 'm̲ax r̲/ v }
ˡn̲f4Codes : Int -> Float -> (Int, Float)
k n̲f4Codes x: each block divided by its absmax, then each number's
nearest NF4 level, by its index 1 .. 16: (codes, scales), the codes
a row per block.
"qz:" u̲se< "Quant"
(q, s) ← 2 qz:n̲f4Codes 1.0 -4.0 2.0 0.5
q
11 1
16 11
ˡn̲f4Codes ← { k x → s ← k ˡa̲bsmax x B ← k ˡb̲locks x N ← B ÷ 0.000000000001 m̲ax s 'l̲eft t̲able o̲ffsets k ((s̲hape N) r̲eshape '{ v → f̲irst g̲rade a̲bs v − nf4 } e̲ach r̲avel N, s) }
ˡn̲f4Values : (Int, Float) -> Float
n̲f4Values (q, s): NF4 codes back to numbers, each code's level
times its block's scale (raveled; the codes a row per block).
"qz:" u̲se< "Quant"
qz:n̲f4Values 2 qz:n̲f4Codes 1.0 -4.0 2.0 0.5 0.9844492077827454 -4.0 2.0 0.4922246038913727
ˡn̲f4Values ← { (q, s) → r̲avel ((s̲hape q) r̲eshape (r̲avel q) s̲elect nf4) × s 'l̲eft t̲able o̲ffsets 2 s̲elect s̲hape q }
ˡn̲f4 : Int -> Float -> Float
k n̲f4 x: x through NF4 and back (each code's level times its
block's scale), shaped as x.
"qz:" u̲se< "Quant"
2 qz:n̲f4 1.0 -4.0 2.0 0.5 0.9844492077827454 -4.0 2.0 0.4922246038913727
ˡn̲f4 ← { k x → (s̲hape x) r̲eshape ˡn̲f4Values k ˡn̲f4Codes x }
Double quantization: the scales in 8 bits
ˡd̲ouble : Int -> Float -> Float
k2 d̲ouble s: the block scales themselves quantized, as QLoRA does
to save their bytes: their mean taken off, then blockwise symmetric
8-bit integers over blocks of k2 scales (the last block made up with
zeros, which change no block's absmax), and back, the mean added.
(QLoRA's second level is an 8-bit float; 8-bit integers here, the
same bytes.)
"qz:" u̲se< "Quant"
2 qz:d̲ouble 0.5 0.25 1.0 0.75 0.5009842519685039 0.25 1.0 0.7490157480314961
ˡd̲ouble ← { k2 s → n ← t̲ally s m ← ('+ r̲/ s) ÷ f̲loat n pad ← (k2 × c̲eiling (f̲loat n) ÷ f̲loat k2) − n m + n t̲ake (8, k2) ˡu̲niform (s − m) c̲at pad r̲eshape 0.0 }
ˡn̲f4Double : Int -> (Int, Float) -> Float
k2 n̲f4Double (k, x): NF4 with its scales double-quantized: x
through NF4 and back, the scales first through d_ouble.
ˡn̲f4Double ← { k2 (k, x) → (q, s) ← k ˡn̲f4Codes x (s̲hape x) r̲eshape ((s̲hape q) r̲eshape (r̲avel q) s̲elect nf4) × (k2 ˡd̲ouble s) 'l̲eft t̲able o̲ffsets k }
Bits
ˡb̲its : (Num a, Num b) => (a, a) -> b -> Float
(k, k2) b̲its 4: bits a weight takes: 4 for its code plus its
block's scale shared by k weights, at 32 bits; then with double
quantization, the scale at 8 bits plus a 32-bit scale and mean shared
by k2 scales. QLoRA's k 64 and k2 256: 4.5, and 4.129 (QLoRA's
paper counts 4.127, the mean left out).
"qz:" u̲se< "Quant"
(64, 256) qz:b̲its 4 4.5 4.12890625
ˡb̲its ← { (k, k2) b → (f̲loat b) + (32.0 ÷ f̲loat k) c̲at (8.0 ÷ f̲loat k) + 64.0 ÷ f̲loat k × k2 }