Auditable Early Stopping for Agentic Routing: Ledger-Verified Run-Wise Certificates under Local DP
This addresses the challenge of efficient and private agent routing with verifiable stopping decisions, though it appears incremental as it builds on existing routing and privacy techniques.
The paper tackles the problem of determining when a best-first router for tool-use agents can safely stop exploring without missing better options, while maintaining local differential privacy and providing an audit trail. They introduce run-wise certificates that enable tight stopping with deterministic replay and low overhead in experiments.
We address when a best-first router for tool-use agents can stop exploring without missing a better leaf, while preserving local differential privacy (LDP) and leaving an audit trail. We introduce a run-wise certificate that couples each node's key to the same exponential race that realizes leaf perturbations; the usual halting rule (stop when the maximum over $v$ in $F$ of Key$(v) \le B^*$) then certifies the realized run. We give two certified modes on context-indexed prefix DAGs with child partition: (i) Exact (known counts), using lazy offset propagation with winner reuse; and (ii) Surrogate (upper bounds only), which anchors keys to a parent-level surrogate race and allows validator tightening via $κ= \log(N / N_{ub}$). A small compiler enforces the partition property, and an admissible, race-independent M(tau) keeps keys sound. The ledger logs uniforms, counts, and tie handling; privacy follows by post-processing. Experiments on synthetic graphs and a small real pipeline show tight stopping, deterministic replay, and low overhead.