1use futures_util::{stream, StreamExt, TryStreamExt};
2use ml_runtime_backend::DecisionModel;
3use ml_runtime_common::{CancellationToken, RuntimeError, RuntimeResult};
4use ml_runtime_inference::{
5 DecisionDependencyCondition, DecisionExecution, DecisionExecutionDiagnostics,
6 DecisionExecutionPlan, DecisionExecutionPolicy, DecisionExecutionStrategy,
7 DecisionGraphRequest, DecisionModelCapabilities, DecisionPlanStage, DecisionRequest,
8 DecisionResult, DecisionValue, PlannedDecisionResult, TypedDecision,
9};
10use std::{
11 collections::{BTreeMap, BTreeSet},
12 sync::Arc,
13 time::Instant,
14};
15
16#[derive(Clone, Debug, Default)]
17pub struct DecisionPlanner;
18
19impl DecisionPlanner {
20 pub fn plan(
21 &self,
22 request: &DecisionGraphRequest,
23 capabilities: &DecisionModelCapabilities,
24 ) -> RuntimeResult<DecisionExecutionPlan> {
25 let levels = validate_graph(request)?;
26 let count = request.nodes.len();
27 let has_dependencies = request
28 .nodes
29 .iter()
30 .any(|node| !node.dependencies.is_empty());
31 let (strategy, reason) = if count == 1 {
32 (DecisionExecutionStrategy::Single, "single_node")
33 } else if has_dependencies && request.policy.allow_selective_execution {
34 (DecisionExecutionStrategy::Selective, "dependency_graph")
35 } else if let Some(batch_size) = effective_batch_size(capabilities, &request.policy, count)
36 {
37 (
38 DecisionExecutionStrategy::Batched { batch_size },
39 "backend_batching",
40 )
41 } else if let Some(concurrency) =
42 effective_parallelism(capabilities, &request.policy, count)
43 {
44 (
45 DecisionExecutionStrategy::Parallel { concurrency },
46 "bounded_parallelism",
47 )
48 } else {
49 (
50 DecisionExecutionStrategy::Sequential,
51 if capabilities.batch_size == Some(1) {
52 "batch_size_1"
53 } else {
54 "serial_capability"
55 },
56 )
57 };
58 let stages = levels
59 .into_iter()
60 .map(|indices| {
61 let nodes: Vec<_> = indices
62 .iter()
63 .map(|index| request.nodes[*index].question.name.clone())
64 .collect();
65 let size = match strategy {
66 DecisionExecutionStrategy::Batched { batch_size } => batch_size,
67 DecisionExecutionStrategy::Selective => {
68 effective_batch_size(capabilities, &request.policy, nodes.len())
69 .unwrap_or(1)
70 }
71 _ => 1,
72 };
73 DecisionPlanStage {
74 batches: nodes.chunks(size).map(<[String]>::to_vec).collect(),
75 nodes,
76 }
77 })
78 .collect();
79 Ok(DecisionExecutionPlan {
80 strategy,
81 reason: reason.to_owned(),
82 stages,
83 })
84 }
85}
86
87pub async fn execute_graph(
88 model: Arc<dyn DecisionModel>,
89 request: DecisionGraphRequest,
90 cancellation: Option<CancellationToken>,
91) -> RuntimeResult<PlannedDecisionResult> {
92 if cancellation
93 .as_ref()
94 .is_some_and(CancellationToken::is_cancelled)
95 {
96 return Err(RuntimeError::Cancelled);
97 }
98 let capabilities = model.capabilities();
99 if !capabilities.supports_structured_decisions {
100 return Err(RuntimeError::CapabilityMismatch {
101 reason: "loaded model does not support structured decisions".to_owned(),
102 });
103 }
104 let plan = DecisionPlanner.plan(&request, &capabilities)?;
105 let started = Instant::now();
106 let mut pending: BTreeSet<usize> = (0..request.nodes.len()).collect();
107 let mut skipped = BTreeSet::new();
108 let mut resolved: BTreeMap<String, TypedDecision> = BTreeMap::new();
109 let mut decisions: Vec<Option<TypedDecision>> = vec![None; request.nodes.len()];
110 let mut first_result: Option<DecisionResult> = None;
111 let mut input_tokens = 0_u64;
112 let mut output_tokens = 0_u64;
113 let mut batches = Vec::new();
114 let mut max_concurrency = 1_usize;
115
116 while !pending.is_empty() {
117 if cancellation
118 .as_ref()
119 .is_some_and(CancellationToken::is_cancelled)
120 {
121 return Err(RuntimeError::Cancelled);
122 }
123 if request.policy.allow_selective_execution {
124 loop {
125 let newly_skipped: Vec<_> = pending
126 .iter()
127 .copied()
128 .filter(|index| {
129 request.nodes[*index].dependencies.iter().any(|dependency| {
130 let dependency_index = request
131 .nodes
132 .iter()
133 .position(|node| node.question.name == dependency.decision)
134 .expect("validated dependency");
135 skipped.contains(&dependency_index)
136 || resolved.get(&dependency.decision).is_some_and(|decision| {
137 !condition_matches(&dependency.condition, &decision.value)
138 })
139 })
140 })
141 .collect();
142 if newly_skipped.is_empty() {
143 break;
144 }
145 for index in newly_skipped {
146 pending.remove(&index);
147 skipped.insert(index);
148 }
149 }
150 }
151 let eligible: Vec<_> = pending
152 .iter()
153 .copied()
154 .filter(|index| {
155 request.nodes[*index]
156 .dependencies
157 .iter()
158 .all(|dependency| resolved.contains_key(&dependency.decision))
159 })
160 .collect();
161 if eligible.is_empty() {
162 return Err(RuntimeError::InvalidRequest {
163 reason: "decision graph could not make progress".to_owned(),
164 });
165 }
166 let wave = execute_wave(
167 model.clone(),
168 &request,
169 &capabilities,
170 &eligible,
171 cancellation.clone(),
172 )
173 .await?;
174 max_concurrency = max_concurrency.max(wave.max_concurrency);
175 batches.extend(wave.batches);
176 for (index, result) in wave.results {
177 input_tokens = input_tokens.saturating_add(result.execution.input_tokens);
178 output_tokens = output_tokens.saturating_add(result.execution.output_tokens);
179 let decision =
180 result
181 .decisions
182 .first()
183 .cloned()
184 .ok_or_else(|| RuntimeError::InvalidOutput {
185 reason: "decision execution returned no typed result".to_owned(),
186 })?;
187 resolved.insert(decision.name.clone(), decision.clone());
188 decisions[index] = Some(decision);
189 pending.remove(&index);
190 first_result.get_or_insert(result);
191 }
192 }
193
194 let mut result = first_result.ok_or_else(|| RuntimeError::InvalidRequest {
195 reason: "decision graph executed no nodes".to_owned(),
196 })?;
197 result.decisions = decisions.into_iter().flatten().collect();
198 result.execution = DecisionExecution {
199 latency: started.elapsed(),
200 input_tokens,
201 output_tokens,
202 };
203 let planning = DecisionExecutionDiagnostics {
204 capabilities,
205 strategy: plan.strategy,
206 reason: plan.reason,
207 requested_nodes: request.nodes.len(),
208 executed_nodes: result.decisions.len(),
209 skipped_nodes: skipped.len(),
210 batches,
211 max_concurrency,
212 cancelled: false,
213 };
214 Ok(PlannedDecisionResult { result, planning })
215}
216
217struct WaveResult {
218 results: Vec<(usize, DecisionResult)>,
219 batches: Vec<Vec<String>>,
220 max_concurrency: usize,
221}
222
223async fn execute_wave(
224 model: Arc<dyn DecisionModel>,
225 request: &DecisionGraphRequest,
226 capabilities: &DecisionModelCapabilities,
227 eligible: &[usize],
228 cancellation: Option<CancellationToken>,
229) -> RuntimeResult<WaveResult> {
230 if let Some(batch_size) = effective_batch_size(capabilities, &request.policy, eligible.len()) {
231 let mut results = Vec::new();
232 let mut batches = Vec::new();
233 for chunk in eligible.chunks(batch_size) {
234 check_cancelled(cancellation.as_ref())?;
235 let questions = chunk
236 .iter()
237 .map(|index| request.nodes[*index].question.clone())
238 .collect();
239 let result = call_model(
240 model.clone(),
241 DecisionRequest::new(request.state.clone(), questions),
242 )
243 .await?;
244 if result.decisions.len() != chunk.len() {
245 return Err(RuntimeError::InvalidOutput {
246 reason: "batched decision result count does not match its request".to_owned(),
247 });
248 }
249 batches.push(
250 chunk
251 .iter()
252 .map(|index| request.nodes[*index].question.name.clone())
253 .collect(),
254 );
255 results.extend(chunk.iter().copied().zip(split_result(result)));
256 }
257 return Ok(WaveResult {
258 results,
259 batches,
260 max_concurrency: 1,
261 });
262 }
263 if let Some(concurrency) = effective_parallelism(capabilities, &request.policy, eligible.len())
264 {
265 let state = request.state.clone();
266 let futures = eligible.iter().copied().map(|index| {
267 let model = model.clone();
268 let question = request.nodes[index].question.clone();
269 let state = state.clone();
270 let cancellation = cancellation.clone();
271 async move {
272 check_cancelled(cancellation.as_ref())?;
273 let result = call_model(model, DecisionRequest::new(state, vec![question])).await?;
274 Ok::<_, RuntimeError>((index, result))
275 }
276 });
277 let results = stream::iter(futures)
278 .buffered(concurrency)
279 .try_collect::<Vec<_>>()
280 .await?;
281 return Ok(WaveResult {
282 batches: eligible
283 .iter()
284 .map(|index| vec![request.nodes[*index].question.name.clone()])
285 .collect(),
286 results,
287 max_concurrency: concurrency.min(eligible.len()),
288 });
289 }
290 let mut results = Vec::new();
291 for index in eligible {
292 check_cancelled(cancellation.as_ref())?;
293 let result = call_model(
294 model.clone(),
295 DecisionRequest::new(
296 request.state.clone(),
297 vec![request.nodes[*index].question.clone()],
298 ),
299 )
300 .await?;
301 results.push((*index, result));
302 }
303 Ok(WaveResult {
304 batches: eligible
305 .iter()
306 .map(|index| vec![request.nodes[*index].question.name.clone()])
307 .collect(),
308 results,
309 max_concurrency: 1,
310 })
311}
312
313async fn call_model(
314 model: Arc<dyn DecisionModel>,
315 request: DecisionRequest,
316) -> RuntimeResult<DecisionResult> {
317 tokio::task::spawn_blocking(move || model.decide(&request))
318 .await
319 .map_err(|error| RuntimeError::execution("structured decision task", error.to_string()))?
320}
321
322fn split_result(result: DecisionResult) -> Vec<DecisionResult> {
323 let DecisionResult {
324 model,
325 backend,
326 decisions,
327 execution,
328 provenance,
329 } = result;
330 let count = decisions.len().max(1) as u64;
331 decisions
332 .into_iter()
333 .map(|decision| DecisionResult {
334 model: model.clone(),
335 backend: backend.clone(),
336 decisions: vec![decision],
337 execution: DecisionExecution {
338 latency: execution.latency,
339 input_tokens: execution.input_tokens / count,
340 output_tokens: execution.output_tokens / count,
341 },
342 provenance: provenance.clone(),
343 })
344 .collect()
345}
346
347fn effective_batch_size(
348 capabilities: &DecisionModelCapabilities,
349 policy: &DecisionExecutionPolicy,
350 count: usize,
351) -> Option<usize> {
352 if count < 2 || !policy.allow_batching || !capabilities.supports_batching {
353 return None;
354 }
355 let size = capabilities
356 .max_batch_size
357 .unwrap_or(count)
358 .min(policy.max_batch_size.unwrap_or(count))
359 .min(count);
360 (size > 1 && capabilities.batch_size != Some(1)).then_some(size)
361}
362
363fn effective_parallelism(
364 capabilities: &DecisionModelCapabilities,
365 policy: &DecisionExecutionPolicy,
366 count: usize,
367) -> Option<usize> {
368 if count < 2 || !policy.allow_parallel || !capabilities.supports_parallel_execution {
369 return None;
370 }
371 let concurrency = capabilities
372 .recommended_parallelism
373 .unwrap_or(1)
374 .min(policy.max_parallelism.unwrap_or(usize::MAX))
375 .min(count);
376 (concurrency > 1).then_some(concurrency)
377}
378
379fn validate_graph(request: &DecisionGraphRequest) -> RuntimeResult<Vec<Vec<usize>>> {
380 if request.nodes.is_empty() {
381 return Err(RuntimeError::InvalidRequest {
382 reason: "decision graph requires at least one node".to_owned(),
383 });
384 }
385 if request.policy.max_parallelism == Some(0) || request.policy.max_batch_size == Some(0) {
386 return Err(RuntimeError::InvalidRequest {
387 reason: "decision execution limits must be greater than zero".to_owned(),
388 });
389 }
390 let mut names = BTreeMap::new();
391 for (index, node) in request.nodes.iter().enumerate() {
392 if node.question.name.is_empty() || names.insert(&node.question.name, index).is_some() {
393 return Err(RuntimeError::InvalidRequest {
394 reason: "decision graph node names must be nonempty and unique".to_owned(),
395 });
396 }
397 }
398 let mut remaining: BTreeSet<_> = (0..request.nodes.len()).collect();
399 let mut completed = BTreeSet::new();
400 let mut levels = Vec::new();
401 while !remaining.is_empty() {
402 let level: Vec<_> = remaining
403 .iter()
404 .copied()
405 .filter(|index| {
406 request.nodes[*index].dependencies.iter().all(|dependency| {
407 names
408 .get(&dependency.decision)
409 .is_some_and(|dependency_index| completed.contains(dependency_index))
410 })
411 })
412 .collect();
413 if level.is_empty() {
414 let missing = request
415 .nodes
416 .iter()
417 .flat_map(|node| &node.dependencies)
418 .find(|dependency| !names.contains_key(&dependency.decision));
419 return Err(RuntimeError::InvalidRequest {
420 reason: missing.map_or_else(
421 || "decision graph contains a dependency cycle".to_owned(),
422 |dependency| {
423 format!(
424 "decision graph references missing node {:?}",
425 dependency.decision
426 )
427 },
428 ),
429 });
430 }
431 for index in &level {
432 remaining.remove(index);
433 completed.insert(*index);
434 }
435 levels.push(level);
436 }
437 Ok(levels)
438}
439
440fn condition_matches(condition: &DecisionDependencyCondition, value: &DecisionValue) -> bool {
441 match (condition, value) {
442 (DecisionDependencyCondition::Completed, _) => true,
443 (DecisionDependencyCondition::ChoiceEquals(expected), DecisionValue::Choice(actual)) => {
444 expected == actual
445 }
446 (DecisionDependencyCondition::NoulEquals(expected), DecisionValue::Noul(actual)) => {
447 expected == actual
448 }
449 (DecisionDependencyCondition::ScoreAtLeast(expected), DecisionValue::Score(actual)) => {
450 actual >= expected
451 }
452 (DecisionDependencyCondition::ScoreAtMost(expected), DecisionValue::Score(actual)) => {
453 actual <= expected
454 }
455 _ => false,
456 }
457}
458
459fn check_cancelled(cancellation: Option<&CancellationToken>) -> RuntimeResult<()> {
460 if cancellation.is_some_and(CancellationToken::is_cancelled) {
461 Err(RuntimeError::Cancelled)
462 } else {
463 Ok(())
464 }
465}
466
467#[cfg(test)]
468mod tests {
469 use super::*;
470 use ml_runtime_inference::{
471 DecisionDependency, DecisionNode, DecisionOption, DecisionProvenance, DecisionQuestion,
472 DecisionType, DeviceKind, ModelArchitecture, ModelDescription, ModelIdentity,
473 };
474 use serde_json::json;
475 use std::{
476 path::PathBuf,
477 sync::atomic::{AtomicUsize, Ordering},
478 time::Duration,
479 };
480
481 fn capabilities(batch: bool, parallel: bool) -> DecisionModelCapabilities {
482 DecisionModelCapabilities {
483 backend: "fixture".to_owned(),
484 device: DeviceKind::Cpu,
485 model_architecture: ModelArchitecture::StructuredDecision,
486 supports_batching: batch,
487 max_batch_size: batch.then_some(4),
488 batch_size: (!batch).then_some(1),
489 supports_async: false,
490 supports_cancellation: false,
491 supports_parallel_execution: parallel,
492 recommended_parallelism: parallel.then_some(3),
493 supports_structured_decisions: true,
494 }
495 }
496
497 fn question(name: &str) -> DecisionQuestion {
498 DecisionQuestion {
499 name: name.to_owned(),
500 instructions: format!("evaluate {name}"),
501 kind: DecisionType::Noul {
502 false_description: None,
503 true_description: None,
504 },
505 }
506 }
507
508 fn independent(count: usize) -> DecisionGraphRequest {
509 DecisionGraphRequest {
510 state: json!({"fixture": true}),
511 nodes: (0..count)
512 .map(|index| DecisionNode {
513 question: question(&format!("node-{index}")),
514 dependencies: Vec::new(),
515 })
516 .collect(),
517 policy: DecisionExecutionPolicy::default(),
518 }
519 }
520
521 #[test]
522 fn planner_selects_deterministic_strategies_and_batch_chunks() {
523 let planner = DecisionPlanner;
524 let batch = planner
525 .plan(&independent(10), &capabilities(true, true))
526 .unwrap();
527 assert_eq!(
528 batch.strategy,
529 DecisionExecutionStrategy::Batched { batch_size: 4 }
530 );
531 assert_eq!(
532 batch.stages[0]
533 .batches
534 .iter()
535 .map(Vec::len)
536 .collect::<Vec<_>>(),
537 vec![4, 4, 2]
538 );
539
540 let parallel = planner
541 .plan(&independent(4), &capabilities(false, true))
542 .unwrap();
543 assert_eq!(
544 parallel.strategy,
545 DecisionExecutionStrategy::Parallel { concurrency: 3 }
546 );
547
548 let mut serial_request = independent(4);
549 serial_request.policy.allow_parallel = false;
550 assert_eq!(
551 planner
552 .plan(&serial_request, &capabilities(false, true))
553 .unwrap()
554 .strategy,
555 DecisionExecutionStrategy::Sequential
556 );
557
558 let mut selective = independent(2);
559 selective.nodes[1].dependencies.push(DecisionDependency {
560 decision: "node-0".to_owned(),
561 condition: DecisionDependencyCondition::NoulEquals(true),
562 });
563 let plan = planner
564 .plan(&selective, &capabilities(false, true))
565 .unwrap();
566 assert_eq!(plan.strategy, DecisionExecutionStrategy::Selective);
567 assert_eq!(plan.reason, "dependency_graph");
568 }
569
570 #[test]
571 fn planner_consumes_real_backend_capability_contracts() {
572 let planner = DecisionPlanner;
573 let onnx = ml_runtime_onnx_backend::OnnxBackend::laya_decision_capabilities();
574 assert_eq!(
575 planner.plan(&independent(8), &onnx).unwrap().strategy,
576 DecisionExecutionStrategy::Batched { batch_size: 8 }
577 );
578
579 #[cfg(feature = "coreml")]
580 {
581 let coreml = ml_runtime_coreml_backend::CoreMlBackend::laya_decision_capabilities();
582 assert_eq!(
583 planner.plan(&independent(8), &coreml).unwrap().strategy,
584 DecisionExecutionStrategy::Sequential
585 );
586 }
587 }
588
589 struct FixtureModel {
590 capabilities: DecisionModelCapabilities,
591 calls: AtomicUsize,
592 cancel_after_call: Option<CancellationToken>,
593 }
594
595 impl FixtureModel {
596 fn new(capabilities: DecisionModelCapabilities) -> Self {
597 Self {
598 capabilities,
599 calls: AtomicUsize::new(0),
600 cancel_after_call: None,
601 }
602 }
603 }
604
605 impl DecisionModel for FixtureModel {
606 fn describe(&self) -> ModelDescription {
607 ModelDescription {
608 identifier: "fixture".to_owned(),
609 revision: None,
610 backend: "fixture".to_owned(),
611 artifact_path: PathBuf::from("fixture"),
612 artifact_sha256: "fixture".to_owned(),
613 decision_types: vec!["choice".to_owned(), "noul".to_owned()],
614 }
615 }
616
617 fn capabilities(&self) -> DecisionModelCapabilities {
618 self.capabilities.clone()
619 }
620
621 fn decide(&self, request: &DecisionRequest) -> RuntimeResult<DecisionResult> {
622 self.calls.fetch_add(1, Ordering::SeqCst);
623 let decisions = request
624 .decisions
625 .iter()
626 .map(|question| {
627 let (kind, value) = match &question.kind {
628 DecisionType::Choice { .. } => {
629 ("choice", DecisionValue::Choice("event".to_owned()))
630 }
631 DecisionType::Score { .. } => ("score", DecisionValue::Score(1.0)),
632 DecisionType::Noul { .. } => ("noul", DecisionValue::Noul(true)),
633 };
634 TypedDecision {
635 name: question.name.clone(),
636 kind: kind.to_owned(),
637 value,
638 probabilities: BTreeMap::new(),
639 confidence: 1.0,
640 action_probability: 1.0,
641 }
642 })
643 .collect();
644 if let Some(token) = &self.cancel_after_call {
645 token.cancel();
646 }
647 Ok(DecisionResult {
648 model: ModelIdentity {
649 identifier: "fixture".to_owned(),
650 revision: None,
651 },
652 backend: "fixture".to_owned(),
653 decisions,
654 execution: DecisionExecution {
655 latency: Duration::ZERO,
656 input_tokens: request.decisions.len() as u64,
657 output_tokens: 0,
658 },
659 provenance: DecisionProvenance {
660 artifact_path: PathBuf::from("fixture"),
661 artifact_sha256: "fixture".to_owned(),
662 runtime_version: "test".to_owned(),
663 },
664 })
665 }
666 }
667
668 #[tokio::test]
669 async fn selective_execution_runs_only_matching_children() {
670 let root = DecisionQuestion {
671 name: "intent".to_owned(),
672 instructions: "classify intent".to_owned(),
673 kind: DecisionType::Choice {
674 options: vec![
675 DecisionOption {
676 label: "event".to_owned(),
677 description: None,
678 },
679 DecisionOption {
680 label: "expense".to_owned(),
681 description: None,
682 },
683 ],
684 },
685 };
686 let graph = DecisionGraphRequest {
687 state: json!({}),
688 nodes: vec![
689 DecisionNode {
690 question: root,
691 dependencies: vec![],
692 },
693 DecisionNode {
694 question: question("event-signal"),
695 dependencies: vec![DecisionDependency {
696 decision: "intent".to_owned(),
697 condition: DecisionDependencyCondition::ChoiceEquals("event".to_owned()),
698 }],
699 },
700 DecisionNode {
701 question: question("expense-signal"),
702 dependencies: vec![DecisionDependency {
703 decision: "intent".to_owned(),
704 condition: DecisionDependencyCondition::ChoiceEquals("expense".to_owned()),
705 }],
706 },
707 ],
708 policy: DecisionExecutionPolicy::default(),
709 };
710 let model = Arc::new(FixtureModel::new(capabilities(false, false)));
711 let result = execute_graph(model.clone(), graph, None).await.unwrap();
712 assert_eq!(
713 result
714 .decisions
715 .iter()
716 .map(|decision| decision.name.as_str())
717 .collect::<Vec<_>>(),
718 vec!["intent", "event-signal"]
719 );
720 let diagnostics = result.planning;
721 assert_eq!(diagnostics.strategy, DecisionExecutionStrategy::Selective);
722 assert_eq!(diagnostics.executed_nodes, 2);
723 assert_eq!(diagnostics.skipped_nodes, 1);
724 assert_eq!(model.calls.load(Ordering::SeqCst), 2);
725 }
726
727 #[tokio::test]
728 async fn cancellation_stops_before_and_between_nodes() {
729 let cancelled = CancellationToken::new();
730 cancelled.cancel();
731 let model = Arc::new(FixtureModel::new(capabilities(false, false)));
732 assert_eq!(
733 execute_graph(model.clone(), independent(2), Some(cancelled)).await,
734 Err(RuntimeError::Cancelled)
735 );
736 assert_eq!(model.calls.load(Ordering::SeqCst), 0);
737
738 let token = CancellationToken::new();
739 let model = Arc::new(FixtureModel {
740 capabilities: capabilities(false, false),
741 calls: AtomicUsize::new(0),
742 cancel_after_call: Some(token.clone()),
743 });
744 assert_eq!(
745 execute_graph(model.clone(), independent(3), Some(token)).await,
746 Err(RuntimeError::Cancelled)
747 );
748 assert_eq!(model.calls.load(Ordering::SeqCst), 1);
749 }
750}