Graph-Based Self-Healing Tool Routing for Cost-Efficient LLM Agents

• URL: http://arxiv.org/abs/2603.01548v1
• Date: Mon, 02 Mar 2026 07:21:15 GMT
• Title: Graph-Based Self-Healing Tool Routing for Cost-Efficient LLM Agents
• Authors: Neeraj Bholani,
• Abstract summary: Self-Healing Router is a fault-tolerant orchestration architecture.<n>It treats most agent control-flow decisions as routing rather than reasoning.<n>Every failure is either a logged reroute or an explicit escalation, never a silent skip.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Tool-using LLM agents face a reliability-cost tradeoff: routing every decision through the LLM improves correctness but incurs high latency and inference cost, while pre-coded workflow graphs reduce cost but become brittle under unanticipated compound tool failures. We present Self-Healing Router, a fault-tolerant orchestration architecture that treats most agent control-flow decisions as routing rather than reasoning. The system combines (i) parallel health monitors that assign priority scores to runtime conditions such as tool outages and risk signals, and (ii) a cost-weighted tool graph where Dijkstra's algorithm performs deterministic shortest-path routing. When a tool fails mid-execution, its edges are reweighted to infinity and the path is recomputed -- yielding automatic recovery without invoking the LLM. The LLM is reserved exclusively for cases where no feasible path exists, enabling goal demotion or escalation. Prior graph-based tool-use systems (ControlLLM, ToolNet, NaviAgent) focus on tool selection and planning; our contribution is runtime fault tolerance with deterministic recovery and binary observability -- every failure is either a logged reroute or an explicit escalation, never a silent skip. Across 19 scenarios spanning three graph topologies (linear pipeline, dependency DAG, parallel fan-out), Self-Healing Router matches ReAct's correctness while reducing control-plane LLM calls by 93% (9 vs 123 aggregate) and eliminating the silent-failure cases observed in a well-engineered static workflow baseline under compound failures.

Related papers

• 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)
• CASTER: Breaking the Cost-Performance Barrier in Multi-Agent Orchestration via Context-Aware Strategy for Task Efficient Routing [25.48759875572515]
  CASTER (Context-Aware Strategy for Task Efficient Routing) is a lightweight router for dynamic model selection in graph-based MAS.<n>CASTER reduces inference cost by up to 72.4% compared to strong-model baselines.
  arXiv  Detail & Related papers  (2026-01-27T16:52:47Z)
• Dynamic System Instructions and Tool Exposure for Efficient Agentic LLMs [1.2691047660244335]
  Large Language Model (LLM) agents often run for many steps while re-ingesting long system instructions and large tool catalogs each turn.<n>We propose Instruction-Tool Retrieval (ITR), a RAG variant that retrieves, per step, only the minimal system-prompt fragments and the smallest necessary subset of tools.<n>ITR reduces per-step context tokens by 95%, improves correct tool routing by 32% relative, and cuts end-to-end episode cost by 70% versus a monolithic baseline.
  arXiv  Detail & Related papers  (2025-12-01T06:43:43Z)
• Dr.LLM: Dynamic Layer Routing in LLMs [55.11953638340419]
  Dr.LLM is a retrofittable framework that equips pretrained models with lightweight per-layer routers deciding to skip, execute, or repeat a block.<n>On ARC (logic) and DART (math), Dr.LLM improves accuracy by up to +3.4%p while saving 5 layers per example on average.
  arXiv  Detail & Related papers  (2025-10-14T17:51:26Z)
• xRouter: Training Cost-Aware LLMs Orchestration System via Reinforcement Learning [104.63494870852894]
  We present x, a tool-calling-based routing system in which a learned router can either answer directly or invoke one or more external models.<n>Our implementation encompasses the full reinforcement learning framework, including reward and cost accounting.<n>Across diverse benchmarks, x achieves strong cost-performance trade-offs.
  arXiv  Detail & Related papers  (2025-10-09T16:52:01Z)
• R-Stitch: Dynamic Trajectory Stitching for Efficient Reasoning [80.104336426172]
  Chain-of-thought (CoT) enhances problem-solving ability of large language models.<n>CoT incurs substantial inference cost due to long autoregressive trajectories.<n>We introduce R-Stitch, a training-free hybrid decoding framework.
  arXiv  Detail & Related papers  (2025-07-23T08:14:36Z)
• RadialRouter: Structured Representation for Efficient and Robust Large Language Models Routing [27.481573948464987]
  Radial is a novel framework for large language models routing.<n>It uses a lightweight Transformer-based backbone with a radial structure named RadialFormer to articulate the query-LLMs relationship.<n>It significantly outperforms existing routing methods by 9.2% and 5.8% in the Balance and Cost First scenarios.
  arXiv  Detail & Related papers  (2025-06-04T12:16:41Z)
• 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)
• Universal Model Routing for Efficient LLM Inference [69.86195589350264]
  Model routing is a technique for reducing the inference cost of large language models (LLMs)<n>We propose UniRoute, a new approach to the problem of dynamic routing, where new, previously unobserved LLMs are available at test time.<n>We show that these are estimates of a theoretically optimal routing rule, and quantify their errors via an excess risk bound.
  arXiv  Detail & Related papers  (2025-02-12T20:30:28Z)
• Confident or Seek Stronger: Exploring Uncertainty-Based On-device LLM Routing From Benchmarking to Generalization [61.02719787737867]
  Large language models (LLMs) are increasingly deployed and democratized on edge devices.<n>One promising solution is uncertainty-based SLM routing, offloading high-stakes queries to stronger LLMs when resulting in low-confidence responses on SLM.<n>We conduct a comprehensive investigation into benchmarking and generalization of uncertainty-driven routing strategies from SLMs to LLMs over 1500+ settings.
  arXiv  Detail & Related papers  (2025-02-06T18:59:11Z)

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.