PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Nazib Sorathiya, Daniel Zhang, Bardiya Akhbari

arXiv:2608.22695v1cs.CLcs.AIcs.IR

TL;DR

Large capability registries make in-context routing costly and unreliable, creating a need for scalable discovery. The paper uses offline metadata enrichment with online retrieve-then-rank search, and reports gentler degradation plus lower full-scale cost than in-context baselines. Its strongest conclusions come from ToolRet, while several benchmark and metadata limitations constrain cross-type claims.

  • Problem

    Large registries force orchestrators to narrow candidates before choosing, while in-context discovery couples cost and accuracy to registry size.

  • Method

    The pipeline rewrites sparse metadata into searchable profiles offline, retrieves candidates, and ranks them without invoking capabilities online.

  • Results

    At full scale, the pipeline reaches Match@1 0.397 on Tools-ToolRet, leads Search&Pick by 6.5 pp at half the token cost, and reduces cost 70× versus Full-Ctx.

  • Takeaways & Limitations

    Retrieve-then-rank degrades more gently than in-context routing across registry sizes and is deployed as a capability-discovery layer in a multi-agent platform.

  • Takeaways & Limitations

    The strongest conclusions come from ToolRet, while agent and skill benchmarks have construction limits that prevent independent cross-type claims.

Abstract

from arXiv · show

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.

1 Introduction

Capability discovery becomes unreliable as registries scale, motivating a search-based pipeline that enriches metadata, retrieves candidates, and ranks a shortlist without online invocation.

  • 7,278 tools are included in the largest benchmark, while registries exceed 500 entries for every MATS type in production.
  • In-context routing couples discovery cost and accuracy to registry size by showing candidates, invoking a choice, and retrying after failures.Wrong invocations consume tokens and latency and may contact an untrusted endpoint.
  • Retrieve-then-rank treats capability discovery as search, returning ranked candidates without invoking them online.The approach retrieves a shortlist from a registry rather than presenting every capability to the orchestrator.
  • The pipeline decomposes performance into retrieval recall and reranker conditional accuracy, with larger-scale misses originating mostly in retrieval.At full scale it leads Search&Pick in match accuracy while using half the tokens.
  • Offline enrichment rewrites sparse metadata into rich profiles at registration time, but its benchmark value is neutral-to-negative on well-documented public data.The paper presents enrichment as a production design choice rather than a source of benchmark gains.
  • One online LLM call performs the final ranking after top-k retrieval from the enriched index.The figure describes bounded-latency online operation, with data and computation represented separately.

2 Related work

Prior work addresses tool selection, agent routing, and capability enumeration, but this paper studies capability discovery as a scalable retrieve-then-rank problem and measures its degradation curve and error sources.

  • Tool retrieval: Tool-retrieval research includes fixed-pool API learning, retriever-assisted calling, enrichment methods, and hierarchical selection, but generally leaves retrieval implicit or does not separate retrieval from invocation.The cited systems differ in training, enrichment, and orchestration strategy, while the paper identifies retrieve-versus-rerank analysis as missing.
  • Agent routing: Agent-routing systems often select from static or context-sized menus, whereas the Nova Micro sweep places the observed breakdown around N = 500.The paper contributes a retrieval primitive for heterogeneous agent registries.
  • Capability discovery: Capability-enumeration standards support listing and invocation but assume the client already knows which server to call.Other work applies embeddings or knowledge-graph filtering, with reported gains at particular registry sizes rather than a general retrieve-then-rank study.
  • IR, dense embeddings, and LLM reranking: The paper adapts web-search architecture to capability metadata, using offline indexing and retrieve-then-rerank rather than requiring the LLM to inspect every capability.BM25 is the lexical baseline, while enrichment writes structured fields consumed by retrieval and reranking.
  • Our contribution: The paper is a systems-and-scaling study that composes established components and contributes scale evaluation, retrieval-versus-reranking decomposition, and deployment-oriented baseline comparisons.Its degradation curve spans N = 10 to 7,278, and its fixed-k reranker has 0.70–0.87 conditional accuracy.

3 Method

The method enriches each capability once at registration, indexes the resulting structured profile lexically and densely, then combines retrieval and metadata signals before one LLM reranking call.

  • Each query and registry produce a ranked list without invoking any capability online, after which the orchestrator consumes the top-k candidates.The experiments cover Tools, Agents, and Skills, while model routing is left to existing work.
  • At registration time, an LLM rewrites sparse metadata into five typed fields: summary, action-led description, differentiating keywords, and positive and negative examples.Production registries additionally use trust scores and self-reported capability tags.
  • The typed fields feed both lexical or dense retrieval and verbatim reranking, unlike query-time hypothetical documents or retrieval-only surrogate-query expansion.The implementation concatenates fields for BM25 and encodes them with BGE-large-en-v1.5 or Amazon Titan Embed V2.
  • Four scores combine into [0, 1]: LLM 0.50, BM25 0.05, Quality 0.30, and Intent 0.15.Quality and Intent are production-only signals that drop out when public registries lack trust or type metadata.
  • Missing-signal weights are renormalized, so public results use only LLM and BM25 at a fixed 10:1 ratio.Weights are set once according to signal roles and are not tuned by capability type or dataset.

4 Experiments

The experiments evaluate retrieve-then-rank across capability types, registry sizes, retrievers, rerankers, and efficiency baselines. Results show graceful scaling and strong large-registry efficiency, while retrieval—not reranking—is the main remaining bottleneck and public agent/skill evidence remains limited.

  • 4.1 Setup: The evaluation covers three capability types and five dataset/type combinations, reporting Match@k, MRR, Recall@k, and bootstrap 95% confidence intervals.Nova Micro is the default reranker, with a four-model experiment testing method-order stability.
  • 4.2 Results: At N = 7,278, Ours+Titan reaches Match@1 0.397 on Tools-ToolRet, leading Search&Pick by 6.5 pp at half the token cost.The pipeline beats Search&Pick on 13/16 Tools and 12/16 Agents sources with n ≥100.
  • 4.3 Ablations: Enrichment improves Match@1 by +5.8, +9.1, and +25.6 pp as ToolRet metadata is degraded from full descriptions to first-sentence hints and names.At name-only, Recall@15 rises from 0.134 to 0.467, showing that the end-to-end gain originates in retrieval.
  • 4.4 Retrieval analysis: Approximately 70% of large-registry misses occur during retrieval, while denser retrievers raise ToolRet Recall@15 by +4.7–7.6 pp without cleanly improving end-to-end Match@1.The fixed-k reranker’s conditional accuracy remains flat across retrievers, so further gains require a stronger first-stage retriever.
  • 4.5 Scale and latency: Match@1 for single-stage picking falls from 0.85 to 0.12 as N grows, whereas the pipeline declines from 0.81 to 0.39 with reranker conditional accuracy at 0.70–0.87.In the Nova Micro sweep, the crossover is around N = 500; Full-Ctx collapses after alphabetic truncation at N ≥5,000.
  • 4.6 Cross-type generalization: One type-agnostic configuration is used across agent, tool, and skill registries, but public benchmarks do not yet establish an independent agent- or skill-retrieval win at scale.Agents-ToolRet shares queries and 89% of its registry with Tools-ToolRet, while Skills-MCP favors lexical retrievers because queries paraphrase descriptions.

5 Deployment

The pipeline is deployed as the capability-discovery layer for a multi-agent platform, using shared registry infrastructure and offline enrichment. Its production design adds metadata signals while evaluation evidence remains limited to cost and latency.

  • Deployment evidence is architectural, while operational evidence is limited to cost and latency.
  • The pipeline is deployed as the capability-discovery layer for an internal multi-agent platform.
  • Offline enrichment rewrites sparse metadata once at registration time, while the online path retrieves, re-scores, and reranks candidates.The deployed path uses BM25, dense re-scoring, and one Nova Micro reranker call over k = 15 candidates.
  • 500+ capabilities across every MATS type place the production registry beyond the regime where single-stage LLM routing remains reliable.The reported decline is −13 pp Match@1 per doubling past the crossover.
  • +4.5 pp Match@1 comes from adding Quality and Intent signals on an internal registry with trust and type metadata, with retrieval fixed.The improvement is reported at p = 0.031.

6 Conclusion

The paper recasts capability discovery as registry search, combining offline enrichment with online retrieve-then-rank without invoking candidates. Across growing registries, this approach degrades more gently and is cheaper than in-context alternatives at full scale.

  • The system converts sparse registry metadata into searchable profiles and returns ranked candidates without invoking them online.
  • Match@1 falls from 0.85 to 0.12 for in-context routing but from 0.81 to 0.39 for retrieve-then-rank as N grows from 10 to 7,278.The Nova Micro sweep places the crossover around N = 500.
  • At full scale, the pipeline leads Search&Pick by 6.5 pp at about half the cost and reduces cost 70× versus Full-Ctx.

Limitations

The strongest conclusions come from ToolRet, while benchmark construction and metadata availability constrain broader cross-type and production-signal claims.

  • The strongest conclusions are based on ToolRet with n = 7,278.
  • Construction limits in the agent and skill benchmarks prevent independent cross-type claims.
  • Enrichment is neutral-to-negative on well-documented registries, while sparse metadata is evaluated through controlled degradation rather than occurring naturally.
  • Quality and Intent require trust and type metadata absent from public registries, so public results reflect only the two-signal pipeline.
  • The paper reports no model-retrieval numbers despite indexing models in production.

Ethical considerations

The discovery stage avoids running candidate code, but provider-controlled metadata can bias retrieval and therefore requires operational monitoring.

  • The discovery stage ranks candidates without invoking them, so candidate code is not run during discovery.
  • Provider-controlled metadata can bias retrieval, motivating versioned profiles and monitoring of exposure.

A Detailed results

The two-stage pipeline avoids the scale collapse of single-stage LLM picking by keeping reranking fixed at k = 15, leaving retrieval as the main large-registry constraint.

  • Scale and bottlenecks: Full-Ctx Match@1 falls from 0.85 to 0.12 across the scan, while the pipeline reranker stays between 0.85 and 0.70.The reranker always sees exactly k = 15 candidates.
  • Scale and bottlenecks: ∼0.87 conditional accuracy at N = 100 with full retrieval recall is the highest reranker value measured.This indicates the reranker is not the primary constraint.
  • Scale and bottlenecks: ∼0.39 Match@1 at N = 7,278 factors into ∼0.56 retrieval reach and ∼0.70 reranker accuracy.The factorization identifies retrieval as limiting further end-to-end gains.
  • Scale and bottlenecks: N ≥5,000 leaves the pipeline bottlenecked by BM25 recall, while intermediate registries show a 7–17 pp advantage.At N ≤25 retrieval is identity and the pipeline is approximately tied with Full-Ctx; only Figure 2 estimates the crossover at N = 500.

D Failure modes

The reported failure modes separate retrieval misses, reranking errors, ground-truth mismatches, and Full-Ctx truncation, while enrichment mainly helps when metadata is sparse.

  • Cost and robustness: ∼70× lower cost than Full-Ctx accompanies higher Match@1, but Ours-row costs are post-hoc prompt-shape estimates with ±5–10% uncertainty.Table 3 reports Match@1, tokens per query, dollars per 1,000 queries, and p50 latency.
  • Failure modes: A retrieved named sandbox server can lose to a generic Docker tool when reranking overweights surrounding intent.This is the paper’s picked-more-generic failure category.
  • Failure modes: Match@1 penalizes a single predicted tool when the ground truth is a 9-tool trajectory, although Recall@15 does not.This is classified as a prediction outside the ground-truth set.
  • Failure modes: Full-Ctx truncation drops 4,023 of 7,278 tools at full scale and creates additional misses.The cited passage attributes the resulting collapse to truncation.
  • Metadata sparsity: 0.134 to 0.467 Recall@15 at name-only metadata accompanies rerank conditional accuracy rising from 0.63 to 0.73.Enriched and raw inputs have similar Match@1, 0.776 and 0.778, and enrichment leaves 867 of 1,000 summaries empty.

F Results by ToolRet source

ToolRet source-level results favor the pipeline broadly on large ToolRet rows, but dataset construction and metadata conditions constrain how independently the broader claims can be read.

  • Dataset caveats: ∼2 pp higher Tools Match@1 follows from excluding the malformed ultratool source, without changing method ordering.That source contains 500 queries and 287 referenced ground-truth tools absent from the registry.
  • Source-level comparisons: 13/16 Tools sources and 12/16 Agents sources with n ≥100 favor Ours+Titan over Search&Pick.The source-level comparison is reported across representative ToolRet sources.
  • Retriever comparisons: ToolBench-IR improves standalone Match@1 over BM25 but does not exceed the best general encoder on Recall@15 or end-to-end Match@1.The comparison covers both full ToolRet query sets with n = 7,961.
  • Metadata signals: Fourteen queries change from miss to hit and four from hit to miss when Quality and Intent are added, with exact McNemar p = 0.031.Recall remains unchanged because retrieval is shared.
Loading 2608.22695v1…