提出可审计的早停机制，确保工具调用代理在保护隐私前提下不遗漏更优路径。
Auditable Early Stopping for Agentic Routing: Ledger-Verified Run-Wise Certificates under Local DP
- 通过节点密钥与扰动竞争耦合，实现运行级证书验证
- 在真实小规模流水线中实现紧致早停和确定性重放
- 适合需隐私保护与可审计性的智能代理系统
我们解决最佳优先路由在工具使用代理中何时可停止探索而不会遗漏更优叶节点的问题，同时保持局部差分隐私（LDP）并生成可审计记录。提出一种运行级证书，将每个节点的关键值与实现叶节点扰动的指数竞争绑定；常规停止规则（当 $F$ 中所有 $v$ 的 Key$(v) \ leq B^*$ 时停止）可认证实际执行过程。在上下文索引前缀有向无环图与子节点划分结构上，提供两种已认证模式：(i) 精确模式（已知计数），采用懒惰偏移传播与胜者复用；(ii) 代理模式（仅上界），将密钥锚定于父级代理竞争，支持通过 $κ= \log(N / N_{ub})$ 提升验证器精度。小型编译器强制划分属性，且存在无需依赖竞争的适配函数 M(tau) 保证密钥正确性。账本记录均匀随机数、计数及平局处理；隐私性由后处理保证。合成图与小型真实流水线实验表明，该方法实现紧致早停、确定性重放且开销低。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。