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}