Skip to main content

spec_stream_core/
tree.rs

1use crate::error::CoreError;
2use crate::logits::{Logits, TokenId};
3
4/// Node in a speculative candidate tree (used in tree-based speculative decoding like Medusa / Eagle).
5#[derive(Debug, Clone, PartialEq)]
6pub struct TreeNode {
7    pub token_id: TokenId,
8    pub parent: Option<usize>,
9    pub children: Vec<usize>,
10    pub depth: usize,
11    pub cumulative_prob: f32,
12}
13
14/// The result of verifying a speculative tree against the target model.
15#[derive(Debug, Clone, PartialEq)]
16pub struct TreeVerificationResult {
17    /// The token IDs along the best accepted path (excluding the root).
18    pub accepted_tokens: Vec<TokenId>,
19    /// The node indices in the tree corresponding to the accepted path.
20    pub accepted_node_indices: Vec<usize>,
21    /// The token emitted by the target model from the terminal accepted node.
22    pub emitted_target_token: TokenId,
23    /// Total number of tokens produced in this cycle.
24    pub total_tokens_produced: usize,
25}
26
27/// Tree structure representing multiple branch proposals for speculative decoding.
28#[derive(Debug, Clone, Default)]
29pub struct SpeculativeTree {
30    pub nodes: Vec<TreeNode>,
31}
32
33impl SpeculativeTree {
34    pub fn new(root_token: TokenId) -> Self {
35        Self {
36            nodes: vec![TreeNode {
37                token_id: root_token,
38                parent: None,
39                children: Vec::new(),
40                depth: 0,
41                cumulative_prob: 1.0,
42            }],
43        }
44    }
45
46    /// Adds a child branch to an existing node.
47    pub fn add_child(
48        &mut self,
49        parent_idx: usize,
50        token_id: TokenId,
51        prob: f32,
52    ) -> Result<usize, CoreError> {
53        if parent_idx >= self.nodes.len() {
54            return Err(CoreError::TreeError(format!(
55                "Parent node index {parent_idx} out of range"
56            )));
57        }
58
59        let parent_depth = self.nodes[parent_idx].depth;
60        let parent_prob = self.nodes[parent_idx].cumulative_prob;
61        let new_idx = self.nodes.len();
62
63        self.nodes.push(TreeNode {
64            token_id,
65            parent: Some(parent_idx),
66            children: Vec::new(),
67            depth: parent_depth + 1,
68            cumulative_prob: parent_prob * prob,
69        });
70
71        self.nodes[parent_idx].children.push(new_idx);
72        Ok(new_idx)
73    }
74
75    /// Generates the 2D Boolean causal/tree attention mask for parallel target model execution.
76    /// Returns an NxN boolean matrix where `mask[i][j] == true` if node `i` can attend to node `j`.
77    pub fn compute_tree_attention_mask(&self) -> Vec<Vec<bool>> {
78        let n = self.nodes.len();
79        let mut mask = vec![vec![false; n]; n];
80
81        for (i, row) in mask.iter_mut().enumerate().take(n) {
82            // A node can always attend to itself
83            row[i] = true;
84
85            // And to all its ancestors in the tree
86            let mut curr = self.nodes[i].parent;
87            while let Some(parent_idx) = curr {
88                row[parent_idx] = true;
89                curr = self.nodes[parent_idx].parent;
90            }
91        }
92
93        mask
94    }
95
96    /// Returns the flattened list of token IDs in tree order.
97    pub fn token_ids(&self) -> Vec<TokenId> {
98        self.nodes.iter().map(|n| n.token_id).collect()
99    }
100
101    /// Verifies the entire candidate tree against the target model's logits.
102    /// Finds the longest valid path where the target model's prediction at each parent matches the child token.
103    pub fn verify_greedy(
104        &self,
105        target_logits: &[Logits],
106    ) -> Result<TreeVerificationResult, CoreError> {
107        let n = self.nodes.len();
108        if target_logits.len() < n {
109            return Err(CoreError::DimensionMismatch {
110                expected: n,
111                actual: target_logits.len(),
112            });
113        }
114
115        // Compute argmax predictions for each node in the tree
116        let mut target_preds = Vec::with_capacity(n);
117        for logits in target_logits.iter().take(n) {
118            target_preds.push(logits.argmax()?);
119        }
120
121        // Traverse using DFS / BFS to find the longest accepted branch
122        let mut best_path = Vec::new();
123        let mut stack = vec![(0usize, Vec::new())]; // (current_node_idx, current_path)
124
125        while let Some((node_idx, path)) = stack.pop() {
126            let mut extended = false;
127            let expected_next = target_preds[node_idx];
128
129            for &child_idx in &self.nodes[node_idx].children {
130                // If child matches the target model's prediction from node_idx
131                if self.nodes[child_idx].token_id == expected_next {
132                    let mut child_path = path.clone();
133                    child_path.push(child_idx);
134                    stack.push((child_idx, child_path));
135                    extended = true;
136                }
137            }
138
139            if !extended && path.len() > best_path.len() {
140                best_path = path;
141            }
142        }
143
144        // The terminal node of the best accepted path (or root 0 if no children accepted)
145        let terminal_node = best_path.last().copied().unwrap_or(0);
146        let emitted_token = target_preds[terminal_node];
147
148        let accepted_tokens: Vec<TokenId> = best_path
149            .iter()
150            .map(|&idx| self.nodes[idx].token_id)
151            .collect();
152
153        let total_tokens_produced = accepted_tokens.len() + 1;
154
155        Ok(TreeVerificationResult {
156            accepted_tokens,
157            accepted_node_indices: best_path,
158            emitted_target_token: emitted_token,
159            total_tokens_produced,
160        })
161    }
162}
163
164#[cfg(test)]
165mod tests {
166    use super::*;
167
168    fn make_logits(vocab_size: usize, target_token: usize) -> Logits {
169        let mut vals = vec![0.0f32; vocab_size];
170        vals[target_token] = 10.0;
171        Logits::new(vals)
172    }
173
174    #[test]
175    fn test_tree_attention_mask() {
176        let mut tree = SpeculativeTree::new(100);
177        let a = tree.add_child(0, 101, 0.8).unwrap();
178        let _b = tree.add_child(a, 102, 0.7).unwrap();
179        let _c = tree.add_child(0, 103, 0.2).unwrap();
180
181        let mask = tree.compute_tree_attention_mask();
182        assert_eq!(mask.len(), 4);
183
184        assert!(mask[2][2]);
185        assert!(mask[2][1]);
186        assert!(mask[2][0]);
187        assert!(!mask[2][3]);
188
189        assert!(mask[3][3]);
190        assert!(mask[3][0]);
191        assert!(!mask[3][1]);
192        assert!(!mask[3][2]);
193    }
194
195    #[test]
196    fn test_tree_speculative_verification() {
197        // Tree:
198        // Root (0, id=10)
199        //   ├── Branch 1: Child A (1, id=20) -> Child B (2, id=30)
200        //   └── Branch 2: Child C (3, id=40) -> Child D (4, id=50)
201        let mut tree = SpeculativeTree::new(10);
202        let a = tree.add_child(0, 20, 0.5).unwrap();
203        let _b = tree.add_child(a, 30, 0.5).unwrap();
204        let c = tree.add_child(0, 40, 0.5).unwrap();
205        let _d = tree.add_child(c, 50, 0.5).unwrap();
206
207        // Suppose Root predicts 40 (Branch 2 chosen), Child C predicts 50, and Child D predicts 99 (Bonus token)
208        let target_logits = vec![
209            make_logits(100, 40), // From Root -> matches Child C (3)
210            make_logits(100, 99), // Child A (ignored)
211            make_logits(100, 99), // Child B (ignored)
212            make_logits(100, 50), // From Child C -> matches Child D (4)
213            make_logits(100, 77), // From Child D -> Bonus token = 77
214        ];
215
216        let result = tree.verify_greedy(&target_logits).unwrap();
217        assert_eq!(result.accepted_tokens, vec![40, 50]);
218        assert_eq!(result.accepted_node_indices, vec![3, 4]);
219        assert_eq!(result.emitted_target_token, 77);
220        assert_eq!(result.total_tokens_produced, 3);
221    }
222}