1use crate::error::EngineError;
2use crate::model::ModelEngine;
3use crate::pipeline::SpeculativeConfig;
4use crate::stream::GenerationEvent;
5use spec_stream_cache::PagedKvCacheManager;
6use spec_stream_core::{DraftProposal, Logits, SpeculativeMetrics, SpeculativeVerifier, TokenId};
7use std::collections::VecDeque;
8use std::sync::atomic::{AtomicUsize, Ordering};
9use std::sync::{Arc, Mutex as StdMutex};
10use tokio::sync::{mpsc, Mutex as AsyncMutex};
11use tokio::time::Instant;
12
13pub struct QueuedRequest {
15 pub sequence_id: u64,
16 pub prompt: Vec<TokenId>,
17 pub config: SpeculativeConfig,
18 pub sender: mpsc::Sender<GenerationEvent>,
19 pub priority: usize,
20 pub created_at: Instant,
21}
22
23impl QueuedRequest {
24 pub fn new(
25 sequence_id: u64,
26 prompt: Vec<TokenId>,
27 config: SpeculativeConfig,
28 sender: mpsc::Sender<GenerationEvent>,
29 ) -> Self {
30 Self {
31 sequence_id,
32 prompt,
33 config,
34 sender,
35 priority: 0,
36 created_at: Instant::now(),
37 }
38 }
39}
40
41struct ActiveSequence {
43 sequence_id: u64,
44 current_prefix: Vec<TokenId>,
45 total_generated: usize,
46 config: SpeculativeConfig,
47 current_k: usize,
48 ema_acceptance: Option<f32>,
49 metrics: SpeculativeMetrics,
50 sender: mpsc::Sender<GenerationEvent>,
51}
52
53#[derive(Debug, Clone, Default)]
55pub struct SchedulerStats {
56 pub active_sequences: usize,
57 pub queued_requests: usize,
58 pub completed_sequences: usize,
59 pub total_tokens_emitted: usize,
60 pub total_batch_steps: usize,
61}
62
63pub struct ContinuousBatchScheduler<D: ModelEngine, T: ModelEngine> {
66 draft_model: Arc<AsyncMutex<D>>,
67 target_model: Arc<AsyncMutex<T>>,
68 cache_manager: Arc<PagedKvCacheManager>,
69 queue: Arc<StdMutex<VecDeque<QueuedRequest>>>,
70 active: Arc<StdMutex<Vec<ActiveSequence>>>,
71 max_batch_size: usize,
72 completed_counter: Arc<AtomicUsize>,
73 tokens_emitted_counter: Arc<AtomicUsize>,
74 batch_steps_counter: Arc<AtomicUsize>,
75}
76
77impl<D: ModelEngine + 'static, T: ModelEngine + 'static> ContinuousBatchScheduler<D, T> {
78 pub fn new(
79 draft_model: D,
80 target_model: T,
81 cache_manager: Arc<PagedKvCacheManager>,
82 max_batch_size: usize,
83 ) -> Self {
84 Self {
85 draft_model: Arc::new(AsyncMutex::new(draft_model)),
86 target_model: Arc::new(AsyncMutex::new(target_model)),
87 cache_manager,
88 queue: Arc::new(StdMutex::new(VecDeque::new())),
89 active: Arc::new(StdMutex::new(Vec::new())),
90 max_batch_size: max_batch_size.max(1),
91 completed_counter: Arc::new(AtomicUsize::new(0)),
92 tokens_emitted_counter: Arc::new(AtomicUsize::new(0)),
93 batch_steps_counter: Arc::new(AtomicUsize::new(0)),
94 }
95 }
96
97 pub fn submit(&self, request: QueuedRequest) -> Result<(), EngineError> {
99 let mut queue = self.queue.lock().unwrap();
100 queue.push_back(request);
101 Ok(())
102 }
103
104 pub fn queue_len(&self) -> usize {
106 self.queue.lock().unwrap().len()
107 }
108
109 pub fn active_len(&self) -> usize {
111 self.active.lock().unwrap().len()
112 }
113
114 pub fn stats(&self) -> SchedulerStats {
116 SchedulerStats {
117 active_sequences: self.active.lock().unwrap().len(),
118 queued_requests: self.queue.lock().unwrap().len(),
119 completed_sequences: self.completed_counter.load(Ordering::Relaxed),
120 total_tokens_emitted: self.tokens_emitted_counter.load(Ordering::Relaxed),
121 total_batch_steps: self.batch_steps_counter.load(Ordering::Relaxed),
122 }
123 }
124
125 pub async fn step_iteration(&self) -> Result<usize, EngineError> {
128 self.batch_steps_counter.fetch_add(1, Ordering::Relaxed);
129
130 {
132 let mut active = self.active.lock().unwrap();
133 let mut queue = self.queue.lock().unwrap();
134
135 while active.len() < self.max_batch_size && !queue.is_empty() {
136 if self.cache_manager.free_blocks() < 2 {
138 break;
139 }
140
141 if let Some(req) = queue.pop_front() {
142 self.cache_manager.create_sequence(req.sequence_id);
143 let _ = self
144 .cache_manager
145 .append_tokens(req.sequence_id, &req.prompt);
146
147 let initial_k = req.config.k_draft_tokens;
148 active.push(ActiveSequence {
149 sequence_id: req.sequence_id,
150 current_prefix: req.prompt,
151 total_generated: 0,
152 config: req.config,
153 current_k: initial_k,
154 ema_acceptance: None,
155 metrics: SpeculativeMetrics::new(),
156 sender: req.sender,
157 });
158 }
159 }
160 }
161
162 let num_active = self.active.lock().unwrap().len();
163 if num_active == 0 {
164 return Ok(0);
165 }
166
167 struct SeqProposal {
169 seq_idx: usize,
170 last_token: TokenId,
171 proposal: DraftProposal,
172 }
173
174 let mut proposals = Vec::with_capacity(num_active);
175 {
176 let active = self.active.lock().unwrap();
177 for (idx, seq) in active.iter().enumerate() {
178 if let Some(&last_t) = seq.current_prefix.last() {
179 proposals.push(SeqProposal {
180 seq_idx: idx,
181 last_token: last_t,
182 proposal: DraftProposal::new(),
183 });
184 }
185 }
186 }
187
188 for p in &mut proposals {
190 let k = self.active.lock().unwrap()[p.seq_idx].current_k;
191 let mut draft_token = p.last_token;
192
193 for _ in 0..k {
194 let logits = {
195 let mut draft_guard = self.draft_model.lock().await;
196 draft_guard.forward_token(draft_token).await?
197 };
198
199 let next_id = match logits.argmax() {
200 Ok(id) => id,
201 Err(_) => break,
202 };
203
204 let prob = logits
205 .softmax()
206 .ok()
207 .and_then(|probs| probs.get(next_id as usize).copied())
208 .unwrap_or(0.85);
209
210 p.proposal.push(next_id, prob);
211 draft_token = next_id;
212 }
213 }
214
215 let mut total_tokens_this_step = 0;
217 let mut finished_indices = Vec::new();
218
219 for p in proposals {
220 if p.proposal.is_empty() {
221 continue;
222 }
223
224 let proposed_ids = p.proposal.token_ids();
225 let seq_id = self.active.lock().unwrap()[p.seq_idx].sequence_id;
226 let _ = self.cache_manager.append_tokens(seq_id, &proposed_ids);
227
228 let mut target_inputs = Vec::with_capacity(proposed_ids.len() + 1);
229 target_inputs.push(p.last_token);
230 target_inputs.extend_from_slice(&proposed_ids);
231
232 let target_logits: Vec<Logits> = {
233 let mut target_guard = self.target_model.lock().await;
234 target_guard.forward_batch(&target_inputs).await?
235 };
236
237 let verifier = {
238 let active = self.active.lock().unwrap();
239 SpeculativeVerifier::new(active[p.seq_idx].config.strategy)
240 };
241
242 let verif_result = match verifier.verify(&p.proposal, &target_logits) {
243 Ok(r) => r,
244 Err(e) => {
245 tracing::error!("Scheduler verification error: {:?}", e);
246 continue;
247 }
248 };
249
250 let mut active = self.active.lock().unwrap();
252 let seq = &mut active[p.seq_idx];
253
254 let valid_tokens_to_keep = seq.current_prefix.len() + verif_result.accepted_count;
255 let _ = self
256 .cache_manager
257 .rollback_sequence(seq.sequence_id, valid_tokens_to_keep);
258 let _ = self
259 .cache_manager
260 .append_tokens(seq.sequence_id, &[verif_result.emitted_target_token]);
261
262 seq.metrics.record_cycle(
263 p.proposal.len(),
264 verif_result.accepted_count,
265 verif_result.total_tokens_produced,
266 );
267
268 for &tok in &verif_result.accepted_tokens {
270 seq.current_prefix.push(tok);
271 seq.total_generated += 1;
272 total_tokens_this_step += 1;
273 let _ = seq.sender.try_send(GenerationEvent::Token {
274 token_id: tok,
275 is_draft: true,
276 });
277 }
278
279 seq.current_prefix.push(verif_result.emitted_target_token);
281 seq.total_generated += 1;
282 total_tokens_this_step += 1;
283 let _ = seq.sender.try_send(GenerationEvent::Token {
284 token_id: verif_result.emitted_target_token,
285 is_draft: false,
286 });
287
288 let acc_rate = verif_result.accepted_count as f32 / p.proposal.len().max(1) as f32;
290 let ema = match seq.ema_acceptance {
291 Some(prev) => 0.5 * acc_rate + 0.5 * prev,
292 None => acc_rate,
293 };
294 seq.ema_acceptance = Some(ema);
295
296 if seq.config.adaptive_k {
297 if ema >= 0.75 && seq.current_k < seq.config.max_k {
298 seq.current_k += 1;
299 } else if ema <= 0.35 && seq.current_k > seq.config.min_k {
300 seq.current_k -= 1;
301 }
302 }
303
304 let eos_reached = seq.config.eos_token_id == Some(verif_result.emitted_target_token);
306 let max_reached = seq.total_generated >= seq.config.max_new_tokens;
307
308 if eos_reached || max_reached {
309 let reason = if eos_reached { "EOS" } else { "MaxTokens" };
310 let _ = seq.sender.try_send(GenerationEvent::Finished {
311 total_tokens: seq.total_generated,
312 reason: reason.into(),
313 });
314 finished_indices.push(p.seq_idx);
315 }
316 }
317
318 self.tokens_emitted_counter
319 .fetch_add(total_tokens_this_step, Ordering::Relaxed);
320
321 if !finished_indices.is_empty() {
323 finished_indices.sort_unstable_by(|a, b| b.cmp(a)); let mut active = self.active.lock().unwrap();
325 for idx in finished_indices {
326 let finished_seq = active.swap_remove(idx);
327 let _ = self.cache_manager.remove_sequence(finished_seq.sequence_id);
328 self.completed_counter.fetch_add(1, Ordering::Relaxed);
329 }
330 }
331
332 Ok(total_tokens_this_step)
333 }
334}
335
336#[cfg(test)]
337mod tests {
338 use super::*;
339 use crate::model::SyntheticModel;
340
341 #[tokio::test]
342 async fn test_continuous_batch_scheduler() {
343 let vocab_size = 50;
344 let draft = SyntheticModel::new("draft", vocab_size, 0.8, 42);
345 let target = SyntheticModel::new("target", vocab_size, 0.95, 1337);
346 let cache = Arc::new(PagedKvCacheManager::with_defaults(64));
347
348 let scheduler = ContinuousBatchScheduler::new(draft, target, cache, 4);
349
350 let (tx1, mut rx1) = mpsc::channel(32);
351 let (tx2, mut rx2) = mpsc::channel(32);
352
353 let config1 = SpeculativeConfig {
354 max_new_tokens: 6,
355 ..Default::default()
356 };
357 let config2 = SpeculativeConfig {
358 max_new_tokens: 8,
359 ..Default::default()
360 };
361
362 scheduler
363 .submit(QueuedRequest::new(101, vec![1, 2], config1, tx1))
364 .unwrap();
365 scheduler
366 .submit(QueuedRequest::new(102, vec![3, 4], config2, tx2))
367 .unwrap();
368
369 assert_eq!(scheduler.queue_len(), 2);
370 assert_eq!(scheduler.active_len(), 0);
371
372 let mut iterations = 0;
374 while scheduler.active_len() > 0 || scheduler.queue_len() > 0 {
375 let tokens = scheduler.step_iteration().await.unwrap();
376 iterations += 1;
377 if iterations > 20 {
378 break;
379 }
380 if tokens == 0 && scheduler.active_len() == 0 {
381 break;
382 }
383 }
384
385 let stats = scheduler.stats();
386 assert_eq!(stats.completed_sequences, 2);
387 assert!(stats.total_tokens_emitted >= 14);
388
389 let mut tokens_req1 = 0;
391 while let Ok(event) = rx1.try_recv() {
392 if let GenerationEvent::Token { .. } = event {
393 tokens_req1 += 1;
394 }
395 }
396 assert!(tokens_req1 >= 6);
397
398 let mut tokens_req2 = 0;
399 while let Ok(event) = rx2.try_recv() {
400 if let GenerationEvent::Token { .. } = event {
401 tokens_req2 += 1;
402 }
403 }
404 assert!(tokens_req2 >= 8);
405 }
406}