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

• URL: http://arxiv.org/abs/2605.10057v3
• Date: Fri, 15 May 2026 00:13:12 GMT
• Title: STAR: Failure-Aware Markovian Routing for Multi-Agent Spatiotemporal Reasoning
• Abstract summary: This paper presents STAR, a failureaware routing framework that externalizes interagent control as a state-conditioned policy over the current agent, task type, and typed execution status.<n>Because the traces on failure states are distinct, the router can respond differently to malformed outputs, missing dependencies, and tool-ground extract-- compute-deposit protocol and write intermediate results to a shared blackboard for downstream fusion.<n>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.
• Score: 13.329339723676147
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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.

Related papers

• DCFA: Dual-view Causal-inspired Attribution for Failure Reasoning in LLM-based Multi-agent Systems [61.11435469308521]
  We propose DCFA, a training-free framework for failure attribution in large language model systems.<n> DCFA integrates a global module that constructs structured causal-inspired dependency graphs from system traces.<n>Experiments show that DCFA improves step-level accuracy by up to 8.27% over state-of-the-art baselines.
  arXiv  Detail & Related papers  (2026-09-04T05:29:31Z)
• Who Broke the System? Failure Localization in LLM-Based Multi-Agent Systems [9.458292549037155]
  We study the problem of failure localization in LLM-based multi-agent systems.<n>We present Agent, a framework that attributes failures to both a specific agent and the earliest decisive step.<n> Experimental results show that Agent consistently outperforms existing failure localization methods.
  arXiv  Detail & Related papers  (2026-07-08T23:33:49Z)
• FALAT: Tracing Failures in LLM Agent Trajectories via Dependency-Guided Search [11.638321375070047]
  We propose FALAT, a diagnostic framework for failure attribution in LLM agent trajectories.<n>We evaluate FALAT on the Who&When benchmark, which includes both algorithm-generated and hand-crafted multi-agent failure trajectories.
  arXiv  Detail & Related papers  (2026-05-30T15:11:35Z)
• CodeTracer: Towards Traceable Agent States [40.51936201889185]
  We present CodeTracer, a tracing architecture that parses heterogeneous run artifacts through evolving extractors.<n>CodeTracer reconstructs the full state transition history as a hierarchical trace tree with persistent memory.<n>It performs failure onset localization to pinpoint the failure origin and its downstream chain.
  arXiv  Detail & Related papers  (2026-04-13T15:52:03Z)
• Runtime Burden Allocation for Structured LLM Routing in Agentic Expert Systems: A Full-Factorial Cross-Backend Methodology [16.053669481561354]
  As large language models (LLMs) become core control components in agentic AI systems, reliable structured routing must balance correctness, latency, and implementation cost.<n>We show that this balance is shaped not only by prompts or schemas, but also by how structural work is allocated across the generation stack.<n>We evaluate this formulation through a comprehensive full-factorial benchmark covering 48 deployment configurations and 15,552 requests across OpenAI, Gemini, and Llama backends.
  arXiv  Detail & Related papers  (2026-03-26T18:50:46Z)
• AgentTrace: Causal Graph Tracing for Root Cause Analysis in Deployed Multi-Agent Systems [0.0]
  We present AgentTrace, a lightweight causal tracing framework for post-hoc failure diagnosis in deployed multi-agent AI systems.<n>AgentTrace reconstructs causal graphs from execution logs, traces backward from error manifestations, and ranks candidate root causes using interpretable structural and positional signals.<n>Our results suggest that causal tracing provides a practical foundation for improving the reliability and trustworthiness of agentic systems in the wild.
  arXiv  Detail & Related papers  (2026-03-16T00:46:44Z)
• Efficient and Interpretable Multi-Agent LLM Routing via Ant Colony Optimization [58.59491516762626]
  We propose AMRO-S, an efficient and interpretable routing framework for Multi-Agent Systems (MAS)<n>AMRO-S models MAS routing as a semantic-conditioned path selection problem, enhancing routing performance through three key mechanisms.<n>Extensive experiments on five public benchmarks and high-concurrency stress tests demonstrate that AMRO-S consistently improves the quality--cost trade-off over strong routing baselines.
  arXiv  Detail & Related papers  (2026-03-13T12:26:05Z)
• AgentRx: Diagnosing AI Agent Failures from Execution Trajectories [9.61742219198197]
  We release a benchmark of 115 failed trajectories spanning structured API, incident management, and open-ended web/file tasks.<n>Each trajectory is annotated with a critical failure step and a category from a grounded-theory derived, cross-domain failure taxonomy.<n>We present AGENTRX, an automated domain-agnostic diagnostic framework that pinpoints the critical failure step in a failed agent trajectory.
  arXiv  Detail & Related papers  (2026-02-02T18:54:07Z)
• AgentRouter: A Knowledge-Graph-Guided LLM Router for Collaborative Multi-Agent Question Answering [51.07491603393163]
  tAgent is a framework that formulates multi-agent QA as a knowledge-graph-guided routing problem supervised by empirical performance signals.<n>By leveraging soft supervision and weighted aggregation of agent outputs, Agent learns principled collaboration schemes that capture the complementary strengths of diverse agents.
  arXiv  Detail & Related papers  (2025-10-06T23:20:49Z)
• Just-in-time Episodic Feedback Hinter: Leveraging Offline Knowledge to Improve LLM Agents Adaptation [77.90555621662345]
  We present JEF Hinter, an agentic system that distills offline traces into compact, context-aware hints.<n>A zooming mechanism highlights decisive steps in long trajectories, capturing both strategies and pitfalls.<n>Experiments on MiniWoB++, WorkArena-L1, and WebArena-Lite show that JEF Hinter consistently outperforms strong baselines.
  arXiv  Detail & Related papers  (2025-10-05T21:34:42Z)
• Which Agent Causes Task Failures and When? On Automated Failure Attribution of LLM Multi-Agent Systems [50.29939179830491]
  Failure attribution in LLM multi-agent systems remains underexplored and labor-intensive.<n>We develop and evaluate three automated failure attribution methods, summarizing their corresponding pros and cons.<n>The best method achieves 53.5% accuracy in identifying failure-responsible agents but only 14.2% in pinpointing failure steps.
  arXiv  Detail & Related papers  (2025-04-30T23:09:44Z)
• When Disagreements Elicit Robustness: Investigating Self-Repair Capabilities under LLM Multi-Agent Disagreements [56.29265568399648]
  We argue that disagreements prevent premature consensus and expand the explored solution space.<n>Disagreements on task-critical steps can derail collaboration depending on the topology of solution paths.
  arXiv  Detail & Related papers  (2025-02-21T02:24:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.