Skip to main content

qualia_core_db/inference/
prompt_lookup.rs

1//! W6a — prompt-lookup (n-gram) speculative decoding: the proposer.
2//!
3//! Standard "prompt lookup decoding" (a.k.a. LLMA): instead of a separate draft model, draft the
4//! next few tokens by finding where the current context suffix already occurred earlier in the same
5//! context (prompt + generated), and proposing the tokens that FOLLOWED that earlier occurrence.
6//! Those drafts are then VERIFIED by one batched forward and the longest agreeing prefix is kept —
7//! so the emitted text is **bit-identical to greedy decode** (the verify step never accepts a token
8//! the model would not have produced greedily). The win is pure latency on repetitive / quoting /
9//! structured text (code, JSON, lists, cited passages); on non-repetitive text it proposes little
10//! and costs ~nothing. This module is the PROPOSER only — pure, allocation-light, unit-tested, no
11//! GPU. The verify/accept wiring lives in the decode loop.
12
13/// Longest n-gram suffix length to try when looking for a recurrence.
14pub const MAX_NGRAM: usize = 3;
15/// Hard cap on draft length (also bounded by the caller's scratch/batch width).
16pub const MAX_DRAFT: usize = 8;
17
18/// A drafted continuation: `tokens[..len]` are the proposed next-token ids.
19#[derive(Debug, Clone, Copy, PartialEq, Eq)]
20pub struct Draft {
21    pub tokens: [u32; MAX_DRAFT],
22    pub len: usize,
23}
24
25impl Draft {
26    #[inline]
27    /// Empty value.
28    pub const fn empty() -> Self {
29        Self {
30            tokens: [0; MAX_DRAFT],
31            len: 0,
32        }
33    }
34    #[inline]
35    /// Slice view.
36    pub fn as_slice(&self) -> &[u32] {
37        &self.tokens[..self.len]
38    }
39}
40
41/// Propose up to `max_draft` tokens by matching the longest available suffix of `ctx` against an
42/// earlier occurrence in `ctx`, and returning the tokens that followed that occurrence.
43///
44/// - Tries suffix lengths `MAX_NGRAM..=1` (longest match first — higher-order n-grams are more
45///   selective, so their continuation is likelier to be accepted).
46/// - For a given n-gram, uses the MOST RECENT earlier occurrence (locality: recent context is the
47///   best predictor of the immediate continuation).
48/// - Never proposes past the end of `ctx` (only real, already-seen tokens are drafted).
49/// - Returns [`Draft::empty`] when nothing recurs (the common case for novel text).
50pub fn propose(ctx: &[u32], max_draft: usize) -> Draft {
51    let k = max_draft.min(MAX_DRAFT);
52    if k == 0 || ctx.len() < 2 {
53        return Draft::empty();
54    }
55    let n = ctx.len();
56    // Try the longest suffix first. Suffix length `g` must leave room for an earlier occurrence
57    // plus at least one following token: earliest match start `i` satisfies `i + g < n` (so
58    // `ctx[i+g]` exists) and `i < n - g` (the match is strictly before the current suffix).
59    let max_g = MAX_NGRAM.min(n - 1);
60    for g in (1..=max_g).rev() {
61        let suffix = &ctx[n - g..];
62        // Search earlier windows [0, n-g) for the LAST occurrence of `suffix`, scanning right→left
63        // so the first hit is the most recent. The match must start at `i` with `i + g <= n - 1`
64        // (i.e. `i <= n - g - 1`) so that at least one continuation token `ctx[i+g]` exists.
65        if n < g + 1 {
66            continue;
67        }
68        let latest_start = n - g - 1; // inclusive upper bound on match start
69        let mut i = latest_start as isize;
70        while i >= 0 {
71            let ii = i as usize;
72            if ctx[ii..ii + g] == *suffix {
73                let mut d = Draft::empty();
74                let src = ii + g; // first continuation token position
75                let avail = n - src; // tokens available after the match
76                let take = avail.min(k);
77                d.tokens[..take].copy_from_slice(&ctx[src..src + take]);
78                d.len = take;
79                if d.len > 0 {
80                    return d;
81                }
82            }
83            i -= 1;
84        }
85    }
86    Draft::empty()
87}
88
89#[cfg(test)]
90mod tests {
91    use super::*;
92
93    #[test]
94    fn empty_on_short_or_novel() {
95        assert_eq!(propose(&[], 4).len, 0);
96        assert_eq!(propose(&[7], 4).len, 0);
97        // strictly increasing, no recurrence
98        assert_eq!(propose(&[1, 2, 3, 4, 5], 4).len, 0);
99    }
100
101    #[test]
102    fn proposes_bigram_continuation() {
103        // "1 2 3 9 | 1 2" → suffix [1,2] recurs at pos 0; the drafter proposes the WHOLE earlier
104        // continuation [3,9,1,2] (the verify step later trims to the model-agreeing prefix — drafting
105        // several ahead is the point).
106        let ctx = [1u32, 2, 3, 9, 1, 2];
107        let d = propose(&ctx, 4);
108        assert_eq!(
109            d.as_slice(),
110            &[3, 9, 1, 2],
111            "drafts the earlier continuation of [1,2]"
112        );
113    }
114
115    #[test]
116    fn prefers_longest_ngram() {
117        // The trigram [7,1,2] and the bigram [1,2] recur with DIFFERENT continuations: after the
118        // earlier [7,1,2] came 9; after the more-recent bare [1,2] came 7. The trigram is more
119        // selective and must win → draft starts with 9, not 7.
120        let ctx = [7u32, 1, 2, 9, 3, 1, 2, 7, 1, 2];
121        let d = propose(&ctx, 4);
122        assert_eq!(
123            d.as_slice()[0],
124            9,
125            "trigram continuation (9), not the bigram's (7)"
126        );
127    }
128
129    #[test]
130    fn uses_most_recent_occurrence() {
131        // Bare [5] recurs at idx 0 (→ next is 1) and idx 2 (→ next is 2). The MOST RECENT earlier
132        // occurrence (idx 2) governs → draft starts with 2, not 1.
133        let ctx = [5u32, 1, 5, 2, 5];
134        let d = propose(&ctx, 3);
135        assert_eq!(d.as_slice()[0], 2, "most-recent [5] is followed by 2");
136    }
137
138    #[test]
139    fn respects_max_draft() {
140        // long repeat so many continuation tokens are available; cap at max_draft.
141        let ctx = [1u32, 2, 3, 4, 5, 6, 7, 1, 2];
142        let d = propose(&ctx, 3);
143        assert_eq!(d.as_slice(), &[3, 4, 5], "capped at max_draft=3");
144        let d2 = propose(&ctx, MAX_DRAFT + 100);
145        assert!(d2.len <= MAX_DRAFT, "never exceeds MAX_DRAFT");
146    }
147
148    #[test]
149    fn no_continuation_when_match_is_the_tail() {
150        // The only earlier occurrence has no following token — must not propose (no OOB read).
151        // suffix [2] ; earlier [2] only at idx that is immediately before the suffix → still has a
152        // continuation here, so construct a true no-continuation: [2, 5, 2] suffix [2] earlier at 0
153        // → continuation [5]; to get none, the match must be at n-g-... covered by bounds. Verify a
154        // degenerate all-same case stays in-bounds and terminates.
155        let ctx = [2u32, 2, 2, 2];
156        let d = propose(&ctx, 4);
157        // suffix [2,2,2] (g=3) earlier occurrence start 0? ctx[0..3]=[2,2,2]==suffix ctx[1..4] → yes,
158        // continuation at src=3 → [2]. Deterministic + in-bounds.
159        assert_eq!(d.as_slice(), &[2]);
160    }
161
162    #[test]
163    fn draft_is_a_prefix_of_real_tokens() {
164        // Whatever is drafted must be tokens that literally appear in ctx (never fabricated) —
165        // the exact-output safety premise. Fuzz a few structured inputs.
166        let inputs: [&[u32]; 3] = [
167            &[1, 2, 1, 2, 1, 2],
168            &[4, 4, 5, 4, 4],
169            &[7, 8, 9, 7, 8, 9, 7],
170        ];
171        for ctx in inputs {
172            let d = propose(ctx, MAX_DRAFT);
173            for &t in d.as_slice() {
174                assert!(
175                    ctx.contains(&t),
176                    "drafted token {t} not present in ctx {ctx:?}"
177                );
178            }
179        }
180    }
181}