# STAR: Failure-Aware Markovian Routing for Multi-Agent Spatiotemporal Reasoning arXiv: https://arxiv.org/abs/2605.10057 ยท HTML: https://mlsanity.com/paper/2605.10057/ ## Key facts - Cited by 1 papers in the map (data through 14 Oct 2026). - Placed in Spatial and embodied reasoning, one of 17 directions in LLM reasoning. - Builds on 28 of its 32 references that are in the map. - First posted on arXiv 11 May 2026. ## Placed in - LLM reasoning / [Spatial and embodied reasoning](https://mlsanity.com/lr/spatial-and-embodied-reasoning/) - LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/) ## Builds on (most cited first, 28 of 28) - [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022) - [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023) - [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023) - [Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer](https://mlsanity.com/paper/1701.06538/) (2017) - [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023) - [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023) - [AutoGen: Enabling Next-Gen LLM Applications via Multi-Agent Conversation](https://mlsanity.com/paper/2308.08155/) (2023) - [MetaGPT: Meta Programming for A Multi-Agent Collaborative Framework](https://mlsanity.com/paper/2308.00352/) (2023) - [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023) - [Multi-Agent Collaboration Mechanisms: A Survey of LLMs](https://mlsanity.com/paper/2501.06322/) (2025) - [Chameleon: Plug-and-Play Compositional Reasoning with Large Language Models](https://mlsanity.com/paper/2304.09842/) (2023) - [From LLM Reasoning to Autonomous AI Agents: A Comprehensive Review](https://mlsanity.com/paper/2504.19678/) (2025) - [Large Language Models Can Learn Temporal Reasoning](https://mlsanity.com/paper/2401.06853/) (2024) - [TaskWeaver: A Code-First Agent Framework](https://mlsanity.com/paper/2311.17541/) (2023) - [V-STaR: Benchmarking Video-LLMs on Video Spatio-Temporal Reasoning](https://mlsanity.com/paper/2503.11495/) (2025) - [Can Large Language Models be Good Path Planners? A Benchmark and Investigation on Spatial-temporal Reasoning](https://mlsanity.com/paper/2310.03249/) (2023) - [OmniRouter: Budget and Performance Controllable Multi-LLM Routing](https://mlsanity.com/paper/2502.20576/) (2025) - [TReMu: Towards Neuro-Symbolic Temporal Reasoning for LLM-Agents with Memory in Multi-Session Dialogues](https://mlsanity.com/paper/2502.01630/) (2025) - [Beyond ReAct: A Planner-Centric Framework for Complex Tool-Augmented LLM Reasoning](https://mlsanity.com/paper/2511.10037/) (2025) - [ZARA: Training-Free Motion Time-Series Reasoning via Evidence-Grounded LLM Agents](https://mlsanity.com/paper/2508.04038/) (2025) - [LLM-Based Multi-Agent Blackboard System for Information Discovery in Data Science](https://mlsanity.com/paper/2510.01285/) (2025) - [LLM-Based Intent Processing and Network Optimization Using Attention-Based Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2406.06059/) (2024) - [STBench: Assessing the Ability of Large Language Models in Spatio-Temporal Analysis](https://mlsanity.com/paper/2406.19065/) (2024) - [Exploring Multi-Modal Data with Tool-Augmented LLM Agents for Precise Causal Discovery](https://mlsanity.com/paper/2412.13667/) (2024) - [Exploring Advanced LLM Multi-Agent Systems Based on Blackboard Architecture](https://mlsanity.com/paper/2507.01701/) (2025) - [STReasoner: Empowering LLMs for Spatio-Temporal Reasoning in Time Series via Spatial-Aware Reinforcement Learning](https://mlsanity.com/paper/2601.03248/) (2026) - [Benchmarking Spatiotemporal Reasoning in LLMs and Reasoning Models: Capabilities and Challenges](https://mlsanity.com/paper/2505.11618/) (2025) - [RELOOP: Recursive Retrieval with Multi-Hop Reasoner and Planners for Heterogeneous QA](https://mlsanity.com/paper/2510.20505/) (2025) ## Built on by (most cited first, 1 of 1) - [What Can Component-Replacement Evidence Establish? A Critical Scoping Review of Local Decisions in LLM Agents](https://mlsanity.com/paper/2609.39989/) (2026) ## Abstract (arXiv) 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.