Cascade-Aware Multi-Agent Routing: Spatio-Temporal Sidecars and Geometry-Switching

Davide Di Gioia

cs.AIMar 17, 2026

Cascade-Aware Multi-Agent Routing: Spatio-Temporal Sidecars and Geometry-Switching

Authors: Davide Di Gioia

Abstract

Advanced AI reasoning systems route tasks through dynamic execution graphs of specialized agents. We identify a structural blind spot in this architecture: schedulers optimize load and fitness but lack a model of how failure propagates differently in tree-like versus cyclic graphs. In tree-like regimes, a single failure cascades exponentially; in dense cyclic regimes, it self-limits. A geometry-blind scheduler cannot distinguish these cases. We formalize this observability gap as an online geometry-control problem. We prove a cascade-sensitivity condition: failure spread is supercritical when per-edge propagation probability exceeds the inverse of the graph's branching factor (p > e^{-γ}, where γis the BFS shell-growth exponent). We close this gap with a spatio-temporal sidecar that predicts which routing geometry fits the current topology. The sidecar comprises (i) a Euclidean propagation scorer for dense, cyclic subgraphs, (ii) a hyperbolic scorer capturing exponential risk in tree-like subgraphs, and (iii) a compact learned gate (133 parameters) that blends the two scores using topology and geometry-aware features. On 250 benchmark scenarios spanning five topology regimes, the sidecar lifts the native scheduler's win rate from 50.4% to 87.2% (+36.8 pp). In tree-like regimes, gains reach +48 to +68 pp. The learned gate achieves held-out AUC = 0.9247, confirming geometry preference is recoverable from live signals. Cross-architecture validation on Barabasi-Albert, Watts-Strogatz, and Erdos-Renyi graphs confirms propagation modeling generalizes across graph families.

Figures & tables

Panel of Figure 1 — Figure 1: The geometry-blindness problem. The same single-agent failure (red) injected into a tree-like execution graph cascades exponentially through all downstream delegation chains (a), while in a dense, cyclic graph (b) it is absorbed within one hop because alternative paths reroute around the failure. A scheduler that sees only node load and fitness cannot distinguish these two cases; our sidecar detects the relevant structural difference, branching rate vs. cycle density, from live graph features and adjusts its risk model accordingly.

Panel of Figure 2 — Figure 2: Spatio-temporal sidecar architecture. The execution graph $G_{t}$ , failure history $\mathcal{F}$ , and candidate route $r$ feed into a 9-dimensional structural feature map $\phi$ , which drives both the Euclidean/hyperbolic scoring branches and a learned geometry gate. The gate output $\pi_{t}(r)$ blends the two scores into a single route-risk signal for the scheduler.

	Feature	Definition	Scope
$\phi_{1}$	Edge-surplus ratio	$(\|E\|-(\|V\|-1))/\|V\|$	Global
$\phi_{2}$	Reciprocal ratio	Fraction of bidirectional edges	Global
$\phi_{3}$	Triangle density	Closed triplets / possible triplets	Global
$\phi_{4}$	Route crosslink ratio	Excess route-local edges / route $\|V\|$	Route
$\phi_{5}$	Route load mean	Mean node load over active route	Route
$\phi_{6}$	Route length norm	Route $\|V\|$ / total $\|V\|$	Ratio

Table 1: Nine structural features used by the geometry gate.

\hat{\gamma}

is the OLS slope of

\ln(|V_{k}|+1)

on BFS depth

k

;

\hat{\kappa}

is the Poincaré-ball curvature fitted by golden-section search. All features are normalized to

[0,1]

Model	Margin	Win%	Note
Genesis 3 native (no sidecar)	$-0.023$	$50.4$	Load $\times$ fitness only
Euclidean	$-0.024$	$48.0$	Euclidean propagation
NetworkX external	$+0.032$	$65.6$	External graph baseline
Structural baseline	$+0.267$	$87.2$	Centrality + load + 2-hop
Hand-designed switching	$+0.255$	$82.4$	Cycle-rank threshold
Learned gate ( $9\!\to\!12\!\to\!1$ )	$+0.385$	$\mathbf{87.2}$	Tied best win rate

Table 2: Overall benchmark performance. The learned gate ties the structural baseline on win rate while achieving

+44\%

larger mean margin (

0.385

vs.

0.267

), demonstrating that adaptive geometry improves separation quality, not just binary correctness. The

+36.8

pp gap between native routing and the learned gate is the total sidecar value.

	Fixed hyperbolic		Learned gate
Regime	Margin	Win%	Margin	Win%
non_tree	$.259$ – $.285$	$64$ – $72$	$\mathbf{.340}$	$\mathbf{92}$
mixed	$.202$ – $.253$	$64$	$\mathbf{.275}$	$\mathbf{84}$

Table 3: Learned geometry switching resolves the principal failure mode of fixed hyperbolic models in non-tree and mixed regimes.

Regime	Native	Sidecar	$\Delta$
clean	$20\%$	$84\%$	$\mathbf{+64}$ pp
noise	$20\%$	$88\%$	$\mathbf{+68}$ pp
churn	$40\%$	$88\%$	$\mathbf{+48}$ pp
non_tree	$92\%$	$92\%$	$0$ pp
mixed	$80\%$	$84\%$	$+4$ pp
Overall	$\mathbf{50.4\%}$	$\mathbf{87.2\%}$	$\mathbf{+36.8}$ pp

Table 4: System-level ablation: Genesis 3 without vs. with the spatio-temporal sidecar. The pattern matches Proposition 4 : the sidecar is indispensable in tree-like regimes (high

\gamma

, supercritical cascades) and adds little in dense regimes (self-limiting cascades).

Component	Model row	Win%	Margin	Interpretation
Neither	Native	$50.4$	$-0.023$	Geometry-blind; essentially random
Temporal only	Euclidean	$48.0$	$-0.024$	Temporal propagation without spatial awareness adds noise and underperforms native
Spatial only	Structural baseline	$87.2$	$+0.267$	Graph structure (centrality, 2-hop) is the decisive signal
Spatio-temporal	Learned gate	$87.2$	$+0.385$	Adaptive geometry preserves win rate and improves separation margin by $44\%$

Table 5: Component decomposition of the sidecar. Adding temporal propagation without spatial awareness is actively harmful (

48.0\%<50.4\%

). Spatial structure alone accounts for the win-rate gain. The full spatio-temporal model matches win rate while substantially improving separation quality (margin), confirming that both dimensions contribute but spatial structure is the prerequisite.

Regime	$n$	AUC	Acc.%	ECE	Pos. rate
Overall	250	.925	86.4	.068	74.4%
clean	50	.923	84.0	.046	80.0%
noise	50	.946	84.0	.084	76.0%
churn	50	.726	76.0	.120	64.0%
non_tree	50	.964	92.0	.075	88.0%
mixed	50	.938	96.0	.080	64.0%

Table 6: Held-out gate diagnostics. Discrimination is strong in four of five regimes (AUC

\geq 0.92

); only churn degrades (AUC

0.73

, ECE

0.12

). Overall confusion matrix:

(\mathrm{TP},\mathrm{TN},\mathrm{FP},\mathrm{FN})=(182,34,30,4)

; the gate rarely misses hyperbolic-win cases, and its error mode is over-selecting hyperbolic in some Euclidean cases.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning
$G_{t}=(V_{t},E_{t},w_{t},\ell_{t})$	Execution graph at time $t$
$\mathcal{F}$	Timestamped failure-event history
$\lambda_{t}(v;r)$ , $\tilde{\lambda}_{t}(v;r)$	Base and burst-augmented failure intensity
$R_{\mathrm{Euc}}$ , $R_{\mathrm{Hyp}}$ , $R$	Euclidean, hyperbolic, and blended route-risk scores
$\phi(G_{t}[r])\in\mathbb{R}^{9}$	Structural feature map for the geometry gate
$\pi_{t}(r)$	Gate output: hyperbolic preference probability

Appendix

Table 7: Notation summary.

Regime	Model	Margin CI	Win-rate CI
Overall	Native	$[-0.039,-0.009]$	$[40.8,59.2]\%$
Overall	Structural baseline	$[0.221,0.301]$	$[80.0,92.8]\%$
Overall	Learned	$[0.341,0.440]$	$[81.6,93.6]\%$
Overall	Hyp. no excitation	$[0.355,0.492]$	$[74.4,87.2]\%$
clean	Native	$[-0.105,-0.057]$	$[10,30]\%$
clean	Learned	$[0.305,0.517]$	$[74,92]\%$

Appendix

Table 8: Bootstrap 95% CIs confirm large, non-overlapping separations in tree-like regimes and convergence in dense regimes.

Protocol	Sidecar win%	Sidecar margin	Native win%
severity_load	$69.6$	$0.153$	$53.2$
load_matched	$88.8$	$0.194$	$100.0$
random	$78.8$	$0.158$	$54.4$

Appendix

Table 9: The sidecar is stable across attack protocols (

69.6

–

88.8\%

); the native baseline varies widely. Under random (no load correlation), the

+24.4

pp gap is attributable solely to propagation modeling; random is therefore the cleanest estimate of propagation-model value ( load_matched is an alignment sanity check; see text).

Pair	Pearson	Spearman	Heuristic expectation
$\delta$ vs. $\phi_{7}$ (shell-growth)	$-0.18$	$+0.16$	Weak / mixed signal
$\delta$ vs. $\phi_{8}$ (cycle-rank)	$+0.31$	$+0.41$	More cycles $\to$ larger $\delta$
$\delta$ vs. $\phi_{9}$ (curvature)	$-0.51$	$-0.41$	Higher fitted curvature $\to$ smaller $\delta$
$\delta$ vs. hyp. margin	$-0.23$	$-0.09$	Larger $\delta$ $\to$ reduced hyperbolic advantage

Appendix

Table 10: Sanity-check correlations between Gromov

\delta

and geometry-aware features.

\phi_{8}

and

\phi_{9}

show the strongest and most consistent associations.

\delta

is an auxiliary diagnostic computed on an undirected projection with sampling noise and is not used in the model; only correlation directionality is interpreted.

Scorer	Mean ( $\mu$ s)	Median	p95	Peak mem. (KB)
Native (no sidecar)	$0.7$	$0.7$	$0.8$	$0.4$
Structural baseline	$6.6$	$6.2$	$8.2$	$1.3$
Euclidean	$12.8$	$11.7$	$16.4$	$2.1$
Geometry switching	$280.7$	$240.9$	$392.0$	$5.5$
Learned sidecar	$304.5$	$271.2$	$427.6$	$5.1$
NetworkX external	$487.0$	$485.0$	$604.0$	$7.7$

Appendix

Table 11: The learned sidecar adds

\approx

305

\mu

s and 5 KB per call, negligible relative to LLM-backed solve episodes (seconds to minutes).

Family	Euclidean	Structural	NetworkX	Learned
BA tree-like	$5\%$	$\mathbf{100\%}$	$10\%$	$7\%$
WS small-world	$63\%$	$\mathbf{100\%}$	$82\%$	$65\%$
ER dense	$56\%$	$\mathbf{100\%}$	$70\%$	$46\%$

Appendix

Table 12: The structural baseline achieves

100\%

on all families, confirming that propagation modeling generalizes. The trained gate (without fine-tuning) is weaker on out-of-distribution topologies, especially BA trees.

Condition	Win%	Margin	Margin 95% CI
Full 9-feature	$81.6$	$0.305$	$[0.272,0.346]$
Remove $\phi_{7}$	$81.6$	$0.305$	$[0.272,0.346]$
Remove $\phi_{8}$	$81.6$	$0.305$	$[0.272,0.346]$
Remove $\phi_{9}$	$81.6$	$0.305$	$[0.273,0.346]$
Topology only ( $\phi_{1}$ – $\phi_{6}$ )	$81.6$	$0.305$	$[0.272,0.345]$
Geometry only ( $\phi_{7}$ – $\phi_{9}$ )	$82.0$	$0.293$	$[0.261,0.335]$

Appendix

Table 13: Per-feature deltas (

\phi_{7}

-0.0005

\phi_{8}

-0.0001

\phi_{9}

-0.0004

, full geometry block:

-0.0008

) fall within bootstrap noise on this homogeneous ablation set. The geometry features are conditionally useful: they add signal when the evaluation distribution spans sufficient regime diversity (

+4.6\%

margin on the main benchmark) but are redundant on near-uniform topologies.

LLM Agent Routing

LLM agent routing selects models, tools, skills, or collaboration workflows for each task or step to balance capability, cost, latency, and reliability.

See all 96 papers

Aug 13, 2026

TANGCO: Learning Topology-Aware Capacity Allocation for Overload-driven Cascading Failures

Networked systems, from power grids to traffic networks and cloud clusters, carry loads across nodes with limited capacity. A node whose load exceeds its capacity fails and sheds its load onto its neighbors, which can trigger a system-wide cascade. We study how to allocate a fixed capacity budget across nodes to resist these cascades under local load redistribution. The problem is difficult because no optimal allocation is known, and the fail-or-survive objective is non-differentiable and piecewise constant, so exact and gradient-based optimization methods do not directly apply. We introduce TANGCO (Topology-Aware Neural Graph-Guided Capacity Optimization), which uses a graph neural network policy trained through the cascade simulator with policy-gradient learning and a heuristic anchor. We evaluate TANGCO on five synthetic graph families and five real networks spanning power, road, air, and Internet topologies. The learned policy improves on the best of four hand-designed heuristics in all 450 synthetic instances and in 40 of 45 real-network conditions, with robustness gains ranging from 1.6% to 246%. The learned policies transfer to unseen graphs within a family and partially across related topologies, and TANGCO

^{pre}

, pre-trained on synthetic graphs, matches per-network training on unseen real networks. Training scales near-linearly with graph size, and TANGCO

^{pre}

allocates on a new network with no per-target training, matching the deployment cost of a hand-designed heuristic. Free-vector variants without the GNN, stay close to the heuristics, so the graph representation carries the gain beyond numerical search. Finally, analysis of the learned allocations identifies when local risk is sufficient, leads to an improved closed-form heuristic, and reveals the regimes where a topology-aware learned policy remains necessary.

Orkun Irsoy, Leman Akoglu, Osman Yagan

Carnegie Mellon University · Electrical and Computer Engineering · Pittsburgh, Pennsylvania, USA +1

Topic pending

Ask PDF

Aug 6, 2026

ASGE-RR: Agentic Service Graph Embedding with Revisable Reservations for Dynamic AI-Agent Calls

AI-agent workflows often involve remote calls to models, memory stores, and tools distributed across a network. As execution progresses, these dependency calls collectively form an agentic service graph (ASG). Unlike traditional service requests, many dependency calls are revealed only at runtime. Consequently, allocating resources to a currently visible call may consume capacity later needed by a call from a higher-value workflow. We formulate this challenge as Agentic Service Graph Embedding (ASGE), an online network-control problem that maps runtime-revealed workflow calls to service replicas and network paths under capacity, cost and deadline constraints. We present ASGE-RR, an online ASGE controller with revisable reservations. ASGE-RR protects capacity for likely future calls while enforcing the constraints. ASGE-RR evaluates candidate replica-and-path mappings against predicted workflow continuations and updates reservations as new execution information becomes available. We evaluate ASGE-RR using OpenHands and GPT Researcher workflows executed with gpt-5.6-luna and replayed over in two complementary experimental environments, a controlled Docker testbed and a WAN testbed. The investigation shows that all the evaluated AI-agent tasks expose at least one runtime-revealed dependency call that can be steered before connection establishment. Exploiting this control point, even though the experimental environments are small-scale, ASGE-RR already demonstrates noticeable potential: It completes (up to) 10% more workflow value than a same-information rolling-horizon controller and a current-call steering controller on the WAN testbed. The results suggest that runtime-revealed workflow structure creates a new network control opportunity: protecting resources for likely future calls allows more AI-agent workflows to finish in time.

Trond Vatten, Yuming Jiang

Norwegian University of Science and Technology (NTNU), Trondheim, Norway

Agentic Workflows Online Resource Allocation

Ask PDF

Apr 7, 2026

Cayley Graph Optimization for Scalable Multi-Agent Communication Topologies

Large-scale multi-agent communication has long faced a scalability bottleneck: fully connected networks require quadratic complexity, yet existing sparse topologies rely on hand-crafted rules. This paper treats the communication graph itself as a design variable and proposes CayleyTopo, a family of circulant Cayley graphs whose generator sets are optimized to minimize diameter, directly targeting worst-case information propagation speed. To navigate the enormous search space of possible generator sets, we develop a lightweight reinforcement learning framework that injects a number-theoretic prior to favor structurally rich generators, alongside a message-propagation score that provides dense connectivity feedback during construction. The resulting CayleyTopo consistently outperforms existing hand-crafted topologies, achieving faster information dissemination, greater resilience to link failures, and lower communication load, all while approaching the theoretical Moore bound. Our study opens the door to scalable, robust, and efficient communication foundations for future multi-agent systems, where the graph itself becomes optimizable rather than a fixed constraint.

Jingkai Luo, Yulin Shao

Department of Electrical and Computer Engineering, The University of Hong Kong, Hong Kong, China

Communication Topology Optimization Multi-Agent Communication Topology Multi-Agent Communication Combinatorial Optimization

Ask PDF

Abstract

LLM Agent Routing

Explore similar work

TANGCO: Learning Topology-Aware Capacity Allocation for Overload-driven Cascading Failures

ASGE-RR: Agentic Service Graph Embedding with Revisable Reservations for Dynamic AI-Agent Calls

Cayley Graph Optimization for Scalable Multi-Agent Communication Topologies