sourcelibs/Quant/src/Quant.xtl

1⍝│ Quant: weights in fewer bits: float rounding, integer and ternary quantization, a ternary layer as additions, blockwise 4-bit and NF4 with double quantization 2⍝│ 3⍝│ Import it with an alias of your choice: "qz:" u_se< "Quant". 4⍝│ Put libs/Quant/src on XETAL_PATH ("just path"); the reference is libs/Quant/docs. 5⍝│ Names with l: are exported; h: names are private to this file. 6⍝│ 7⍝│ Every format is simulated: the numbers stay Float, rounded as the 8⍝│ format would store them, so a network runs unchanged on the rounded 9⍝│ weights. A scale or a threshold is a number for the whole array, or 10⍝│ an array shaped as the weights (per layer, per row: the caller 11⍝│ chooses). 12 13⍝━━ Floats 14 15⍝│ b f̲loats x: each number rounded to b bits after its leading one, 16⍝│ as a float format keeps it (23 for FP32, 10 for FP16, 7 for bfloat16). 17⍝│ >> "qz:" u_se< "Quant" 18⍝│ >> 2.0 qz:f_loats 1.0 1.3 6.2 19⍝│ 1.0 1.25 6.0 20ˡf̲loats ← { b x → 21 s ← 2.0 ^ (f̲loat f̲loor (l̲og 0.000000001 m̲ax a̲bs x) ÷ l̲og 2.0) − b 22 s × f̲loat f̲loor 0.5 + x ÷ s 23} 24 25⍝━━ Integers 26 27⍝│ s s̲nap x: each number rounded to the nearest multiple of the step s. 28⍝│ >> "qz:" u_se< "Quant" 29⍝│ >> 0.25 qz:s_nap 0.1 0.2 0.9 30⍝│ 0.0 0.25 1.0 31ˡs̲nap ← { s x → s × f̲loat f̲loor 0.5 + x ÷ s } 32 33⍝│ b i̲nt x: symmetric b-bit integers for the whole array: the 34⍝│ largest size becomes 2^(b-1) - 1 steps (127 for 8 bits); the values 35⍝│ come back as Float. 36⍝│ >> "qz:" u_se< "Quant" 37⍝│ >> 4 qz:i_nt 0.875 -0.5 0.1 38⍝│ 0.875 -0.5 0.125 39ˡi̲nt ← { b x → (('m̲ax r̲/ r̲avel a̲bs x) ÷ (2.0 ^ f̲loat b − 1) − 1.0) ˡs̲nap x } 40 41⍝━━ Ternary: 1.58 bits 42 43⍝│ s c̲ut x: -1, 0 or +1 for each number: +1 where it passes s, -1 44⍝│ where it is below -s. 45⍝│ >> "qz:" u_se< "Quant" 46⍝│ >> 0.5 qz:c_ut 0.9 0.2 -0.7 -0.1 47⍝│ 1.0 0.0 -1.0 0.0 48ˡc̲ut ← { s x → (f̲loat x > s) − f̲loat x < n̲eg s } 49 50⍝│ t t̲ernary x: c_ut at t times the array's mean size. 51ˡt̲ernary ← { t x → (t × ('+ r̲/ r̲avel a̲bs x) ÷ f̲loat t̲ally r̲avel x) ˡc̲ut x } 52 53⍝│ x s̲cale q: the mean size of the numbers ternary codes q keep (q 54⍝│ not 0): the one multiply a ternary layer needs (q times it stands 55⍝│ for x). 56⍝│ >> "qz:" u_se< "Quant" 57⍝│ >> 0.9 0.2 -0.7 -0.1 qz:s_cale 1.0 0.0 -1.0 0.0 58⍝│ 0.8 59ˡs̲cale ← { x q → ('+ r̲/ r̲avel (a̲bs x) × a̲bs q) ÷ 1.0 m̲ax '+ r̲/ r̲avel a̲bs q } 60 61⍝━━ Additions 62 63⍝│ h a̲dds q: a ternary layer without multiplying: for the input 64⍝│ vector h (an item per row of q) and each column of q, the sum of the 65⍝│ inputs under +1 minus the sum of those under -1. Times the scale, it 66⍝│ is h times the ternary weights. 67⍝│ >> "qz:" u_se< "Quant" 68⍝│ >> 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 69⍝│ -1.0 -1.0 70ˡa̲dds ← { h q → 71 H ← h 'l̲eft t̲able o̲ffsets 2 s̲elect s̲hape q 72 ('+ r̲/ H × f̲loat q = 1.0) − '+ r̲/ H × f̲loat q = -1.0 73} 74 75⍝━━ Blocks: 4 bits, a scale per block 76 77⍝│ k b̲locks x: x's numbers (raveled) as rows of k, a block each; the 78⍝│ count must be a multiple of k. 79⍝│ >> "qz:" u_se< "Quant" 80⍝│ >> 2 qz:b_locks 1.0 -4.0 2.0 0.5 81⍝│ 1.0 -4.0 82⍝│ 2.0 0.5 83ˡb̲locks ← { k x → 84 n ← t̲ally r̲avel x 85 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 86 ((n d̲iv k) c̲at k) r̲eshape r̲avel x 87} 88 89⍝│ k a̲bsmax x: each block's largest size, its scale (absmax). 90⍝│ >> "qz:" u_se< "Quant" 91⍝│ >> 2 qz:a_bsmax 1.0 -4.0 2.0 0.5 92⍝│ 4.0 2.0 93ˡa̲bsmax ← { k x → 'm̲ax r̲/₂ a̲bs k ˡb̲locks x } 94 95⍝│ (b, k) u̲niformCodes x: blockwise symmetric b-bit integers: each 96⍝│ block divided by its scale, its absmax over 2^(b-1) - 1 (7 for 4 97⍝│ bits), rounded and clipped to -7 .. 7: (codes, scales), the codes as 98⍝│ Floats a row per block. 99⍝│ >> "qz:" u_se< "Quant" 100⍝│ >> (q, s) := (4, 2) qz:u_niformCodes 1.0 -4.0 2.0 0.5 101⍝│ >> q 102⍝│ 2.0 -7.0 103⍝│ 7.0 2.0 104ˡu̲niformCodes ← { (b, k) x → 105 top ← (2.0 ^ f̲loat b − 1) − 1.0 106 s ← (k ˡa̲bsmax x) ÷ top 107 B ← k ˡb̲locks x 108 S ← s 'l̲eft t̲able o̲ffsets k 109 (top m̲in (n̲eg top) m̲ax f̲loat f̲loor 0.5 + B ÷ 0.000000000001 m̲ax S, s) 110} 111 112⍝│ (b, k) u̲niform x: x through blockwise b-bit integers and back 113⍝│ (codes times their block's scale), shaped as x: what a uniform 4-bit 114⍝│ base computes with. 115⍝│ >> "qz:" u_se< "Quant" 116⍝│ >> (4, 2) qz:u_niform 1.0 -4.0 2.0 0.5 117⍝│ 1.1428571428571428 -4.0 2.0 0.5714285714285714 118ˡu̲niform ← { (b, k) x → 119 (q, s) ← (b, k) ˡu̲niformCodes x 120 (s̲hape x) r̲eshape q × s 'l̲eft t̲able o̲ffsets k 121} 122 123⍝━━ NF4: 16 levels at the normal's quantiles 124 125⍝│ The NF4 codebook as QLoRA publishes it (Dettmers et al. 2023, 126⍝│ appendix E; bitsandbytes' create_normal_map, float32), derived again 127⍝│ by c_odebook and checked against it in the tests. 128nf4 ← -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 129 130⍝│ erf by its series, 80 terms: 2/sqrt(pi) sum (-1)^n z^(2n+1) / (n! (2n+1)); 131⍝│ to 1e-15 for |z| up to about 3. 132ʰe̲rf ← { z → 133 (_, _, 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) 134 t × 2.0 ÷ s̲qrt 3.141592653589793 135} 136⍝│ One halving of (lo, hi) toward the x where Phi(x) is p. 137ʰh̲alf ← { p (lo, hi) → 138 m ← 0.5 × lo + hi 139 (ˡp̲hi m) < p ? (m, hi) 140 (lo, m) 141} 142⍝│ n points from a to b, both included. 143ʰs̲pan ← { (a, b) n → a + (b − a) × (f̲loat (r̲ange n) − 1) ÷ f̲loat n − 1 } 144 145⍝│ p̲hi x: the standard normal's cumulative distribution, 1/2 (1 + 146⍝│ erf(x / sqrt 2)), erf by its series. 147⍝│ >> "qz:" u_se< "Quant" 148⍝│ >> qz:p_hi 1.0 149⍝│ 0.8413447460685428 150ˡp̲hi ← { x → 0.5 × 1.0 + ʰe̲rf x ÷ s̲qrt 2.0 } 151 152⍝│ q̲uantile p: the normal's inverse, the x with Phi(x) = p, by 60 153⍝│ halvings of -4 .. 4 (to 1e-15 of p in 0.00004 .. 0.99996). 154⍝│ >> "qz:" u_se< "Quant" 155⍝│ >> qz:q_uantile 0.975 156⍝│ 1.959963984540054 157ˡq̲uantile ← { p → 158 (lo, hi) ← 60 '{ q → p ʰh̲alf q } p̲ower (-4.0, 4.0) 159 0.5 × lo + hi 160} 161 162⍝│ c̲odebook offset: NF4's 16 levels, made as QLoRA makes them: the 163⍝│ normal's quantiles at 9 points from offset to 1/2 (8 positive) and at 164⍝│ 8 (7 negative, mirrored), with 0, scaled so the largest is 1. Each 165⍝│ level is as likely as the next for normal weights, and 0 is exact. 166⍝│ QLoRA's offset is 0.9677083, the mean of 1 - 1/(2 15) and 1 - 1/(2 16). 167⍝│ >> "qz:" u_se< "Quant" 168⍝│ >> 8 t_ake qz:c_odebook 0.9677083 169⍝│ -1.0 -0.6961928906037205 -0.5250730386952299 -0.39491749069931015 -0.2844413576181078 -0.18477343519288897 -0.0910499921442795 0.0 170ˡc̲odebook ← { offset → 171 pos ← 'ˡq̲uantile e̲ach -1 d̲rop (offset, 0.5) ʰs̲pan 9 172 neg ← 'ˡq̲uantile e̲ach -1 d̲rop (offset, 0.5) ʰs̲pan 8 173 v ← s̲ort pos c̲at 0.0 c̲at n̲eg neg 174 v ÷ 'm̲ax r̲/ v 175} 176 177⍝│ k n̲f4Codes x: each block divided by its absmax, then each number's 178⍝│ nearest NF4 level, by its index 1 .. 16: (codes, scales), the codes 179⍝│ a row per block. 180⍝│ >> "qz:" u_se< "Quant" 181⍝│ >> (q, s) := 2 qz:n_f4Codes 1.0 -4.0 2.0 0.5 182⍝│ >> q 183⍝│ 11 1 184⍝│ 16 11 185ˡn̲f4Codes ← { k x → 186 s ← k ˡa̲bsmax x 187 B ← k ˡb̲locks x 188 N ← B ÷ 0.000000000001 m̲ax s 'l̲eft t̲able o̲ffsets k 189 ((s̲hape N) r̲eshape '{ v → f̲irst g̲rade a̲bs v − nf4 } e̲ach r̲avel N, s) 190} 191 192⍝│ n̲f4Values (q, s): NF4 codes back to numbers, each code's level 193⍝│ times its block's scale (raveled; the codes a row per block). 194⍝│ >> "qz:" u_se< "Quant" 195⍝│ >> qz:n_f4Values 2 qz:n_f4Codes 1.0 -4.0 2.0 0.5 196⍝│ 0.9844492077827454 -4.0 2.0 0.4922246038913727 197ˡ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 } 198 199⍝│ k n̲f4 x: x through NF4 and back (each code's level times its 200⍝│ block's scale), shaped as x. 201⍝│ >> "qz:" u_se< "Quant" 202⍝│ >> 2 qz:n_f4 1.0 -4.0 2.0 0.5 203⍝│ 0.9844492077827454 -4.0 2.0 0.4922246038913727 204ˡn̲f4 ← { k x → (s̲hape x) r̲eshape ˡn̲f4Values k ˡn̲f4Codes x } 205 206⍝━━ Double quantization: the scales in 8 bits 207 208⍝│ k2 d̲ouble s: the block scales themselves quantized, as QLoRA does 209⍝│ to save their bytes: their mean taken off, then blockwise symmetric 210⍝│ 8-bit integers over blocks of k2 scales (the last block made up with 211⍝│ zeros, which change no block's absmax), and back, the mean added. 212⍝│ (QLoRA's second level is an 8-bit float; 8-bit integers here, the 213⍝│ same bytes.) 214⍝│ >> "qz:" u_se< "Quant" 215⍝│ >> 2 qz:d_ouble 0.5 0.25 1.0 0.75 216⍝│ 0.5009842519685039 0.25 1.0 0.7490157480314961 217ˡd̲ouble ← { k2 s → 218 n ← t̲ally s 219 m ← ('+ r̲/ s) ÷ f̲loat n 220 pad ← (k2 × c̲eiling (f̲loat n) ÷ f̲loat k2) − n 221 m + n t̲ake (8, k2) ˡu̲niform (s − m) c̲at pad r̲eshape 0.0 222} 223 224⍝│ k2 n̲f4Double (k, x): NF4 with its scales double-quantized: x 225⍝│ through NF4 and back, the scales first through d_ouble. 226ˡn̲f4Double ← { k2 (k, x) → 227 (q, s) ← k ˡn̲f4Codes x 228 (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 229} 230 231⍝━━ Bits 232 233⍝│ (k, k2) b̲its 4: bits a weight takes: 4 for its code plus its 234⍝│ block's scale shared by k weights, at 32 bits; then with double 235⍝│ quantization, the scale at 8 bits plus a 32-bit scale and mean shared 236⍝│ by k2 scales. QLoRA's k 64 and k2 256: 4.5, and 4.129 (QLoRA's 237⍝│ paper counts 4.127, the mean left out). 238⍝│ >> "qz:" u_se< "Quant" 239⍝│ >> (64, 256) qz:b_its 4 240⍝│ 4.5 4.12890625 241ˡb̲its ← { (k, k2) b → 242 (f̲loat b) + (32.0 ÷ f̲loat k) c̲at (8.0 ÷ f̲loat k) + 64.0 ÷ f̲loat k × k2 243}