spec_stream_engine/
tree_pipeline.rs1use crate::error::EngineError;
2use crate::model::ModelEngine;
3use crate::stream::{GenerationEvent, SpeculativeStream};
4use spec_stream_cache::PagedKvCacheManager;
5use spec_stream_core::{SpeculativeMetrics, SpeculativeTree, TokenId};
6use std::sync::Arc;
7use tokio::sync::mpsc;
8
9#[derive(Debug, Clone)]
11pub struct TreeSpeculativeConfig {
12 pub branching_factor: usize,
14 pub depth: usize,
16 pub max_new_tokens: usize,
18 pub eos_token_id: Option<TokenId>,
20}
21
22impl Default for TreeSpeculativeConfig {
23 fn default() -> Self {
24 Self {
25 branching_factor: 2,
26 depth: 2,
27 max_new_tokens: 64,
28 eos_token_id: Some(2),
29 }
30 }
31}
32
33pub struct TreeSpeculativePipeline<D: ModelEngine, T: ModelEngine> {
35 draft_model: D,
36 target_model: T,
37 cache_manager: Arc<PagedKvCacheManager>,
38 config: TreeSpeculativeConfig,
39}
40
41impl<D: ModelEngine + 'static, T: ModelEngine + 'static> TreeSpeculativePipeline<D, T> {
42 pub fn new(
43 draft_model: D,
44 target_model: T,
45 cache_manager: Arc<PagedKvCacheManager>,
46 config: TreeSpeculativeConfig,
47 ) -> Self {
48 Self {
49 draft_model,
50 target_model,
51 cache_manager,
52 config,
53 }
54 }
55
56 pub fn generate_stream(
58 mut self,
59 prompt: Vec<TokenId>,
60 sequence_id: u64,
61 ) -> Result<SpeculativeStream, EngineError> {
62 let (tx, rx) = mpsc::channel(32);
63
64 self.cache_manager.create_sequence(sequence_id);
65 self.cache_manager
66 .append_tokens(sequence_id, &prompt)
67 .map_err(EngineError::Cache)?;
68
69 tokio::spawn(async move {
70 let mut current_prefix = prompt;
71 let mut total_generated = 0;
72 let mut metrics = SpeculativeMetrics::new();
73
74 while total_generated < self.config.max_new_tokens {
75 let last_token = match current_prefix.last() {
76 Some(&t) => t,
77 None => break,
78 };
79
80 if let Some(eos) = self.config.eos_token_id {
82 if last_token == eos {
83 let _ = tx
84 .send(GenerationEvent::Finished {
85 total_tokens: total_generated,
86 reason: "EOS token reached".into(),
87 })
88 .await;
89 break;
90 }
91 }
92
93 let mut tree = SpeculativeTree::new(last_token);
95 let mut current_level_nodes = vec![0usize]; for _d in 0..self.config.depth {
98 let mut next_level_nodes = Vec::new();
99
100 for &parent_node_idx in ¤t_level_nodes {
101 let parent_token = tree.nodes[parent_node_idx].token_id;
102 let logits = match self.draft_model.forward_token(parent_token).await {
103 Ok(l) => l,
104 Err(e) => {
105 tracing::error!("Draft model tree forward error: {:?}", e);
106 break;
107 }
108 };
109
110 let probs = logits.softmax().unwrap_or_default();
111 let mut indexed: Vec<(usize, f32)> =
112 probs.into_iter().enumerate().collect();
113 indexed.sort_by(|a, b| {
114 b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal)
115 });
116
117 for &(candidate_id, prob) in
118 indexed.iter().take(self.config.branching_factor)
119 {
120 if let Ok(child_idx) =
121 tree.add_child(parent_node_idx, candidate_id as TokenId, prob)
122 {
123 next_level_nodes.push(child_idx);
124 }
125 }
126 }
127
128 if next_level_nodes.is_empty() {
129 break;
130 }
131 current_level_nodes = next_level_nodes;
132 }
133
134 if tree.nodes.len() <= 1 {
135 break;
136 }
137
138 let tree_tokens = tree.token_ids();
140 let _tree_mask = tree.compute_tree_attention_mask();
141
142 let target_logits = match self.target_model.forward_batch(&tree_tokens).await {
143 Ok(l) => l,
144 Err(e) => {
145 tracing::error!("Target model tree forward error: {:?}", e);
146 break;
147 }
148 };
149
150 let tree_result = match tree.verify_greedy(&target_logits) {
152 Ok(r) => r,
153 Err(e) => {
154 tracing::error!("Tree verification error: {:?}", e);
155 break;
156 }
157 };
158
159 let valid_tokens_to_keep = current_prefix.len() + tree_result.accepted_tokens.len();
161 let _ = self
162 .cache_manager
163 .rollback_sequence(sequence_id, valid_tokens_to_keep);
164
165 let _ = self
166 .cache_manager
167 .append_tokens(sequence_id, &[tree_result.emitted_target_token]);
168
169 let draft_nodes_count = tree.nodes.len() - 1;
171 metrics.record_cycle(
172 draft_nodes_count,
173 tree_result.accepted_tokens.len(),
174 tree_result.total_tokens_produced,
175 );
176
177 for &tok in &tree_result.accepted_tokens {
178 current_prefix.push(tok);
179 total_generated += 1;
180 if tx
181 .send(GenerationEvent::Token {
182 token_id: tok,
183 is_draft: true,
184 })
185 .await
186 .is_err()
187 {
188 return;
189 }
190 }
191
192 current_prefix.push(tree_result.emitted_target_token);
193 total_generated += 1;
194 if tx
195 .send(GenerationEvent::Token {
196 token_id: tree_result.emitted_target_token,
197 is_draft: false,
198 })
199 .await
200 .is_err()
201 {
202 return;
203 }
204
205 let _ = tx
206 .send(GenerationEvent::Burst {
207 accepted: tree_result.accepted_tokens.len(),
208 total_produced: tree_result.total_tokens_produced,
209 })
210 .await;
211
212 let _ = tx.send(GenerationEvent::Metrics(metrics.clone())).await;
213
214 if total_generated >= self.config.max_new_tokens {
215 let _ = tx
216 .send(GenerationEvent::Finished {
217 total_tokens: total_generated,
218 reason: "Max new tokens reached".into(),
219 })
220 .await;
221 break;
222 }
223 }
224
225 let _ = self.cache_manager.remove_sequence(sequence_id);
226 });
227
228 Ok(SpeculativeStream::new(rx))
229 }
230}
231
232#[cfg(test)]
233mod tests {
234 use super::*;
235 use crate::model::SyntheticModel;
236 use tokio_stream::StreamExt;
237
238 #[tokio::test]
239 async fn test_tree_speculative_pipeline() {
240 let vocab_size = 50;
241 let draft = SyntheticModel::new("draft-tree", vocab_size, 0.8, 42);
242 let target = SyntheticModel::new("target-tree", vocab_size, 0.95, 1337);
243
244 let cache = Arc::new(PagedKvCacheManager::with_defaults(64));
245 let config = TreeSpeculativeConfig {
246 branching_factor: 2,
247 depth: 2,
248 max_new_tokens: 10,
249 eos_token_id: None,
250 };
251
252 let pipeline = TreeSpeculativePipeline::new(draft, target, cache, config);
253 let mut stream = pipeline.generate_stream(vec![5, 6], 200).unwrap();
254
255 let mut token_count = 0;
256 while let Some(event) = stream.next().await {
257 if let GenerationEvent::Token { .. } = event {
258 token_count += 1;
259 }
260 }
261
262 assert!(token_count >= 10);
263 }
264}