mlsanityData to 7 Oct 2026

Auditable Early Stopping for Agentic Routing: Ledger-Verified Run-Wise Certificates under Local DP

arXiv 2509.10550 ↗First posted 9 Sep 2025cs.CR cs.LGcited by 0

On the map: LLM agents and tool use → Agent threats, guardrails and governance

Abstract (arXiv)

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) ≤ 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 kappa = log(N / Nub). 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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Placed in Agent threats, guardrails and governance, one of 16 directions in LLM agents and tool use. Builds on 14 of its 34 references that are in the map. First posted on arXiv 9 Sep 2025.

Builds on

14 of 34 references.

References · 14

  1. 2021LoRA: Low-Rank Adaptation of Large Language Modelscited by 14,084
  2. 2022ReAct: Synergizing Reasoning and Acting in Language Modelscited by 8,355
  3. 2023Toolformer: Language Models Can Teach Themselves to Use Toolscited by 4,072
  4. 2023Gorilla: Large Language Model Connected with Massive APIscited by 1,302
  5. 2021Differentially Private Fine-tuning of Language Modelscited by 392
  6. 2019Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacementcited by 205
  7. 2014A* Samplingcited by 150
  8. 2020The Discrete Gaussian for Differential Privacycited by 134
  9. 2021Optimal Accounting of Differential Privacy via Characteristic Functioncited by 83
  10. 2021A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learningcited by 82
  11. 2023Differentially Private Low-Rank Adaptation of Large Language Model Using Federated Learningcited by 41
  12. 2024Fine-Tuning Large Language Models with User-Level Differential Privacycited by 28
2 more
  1. 2024Mind the Privacy Unit! User-Level Differential Privacy for Language Model Fine-Tuningcited by 21
  2. 2022Faster Privacy Accounting via Evolving Discretizationcited by 14

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026RouteGuard: Certifying Routing Gain in LLM Multi-Agent Systems When Complementarity Is Not Enough
  2. 2026CAGE: Certified Authorization under Typed-Return Uncertainty for Tool-Using Agents
  3. 2025Zero-Knowledge Audit for Internet of Agents: Privacy-Preserving Communication Verification with Model Context Protocol
  4. 2026Agent Flight Recorder: Tamper-Evident Audit Trails with On-Chain Anchoring for Long-Horizon Tool-Using Agents
  5. 2026Goal-Autopilot: A Verifiable Anti-Fabrication Firewall for Unattended Long-Horizon Agents
  6. 2026Structurally Close, Temporally Distant: Measuring Security Exposure in Long-Horizon LLM Agents
  7. 2026VST: Verifiable Structured Transport for Auditable Agent-to-Agent Alpha Discovery
  8. 2026Agentic Witnessing: Pragmatic and Scalable TEE-Enabled Privacy-Preserving Auditing