Skip to main content

qualia_core_db/inference/
kv_dict.rs

1//! W5b Phase 4b — the KV-dictionary type and its sparse **codec**, in CORE.
2//!
3//! This is the "engine runs the certified artifact" half of the sparse-KV-dictionary work. A learned
4//! per-layer dictionary `D` of `n_atoms` unit atoms represents each KV vector as a **k-sparse** linear
5//! combination — `k` (atom_index, coefficient) pairs. The engine needs two operations at runtime, and
6//! neither may depend on the forge feature:
7//!   * [`KvDictionary::encode`] — Orthogonal Matching Pursuit: a vector → its k-sparse code (write path).
8//!   * [`KvDictionary::reconstruct`] — code → vector (read path, in attention).
9//!
10//! The MOD **learner** that PRODUCES a dictionary is a forge/training step and lives in
11//! `wgsl_forge::calibration::kv_dictionary` (which re-exports this type). Colocation would blur "forge
12//! produces, engine runs", so only the data + codec + the small numeric helpers they share live here.
13//! Pure CPU + `f32`; the GPU reconstruction shader (Phase 4b step 5) mirrors `reconstruct()` in WGSL.
14
15/// A learned per-layer KV dictionary: `n_atoms` atoms, each of length `dim`, row-major in `atoms`.
16#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
17pub struct KvDictionary {
18    pub dim: usize,
19    pub n_atoms: usize,
20    /// `n_atoms × dim`, row-major; each atom is L2-normalized.
21    pub atoms: Vec<f32>,
22    /// Sparsity `k` this dictionary was trained for (atoms per coded vector).
23    pub sparsity: usize,
24}
25
26/// A K-sparse code of one vector: `indices[i]` selects an atom, `coeffs[i]` its weight.
27#[derive(Debug, Clone, PartialEq)]
28pub struct SparseCode {
29    pub indices: Vec<u32>,
30    pub coeffs: Vec<f32>,
31}
32
33impl KvDictionary {
34    #[inline]
35    /// `KvDictionary::atom`.
36    pub(crate) fn atom(&self, a: usize) -> &[f32] {
37        &self.atoms[a * self.dim..(a + 1) * self.dim]
38    }
39
40    /// Normalize every dictionary atom in place after loading or training.
41    /// Returns `false` when the declared shape is inconsistent or an atom has
42    /// effectively zero magnitude.
43    pub fn normalize_atoms(&mut self) -> bool {
44        if self.dim == 0 || self.atoms.len() != self.dim.saturating_mul(self.n_atoms) {
45            return false;
46        }
47        for atom in self.atoms.chunks_exact_mut(self.dim) {
48            if l2(atom) <= 1e-12 {
49                return false;
50            }
51            normalize(atom);
52        }
53        true
54    }
55
56    /// Reconstruct a vector from its sparse code: `Σ coeffs[i] · atom(indices[i])`. The read-path
57    /// operation the attention shader mirrors.
58    pub fn reconstruct(&self, code: &SparseCode) -> Vec<f32> {
59        let mut out = vec![0f32; self.dim];
60        for (idx, &c) in code.indices.iter().zip(&code.coeffs) {
61            let atom = self.atom(*idx as usize);
62            for (o, &a) in out.iter_mut().zip(atom) {
63                *o += c * a;
64            }
65        }
66        out
67    }
68
69    /// Orthogonal Matching Pursuit: encode `v` with at most `k` atoms. Greedy selection by maximum
70    /// absolute correlation with the residual, re-solving all selected coefficients by least squares
71    /// each step (the "orthogonal" in OMP). Stops early if the residual is already ~0.
72    pub fn encode(&self, v: &[f32], k: usize) -> SparseCode {
73        debug_assert_eq!(v.len(), self.dim);
74        let k = k.min(self.n_atoms).max(1);
75        let mut residual = v.to_vec();
76        let mut selected: Vec<usize> = Vec::with_capacity(k);
77        let mut coeffs: Vec<f32> = Vec::with_capacity(k);
78
79        for _ in 0..k {
80            // Pick the atom most correlated with the current residual (excluding already-picked).
81            let mut best = usize::MAX;
82            let mut best_abs = 0f32;
83            for a in 0..self.n_atoms {
84                if selected.contains(&a) {
85                    continue;
86                }
87                let corr = dot(self.atom(a), &residual);
88                if corr.abs() > best_abs {
89                    best_abs = corr.abs();
90                    best = a;
91                }
92            }
93            if best == usize::MAX || best_abs <= 1e-12 {
94                break;
95            }
96            selected.push(best);
97            // Re-solve coefficients for ALL selected atoms by least squares (normal equations on the
98            // small |S|×|S| Gram matrix), then recompute the residual.
99            coeffs = least_squares_coeffs(&selected, self, v);
100            residual = v.to_vec();
101            for (&s, &c) in selected.iter().zip(&coeffs) {
102                let atom = self.atom(s);
103                for (r, &a) in residual.iter_mut().zip(atom) {
104                    *r -= c * a;
105                }
106            }
107            if l2(&residual) <= 1e-8 {
108                break;
109            }
110        }
111        SparseCode {
112            indices: selected.iter().map(|&s| s as u32).collect(),
113            coeffs,
114        }
115    }
116}
117
118/// Pack a `(atom_index, coefficient)` pair into one 32-bit KV code word — `u16 atom-index (high) |
119/// f16 coeff (low)` — stored as an `f32` in the dict-mode KV arena. The GPU attention shader unpacks the
120/// coeff with `unpack2x16float(word).x` and the index with `word >> 16`.
121#[inline]
122pub fn pack_code_word(index: u32, coeff: f32) -> f32 {
123    let w = (index << 16) | (half::f16::from_f32(coeff).to_bits() as u32);
124    f32::from_bits(w)
125}
126
127/// Inverse of [`pack_code_word`]: `(atom_index, coefficient)` from a code word.
128#[inline]
129pub fn unpack_code_word(word: f32) -> (usize, f32) {
130    let w = word.to_bits();
131    (
132        (w >> 16) as usize,
133        half::f16::from_bits((w & 0xFFFF) as u16).to_f32(),
134    )
135}
136
137impl KvDictionary {
138    /// Encode `vec` to `k` contiguous code words in `out` (len ≥ `k`). Pads with zero-coeff words if OMP
139    /// selected fewer than `k` atoms (a zero coeff reconstructs to nothing).
140    pub fn encode_to_words(&self, vec: &[f32], k: usize, out: &mut [f32]) {
141        let code = self.encode(vec, k);
142        for (i, slot) in out.iter_mut().enumerate().take(k) {
143            let (ai, ci) = if i < code.indices.len() {
144                (code.indices[i], code.coeffs[i])
145            } else {
146                (0, 0.0)
147            };
148            *slot = pack_code_word(ai, ci);
149        }
150    }
151
152    /// Reconstruct a vector from `k` contiguous code words (`words` len ≥ `k`) into `out` (len = `dim`).
153    /// The exact `f16`-coefficient inverse of `encode_to_words()` — the compressed-cache read path.
154    pub fn reconstruct_from_words(&self, words: &[f32], k: usize, out: &mut [f32]) {
155        for o in out.iter_mut() {
156            *o = 0.0;
157        }
158        for &word in words.iter().take(k) {
159            let (ai, ci) = unpack_code_word(word);
160            if ci != 0.0 && ai < self.n_atoms {
161                let atom = self.atom(ai);
162                for (o, &a) in out.iter_mut().zip(atom) {
163                    *o += ci * a;
164                }
165            }
166        }
167    }
168}
169
170/// Least-squares coefficients for the selected atoms fitting `v`: solve `(DₛᵀDₛ) c = Dₛᵀv` via the
171/// normal equations (Gaussian elimination on the small `|S|×|S|` system).
172fn least_squares_coeffs(selected: &[usize], dict: &KvDictionary, v: &[f32]) -> Vec<f32> {
173    let s = selected.len();
174    // Gram matrix G = Dₛᵀ Dₛ (s×s) and rhs = Dₛᵀ v (s).
175    let mut g = vec![0f32; s * s];
176    let mut rhs = vec![0f32; s];
177    for i in 0..s {
178        let ai = dict.atom(selected[i]);
179        rhs[i] = dot(ai, v);
180        for j in i..s {
181            let aj = dict.atom(selected[j]);
182            let val = dot(ai, aj);
183            g[i * s + j] = val;
184            g[j * s + i] = val;
185        }
186    }
187    solve_spd(&mut g, &mut rhs, s);
188    rhs
189}
190
191/// Solve a small dense symmetric system `G c = b` in place via Gaussian elimination with partial
192/// pivoting (SPD in exact arithmetic; the pivoting + tiny ridge keep it robust to near-singular Gram
193/// matrices from correlated atoms). Result written back into `b`.
194fn solve_spd(g: &mut [f32], b: &mut [f32], n: usize) {
195    // Tiny ridge for numerical stability against duplicate/near-duplicate atoms.
196    for i in 0..n {
197        g[i * n + i] += 1e-6;
198    }
199    for col in 0..n {
200        // Partial pivot.
201        let mut piv = col;
202        let mut piv_abs = g[col * n + col].abs();
203        for r in (col + 1)..n {
204            let a = g[r * n + col].abs();
205            if a > piv_abs {
206                piv_abs = a;
207                piv = r;
208            }
209        }
210        if piv != col {
211            for c in 0..n {
212                g.swap(col * n + c, piv * n + c);
213            }
214            b.swap(col, piv);
215        }
216        let d = g[col * n + col];
217        if d.abs() <= 1e-12 {
218            continue;
219        }
220        for r in 0..n {
221            if r == col {
222                continue;
223            }
224            let factor = g[r * n + col] / d;
225            if factor == 0.0 {
226                continue;
227            }
228            for c in col..n {
229                g[r * n + c] -= factor * g[col * n + c];
230            }
231            b[r] -= factor * b[col];
232        }
233    }
234    for i in 0..n {
235        let d = g[i * n + i];
236        if d.abs() > 1e-12 {
237            b[i] /= d;
238        } else {
239            b[i] = 0.0;
240        }
241    }
242}
243
244#[inline]
245/// `KvDictionary::dot`.
246pub(crate) fn dot(a: &[f32], b: &[f32]) -> f32 {
247    a.iter().zip(b).map(|(x, y)| x * y).sum()
248}
249
250#[inline]
251/// `KvDictionary::l2`.
252pub(crate) fn l2(v: &[f32]) -> f32 {
253    dot(v, v).sqrt()
254}
255
256#[inline]
257/// `KvDictionary::normalize`.
258pub(crate) fn normalize(v: &mut [f32]) {
259    let n = l2(v);
260    if n > 1e-12 {
261        for x in v.iter_mut() {
262            *x /= n;
263        }
264    }
265}
266/// Bifurcated identity of a cached KV prefix (§7.3.3 / §3.4).
267///
268/// Prevents cross-standpoint or cross-epistemic KV-cache leakage by binding
269/// the observer wing, sensitivity ceiling, active manifold mask, and quantum branch q
270/// directly into the prefix cache key.
271#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, serde::Serialize, serde::Deserialize)]
272pub struct BifurcatedPrefixIdentity {
273    pub content_hash: u64,
274    pub observer_wing: u8,
275    pub sensitivity_ceiling: u8,
276    pub manifold_mask: u16,
277    pub quantum_branch_q: u32,
278}
279
280impl BifurcatedPrefixIdentity {
281    /// Construct a new bifurcated prefix identity.
282    pub const fn new(
283        content_hash: u64,
284        observer_wing: u8,
285        sensitivity_ceiling: u8,
286        manifold_mask: u16,
287        quantum_branch_q: u32,
288    ) -> Self {
289        Self {
290            content_hash,
291            observer_wing,
292            sensitivity_ceiling,
293            manifold_mask,
294            quantum_branch_q,
295        }
296    }
297
298    /// Compute a 64-bit rapid FNV-1a hash key mixing the content hash with
299    /// all observer and epistemic bifurcation parameters.
300    pub const fn cache_key(&self) -> u64 {
301        const FNV_OFFSET: u64 = 0xcbf29ce484222325;
302        const FNV_PRIME: u64 = 0x100000001b3;
303
304        let mut h = FNV_OFFSET;
305        let mut ch = self.content_hash;
306        let mut i = 0;
307        while i < 8 {
308            h ^= (ch & 0xFF) as u64;
309            h = h.wrapping_mul(FNV_PRIME);
310            ch >>= 8;
311            i += 1;
312        }
313
314        h ^= self.observer_wing as u64;
315        h = h.wrapping_mul(FNV_PRIME);
316
317        h ^= self.sensitivity_ceiling as u64;
318        h = h.wrapping_mul(FNV_PRIME);
319
320        h ^= (self.manifold_mask & 0xFF) as u64;
321        h = h.wrapping_mul(FNV_PRIME);
322        h ^= ((self.manifold_mask >> 8) & 0xFF) as u64;
323        h = h.wrapping_mul(FNV_PRIME);
324
325        let mut q = self.quantum_branch_q;
326        let mut j = 0;
327        while j < 4 {
328            h ^= (q & 0xFF) as u64;
329            h = h.wrapping_mul(FNV_PRIME);
330            q >>= 8;
331            j += 1;
332        }
333
334        h
335    }
336}
337
338#[cfg(test)]
339mod tests {
340    use super::*;
341
342    #[test]
343    fn bifurcated_prefix_identity_cache_key_distinct_across_parameters() {
344        let base = BifurcatedPrefixIdentity::new(0x1234_5678, 0, 0, 0x1FFF, 0);
345        let key_base = base.cache_key();
346
347        // Different observer wing
348        let mut diff_wing = base;
349        diff_wing.observer_wing = 1;
350        assert_ne!(key_base, diff_wing.cache_key());
351
352        // Different sensitivity ceiling
353        let mut diff_sens = base;
354        diff_sens.sensitivity_ceiling = 2;
355        assert_ne!(key_base, diff_sens.cache_key());
356
357        // Different manifold mask
358        let mut diff_mask = base;
359        diff_mask.manifold_mask = 0x00FF;
360        assert_ne!(key_base, diff_mask.cache_key());
361
362        // Different quantum branch q
363        let mut diff_q = base;
364        diff_q.quantum_branch_q = 1000;
365        assert_ne!(key_base, diff_q.cache_key());
366
367        // Different content hash
368        let mut diff_content = base;
369        diff_content.content_hash = 0x8765_4321;
370        assert_ne!(key_base, diff_content.cache_key());
371    }
372
373    #[test]
374    fn bifurcated_prefix_identity_cache_key_is_deterministic() {
375        let id1 = BifurcatedPrefixIdentity::new(0xDEAD_BEEF, 2, 1, 0x0F0F, 42);
376        let id2 = BifurcatedPrefixIdentity::new(0xDEAD_BEEF, 2, 1, 0x0F0F, 42);
377        assert_eq!(id1.cache_key(), id2.cache_key());
378    }
379}