Skip to main content

spec_stream_engine/
tree_pipeline.rs

1use 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/// Configuration for Tree-based Speculative Decoding (Medusa / Eagle style).
10#[derive(Debug, Clone)]
11pub struct TreeSpeculativeConfig {
12    /// Number of candidate branches to expand from each node (typically 2 or 3).
13    pub branching_factor: usize,
14    /// Tree exploration depth (typically 2 or 3).
15    pub depth: usize,
16    /// Maximum new tokens to generate before stopping.
17    pub max_new_tokens: usize,
18    /// Optional End-of-Sequence token ID to terminate generation.
19    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
33/// Orchestrator for Tree-based Speculative Decoding execution and streaming.
34pub 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    /// Starts tree speculative generation from a prompt and returns an asynchronous stream of events.
57    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                // Check EOS
81                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                // 1. TREE DRAFT PHASE: Build multi-branch SpeculativeTree
94                let mut tree = SpeculativeTree::new(last_token);
95                let mut current_level_nodes = vec![0usize]; // starts with root node 0
96
97                for _d in 0..self.config.depth {
98                    let mut next_level_nodes = Vec::new();
99
100                    for &parent_node_idx in &current_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                // 2. TARGET EVALUATION WITH 2D TREE ATTENTION MASK
139                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                // 3. TREE VERIFICATION PHASE
151                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                // 4. KV-CACHE COMMIT & ROLLBACK
160                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                // 5. UPDATE METRICS & EMIT STREAM EVENTS
170                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}