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).

source

Floats

ˡf̲loats : Float -> Float -> Float

function · line 20

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

function · line 31

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 }
Used in: ˡi̲nt, m8

ˡi̲nt : Num a => a -> Float -> Float

function · line 39

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

function · line 48

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 }
Used in: ˡt̲ernary, q

ˡt̲ernary : Float -> Float -> Float

function · line 51

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 }
Used in: q

ˡs̲cale : Float -> Float -> Float

function · line 59

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

function · line 70

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

function · line 83

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

function · line 93

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)

function · line 104

(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)
}
Used in: ˡu̲niform

ˡu̲niform : Num a => (a, Int) -> Float -> Float

function · line 118

(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

value (private) · line 128

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

function (private) · line 132

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
}
Used in: ˡp̲hi

ʰh̲alf : Float -> (Float, Float) -> (Float, Float)

function (private) · line 137

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)
}
Used in: ˡq̲uantile

ʰs̲pan : (Float, Float) -> Int -> Float

function (private) · line 143

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 }
Used in: ˡc̲odebook

ˡp̲hi : Float -> Float

function · line 150

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 }
Used in: ʰh̲alf

ˡq̲uantile : Float -> Float

function · line 157

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
}
Used in: ˡc̲odebook

ˡc̲odebook : Float -> Float

function · line 170

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)

function · line 185

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

function · line 197

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

function · line 204

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

function · line 217

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
}
Used in: ˡn̲f4Double

ˡn̲f4Double : Int -> (Int, Float) -> Float

function · line 226

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

function · line 241

(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
}
Used in: bits