Enrich-Retrieve-Rank: Scaling Capability Discovery Beyond In-Context Routing

Nazib Sorathiya; Daniel Zhang; Bardiya Akhbari

cs.CLAug 24, 2026

Enrich-Retrieve-Rank: Scaling Capability Discovery Beyond In-Context Routing

Authors: Nazib Sorathiya, Daniel Zhang, Bardiya Akhbari

Organizations: Amazon AGI Seattle, WA, USA

Abstract

Agent ecosystems now include thousands of MATS components (Models, Agents, Tools, and Skills), yet their discovery still relies on in-context routing. These systems read a registry (names, hints, or descriptions, as context budget permits), pick a candidate, invoke it, and retry on failure. This pattern degrades with scale, and registries are growing fast. We recast capability discovery as search over a registry by defining an offline enrichment step that turns sparse metadata into searchable profiles, and an online retrieve-then-rank pipeline that returns a ranked shortlist without invoking any candidates online. We show that from N=10 to 7,278 capabilities, in-context routing's top-1 accuracy (Match@1) collapses (0.85 to 0.12), while retrieve-then-rank degrades more gently (0.81 to 0.39) because its reranker still ranks the right capability first 0.70-0.87 of the time once retrieval finds it. In the Nova Micro sweep, the crossover is around N=500. We compare against two in-context baselines. Full-Ctx puts the whole registry in the prompt and asks the LLM to pick. Search&Pick gives the LLM a search tool to narrow candidates before it picks. At full scale the pipeline leads Search&Pick by 6.5 percentage points (pp) on Match@1 at about half the cost. It reduces cost 70x versus Full-Ctx. We use a fixed configuration (same enrichment, retriever, and scorer weights) across agent, tool, and skill registries. The pipeline runs in production as the default capability-discovery layer of a large-scale multi-agent platform.

Figures & tables

Figure 1: The Enrich-Retrieve-Rank pipeline. Phase 1 transforms sparse capability metadata into rich profiles. Phase 2 retrieves top- $k$ candidates from the enriched index. Phase 3 ranks with a single LLM call. The entire online path requires one LLM call at bounded latency. Dashed boxes are data, and solid boxes are computation.

Type	Benchmark	Reg.	Queries
Tools	ToolRet	7,278	7,961
Tools	AppWorld	332	147
Agents	ToolRet	5,885	7,961
Agents	AppWorld	8	147
Skills	MCP	859	1,627

Table 1: Capability

\times

benchmark coverage.

Row ( n / q )	Regex	Full Ctx	Search &Pick	Trial &Err	BM25	BGE 5f	Ours +BM25	Ours +BGE	Ours +Titan
Tools / ToolRet (7,278 / 7,961)	0.231	0.166	0.332	0.054	0.311	0.346	0.388	0.389	0.397
Tools / AppWorld (332 / 147)	0.408	0.762	0.476	0.061	0.483	0.429	0.741	0.735	0.741
Agents / ToolRet (5,885 / 7,961)	0.228	0.148	0.341	0.045	0.336	0.360	0.418	0.412	0.397
Agents / AppWorld (8 / 147)	0.993	0.986	0.973	0.014	1.000	1.000	1.000	1.000	1.000
Skills / MCP, leaky (859 / 1,627)	0.648	0.968	0.829	0.624	0.880	0.892	0.807	0.806	0.942

Table 2: Match@1 splits by registry size (

n

) and query count (

q

): the pipeline leads on large registries while in-context routing wins for the smaller sizes. Ours+BGE is the 5-field BGE config. Bold marks the best result in each row. Ours+Titan uses Amazon Titan Embed V2 as the dense retriever. Full-Ctx uses an

n=500

sub-sample on Tools-ToolRet, Agents-ToolRet, and Skills-MCP because the full registry exceeds Nova Micro’s context window; every other cell is full-

n

. Trial&Err scores its final try and can fall below the

1/n

random-pick rate when it abstains rather than guessing; see footnote. Other metrics are in Appendix B .

Figure 2: Within-benchmark scaling. Match@1 vs. $N$ (Left) and pipeline decomposition (Right).

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Row	Method	M@1	Tok-in/q	Tok-out/q	$/1k q	p50 (ms)	Source
Tools — ToolRet	Full-Ctx	0.166	128,067	8	4.4835	5,841	real
	Search&Pick	0.332	3,141	48	0.1166	1,556	real
	Trial&Err	0.054	1,875	29	0.0697	1,532	real
	Ours+BM25	0.388	1,597	75	0.0664	1,290	est.
	Ours+BGE-5f	0.389	1,586	75	0.0660	1,116	est.
Tools — AppWorld	Full-Ctx	0.762	6,997	10	0.2463	447	real

Appendix

Table 3: Retrieve-then-rank costs

{\sim}

70× less than the full-context picker at higher Match@1. Columns report Match@1, tokens per query, dollars per 1,000 queries, and p50 latency. Trial-and-error rows report real measured token counts; Ours rows are post-hoc prompt-shape estimates (

\pm 5

–

10\%

of real).

Row	Reranker	M@1	p50 (ms)
Tools–ToolRet ( $n{=}500$ )	Nova Micro	0.682	750
	Nova Lite	0.678	1,316
	Cl. 3.5 Haiku	0.496	11,196
	Cl. Sonnet 4	0.722	3,775
Tools–ToolRet (full)	Nova Micro	0.389	807
	Nova Lite	0.395	1,453

Appendix

Table 4: Cross-model robustness of the reranker. The large-registry gain from a stronger reranker is small, consistent with accuracy inside the

0.70

–

0.87

band.

Row	Ranker LLM	Search &Pick	Ours +BM25	Ours +BGE
Tools– ToolRet	Nova Micro	0.332	0.388	0.389
	Qwen3 Next	0.368	0.416	0.419
	Mistral L3	0.365	0.408	0.415
Agents– ToolRet	Nova Micro	0.341	0.418	0.412
	Qwen3 Next	0.385	0.451	0.452
	Mistral L3	0.388	0.451	0.458

Appendix

Table 5: Cross-model generalization of the pipeline (not just the reranker). Match@1 at full

n

. Ours beats the strongest in-context baseline (Search&Pick) under all LLMs: +5.6/+5.1/+5.0 pp on Tools-ToolRet and +7.7/+6.7/+7.0 pp on Agents-ToolRet. The Qwen3 Next ranker is

\sim 3

pp of Nova Micro at full

n

, so the prompt is not tuned. Bold marks the best result.

Benchmark	Cond.	M@1	M@3	R@ $k$
AppWorld (332)	Raw	0.782	0.884	0.420
AppWorld (332)	Enriched	0.782	0.918	0.400
ToolRet (1,000)	Raw	0.124	0.137	0.135
ToolRet (1,000)	Enriched	0.125	0.139	0.138
MCP Skills (859)	Raw	0.929	0.977	0.988
MCP Skills (859)	Enriched	0.885	0.939	0.951

Appendix

Table 6: Enrichment ablation behind § 4.3 . LLM enrichment adds no measurable gain on well-documented public registries. Raw vs. LLM-enriched registry, all else held fixed. The ToolRet rows use a 1,000-tool subset, so absolute numbers are low but the raw-vs-enriched delta is the quantity of interest.

Row	Metric	Regex	BM25	BGE-5f	Ours+BM25	Ours+BGE-5f	Ours+Titan
Tools — ToolRet	M@3	0.314	0.423	0.472	0.493	0.502	0.523
	M@5	0.354	0.464	0.520	0.523	0.539	0.558
	MRR	0.285	0.378	0.424	0.446	0.454	0.467
Tools — AppWorld	M@3	0.687	0.728	0.721	0.884	0.898	0.918
	M@5	0.755	0.837	0.823	0.898	0.932	0.946
	MRR	0.576	0.631	0.594	0.820	0.819	0.832

Appendix

Table 7: Ours+Titan leads on Tools-ToolRet, AppWorld, and Skills-MCP; on Agents-ToolRet, Ours+BGE-5f leads. The saturated Agents-AppWorld row ties. The single-pick baselines (Full-Ctx, Search&Pick, and Trial&Err) emit one capability per query, so these metrics are undefined for them and their columns are omitted.

Row	BM25 M@15	BGE-5f M@15	Titan M@15	Ours+BM25 R@15	Ours+BGE-5f R@15
Tools — ToolRet	0.549	0.618	0.625	0.485	0.517
Tools — AppWorld	0.952	0.966	0.993	0.262	0.261
Agents — ToolRet	0.569	0.626	0.616	0.508	0.538
Agents — AppWorld	1.000	1.000	1.000	1.000	1.000
Skills — MCP	0.991	0.992	0.994	0.951	0.992

Appendix

Table 8: Retrieval at

k=15

. Standalone columns report Match@15, the query-level any-hit rate. Ours columns report Recall@15, the fraction of all ground-truth capabilities retrieved. Single-pick baselines are omitted.

Figure 3: Cross-sectional benchmark comparison. Full-Ctx wins or ties on the small rows, while Ours+BM25 leads on the large ToolRet rows. Full-Ctx uses 500-candidate subsamples on ToolRet and Skills-MCP (Table 2 ), so these points do not estimate a shared threshold.

Input level	Raw	Enriched	R@15 raw $\to$ enr.
Full description	0.720	0.778	$0.905\to 0.933$
First-sentence hint	0.685	0.776	$0.888\to 0.929$
Name-only	0.085	0.341	$0.134\to 0.467$

Appendix

Table 9: Metadata-sparsity ablation (

n=1{,}252

per cell). Match@1 gains are

+5.8

+9.1

, and

+25.6

pp from full to name-only input.

Figure 4: Enrichment acts primarily through retrieval. As input metadata is removed, the raw-versus-enriched gap widens far more in Recall@15 (right) than in Match@1 (left).

Source	$n$	Ours+Titan	S&Pick	$\Delta$
Tools — ToolRet
toolbench	1,100	0.518	0.490	$+0.028$
apigen	1,000	0.702	0.611	$+0.091$
toolace	1,000	0.694	0.620	$+0.074$
toolink	497	0.579	0.348	$+0.231$
apibank	101	0.614	0.426	$+0.188$

Appendix

Table 10: Match@1 for representative ToolRet sources. Across all sources with

n\geq 100

, Ours+Titan leads Search&Pick on 13/16 Tools sources and 12/16 Agents sources. “Long tail” pools 19 smaller Tools sources.

Row	Retriever	Standalone	Standalone	E2E
		M@1	R@15	M@1
Tools	BM25	0.311	0.549	0.388
	ToolBench-IR	0.354	0.608	0.378
	Titan V2	0.358	0.625	0.397
Agents	BM25	0.336	0.569	0.418
	ToolBench-IR	0.362	0.596	0.381

Appendix

Table 11: Tool-tuned and general retrievers on the two full ToolRet query sets (

n=7{,}961

). ToolBench-IR improves standalone Match@1 over BM25 but does not exceed the best general encoder on Recall@15 or end-to-end (E2E) Match@1.

Metric	Four-signal minus two-signal
Match@1	$+4.5$ pp
Match@3	$+5.0$ pp
Recall@15	$0.0$ pp

Appendix

Table 12: Paired effect of adding Quality and Intent on the internal benchmark. Fourteen queries change from miss to hit at rank 1 and four change from hit to miss (exact McNemar

p=0.031

). Recall is unchanged because retrieval is shared.

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 98 papers

AgentSearchBench: A Benchmark for AI Agent Search in the Wild
Apr 24, 2026Bin Wu, Arastun Mammadli, Xiaoyu Zhang +1Agentic Search AI Agent Evaluation
Centre for Artificial Intelligence, University College London
SSR: Structural Signal Retriever for Scalable Agent Discovery in LLM-Orchestrated Multi-Agent Systems
Oct 15, 2026Giancarlo Maldonado Cárdenas, Carlos A. Astudillo, Nelson L. S. da FonsecaMulti-Agent LLM Systems LLM Agent Orchestration
Institute of Computing – State University of Campinas, Brazil
When Tool-Backed Skill Retrieval Fails: Source-Style Collapse in Executable Capability Retrieval
Aug 17, 2026Yiqi Liu, Joseph James, Yang Wang +2LLM Agent Skill Retrieval Tool-Using Agents
University of Manchester · University of Sheffield · Shanghai University of Finance and Economics

Apr 24, 2026J/K move · Enter open · S save

AgentSearchBench: A Benchmark for AI Agent Search in the Wild

Bin Wu, Arastun Mammadli, Xiaoyu Zhang, Emine Yilmaz

Centre for Artificial Intelligence, University College London

Agentic Search AI Agent Evaluation AI Agent Benchmarks

Open paper AskPDF arXiv

The rapid growth of AI agent ecosystems is transforming how complex tasks are delegated and executed, creating a new challenge of identifying suitable agents for a given task. Unlike traditional tools, agent capabilities are often compositional and execution-dependent, making them difficult to assess from textual descriptions alone. However, existing research and benchmarks typically assume well-specified functionalities, controlled candidate pools, or only executable task queries, leaving realistic agent search scenarios insufficiently studied. We introduce AgentSearchBench, a large-scale benchmark for agent search in the wild, built from nearly 10,000 real-world agents across multiple providers. The benchmark formalizes agent search as retrieval and reranking problems under both executable task queries and high-level task descriptions, and evaluates relevance using execution-grounded performance signals. Experiments reveal a consistent gap between semantic similarity and actual agent performance, exposing the limitations of description-based retrieval and reranking methods. We further show that lightweight behavioral signals, including execution-aware probing, can substantially improve ranking quality, highlighting the importance of incorporating execution signals into agent discovery. Our code is available at https://github.com/Bingo-W/AgentSearchBench.

Abstract

LLM Agent Routing

Explore similar work

AgentSearchBench: A Benchmark for AI Agent Search in the Wild

SSR: Structural Signal Retriever for Scalable Agent Discovery in LLM-Orchestrated Multi-Agent Systems

When Tool-Backed Skill Retrieval Fails: Source-Style Collapse in Executable Capability Retrieval