💬 NLP

Learning Agent Routing From Early Experience

This paper introduces BoundaryRouter, a training-free framework that optimizes the trade-off between latency and performance by dynamically routing queries to either lightweight LLM inference or full agent execution based on early behavioral experience and rubric-guided reasoning, achieving significant improvements in both speed and accuracy over existing methods.

Original authors: Yimin Wang, Jiahao Qiu, Xuan Qi, Xinzhe Juan, Jingzhe Shi, Zelin Zhao, Hongru Wang, Shilong Liu, Mengdi Wang

Published 2026-05-11

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yimin Wang, Jiahao Qiu, Xuan Qi, Xinzhe Juan, Jingzhe Shi, Zelin Zhao, Hongru Wang, Shilong Liu, Mengdi Wang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very smart, fast, but sometimes overconfident assistant (the LLM) and a highly skilled, thorough, but slow and expensive expert consultant (the Agent).

The Assistant can answer simple questions like "What's the capital of France?" instantly and for free. But if you ask it to solve a complex physics problem or write a long, multi-step code, it might guess wrong or hallucinate.
The Expert can solve those hard problems perfectly by using tools, doing research, and thinking step-by-step. But it takes a long time to do so and costs a lot of money.

The Problem:
Right now, if you have a mix of easy and hard questions, you have to guess which one to send to whom. If you send everything to the Expert, you waste time and money on easy questions. If you send everything to the Assistant, you get wrong answers on hard questions.

The Solution: "BoundaryRouter"
The paper introduces a new system called BoundaryRouter. Think of it as a smart traffic cop standing at the intersection between the Assistant and the Expert. Its job is to look at every incoming question and decide: "Is this easy enough for the Assistant, or does it need the Expert?"

The tricky part is that this traffic cop has to start working immediately, without any prior training data or a "cheat sheet" of right answers. It's a "cold start."

How It Works (The Creative Analogy):
Instead of studying for a test, the traffic cop uses a trick called "Learning from Early Experience."

The "Seed" Test: Before the system goes live, the researchers run a small batch of questions through both the Assistant and the Expert. They don't care about the right answers yet; they just watch how the two behave.
- Example: They notice that when the question is about a specific type of math, the Assistant gives a short, confident answer in 2 seconds, while the Expert takes 300 seconds to pull out a calculator and double-check.
- They save these observations in a small "memory book."
The "Look-Alike" Search: When a new question arrives, the traffic cop flips through its memory book. It asks: "Does this new question look like the ones we saw before?"
- If it finds a match where the Assistant was fast and the Expert was slow, it sends the new question to the Assistant.
- If it finds a match where the Assistant was confused or slow, it sends the question to the Expert.
The "Rulebook" Reasoning: To make sure the traffic cop doesn't just guess, it follows a strict Rulebook (called "Rubric-Guided Reasoning"). It doesn't just "feel" like the Expert is needed; it checks specific criteria: "Did the similar past question take the Expert 10x longer? Did the Assistant's answer look vague?" This keeps the decision logical and consistent.

The Results:
The researchers tested this system on a new benchmark called RouteBench (a collection of tricky questions).

Speed: Compared to using the Expert for everything, this system was 60% faster because it stopped wasting time on easy questions.
Accuracy: Compared to using the Assistant for everything, it was 28% more accurate because it didn't let the Assistant guess on hard problems.
Comparison: It worked much better than other methods that just used simple prompts or basic search tools.

In a Nutshell:
This paper shows that you don't need a massive training dataset to build a smart system that knows when to be fast and when to be thorough. By simply observing how two different systems behave on a few sample questions, you can teach a "traffic cop" to route future questions perfectly, saving time and money without sacrificing quality.

Technical Summary: Learning Agent Routing from Early Experience

Problem Statement

Large Language Model (LLM) agents demonstrate strong capabilities in complex reasoning, planning, and tool use but incur high latency and computational costs. Conversely, direct LLM inference is fast and cost-effective but often unreliable for tasks exceeding its capability boundary. The central challenge addressed in this work is routing queries between lightweight LLM inference and full agent execution under realistic cold-start settings. In these scenarios, incoming queries lack prior performance data or ground-truth labels, making standard supervised training of a router impractical. Existing research largely focuses on routing within homogeneous spaces (e.g., among different LLMs or among different agents), leaving the hybrid routing problem between LLMs and agents largely unexplored.

Methodology: BoundaryRouter

The authors propose BoundaryRouter, a training-free routing framework designed to make routing decisions without ground-truth supervision. The system operates through three core mechanisms:

1. Learning from Early Experience

To overcome the cold-start problem, BoundaryRouter constructs a compact early-experience memory ( $M$ ).

Construction: A small seed set of questions ( $D_{seed}$ ) is executed on both the lightweight LLM and the full agent.
Data Recorded: For each query, the system records the input question, the outputs from both solvers ( $y_{LLM}, y_{Agent}$ ), and their respective latencies ( $t_{LLM}, t_{Agent}$ ).
Constraint: Crucially, no ground-truth answers, correctness labels, or rewards are stored. The memory captures systematic behavioral differences (e.g., response patterns and runtime) between the two systems.

2. Retrieval-Augmented Routing

At inference time, for a new query $x$ :

The system retrieves the top- $K$ most similar records from the early-experience memory using a hybrid retriever (combining sparse lexical matching and dense semantic similarity).
These retrieved cases serve as evidence, allowing the router to compare the current query against historical behaviors of both solvers to infer regularities (e.g., whether similar phrasing previously led to agent-specific multi-step reasoning or latency spikes).

3. Rubric-Guided Chain-of-Thought (CoT)

To ensure decisions align with specific behavioral criteria rather than open-ended reasoning, the routing LLM employs rubric-guided CoT.

Instead of free-form reasoning, the router follows a fixed decision rubric encoded in the prompt.
This rubric directs the model to explicitly evaluate retrieved cases based on observable dimensions (answer characteristics and response times) to trade off expected answer quality against latency.
The output is a binary routing decision: $Route(x) \in \{LLM, Agent\}$ .

Key Contributions

1. The BoundaryRouter Framework

The paper introduces a novel, training-free routing method that leverages early behavioral experience and structured reasoning. It enables reliable routing in cold-start settings where ground-truth labels are unavailable, bridging the gap between fast, low-cost LLM inference and robust, high-cost agent execution.

2. RouteBench Benchmark

To systematically evaluate this problem, the authors introduce RouteBench, a benchmark specifically designed for LLM-agent routing.

Composition: Derived from GAIA and MMLU datasets, it includes paired solver outputs, latency data, and human-annotated routing labels based on a deterministic rule (correctness priority, efficiency tie-break, and failure fallback).
Evaluation Sets: It assesses generalization across three dimensions:
- Base Set: In-domain tasks.
- Rephrase Set: Linguistically perturbed queries to test robustness.
- Advanced Set: Out-of-domain tasks to test distribution shift.
Metrics: It utilizes instance-level accuracy, solver-level F1 scores, and a composite RouteBenchScore to measure overall routing effectiveness.

Experimental Results

Experiments were conducted on RouteBench using 14 contemporary models (including GPT-5, Gemini-3-Pro, and Claude Sonnet 4) as the routing backbone.

Performance vs. Cost Trade-off: BoundaryRouter reduced average inference time by 60.6% compared to using the agent exclusively, while improving performance by 28.6% over direct LLM inference.
Comparison with Baselines:
- Compared to prompt-based routing (without experience), BoundaryRouter improved routing quality by 37.9%.
- Compared to retrieval-only routing (without rubric-guided reasoning), it improved performance by 8.2%.
Generalization: The method maintained strong performance on the Advanced (out-of-domain) set, demonstrating that early behavioral signals paired with rubric-constrained reasoning can generalize beyond the training distribution.
Model Stratification: Among frontier models, GPT-5, Gemini-3-Pro-Preview, and Gemini-2.5-Pro achieved the strongest routing performance, particularly in handling out-of-domain shifts.

Significance and Claims

The paper claims that early behavioral signals, when paired with rubric-guided reasoning, can enable reliable routing between LLMs and agents even in the absence of ground-truth labels or routing supervision.

Practicality: The framework offers a practical path toward scalable coordination in heterogeneous reasoning systems without the need for expensive supervised training data.
Insight on Routing Difficulty: The results highlight that routing remains a challenging problem even in in-domain settings, with performance degrading significantly under distribution shifts for weaker models.
Future Direction: While the current work focuses on binary routing between a single LLM and a single agent pipeline, the authors suggest this approach lays the groundwork for more complex scenarios involving multiple agents or heterogeneous tools.

The authors emphasize that their findings demonstrate the viability of using self-generated early experience as a lightweight reference to guide system-level decisions, shifting the paradigm from static model selection to dynamic, experience-driven coordination.