TRACE-ROUTER: Task-Consistent and Adaptive Online Routing for Agentic AI

Source: arXiv:2607.22465 · Published 2026-07-24 · By Ritik Raj, Souvik Kundu, Sarbartha Banerjee, Dheemanth Joshi, Ishita Vohra, Tushar Krishna

TL;DR

This paper addresses the challenge of routing large language model (LLM) requests for agentic AI workloads, where each user task consists of a long sequence of LLM calls and the ultimate quality signal is delayed until task completion. Existing routing methods make independent routing decisions per LLM request, which leads to misaligned credit assignment and suboptimal task-level outcomes. The authors propose TRACE-Router, a task-consistent routing framework that assigns a single LLM backend to an entire task at admission and then uses the final task accuracy and latency as delayed reward to update an online contextual bandit policy. This aligns the routing granularity with the feedback granularity and enables learning from delayed outcomes while avoiding explicit task complexity estimation.

TRACE-Router incorporates context-conditioning to differentiate among coarse task contexts and learns an adaptive routing policy that balances accuracy and latency. Through live end-to-end experiments on multiple agentic benchmarks including tau2-Bench and Terminal-Bench, TRACE-Router consistently achieves superior accuracy-latency trade-offs, forming a non-dominated Pareto frontier that strictly dominates heuristic and learned request-level baselines. Notably, it exceeds the accuracy of latency-matched model mixing baselines by 7–8 points on tau2-Bench and outperforms the best single large model on Terminal-Bench with 36% lower latency.

This work highlights that aligning the unit of routing decisions with the unit of supervision (task-level rather than per-call) is crucial to effective online LLM routing in agentic applications. The contextual bandit approach enables principled credit assignment from delayed task outcomes and adapts routing policies on the fly to workload regimes. TRACE-Router’s task-consistent, context-aware online routing provides a significant step beyond prior request-level or offline-trained routing methods for deploying heterogeneous LLM pools under latency and accuracy constraints.

Key findings

• TRACE-Router on tau2-Bench achieves 61.2% task accuracy at 26.4s latency, outperforming latency-matched interpolation between small and large models by 7.5 accuracy points.
• On Terminal-Bench, TRACE-Router resolves 46.8% of tasks at 172s latency, 7.1 points more accurate than always using the 27B backend at 268s (36% lower latency).
• The context-conditioned routing variant outperforms a context-free variant by around 1.3–1.5 points accuracy on average, enabling feasibility of operating points unreachable by a single global policy.
• Cold-start contextual UCB with forced round-robin exploration is preferred over warm-starting priors due to better exploration-exploitation balance.
• UCB policy is more stable and slightly better at capturing the superior backend reward than epsilon-greedy or Thompson sampling across benchmarks.
• Smaller backends that fail many tasks may not offer significant latency savings, as in tau2-Telecom where the small backend solves only 10.5% of tasks vs 60.5% for the large backend.
• Routing a single model per entire agentic task enables consistent credit assignment and state preservation inaccessible to per-call routing.
• TRACE-Router empirically attains a non-dominated accuracy–latency Pareto frontier superior to heuristics and learned baselines on multiple benchmarks.

Threat model

Not a security-focused paper. The threat model assumes an unknown, evolving task workload and offline unknown distribution of task complexities. The adversary is effectively the deployment environment with delayed, sparse feedback limiting routing policy knowledge. The system cannot observe per-call ground truth or immediate accuracy feedback, and must learn from delayed task-level outcomes without adversarial manipulation.

Methodology — deep read

The paper's threat model assumes an enterprise AI deployment scenario where multiple LLM backends of varying cost-quality tradeoffs are available. The adversary is not explicitly defined in a security context, but the system must robustly select models under unknown and evolving task workloads without per-call feedback.

Data provenance derives from multiple agentic benchmarks: tau2-Bench with retail and telecom domains (114 tasks each), LiveCodeBench (300 tasks), and Terminal-Bench (48 tasks). Tasks are labeled with task-level success or graded accuracy, and latency is measured end-to-end per task including tool execution. The data split is natural streaming of tasks for online learning.

TRACE-Router treats each user task as a sequence (trace) of LLM requests and assigns all requests to a single backend model. Each incoming request carries a persistent task identifier used to enforce sticky assignment. A context function maps initial task descriptors to one of three coarse contexts (EASY, MEDIUM, HARD) via regex keyword and length rules, selected for low overhead and no training.

Routing is formulated as a contextual multi-armed bandit with one bandit per task context. Each bandit's arms correspond to available backend LLMs. At task admission, the bandit selects one backend which is pinned for all that task's requests. On task completion, the final task accuracy and latency produce a scalar reward (weighted accuracy - alpha * normalized latency). This delayed reward updates only the bandit responsible for that context to improve future routing decisions.

Bandit policy uses cold-start Upper Confidence Bound (UCB) with forced initial pulls to ensure exploration, and an exploration strength delta parameter. The replay analysis compares against epsilon-greedy and Thompson sampling variants.

The evaluation protocol measures end-to-end accuracy–latency trade-offs via Pareto frontiers on live deployments inside a patched LiteLLM proxy with matched task counts. Baselines include single models, semantic and complexity rule routers, and task-matched oracles. Ablations isolate the impact of context conditioning, cold vs warm start, and bandit policy choice.

Reproducibility: The framework is described independently of any specific serving stack or context classifier, with code and environment details fixed for experiments but not publicly released per the paper. Specific datasets are public or referenced from prior works. The implementation is inside LiteLLM proxy for live task executions.

As a concrete example: Upon arrival of a new task with descriptor x_t, the context function g(x_t) assigns a context c_t. The contextual bandit B_c_t selects a backend m_t via UCB. The router pins m_t for all requests with task ID κ_t until task completion. The delayed reward r_t,m_t is computed using the final accuracy a_t,m_t and latency ℓ_t,m_t normalized against ℓ_0 with preference α. This reward updates B_c_t statistics N_c,t,m_t and S_c,t,m_t. Completed tasks are removed from the active-task table. Subsequent new tasks leverage updated bandit policies to adapt routing online.

Technical innovations

• Introduces task-consistent routing for agentic AI workloads, assigning a single model to entire multi-query tasks to align decision granularity with delayed feedback.
• Proposes a context-conditioned online multi-armed bandit mechanism to adaptively learn routing policies per coarse task context without offline training or explicit task complexity modeling.
• Designs a scalarized reward combining accuracy and normalized latency with a tunable trade-off parameter α to enable Pareto frontier learning.
• Demonstrates cold-start UCB with forced initial exploration as a stable and effective policy for delayed, sparse task-level rewards.

Datasets

• tau2-Bench (retail) — 114 tasks — public benchmark from Barres et al., 2025
• tau2-Bench (telecom) — 114 tasks — public benchmark from Barres et al., 2025
• LiveCodeBench — 300 tasks — public agentic code benchmark
• Terminal-Bench — 48 tasks — public benchmark pairing 9B and 27B models

Baselines vs proposed

• Small backend on tau2-Bench (telecom): task accuracy = 10.5% at 30.2s latency vs TRACE-Router: 39.0% at 30.0s
• Large backend on tau2-Bench (telecom): task accuracy = 60.5% at 32.7s latency vs TRACE-Router: 61.2% at 26.4s
• Latency-matched random mixture baseline on tau2-Bench (average): accuracy = 53.7% vs TRACE-Router: 61.2%
• Best single model on Terminal-Bench (27B backend): task solved rate = 39.7% at 268s vs TRACE-Router: 46.8% at 172s
• Complexity router baseline on LiveCodeBench: 49.8% accuracy at 4.6s latency vs TRACE-Router: holds all interior frontier points
• Context-free TRACE-Router variant on tau2-Bench average: accuracy ~1.3% lower than context-conditioned variant

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2607.22465.

Fig 1: Task accuracy–latency trade-off on τ 2-

Fig 5: Bandit policy and exploration parameter. Fraction of the better-versus-worse backend

Fig 6: Routing with four candidate models: Accuracy vs. latency comparison for different

Limitations

• The context classifier is simplistic (regex-based) and coarse, possibly limiting maximal gains from context conditioning.
• Evaluation benchmarks contain relatively small task sets (48–300 tasks), limiting statistical power in some ablations (e.g., warm vs cold start).
• No explicit adversarial or robustness evaluation against malicious workloads or routing attacks.
• The policy does not adapt model choice mid-task, potentially missing gains from dynamic intra-task escalation.
• Reproducibility is limited by lack of public code release and dependency on deployment-specific agent harness and evaluators.
• Latency measurements include environment and tool overheads, but detailed instrumentation per call or per model-side caching is not reported.

Open questions / follow-ons

• Can finer-grained or learned context representations improve routing performance beyond coarse regex-based tiers?
• What are the benefits and trade-offs of dynamic, intra-task model switching rather than sticky task-level bindings?
• How does TRACE-Router perform under adversarial or distribution-shifted workloads where task characteristics change abruptly?
• Can the framework be extended to multi-model ensembles per task or more complex reward structures balancing additional criteria?

Why it matters for bot defense

For bot-defense and CAPTCHA practitioners, TRACE-Router’s approach demonstrates the critical importance of aligning routing decisions with the unit of available feedback to effectively optimize latency-quality trade-offs under delayed supervision. Agentic AI workflows that involve multi-turn, stateful LLM interactions require task-consistent routing to enable reliable credit assignment from terminal outcomes, something that per-call routing cannot provide.

In CAPTCHA-like deployment scenarios involving multi-step verification or adaptive challenge workflows, adopting a similar contextual task-level routing framework could lead to substantial improvements in balancing user experience latency against challenge success accuracy. The contextual bandit formulation can help dynamically adapt backend solver selection policies as the workload shifts, avoiding over-reliance on static heuristics or riskier per-query routing decisions that fragment state or misattribute outcomes. Overall, this work provides actionable insights into online routing design for complex multi-turn AI workloads where feedback is delayed and aggregated at the task level.

Cite

@article{arxiv2607_22465,
  title={ TRACE-ROUTER: Task-Consistent and Adaptive Online Routing for Agentic AI },
  author={ Ritik Raj and Souvik Kundu and Sarbartha Banerjee and Dheemanth Joshi and Ishita Vohra and Tushar Krishna },
  journal={arXiv preprint arXiv:2607.22465},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.22465}
}

Read the full paper

• arXiv:2607.22465 (abstract)
• arXiv:2607.22465 (PDF)