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}