- 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.