vyre_primitives/hash/
hypervector.rs

1//! Vector Symbolic Architecture (VSA) primitives  -  bind + bundle on
2//! high-dimensional binary hypervectors.
3//!
4//! VSAs (Plate 1995, Kanerva 2009) compute over 10K-dim ±1 / 0/1
5//! hypervectors using two operations: *binding* (associates two
6//! vectors into a key-value pair) and *bundling* (superposes a set of
7//! vectors into a single representative). Recent ML work (Schlegel
8//! 2022, Hersche 2023) shows VSA + transformers > transformers alone
9//! on systematic-generalization benchmarks.
10//!
11//! This file ships the **binary spatter code** (BSC) variant: each
12//! hypervector is a u32 bitset, binding is bitwise XOR, bundling is
13//! per-bit majority vote. Already GPU-trivial; the gravity gap is
14//! that no one has packaged it as a Tier-2.5 primitive.
15//!
16//! # Why this primitive is dual-use
17//!
18//! | Composition role | Use |
19//! |---|---|
20//! | retrieval | structured key-value lookup |
21//! | symbolic reasoning | compositional symbol algebra |
22//! | program fingerprints | bind op-kind, buffer signature, and region shape into one hypervector so semantically-equivalent regions can share cache entries even when byte-equal hashing misses |
23//!
24//! # Operations
25//!
26//! - `hypervector_xor_bind(a, b, out, dim_words)`  -  bitwise XOR.
27//!   Each output word is `a[i] ^ b[i]`. XOR is its own inverse, so
28//!   `xor_bind(xor_bind(a, b), b) == a` (unbinding by re-binding with
29//!   the same key).
30//! - `hypervector_majority_bundle(stacked, out, dim_words, k)`  -
31//!   per-bit majority over `k` stacked hypervectors. For each bit
32//!   position, output bit = 1 iff > k/2 input bits are 1. Ties
33//!   (k even, exactly k/2) round to 0 (callers typically use odd k).
34
35use std::sync::Arc;
36
37use vyre_foundation::ir::model::expr::Ident;
38use vyre_foundation::ir::{BufferAccess, BufferDecl, DataType, Expr, Node, Program};
39
40/// Canonical op id for the binding primitive.
41pub const BIND_OP_ID: &str = "vyre-primitives::hash::hypervector_xor_bind";
42/// Canonical op id for the bundling primitive.
43pub const BUNDLE_OP_ID: &str = "vyre-primitives::hash::hypervector_majority_bundle";
44
45/// Standard BSC hypervector dimensionality (in bits). 10240 bits =
46/// 320 u32 words. Plate / Kanerva established that dimensions in the
47/// 10K range give negligible chance-binding noise for practical
48/// vocabularies up to ~10⁶ items.
49pub const STANDARD_DIM_BITS: u32 = 10240;
50/// Standard hypervector size in u32 words.
51pub const STANDARD_DIM_WORDS: u32 = STANDARD_DIM_BITS / 32;
52
53/// Emit `out`w` = a`w` ^ b`w`` for each of `dim_words` lanes.
54#[must_use]
55pub fn hypervector_xor_bind(a: &str, b: &str, out: &str, dim_words: u32) -> Program {
56    if dim_words == 0 {
57        return crate::invalid_output_program(
58            BIND_OP_ID,
59            out,
60            DataType::U32,
61            "Fix: hypervector_xor_bind requires dim_words > 0, got 0.".to_string(),
62        );
63    }
64
65    let t = Expr::InvocationId { axis: 0 };
66    let body = vec![Node::if_then(
67        Expr::lt(t.clone(), Expr::u32(dim_words)),
68        vec![Node::store(
69            out,
70            t.clone(),
71            Expr::bitxor(Expr::load(a, t.clone()), Expr::load(b, t)),
72        )],
73    )];
74
75    Program::wrapped(
76        vec![
77            BufferDecl::storage(a, 0, BufferAccess::ReadOnly, DataType::U32).with_count(dim_words),
78            BufferDecl::storage(b, 1, BufferAccess::ReadOnly, DataType::U32).with_count(dim_words),
79            BufferDecl::storage(out, 2, BufferAccess::ReadWrite, DataType::U32)
80                .with_count(dim_words),
81        ],
82        [256, 1, 1],
83        vec![Node::Region {
84            generator: Ident::from(BIND_OP_ID),
85            source_region: None,
86            body: Arc::new(body),
87        }],
88    )
89}
90
91/// Emit per-bit majority vote over `k` hypervectors stacked row-major
92/// in `stacked` (size `k * dim_words`).
93///
94/// For each output word lane `w` and each bit position `bit` in 0..32:
95///   count = popcount of (stacked[i*dim_words + w] >> bit & 1) for i in 0..k
96///   out`w` bit `bit` = 1 iff count > k/2
97#[must_use]
98pub fn hypervector_majority_bundle(stacked: &str, out: &str, dim_words: u32, k: u32) -> Program {
99    if dim_words == 0 {
100        return crate::invalid_output_program(
101            BUNDLE_OP_ID,
102            out,
103            DataType::U32,
104            "Fix: hypervector_majority_bundle requires dim_words > 0, got 0.".to_string(),
105        );
106    }
107    if k == 0 {
108        return crate::invalid_output_program(
109            BUNDLE_OP_ID,
110            out,
111            DataType::U32,
112            "Fix: hypervector_majority_bundle requires k > 0, got 0.".to_string(),
113        );
114    }
115    let Some(stacked_words) = k.checked_mul(dim_words) else {
116        return crate::invalid_output_program(BUNDLE_OP_ID,
117        out,
118        DataType::U32,
119        format!(
120            "Fix: hypervector_majority_bundle k*dim_words overflows stacked input count for k={k}, dim_words={dim_words}; shard the bundle before GPU dispatch."
121        ),);
122    };
123
124    let t = Expr::InvocationId { axis: 0 };
125    let threshold = k / 2; // ties (count == threshold) round to 0.
126
127    let body = vec![Node::if_then(
128        Expr::lt(t.clone(), Expr::u32(dim_words)),
129        vec![
130            Node::let_bind("acc", Expr::u32(0)),
131            Node::loop_for(
132                "bit",
133                Expr::u32(0),
134                Expr::u32(32),
135                vec![
136                    Node::let_bind("count", Expr::u32(0)),
137                    Node::loop_for(
138                        "ii",
139                        Expr::u32(0),
140                        Expr::u32(k),
141                        vec![
142                            Node::let_bind("_unused_assign", Expr::u32(0)),
143                            Node::assign(
144                                "count",
145                                Expr::add(
146                                    Expr::var("count"),
147                                    Expr::bitand(
148                                        Expr::shr(
149                                            Expr::load(
150                                                stacked,
151                                                Expr::add(
152                                                    Expr::mul(
153                                                        Expr::var("ii"),
154                                                        Expr::u32(dim_words),
155                                                    ),
156                                                    t.clone(),
157                                                ),
158                                            ),
159                                            Expr::var("bit"),
160                                        ),
161                                        Expr::u32(1),
162                                    ),
163                                ),
164                            ),
165                        ],
166                    ),
167                    Node::if_then(
168                        Expr::gt(Expr::var("count"), Expr::u32(threshold)),
169                        vec![Node::assign(
170                            "acc",
171                            Expr::bitor(
172                                Expr::var("acc"),
173                                Expr::shl(Expr::u32(1), Expr::var("bit")),
174                            ),
175                        )],
176                    ),
177                ],
178            ),
179            Node::store(out, t, Expr::var("acc")),
180        ],
181    )];
182
183    Program::wrapped(
184        vec![
185            BufferDecl::storage(stacked, 0, BufferAccess::ReadOnly, DataType::U32)
186                .with_count(stacked_words),
187            BufferDecl::storage(out, 1, BufferAccess::ReadWrite, DataType::U32)
188                .with_count(dim_words),
189        ],
190        [256, 1, 1],
191        vec![Node::Region {
192            generator: Ident::from(BUNDLE_OP_ID),
193            source_region: None,
194            body: Arc::new(body),
195        }],
196    )
197}
198
199// ---- CPU references ----
200
201/// CPU reference for [`hypervector_xor_bind`].
202#[must_use]
203#[cfg(any(test, feature = "cpu-parity"))]
204pub fn xor_bind_cpu(a: &[u32], b: &[u32]) -> Vec<u32> {
205    let mut out = Vec::new();
206    match try_xor_bind_cpu_into(a, b, &mut out) {
207        Ok(()) => out,
208        // A parity oracle that returns empty on failure makes the GPU-vs-CPU
209        // assertion pass on empty==empty, silently masking a divergence
210        // (Law 10 / Law 6). Fail loud; callers use the try_ variant.
211        Err(error) => panic!("vyre-primitives hypervector XOR bind CPU reference failed: {error}"),
212    }
213}
214
215/// CPU reference for [`hypervector_xor_bind`] using a caller-owned buffer.
216#[cfg(any(test, feature = "cpu-parity"))]
217pub fn xor_bind_cpu_into(a: &[u32], b: &[u32], out: &mut Vec<u32>) {
218    if let Err(error) = try_xor_bind_cpu_into(a, b, out) {
219        panic!("vyre-primitives hypervector XOR bind CPU reference failed: {error}");
220    }
221}
222
223/// Fallible CPU reference for [`hypervector_xor_bind`] using a caller-owned buffer.
224#[cfg(any(test, feature = "cpu-parity"))]
225pub fn try_xor_bind_cpu_into(a: &[u32], b: &[u32], out: &mut Vec<u32>) -> Result<(), String> {
226    let dim_words = a.len().min(b.len());
227    vyre_foundation::allocation::reserve_exact_cleared(out, dim_words).map_err(|err| {
228        format!("hypervector XOR bind could not reserve {dim_words} output words: {err}")
229    })?;
230    out.extend(a.iter().zip(b.iter()).take(dim_words).map(|(&x, &y)| x ^ y));
231    Ok(())
232}
233
234/// CPU reference for [`hypervector_majority_bundle`].
235#[must_use]
236#[cfg(any(test, feature = "cpu-parity"))]
237pub fn majority_bundle_cpu(hvs: &[Vec<u32>]) -> Vec<u32> {
238    let mut out = Vec::new();
239    match try_majority_bundle_cpu_into(hvs, &mut out) {
240        Ok(()) => out,
241        // A parity oracle that returns empty on failure makes the GPU-vs-CPU
242        // assertion pass on empty==empty, silently masking a divergence
243        // (Law 10 / Law 6). Fail loud; callers use the try_ variant.
244        Err(error) => {
245            panic!("vyre-primitives hypervector majority bundle CPU reference failed: {error}")
246        }
247    }
248}
249
250/// CPU reference for [`hypervector_majority_bundle`] using a caller-owned buffer.
251#[cfg(any(test, feature = "cpu-parity"))]
252pub fn majority_bundle_cpu_into(hvs: &[Vec<u32>], out: &mut Vec<u32>) {
253    if let Err(error) = try_majority_bundle_cpu_into(hvs, out) {
254        panic!("vyre-primitives hypervector majority bundle CPU reference failed: {error}");
255    }
256}
257
258/// Fallible CPU reference for [`hypervector_majority_bundle`] using a caller-owned buffer.
259#[cfg(any(test, feature = "cpu-parity"))]
260pub fn try_majority_bundle_cpu_into(hvs: &[Vec<u32>], out: &mut Vec<u32>) -> Result<(), String> {
261    let Some(dim_words) = hvs.iter().map(Vec::len).min() else {
262        out.clear();
263        return Ok(());
264    };
265    if dim_words == 0 {
266        out.clear();
267        return Ok(());
268    }
269    let k = hvs.len();
270    let threshold = k / 2;
271
272    vyre_foundation::allocation::reserve_exact_cleared(out, dim_words).map_err(|err| {
273        format!("hypervector majority bundle could not reserve {dim_words} output words: {err}")
274    })?;
275    out.resize(dim_words, 0);
276    for w in 0..dim_words {
277        for bit in 0..32 {
278            let mut count = 0;
279            for hv in hvs {
280                count += (hv[w] >> bit) & 1;
281            }
282            if count as usize > threshold {
283                out[w] |= 1 << bit;
284            }
285        }
286    }
287    Ok(())
288}
289
290/// Cosine-style similarity over BSC hypervectors: 1 - 2 · hamming(a, b) /
291/// dim_bits. Returns f32 in roughly [-1, 1] (perfect match = 1.0, anti-
292/// correlation = -1.0, random = 0.0).
293#[must_use]
294pub fn hamming_similarity(a: &[u32], b: &[u32]) -> f32 {
295    let dim_words = a.len().min(b.len());
296    if dim_words == 0 {
297        return 1.0;
298    }
299    let dim_bits = (dim_words * 32) as f32;
300    let hamming: u32 = a
301        .iter()
302        .zip(b.iter())
303        .take(dim_words)
304        .map(|(&x, &y)| (x ^ y).count_ones())
305        .sum();
306    1.0 - 2.0 * (hamming as f32) / dim_bits
307}
308
309#[cfg(test)]
310mod tests {
311    use super::*;
312
313    #[test]
314    fn xor_bind_self_cancels() {
315        // bind(bind(a, b), b) == a  -  XOR is self-inverse.
316        let a = vec![0xDEAD_BEEFu32, 0x0BAD_F00D];
317        let b = vec![0x1234_5678, 0x90AB_CDEF];
318        let bound = xor_bind_cpu(&a, &b);
319        let unbound = xor_bind_cpu(&bound, &b);
320        assert_eq!(unbound, a);
321    }
322
323    #[test]
324    fn xor_bind_zero_is_identity() {
325        let a = vec![0x1234, 0x5678, 0xABCD];
326        let zero = vec![0u32; a.len()];
327        assert_eq!(xor_bind_cpu(&a, &zero), vec![0x1234, 0x5678, 0xABCD]);
328    }
329
330    #[test]
331    fn xor_bind_cpu_into_reuses_output() {
332        let a = vec![0x1234, 0x5678, 0xABCD];
333        let b = vec![0xFFFF, 0x0000, 0x1111];
334        let mut out = Vec::with_capacity(8);
335        let ptr = out.as_ptr();
336        xor_bind_cpu_into(&a, &b, &mut out);
337        assert_eq!(out, vec![0xEDCB, 0x5678, 0xBADC]);
338        assert_eq!(out.as_ptr(), ptr);
339    }
340
341    #[test]
342    fn try_xor_bind_cpu_into_clears_stale_tail_without_reallocating() {
343        let a = vec![0x1234, 0x5678, 0xABCD];
344        let b = vec![0xFFFF];
345        let mut out = Vec::with_capacity(8);
346        out.extend_from_slice(&[u32::MAX; 8]);
347        let ptr = out.as_ptr();
348
349        try_xor_bind_cpu_into(&a, &b, &mut out).unwrap();
350
351        assert_eq!(out, vec![0xEDCB]);
352        assert_eq!(out.as_ptr(), ptr);
353    }
354
355    #[test]
356    fn xor_bind_wrappers_match_fallible_reference() {
357        let a = vec![0x1234, 0x5678, 0xABCD];
358        let b = vec![0xFFFF, 0, 0x1111];
359        let mut compat = Vec::with_capacity(8);
360        let mut fallible = Vec::with_capacity(8);
361
362        xor_bind_cpu_into(&a, &b, &mut compat);
363        try_xor_bind_cpu_into(&a, &b, &mut fallible)
364            .expect("Fix: small hypervector XOR bind CPU reference must reserve");
365
366        assert_eq!(xor_bind_cpu(&a, &b), fallible);
367        assert_eq!(compat, fallible);
368    }
369
370    #[test]
371    fn xor_bind_cpu_truncates_mismatched_inputs() {
372        let a = vec![0x1234, 0x5678, 0xABCD];
373        let b = vec![0xFFFF];
374        assert_eq!(xor_bind_cpu(&a, &b), vec![0xEDCB]);
375    }
376
377    #[test]
378    fn majority_bundle_three_vectors() {
379        // Bit 0 set in 2/3 → output bit 0 = 1.
380        // Bit 1 set in 1/3 → output bit 1 = 0.
381        // Bit 2 set in 0/3 → output bit 2 = 0.
382        let hvs = vec![vec![0b001], vec![0b001], vec![0b010]];
383        let out = majority_bundle_cpu(&hvs);
384        assert_eq!(out, vec![0b001]);
385    }
386
387    #[test]
388    fn majority_bundle_unanimous() {
389        let hvs = vec![vec![0xFF], vec![0xFF], vec![0xFF]];
390        let out = majority_bundle_cpu(&hvs);
391        assert_eq!(out, vec![0xFF]);
392    }
393
394    #[test]
395    fn majority_bundle_cpu_into_reuses_output() {
396        let hvs = vec![vec![0b001], vec![0b001], vec![0b010]];
397        let mut out = Vec::with_capacity(8);
398        let ptr = out.as_ptr();
399        majority_bundle_cpu_into(&hvs, &mut out);
400        assert_eq!(out, vec![0b001]);
401        assert_eq!(out.as_ptr(), ptr);
402    }
403
404    #[test]
405    fn try_majority_bundle_cpu_into_clears_stale_tail_without_reallocating() {
406        let hvs = vec![vec![0b001], vec![0b001], vec![0b010]];
407        let mut out = Vec::with_capacity(8);
408        out.extend_from_slice(&[u32::MAX; 8]);
409        let ptr = out.as_ptr();
410
411        try_majority_bundle_cpu_into(&hvs, &mut out).unwrap();
412
413        assert_eq!(out, vec![0b001]);
414        assert_eq!(out.as_ptr(), ptr);
415    }
416
417    #[test]
418    fn majority_bundle_wrappers_match_fallible_reference() {
419        let hvs = vec![vec![0b001], vec![0b001], vec![0b010]];
420        let mut compat = Vec::with_capacity(8);
421        let mut fallible = Vec::with_capacity(8);
422
423        majority_bundle_cpu_into(&hvs, &mut compat);
424        try_majority_bundle_cpu_into(&hvs, &mut fallible)
425            .expect("Fix: small hypervector majority bundle CPU reference must reserve");
426
427        assert_eq!(majority_bundle_cpu(&hvs), fallible);
428        assert_eq!(compat, fallible);
429    }
430
431    #[test]
432    fn majority_bundle_tie_rounds_to_zero() {
433        // 2 vectors, bit 0 set in 1: count=1, threshold=k/2=1, count > threshold is false
434        let hvs = vec![vec![0b1], vec![0b0]];
435        let out = majority_bundle_cpu(&hvs);
436        assert_eq!(out, vec![0b0]);
437    }
438
439    #[test]
440    fn majority_bundle_cpu_handles_empty_and_mismatched_inputs() {
441        let empty: Vec<Vec<u32>> = Vec::new();
442        assert!(majority_bundle_cpu(&empty).is_empty());
443
444        let hvs = vec![vec![0b001, 0b111], vec![0b001]];
445        assert_eq!(majority_bundle_cpu(&hvs), vec![0b001]);
446    }
447
448    #[test]
449    fn hamming_similarity_self_is_one() {
450        let a = vec![0xDEAD_BEEFu32; 8];
451        assert!((hamming_similarity(&a, &a) - 1.0).abs() < 1e-6);
452    }
453
454    #[test]
455    fn hamming_similarity_complement_is_minus_one() {
456        let a = vec![0xFFFF_FFFFu32; 4];
457        let b = vec![0x0000_0000u32; 4];
458        assert!((hamming_similarity(&a, &b) - (-1.0)).abs() < 1e-6);
459    }
460
461    #[test]
462    fn hamming_similarity_handles_empty_and_mismatched_inputs() {
463        assert_eq!(hamming_similarity(&[], &[]), 1.0);
464        let a = vec![0xFFFF_FFFFu32, 0];
465        let b = vec![0];
466        assert!((hamming_similarity(&a, &b) - (-1.0)).abs() < 1e-6);
467    }
468
469    #[test]
470    fn ir_program_xor_bind_buffer_layout() {
471        let p = hypervector_xor_bind("a", "b", "out", 64);
472        assert_eq!(p.workgroup_size, [256, 1, 1]);
473        let names: Vec<&str> = p.buffers.iter().map(|b| b.name()).collect();
474        assert_eq!(names, vec!["a", "b", "out"]);
475        for buf in p.buffers.iter() {
476            assert_eq!(buf.count(), 64);
477        }
478    }
479
480    #[test]
481    fn ir_program_xor_bind_zero_dim_is_trap() {
482        let p = hypervector_xor_bind("a", "b", "out", 0);
483        assert_eq!(p.buffers.len(), 1);
484        assert_eq!(p.buffers[0].name(), "out");
485    }
486
487    #[test]
488    fn ir_program_bundle_buffer_layout() {
489        let p = hypervector_majority_bundle("stack", "out", 8, 5);
490        assert_eq!(p.buffers[0].count(), 5 * 8);
491        assert_eq!(p.buffers[1].count(), 8);
492    }
493
494    #[test]
495    fn bundle_overflow_lowers_to_trap_not_host_panic() {
496        let p = hypervector_majority_bundle("stack", "out", u32::MAX, 2);
497        assert!(p.stats().trap());
498        assert_eq!(p.buffers[0].name(), "out");
499    }
500
501    #[test]
502    fn standard_dim_constants() {
503        assert_eq!(STANDARD_DIM_BITS, STANDARD_DIM_WORDS * 32);
504        const _: () = assert!(STANDARD_DIM_BITS >= 8192);
505    }
506}
vyre_primitives/hash/hypervector.rs

vyre_primitives/hash/
hypervector.rs
