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

arXiv: https://arxiv.org/abs/2603.01548 · HTML: https://mlsanity.com/paper/2603.01548/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in Software engineering coding agents, one of 16 directions in LLM agents and tool use.
- Builds on 7 of its 13 references that are in the map.
- First posted on arXiv 2 Mar 2026.

## Placed in

- LLM agents and tool use / [Software engineering coding agents](https://mlsanity.com/agents/software-engineering-coding-agents/)

## Builds on (most cited first, 7 of 7)

- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models](https://mlsanity.com/paper/2310.04406/) (2023)
- [ControlLLM: Augment Language Models with Tools by Searching on Graphs](https://mlsanity.com/paper/2310.17796/) (2023)
- [SHIELDA: Structured Handling of Exceptions in LLM-Driven Agentic Workflows](https://mlsanity.com/paper/2508.07935/) (2025)
- [Synergistic Integration of Large Language Models and Cognitive Architectures for Robust AI: An Exploratory Analysis](https://mlsanity.com/paper/2308.09830/) (2023)
- [Adaptive routing protocols for determining optimal paths in AI multi-agent systems: a priority- and learning-enhanced approach](https://mlsanity.com/paper/2503.07686/) (2025)

## Built on by (most cited first, 3 of 3)

- [Retrieval-Conditioned Topology Selection with Provable Budget Conservation for Multi-Agent Code Generation](https://mlsanity.com/paper/2605.05657/) (2026)
- [Autonomous Topology Mutation: Safe Runtime Restructuring for Multi-Agent LLM Systems with Capability, State, and Shadow Invariants](https://mlsanity.com/paper/2607.20488/) (2026)
- [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)

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.