innr 0.3.0

SIMD-accelerated vector similarity primitives with binary, ternary, and scalar quantization
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188

//! Property-based tests for MaxSim late interaction scoring.

use proptest::prelude::*;

/// Generate query/document token pairs.
fn arb_token_pair(
    query_tokens: usize,
    doc_tokens: usize,
    dim: usize,
) -> impl Strategy<Value = (Vec<Vec<f32>>, Vec<Vec<f32>>)> {
    (
        proptest::collection::vec(proptest::collection::vec(-10.0f32..10.0, dim), query_tokens),
        proptest::collection::vec(proptest::collection::vec(-10.0f32..10.0, dim), doc_tokens),
    )
}

proptest! {
    #![proptest_config(ProptestConfig {
        cases: 200,
        ..ProptestConfig::default()
    })]

    /// MaxSim with empty query returns 0.
    #[test]
    fn maxsim_empty_query_is_zero(
        doc_tokens in proptest::collection::vec(
            proptest::collection::vec(-10.0f32..10.0, 32), 1..8
        )
    ) {
        let empty: Vec<&[f32]> = vec![];
        let doc: Vec<&[f32]> = doc_tokens.iter().map(|v| v.as_slice()).collect();
        let score = innr::maxsim(&empty, &doc);
        prop_assert_eq!(score, 0.0);
    }

    /// MaxSim with empty document returns 0.
    #[test]
    fn maxsim_empty_doc_is_zero(
        query_tokens in proptest::collection::vec(
            proptest::collection::vec(-10.0f32..10.0, 32), 1..8
        )
    ) {
        let query: Vec<&[f32]> = query_tokens.iter().map(|v| v.as_slice()).collect();
        let empty: Vec<&[f32]> = vec![];
        let score = innr::maxsim(&query, &empty);
        prop_assert_eq!(score, 0.0);
    }

    /// MaxSim is NOT commutative (important invariant).
    ///
    /// Uses asymmetric inputs (2 query tokens vs 4 doc tokens) where
    /// maxsim(q, d) sums over 2 query tokens but maxsim(d, q) sums over 4.
    /// The sums have different numbers of terms, so they must differ when
    /// the extra doc tokens contribute non-zero maximums.
    #[test]
    fn maxsim_not_commutative((query, doc) in arb_token_pair(2, 4, 32)) {
        let q: Vec<&[f32]> = query.iter().map(|v| v.as_slice()).collect();
        let d: Vec<&[f32]> = doc.iter().map(|v| v.as_slice()).collect();

        let qd = innr::maxsim(&q, &d);
        let dq = innr::maxsim(&d, &q);

        prop_assert!(qd.is_finite() && dq.is_finite(),
            "Scores should be finite: qd={}, dq={}", qd, dq);

        // maxsim(q, d) sums over 2 query tokens; maxsim(d, q) sums over 4 doc tokens.
        // The two can only be equal if the 2 extra terms in dq are exactly zero,
        // which requires two of the doc token vectors to be orthogonal to every query
        // token. With random f32 values in [-10, 10] this is astronomically unlikely.
        prop_assert_ne!(qd, dq,
            "maxsim(q,d)={} should not equal maxsim(d,q)={} for asymmetric inputs", qd, dq);
    }

    /// MaxSim single query token equals max dot product.
    #[test]
    fn maxsim_single_query_equals_max_dot(
        query_token in proptest::collection::vec(-10.0f32..10.0, 64),
        doc_tokens in proptest::collection::vec(
            proptest::collection::vec(-10.0f32..10.0, 64), 1..16
        )
    ) {
        let query: Vec<&[f32]> = vec![query_token.as_slice()];
        let doc: Vec<&[f32]> = doc_tokens.iter().map(|v| v.as_slice()).collect();

        let maxsim_score = innr::maxsim(&query, &doc);

        // Should equal max(dot(query_token, doc_token) for all doc_tokens)
        let max_dot: f32 = doc_tokens
            .iter()
            .map(|d| innr::dot(&query_token, d))
            .fold(f32::NEG_INFINITY, f32::max);

        let tolerance = max_dot.abs() * 1e-4 + 1e-5;
        prop_assert!(
            (maxsim_score - max_dot).abs() < tolerance,
            "Single query maxsim {} != max dot {} (diff: {})",
            maxsim_score, max_dot, (maxsim_score - max_dot).abs()
        );
    }

    /// MaxSim is additive over query tokens.
    #[test]
    fn maxsim_is_additive(
        (query1, doc) in arb_token_pair(2, 4, 32),
        query2 in proptest::collection::vec(
            proptest::collection::vec(-10.0f32..10.0, 32), 2
        )
    ) {
        let q1: Vec<&[f32]> = query1.iter().map(|v| v.as_slice()).collect();
        let q2: Vec<&[f32]> = query2.iter().map(|v| v.as_slice()).collect();
        let d: Vec<&[f32]> = doc.iter().map(|v| v.as_slice()).collect();

        let score1 = innr::maxsim(&q1, &d);
        let score2 = innr::maxsim(&q2, &d);

        // Combined query
        let mut combined_query = query1.clone();
        combined_query.extend(query2.iter().cloned());
        let combined: Vec<&[f32]> = combined_query.iter().map(|v| v.as_slice()).collect();
        let score_combined = innr::maxsim(&combined, &d);

        let expected = score1 + score2;
        // Use tolerance based on max magnitude to handle catastrophic cancellation
        let max_magnitude = score1.abs().max(score2.abs()).max(1.0);
        let tolerance = max_magnitude * 1e-4;
        prop_assert!(
            (score_combined - expected).abs() < tolerance,
            "Additivity: {} != {} + {} = {} (diff: {}, tol: {})",
            score_combined, score1, score2, expected,
            (score_combined - expected).abs(), tolerance
        );
    }

    /// MaxSim with identical query and doc is positive.
    #[test]
    fn maxsim_identical_is_positive(
        tokens in proptest::collection::vec(
            proptest::collection::vec(-10.0f32..10.0, 32)
                .prop_filter("non-zero", |v| v.iter().any(|x| x.abs() > 0.1)),
            1..8
        )
    ) {
        let t: Vec<&[f32]> = tokens.iter().map(|v| v.as_slice()).collect();
        let score = innr::maxsim(&t, &t);

        prop_assert!(
            score >= 0.0,
            "MaxSim with identical tokens should be non-negative, got {}",
            score
        );
    }

    /// MaxSim-cosine is bounded by query token count.
    #[test]
    fn maxsim_cosine_bounded((query, doc) in arb_token_pair(4, 8, 32)) {
        let q: Vec<&[f32]> = query.iter().map(|v| v.as_slice()).collect();
        let d: Vec<&[f32]> = doc.iter().map(|v| v.as_slice()).collect();

        let score = innr::maxsim_cosine(&q, &d);

        // Each query token contributes at most 1.0 (max cosine similarity)
        let upper_bound = query.len() as f32 + 1e-5;
        let lower_bound = -(query.len() as f32) - 1e-5;

        prop_assert!(
            score >= lower_bound && score <= upper_bound,
            "MaxSim-cosine {} out of bounds [{}, {}]",
            score, lower_bound, upper_bound
        );
    }
}

#[test]
fn test_maxsim_basic_example() {
    // Example from documentation
    let q1 = [1.0f32, 0.0];
    let q2 = [0.0f32, 1.0];
    let d1 = [0.9f32, 0.1]; // best match for q1
    let d2 = [0.1f32, 0.9]; // best match for q2
    let d3 = [0.5f32, 0.5];

    let query: &[&[f32]] = &[&q1, &q2];
    let doc: &[&[f32]] = &[&d1, &d2, &d3];

    let score = innr::maxsim(query, doc);
    // score = max(0.9, 0.1, 0.5) + max(0.1, 0.9, 0.5) = 0.9 + 0.9 = 1.8
    assert!((score - 1.8).abs() < 0.01);
}