TLDR: This research introduces DOVIS, a five-layer protocol (Discovery, Orchestration, Verification, Incentives, Semantics) for collecting minimal, privacy-preserving agent performance data, and AgentRank-UC, an algorithm that combines agent usage and competence into a unified, dynamic ranking. It addresses the challenge of agent discovery in the emerging ‘Agentic Web’ by providing theoretical guarantees for fairness, stability, and Sybil resistance, validated through simulations.
The internet is on the cusp of a major transformation, moving beyond a human-centric web of pages to an advanced, machine-native ecosystem called the ‘Agentic Web’. This new paradigm envisions autonomous AI agents, powered by large language models (LLMs) and equipped with various tools, interacting, collaborating, and executing complex tasks at an unprecedented scale. However, realizing this vision presents a significant challenge: how do we effectively discover and select the best agents from a vast and dynamic network?
Unlike the early days of the internet, where PageRank could assess website importance based on transparent hyperlinks, the Agentic Web lacks a global, open record of agent interactions. Usage signals are often fragmented and private, making it difficult to rank agents based on their actual performance. This is the core problem addressed by a new research paper titled Internet 3.0: Architecture for a Web-of-Agents with it’s Algorithm for Ranking Agents, authored by Rajesh T. Krishanamachari and Srividya Rajesh.
Introducing DOVIS: The Operational Protocol for Agent Telemetry
The paper proposes DOVIS, a five-layer operational protocol designed to enable the collection of essential, privacy-preserving data about agent usage and performance across the ecosystem. DOVIS stands for Discovery, Orchestration, Verification, Incentives, and Semantics, each layer playing a crucial role in building a trustworthy foundation for agent ranking.
At its heart is the concept of Minimal Telemetry, specifically the OAT-Lite (Open Agent Telemetry – Lite) schema. Instead of collecting raw, sensitive data, agents only publish aggregate statistics of their interactions. This includes the total number of calls for a specific task, the number of successful calls, and cumulative measures of quality, latency, cost, and risk. This lightweight approach ensures privacy while providing sufficient data for ranking.
Orchestration defines how this telemetry is collected. Callers (agents initiating tasks) are the primary reporters, submitting per-epoch (e.g., hourly or daily) aggregates. Callees (agents performing tasks) can optionally provide acknowledgments of calls received, offering a lightweight cross-check. This structured reporting ensures consistent and timely data collection.
Verification is critical for ensuring the integrity of the reported data. To combat threats like success inflation, failure suppression, usage pumping, or identity churn, DOVIS employs cryptographic signatures for all reports, optional callee acknowledgments for cross-checking, and randomized audits. Reports from verified or staked agents can also be given higher weight, and penalties are imposed for misreporting.
Incentives address the ‘why’ behind agent participation. Since generating telemetry incurs costs, DOVIS proposes mechanisms like exposure rewards (boosting visibility for consistent reporters), penalties for dishonesty, optional telemetry credits (redeemable for benefits), and cold-start support (ensuring new agents aren’t invisible due to lack of history). These mechanisms align individual agent interests with the collective good of a well-ranked ecosystem.
Finally, Semantics ensures that all reported numbers are consistently interpreted. This involves standardizing the OAT-Lite schema fields, defining canonical units (e.g., milliseconds for latency, for quality), and establishing a global task taxonomy registry. This prevents ambiguity and ensures that comparisons across agents are meaningful.
AgentRank-UC: The Algorithm for Smart Agent Discovery
Built upon the DOVIS protocol, AgentRank-UC is a dynamic, trust-aware algorithm that combines two crucial factors: usage (how often an agent is chosen) and competence (the quality, cost, safety, and latency of its outcomes) into a unified ranking. It extends the link-analysis approach of PageRank to two evolving graphs: a usage graph reflecting agent selection patterns and a competence graph capturing task outcomes.
The algorithm formulates the ranking process as two coupled fixed-point problems. One calculates a ‘usage rank’ (x), representing an agent’s popularity or influence. The other calculates a ‘competence rank’ (y), reflecting its demonstrated performance. These two ranks are then combined using a balance parameter ‘p’, allowing for a flexible trade-off between popularity and performance. A geometric fusion method is used, which penalizes agents that are popular but incompetent, or excellent but undiscovered.
AgentRank-UC incorporates several key features for robustness and fairness:
- Recency Decay: More recent performance data is weighted more heavily, ensuring rankings are responsive to current behavior.
- Monotonicity: Improving an agent’s observed outcomes will never reduce its rank.
- Cold-Start Fairness: New agents with no history are given a baseline visibility through ‘priors’, preventing them from being invisible.
- Sybil Resistance: The algorithm is designed to resist manipulation attempts, such as colluding agents artificially inflating their usage.
Theoretical Guarantees and Simulation Results
The paper provides strong theoretical guarantees for AgentRank-UC, including the existence, uniqueness, and convergence of its ranking solutions. It also proves the well-posedness and continuity of the ranking, its monotonicity with respect to improved outcomes, cold-start fairness, and stability under various conditions, including resistance to Sybil attacks.
To validate these claims, the researchers conducted extensive simulations. These experiments demonstrated that AgentRank-UC:
- Outperforms usage-only or competence-only baselines, showcasing the advantage of combining both signals.
- Allows the ‘p’ parameter to smoothly interpolate between usage-only and competence-only rankings.
- Adapts quickly to sudden changes in agent performance (shocks), with the ‘half-life’ parameter controlling responsiveness.
- Ensures that improving agents see their ranks increase and that newcomers gain visibility.
- Significantly reduces the rank mass assigned to collusive ‘Sybil cliques’ compared to usage-based methods, confirming its robustness against manipulation.
Also Read:
- ProToM: An AI That Understands and Encourages Helpful Behavior Among Independent Agents
- Defining Digital Rights: A Formal Semantics for ODRL 2.2
The Path Forward for the Agentic Web
DOVIS and AgentRank-UC represent a significant step towards building a functional and trustworthy Agentic Web. By providing a concrete protocol for collecting performance data and a principled algorithm for ranking, this framework lays the groundwork for scalable and reliable agent discovery. Future work includes extending the telemetry schema, refining incentive mechanisms, exploring personalized ranking, and addressing broader socio-technical implications of agent ecosystems.
