1use crate::error::CoreError;
2use crate::logits::{Logits, TokenId};
3
4#[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#[derive(Debug, Clone, PartialEq)]
16pub struct TreeVerificationResult {
17 pub accepted_tokens: Vec<TokenId>,
19 pub accepted_node_indices: Vec<usize>,
21 pub emitted_target_token: TokenId,
23 pub total_tokens_produced: usize,
25}
26
27#[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 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 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 row[i] = true;
84
85 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 pub fn token_ids(&self) -> Vec<TokenId> {
98 self.nodes.iter().map(|n| n.token_id).collect()
99 }
100
101 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 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 let mut best_path = Vec::new();
123 let mut stack = vec![(0usize, Vec::new())]; 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 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 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 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 let target_logits = vec![
209 make_logits(100, 40), make_logits(100, 99), make_logits(100, 99), make_logits(100, 50), make_logits(100, 77), ];
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}