STAR: Failure-Aware Markovian Routing for Multi-Agent Spatiotemporal Reasoning

Ruiyi Yang, Lihuan Li, Hao Xue, Flora D. SalimarXiv 2026 · arXiv

TL;DR

STAR (Spatio-Temporal Agent Router) introduces an explicit, failure-aware routing framework for multi-agent systems tackling complex spatiotemporal reasoning. By categorizing errors into distinct types—such as malformed outputs or tool mismatches—and training on both successful and failed execution traces, STAR learns optimal recovery pathways that significantly boost system robustness when things go wrong.

What Problem Does This Paper Address?

Spatiotemporal reasoning tasks (like trajectory tracking, route planning, or spatial relation analysis) are highly compositional. To solve them, AI systems must chain together multiple specialized agents—such as geometric solvers, temporal reasoners, and navigation tools.

When one agent in the chain fails, typical Large Language Model (LLM) systems handle recovery implicitly through free-form text generation or basic "retry" loops. This ad-hoc approach treats all failures as a monolithic "error," making it difficult to diagnose, optimize, or elegantly recover. For instance, an agent failing because its output format is malformed requires a completely different fix than an agent failing because an upstream dependency is missing.

Methods

The authors present STAR, a framework that externalizes inter-agent control into an explicit, state-conditioned transition policy (a Markovian routing matrix).

Instead of letting an LLM implicitly guess the next step, STAR formalizes specialist composition as routing over explicit execution states:

  • Typed Execution Statuses: Execution outcomes are explicitly classified into INIT, SUCC (success), FAIL (malformed output), BLOCK (missing dependency), and MISS (tool-query mismatch).
  • Dual-System Routing: System 1 handles standard, successful paths using expert-defined nominal routes. System 2 takes over during failures, using a learned recovery matrix to route to the best alternative specialist based on the specific error type.
  • Extract-Compute-Deposit Protocol: Specialists extract parameters using an LLM, execute deterministic solvers (like Dijkstra for navigation or Shapely for geometry), and deposit results onto a shared blackboard.
  • Failure-Aware Training: Crucially, the routing matrix is trained using both successful and unsuccessful execution traces (weighted by an attenuation hyperparameter $\alpha$). This ensures the model actually encounters and learns how to navigate out of error states.
Figure 1: STAR architecture. Queries are parsed into a task profile, the failure-aware routing matrix selects specialists conditioned on the current agent, task type, execution status, and specialists execute through an extract-compute-deposit protocol over a shared blackboard before final fusion.

Datasets

The framework was evaluated across three distinct spatiotemporal benchmarks:

  1. STARK: 26 task types covering spatial/temporal tracking, gap filling, and forecasting.
  2. STBench (STB24): 11 task types focusing heavily on structured spatiotemporal analysis.
  3. ST-Bench (STB26): 4 complex task types including etiological and graph-structured reasoning.

Key Insights and Ideas

  • Errors are Valuable Training Data: The authors mathematically prove (Theorem 1: Recovery Reachability Dominance) that success-only training leaves error states completely unrepresented in the routing matrix. Retaining failed traces during training is essential to build a functional recovery policy.
  • Not All Failures Are Equal: A tool mismatch (MISS) requires a completely different recovery strategy than a malformed output (FAIL). By separating these states, the router can dynamically escalate a MISS to a semantic LLM agent or reroute a BLOCK to an upstream data producer.
Figure 2: State-conditioned routing matrix slices for a representative task type. Each panel visualizes a row M[a, s, t, ·] with fixed current agent a and task type t but different execution status s. The differing successor distributions show that recovery is conditioned on the type of failure rather than treated as a generic retry action.
  • Failing Upward: Surprisingly, queries that hit a MISS state often achieved higher final accuracy than the baseline queries that never errored out. This indicates the router acts as a self-correcting mechanism, fixing initially suboptimal agent assignments and putting the query on a better computation path.

Key Results

  • STAR consistently outperformed LLM-only, prompting-based (CoT), and advanced agentic baselines (ReAct, Reflexion, Tree-of-Thought, Graph-of-Thought) across all 3 benchmarks and 8 different backbone LLMs (ranging from 3B open-source models to proprietary giants like Claude).
  • On the Qwen3-8B backbone, STAR outperformed the popular Reflexion baseline by +4.2pp on STARK, +39.1pp on STB24, and +15.3pp on STB26.
  • Router-specific ablations showed that removing status conditioning (collapsing all errors into one generic state) caused performance to drop drastically—by up to 33.3 percentage points on STARK queries that deviated from the nominal path.

Limitations and Future Work

  • Taxonomy Bound: STAR currently learns routing matrices tied to a specific task taxonomy. The authors note that future work will focus on developing task-agnostic recovery abstractions that can generalize across entirely unseen domains.
  • Parameter Extraction Bottleneck: While routing can fix where a query goes next, it cannot always fix bad parameter extraction inside the specialist agent itself. This makes FAIL (malformed result) recovery inherently harder than MISS recovery, pointing to parameter-extraction optimization as a key future direction.

Summary updated

Abstract

Compositional spatiotemporal reasoning often requires a system to invoke multiple heterogeneous specialists, such as geometric, temporal, topological, and trajectory agents. A central question is how such a system should route among specialists when execution does not simply succeed or fail, but fails in qualitatively different ways. Existing tool-augmented and multi-agent LLM systems typically leave this routing decision implicit in language generation, making recovery ad hoc, difficult to interpret, and hard to optimize. This paper presents STAR (Spatio-Temporal Agent Router), a failure-aware routing framework that externalizes inter-agent control as a state-conditioned transition policy over the current agent, task type, and typed execution status. At the center of STARis an agent routing matrix that combines expert-specified nominal routes with recovery transitions learned from execution traces. Because the matrix conditions on distinct failure states, the router can respond differently to malformed outputs, missing dependencies, and tool--query mismatches, rather than collapsing them into a generic retry signal. Specialists execute through a tool-grounded extract--compute--deposit protocol and write intermediate results to a shared blackboard for downstream fusion. Results prove that retaining unsuccessful traces during training enlarges the support of the routing policy on error states, enabling recovery transitions that success-only training cannot represent. Across three spatiotemporal benchmarks and eight backbone LLMs, STAR improves over multiple baselines with the clearest gains on queries whose execution deviates from the nominal routing path. Router-specific ablations and recovery analyses further show that typed failure-aware routing, rather than specialist composition alone, is a key factor for these improvements.
BibTeX
@misc{yang2026star,
  author = {Ruiyi Yang and Lihuan Li and Hao Xue and Flora D. Salim},
  title = {{STAR: Failure-Aware Markovian Routing for Multi-Agent Spatiotemporal Reasoning}},
  year = {2026},
  eprint = {2605.10057},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.10057},
}
Figure