acceptodds
Under review as a conference paper at ICLR 2027

Sketch-Informed Capability Discovery in Large Agent Collectives

Abstract

Open collectives of foundation models, agents, and web services now contain thousands of entities, and a coordinator who needs a qualified entity for a task cannot afford to inspect them all. We study the coordinator's discovery problem under a two-tier query model, where each of the entity-groups publishes a free summary of its member's capabilities, alongside a costly query that reveals a random entity from a chosen group. Our main result is a threshold on the summary dimension with resolution . When the dimension is , summaries are informative enough to guide the search. Our proposed SIEVE algorithm uses the summaries to eliminate groups and then queries the remaining groups' members. With probability , SIEVE discovers and returns an entity that can perform the task and ranks in the top fraction of the collective, counted over the groups that contain the capability, with at most queries. This query complexity depends on neither nor the size of the collective, and no algorithm with a worst-case query limit can improve it by more than a constant factor. Below the dimension threshold, we prove in a Gaussian model of the summary readout that the query complexity of any coordinator that reads the summaries through inner products grows polynomially in . Experiments on synthetic populations with up to one million entities, as well as on RapidAPI and the Open LLM Leaderboard, support the predicted dimension threshold and query savings.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
multi-agent systems, pure exploration, sketching

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_DGxrOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper addresses capability discovery in large agent collectives by proposing a two-tier query model and a filtering algorithm based on additive sketches. The authors rigorously prove that when the sketch dimension reaches a specific threshold, the query complexity drops to a level independent of the number of groups and the total collective size, and provide a matching lower bound. Experiments on synthetic and real-world datasets validate the theoretical threshold and query efficiency.

Critical strengths

S1. Rigorous theoretical analysis with matched upper and lower bounds on query complexity, clearly defining the technical boundaries.

S2. Precise problem formulation; the two-tier model combining free group-level summaries and costly individual queries directly addresses practical bottlenecks in large-scale system discovery.

Critical weaknesses

Weaknesses

W1. Overly idealized assumptions for dynamic scenarios.

W2. Insufficient baseline comparisons.

Detailed comments

D1. The paper assumes bounded capability drift and simple additive sketch updates. However, in real-world registries, sudden capability shifts (e.g., major model upgrades) are often non-stationary. The paper fails to discuss the robustness of the sketch dimension against severe concept drift or the practical system overhead of periodically rebuilding sketches, raising concerns about the technical route's validity in dynamic environments.

D2. While several multi-armed bandit methods are compared, there is a lack of direct performance comparison with classical lightweight data structures (e.g., Bloom Filters or Count-Min Sketch) in similar discovery tasks. This weakens the argument for the proposed sketch's absolute advantage over traditional indexing schemes.

Questions for authors

Q1. If a group's capability distribution shifts suddenly, how many queries does the proposed algorithm need to detect and correct its sampling weights? Is there a mechanism to force a sketch refresh?

Q2. What is the empirical value of the maximum qualified label set size in real-world datasets? When this value is large, does the theoretical lower bound cause the sketch dimension to become impractically large, thereby losing its compact advantage?

Q3. Other questions mentioned in Weakness part.

Reviewer_8ro3OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Summary: This paper looks at how to find qualified agents in a large multi-agent collective without having to inspect every agent one by one. The authors propose SIEVE (Sketch-Informed Elimination and Verification), a two-tier approach. It first uses compact group-level capability sketches to rule out groups that are unlikely to contain a qualified agent, and only then queries individual agents. The main theoretical result is a sketch dimension threshold of O(β⁻² log K), above which the algorithm can find a qualified agent with a query complexity that doesn't depend on the number of groups or the total population size. They also give a lower bound under a Gaussian noisy linear-readout model to show what lower-dimensional sketches can't do. Experiments on synthetic populations of up to a million entities, plus RapidAPI and the Open LLM Leaderboard, show large query savings and mostly line up with the theory.

Critical strengths

Strengths: Scalability is a real problem for large multi-agent systems, since finding a suitable agent gets more expensive as the pool grows, so the paper is tackling something worthwhile. I think its main strength is the clean formulation of capability discovery as a two-tier search problem, backed by an algorithm with explicit query-complexity guarantees. The analysis of linking sketch dimension, capability density, and query efficiency is useful for understanding when group-level summaries actually help. I also appreciate that the paper pairs theory with experiments and compares against several other discovery strategies. The experiments show a big drop in individual queries while keeping discovery success high, which suggests the approach could be useful for large agent registries.

Critical weaknesses

Weaknesses: The theory is good, but I have several concerns about how well this carries over to practice. • The framework assumes uniformly random access to agents, group summaries that come for free, bounded population drift, and the ability to judge an agent's feasibility and quality from compressed attribute labels. That is a lot to assume, and it may not reflect real, dynamic multi-agent environments. • It is only established for a restricted Gaussian noisy linear-readout model. So it's unclear whether the same sketch dimension threshold is actually necessary for more general sketching schemes or for adaptive discovery methods. • The evaluation leans on synthetic populations and structured metadata from RapidAPI and the Open LLM Leaderboard. It never involves real agent interactions or task execution, so there's little evidence the approach can reliably find capable agents in realistic multi-agent settings. • The paper compares against several discovery strategies, but not against established sketch-based alternatives such as count-min sketches or Bloom filters. Without these, it's hard to tell what the proposed sketch representation specifically contributes. • The experiments don't really test noisy capability descriptions, heterogeneous query costs, unreliable agent performance, or rapid changes in agent availability. That leaves me unsure how well the framework would hold up under realistic deployment conditions.

Questions for authors

Please see under weaknesses.

Reviewer_68aSOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies capability discovery in a collective of K groups, where each group publishes a free additive torus sketch and a costly query reveals one random member. It proposes SIEVE (sketch-based elimination followed by mass-proportional sampling) with an O(q⁻¹ log δ⁻¹) query bound independent of K and N, argues d = Θ(β⁻² log K) is the required sketch dimension, and evaluates on synthetic needle populations, RapidAPI, and the Open LLM Leaderboard.

Critical strengths

S1. The empirical threshold matches the theory. Above d_lb = β⁻² log K, cost falls to 9.3–10.3 queries against the 1/β = 10 floor for every K from 16 to 512 (Fig. 1a), and 95% success is reached at 0.73–1.08 · d_lb (Fig. 1b). S2. Cost is predictable before searching. 1/R predicts SIEVE's cost in advance (4.4 predicted vs. 4.6 used on Open LLM, Tab. 1), and regrouping RapidAPI at random raises cost from 8 to 59 queries.

Critical weaknesses

W1. The Conclusion overstates the lower bound. The Abstract, Sec. 1, and Thm. 2 restrict the bound to one Gaussian linear readout per stratum (Def. 4), but the Conclusion drops the qualifier and claims "below this size no coordinator reading the summaries can prevent such growth" — more than Lem. 9 proves, and contradicted by Rem. 4. W2. No comparison with simpler summaries. Count-min sketches and Bloom filters are cited in Sec. 2 but never evaluated, nor are exact per-label counts. The sufficient dimension of Thm. 2 is also ~10³× above the observed threshold and grows linearly in A. W3. Three of the six baselines collapse to one behavior. Greedy, Thompson, and MF-LUCB share the same cost (1.00×, 1.01×) and worst-task rates (47%, 23%), suggesting all three reduce to querying the highest-estimate group. SIEVE adds the β/2 elimination and 3q/4 relaxation on top of weighted sampling, so the control that isolates those margins — weighted sampling with them restored — is missing.

Questions for authors

Q1. If greedy, weighted, Thompson, and MF-LUCB are given the same β/2 elimination and 3q/4 relaxation, does the reliability gap in Tab. 2 persist? And why do three of them produce nearly identical rows? Q2. At equal summary size in bytes, how do exact per-label counts, count-min sketches, and Bloom-style indicators compare to the torus sketch in query cost and reliability?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.