vecq_core/
lloyd.rs

1//! Lloyd-Max optimal scalar quantizer tables for N(0,1), precomputed offline.
2//!
3//! Centroids and decision boundaries are computed via Lloyd's algorithm
4//! (2000 iterations, convergence tolerance 1e-12) on the standard normal
5//! distribution, then embedded as constants. No runtime training pass.
6//!
7//! 4-bit: 16 centroids / 15 boundaries. 2-bit: 4 centroids / 3 boundaries.
8
9/// 4-bit Lloyd-Max centroids for N(0,1).
10pub const CENTROIDS_4BIT: [f32; 16] = [
11    -1.996_112, -1.512_225, -1.172_563, -0.887_568, -0.632_509, -0.395_530, -0.169_891, 0.049_892,
12    0.269_673, 0.495_312, 0.732_291, 0.987_350, 1.272_345, 1.612_007, 2.095_894, 2.724_265,
13];
14
15/// 4-bit decision boundaries (index i separates centroid i-1 and i).
16pub const BOUNDARIES_4BIT: [f32; 15] = [
17    -1.751_289, -1.340_438, -1.026_996, -0.756_128, -0.509_062, -0.276_322, -0.056_279, 0.164_289,
18    0.391_029, 0.626_095, 0.868_960, 1.125_026, 1.413_956, 1.764_827, 2.238_297,
19];
20
21/// Quantize one N(0,1)-distributed value to a 4-bit index via binary search
22/// over the decision boundaries.
23#[inline]
24pub fn quantize_4bit(x: f32) -> u8 {
25    let mut lo = 0usize;
26    let mut hi = BOUNDARIES_4BIT.len(); // 15
27    while lo < hi {
28        let mid = (lo + hi) / 2;
29        if x > BOUNDARIES_4BIT[mid] {
30            lo = mid + 1;
31        } else {
32            hi = mid;
33        }
34    }
35    lo as u8
36}
37
38/// Dequantize a 4-bit index back to its centroid value.
39#[inline]
40pub fn dequantize_4bit(i: u8) -> f32 {
41    CENTROIDS_4BIT[i as usize]
42}
43
44#[cfg(test)]
45mod tests {
46    use super::*;
47
48    #[test]
49    fn centroids_are_sorted() {
50        for w in CENTROIDS_4BIT.windows(2) {
51            assert!(w[0] < w[1], "centroids must be strictly increasing");
52        }
53    }
54
55    #[test]
56    fn boundaries_are_sorted_and_interleaved() {
57        for w in BOUNDARIES_4BIT.windows(2) {
58            assert!(w[0] < w[1]);
59        }
60        // boundaries sit between adjacent centroids
61        for i in 0..15 {
62            assert!(CENTROIDS_4BIT[i] < BOUNDARIES_4BIT[i]);
63            assert!(BOUNDARIES_4BIT[i] < CENTROIDS_4BIT[i + 1]);
64        }
65    }
66
67    #[test]
68    fn extreme_values_map_to_endpoints() {
69        assert_eq!(quantize_4bit(-10.0), 0);
70        assert_eq!(quantize_4bit(10.0), 15);
71    }
72
73    #[test]
74    fn zero_maps_near_center() {
75        let i = quantize_4bit(0.0);
76        assert!(
77            (7..=8).contains(&i),
78            "0.0 should map to centroid 7 or 8, got {i}"
79        );
80    }
81
82    #[test]
83    fn round_trip_error_is_bounded() {
84        // Worst-case quantization error for N(0,1) Lloyd-Max 4-bit is half
85        // the largest inter-centroid gap in the tails.
86        let mut max_gap = 0f32;
87        for i in 0..15 {
88            max_gap = max_gap.max(CENTROIDS_4BIT[i + 1] - CENTROIDS_4BIT[i]);
89        }
90        // Lloyd-Max MSE for 4-bit on N(0,1) is ~0.0115; per-dim worst error
91        // must be below the max tail gap.
92        assert!(max_gap < 0.75, "max centroid gap {max_gap} too large");
93    }
94}
vecq_core/lloyd.rs

vecq_core/
lloyd.rs
