{"ID":2872831,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.10550","arxiv_id":"2509.10550","title":"Auditable Early Stopping for Agentic Routing: Ledger-Verified Run-Wise Certificates under Local DP","abstract":"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.","short_abstract":"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 usua...","url_abs":"https://arxiv.org/abs/2509.10550","url_pdf":"https://arxiv.org/pdf/2509.10550v2","authors":"[\"Shivam Akhauri\"]","published":"2025-09-09T01:25:09Z","proceeding":"cs.CR","tasks":"[\"cs.CR\",\"cs.LG\"]","methods":"[]","has_code":false}