Skip to main content

spec_stream_engine/
prompt_lookup.rs

1//! # Prompt Lookup Speculative Decoding Engine
2//!
3//! Implements Prompt Lookup Decoding (n-gram assisted drafting), inspired by
4//! Saxena & Arora (2023) and vLLM's zero-model speculative decoding.
5//!
6//! In tasks like RAG, code editing, summarization, and structured generation,
7//! generated tokens are frequently repeated substrings of the prompt or recent context.
8//! This engine extracts candidate tokens directly from the prompt in nanoseconds
9//! with **zero GPU compute** and **zero draft model weights**.
10
11use crate::error::EngineError;
12use crate::model::ModelEngine;
13use spec_stream_core::{DraftProposal, Logits, TokenId};
14
15/// Configuration for prompt lookup n-gram search.
16#[derive(Debug, Clone)]
17pub struct PromptLookupConfig {
18    /// Maximum n-gram size to search for matching suffixes (default: 3).
19    pub max_ngram_size: usize,
20    /// Minimum n-gram size allowed for a valid match (default: 1).
21    pub min_ngram_size: usize,
22    /// Default vocab size for generating synthetic logits.
23    pub vocab_size: usize,
24}
25
26impl Default for PromptLookupConfig {
27    fn default() -> Self {
28        Self {
29            max_ngram_size: 3,
30            min_ngram_size: 1,
31            vocab_size: 32000,
32        }
33    }
34}
35
36/// Prompt Lookup speculative drafting engine.
37///
38/// Searches for matching n-gram suffixes in the prompt context to predict subsequent tokens.
39#[derive(Debug, Clone)]
40pub struct PromptLookupEngine {
41    /// The reference prompt or document context tokens.
42    context: Vec<TokenId>,
43    config: PromptLookupConfig,
44    /// Step counter for telemetry.
45    step_counter: usize,
46}
47
48impl PromptLookupEngine {
49    /// Creates a new prompt lookup engine initialized with a prompt context.
50    pub fn new(context: Vec<TokenId>, config: PromptLookupConfig) -> Self {
51        Self {
52            context,
53            config,
54            step_counter: 0,
55        }
56    }
57
58    /// Appends generated tokens to the active context pool so the engine learns from ongoing generation.
59    pub fn append_to_context(&mut self, tokens: &[TokenId]) {
60        self.context.extend_from_slice(tokens);
61    }
62
63    /// Finds candidate tokens by matching the suffix of `history` against `self.context`.
64    pub fn find_candidate_tokens(&self, history: &[TokenId], k: usize) -> Vec<TokenId> {
65        if history.is_empty() || self.context.is_empty() || k == 0 {
66            return Vec::new();
67        }
68
69        let max_n = self.config.max_ngram_size.min(history.len());
70        let min_n = self.config.min_ngram_size;
71
72        // Try largest n-gram match first down to min_n
73        for n in (min_n..=max_n).rev() {
74            let query_ngram = &history[history.len() - n..];
75
76            // Scan context for the latest match of this n-gram (excluding the exact tail)
77            if self.context.len() < n + 1 {
78                continue;
79            }
80
81            let search_limit = self.context.len().saturating_sub(n);
82            // Search backwards so we prioritize the most recent context
83            for i in (0..search_limit).rev() {
84                if &self.context[i..i + n] == query_ngram {
85                    // Match found! Extract up to k subsequent tokens
86                    let start = i + n;
87                    let end = (start + k).min(self.context.len());
88                    let candidates = self.context[start..end].to_vec();
89                    if !candidates.is_empty() {
90                        return candidates;
91                    }
92                }
93            }
94        }
95
96        Vec::new()
97    }
98
99    /// Generates a speculative `DraftProposal` directly from prompt n-gram matching.
100    pub fn draft_proposal(&self, history: &[TokenId], k: usize) -> DraftProposal {
101        let candidates = self.find_candidate_tokens(history, k);
102        let mut proposal = DraftProposal::new();
103
104        for (idx, &token_id) in candidates.iter().enumerate() {
105            // High confidence for prompt matches (scaling slightly with position)
106            let prob = 0.95 - (idx as f32 * 0.05).max(0.0);
107            proposal.push(token_id, prob);
108        }
109
110        proposal
111    }
112}
113
114impl ModelEngine for PromptLookupEngine {
115    async fn forward_batch(&mut self, tokens: &[TokenId]) -> Result<Vec<Logits>, EngineError> {
116        self.step_counter += 1;
117        let mut results = Vec::with_capacity(tokens.len() + 1);
118
119        // For each token in tokens, predict next token using lookup
120        for (idx, &tok) in tokens.iter().enumerate() {
121            let history = &tokens[..=idx];
122            let candidates = self.find_candidate_tokens(history, 1);
123            let next_tok = candidates.first().copied().unwrap_or(tok);
124
125            let mut vals = vec![0.0f32; self.config.vocab_size];
126            if (next_tok as usize) < self.config.vocab_size {
127                vals[next_tok as usize] = 10.0;
128            }
129            results.push(Logits::new(vals));
130        }
131
132        // Bonus prediction
133        let last_token = tokens.last().copied().unwrap_or(1);
134        let mut bonus_vals = vec![0.0f32; self.config.vocab_size];
135        let bonus_idx = (last_token as usize + 1) % self.config.vocab_size;
136        bonus_vals[bonus_idx] = 10.0;
137        results.push(Logits::new(bonus_vals));
138
139        Ok(results)
140    }
141
142    async fn forward_token(&mut self, token: TokenId) -> Result<Logits, EngineError> {
143        self.step_counter += 1;
144        let candidates = self.find_candidate_tokens(&[token], 1);
145        let next_tok = candidates.first().copied().unwrap_or(token);
146
147        let mut vals = vec![0.0f32; self.config.vocab_size];
148        if (next_tok as usize) < self.config.vocab_size {
149            vals[next_tok as usize] = 10.0;
150        }
151
152        Ok(Logits::new(vals))
153    }
154}
155
156#[cfg(test)]
157mod tests {
158    use super::*;
159
160    #[test]
161    fn test_prompt_lookup_exact_ngram_match() {
162        // Prompt context: "The quick brown fox jumps over the lazy dog"
163        // Tokens:        [ 10,  20,   30,   40, 50,   60,  10, 70,  80 ]
164        let context = vec![10, 20, 30, 40, 50, 60, 10, 70, 80];
165        let engine = PromptLookupEngine::new(context, PromptLookupConfig::default());
166
167        // History: "The quick" -> [10, 20]
168        // Should predict: "brown fox jumps" -> [30, 40, 50]
169        let candidates = engine.find_candidate_tokens(&[10, 20], 3);
170        assert_eq!(candidates, vec![30, 40, 50]);
171    }
172
173    #[test]
174    fn test_prompt_lookup_fallback_smaller_ngram() {
175        let context = vec![100, 200, 300, 400];
176        let engine = PromptLookupEngine::new(context, PromptLookupConfig::default());
177
178        // Query: [999, 200] -> 2-gram [999, 200] has no match, but 1-gram [200] matches!
179        let candidates = engine.find_candidate_tokens(&[999, 200], 2);
180        assert_eq!(candidates, vec![300, 400]);
181    }
182
183    #[test]
184    fn test_prompt_lookup_draft_proposal() {
185        let context = vec![1, 2, 3, 4, 5, 6, 7];
186        let engine = PromptLookupEngine::new(context, PromptLookupConfig::default());
187
188        let proposal = engine.draft_proposal(&[1, 2], 3);
189        assert_eq!(proposal.len(), 3);
190        assert_eq!(proposal.token_ids(), vec![3, 4, 5]);
191        assert!(proposal.candidates[0].draft_prob > 0.8);
192    }
193}