論文の概要: Auditable Early Stopping for Agentic Routing: Ledger-Verified Run-Wise Certificates under Local DP

• arxiv url: http://arxiv.org/abs/2509.10550v1
• Date: Tue, 09 Sep 2025 01:25:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-16 17:26:22.657831
• Title: Auditable Early Stopping for Agentic Routing: Ledger-Verified Run-Wise Certificates under Local DP
• Title（参考訳）: エージェントルーティングの早期停止:ローカルDPにおけるLedger-Verified Run-Wise Certificates
• Authors: Shivam Akhauri,
• Abstract要約: 本研究では,子どもが葉を分割する文脈インデックス付き接頭辞DAGについて,パーターブ・アンド・マップ(PaM)の早期発見証明書を検索した。 経路スコアと鍵の打ち分けは,オフセット伝搬により遅延的に実現した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In production tool-use agents (e.g., retrieval $\to$ summarization $\to$ calculator), routers must know when to stop exploring while preserving local DP and leaving an auditable trail. We present run-wise early-stopping certificates for perturb-and-MAP (PaM) best-first search on context-indexed prefix DAGs whose children partition the leaves. We couple realized path scores and pruning keys to a single exponential race realized lazily via offset propagation. With exact leaf counts $N(v)$, lazy reuse at winners and independent residuals yield an Exact mode with a sound halting rule based on Key$(v) = M_tau(v) - \log t(v)$, where $t(v)$ is the minimum arrival time among leaves under $v$. With only upper bounds $N_{ub} \ge N$, a Surrogate mode uses a parent-anchored surrogate race without winner reuse; because $-\log \hat t \ge -\log t$, the frontier invariant holds and stopping remains sound. We add a compiler from shared-node DAGs to prefix DAGs, local finiteness checks, a SuffixCountDP routine for exact counts with safe downgrades, a validator-side tightening term $\kappa = \log(N/N_{ub})$, and an auditable ledger/validator that replays runs deterministically. We also give an absolute LogSumExp tail bound, an acyclicity certificate, and a fallback PRF-per-leaf scheme (NoCert) whose work matches a realized-score best-first baseline up to a small per-node overhead. Finally, we integrate a price/latency/$(\epsilon, \delta)$-aware multi-LLM controller and DP-trained LoRA adapters chosen at runtime; these choices do not affect the two-mode frontier invariants. We report Mac/commodity-hardware reproducible results, a small real tool-use pipeline, and validator-checked audit trails, with code and ledgers provided.
• Abstract（参考訳）: 実運用用ツール利用エージェント(例えば、検索$\to$ summarization$\to$ calculator)では、ルータはローカルDPを保存し、監査可能なトレイルを残しながら、いつ探索をやめるべきかを知る必要がある。 本研究では,子どもが葉を分割する文脈インデックス付き接頭辞DAGについて,パーターブ・アンド・マップ(PaM)の早期発見証明書を検索した。 経路スコアと鍵の打ち分けは,オフセット伝搬により遅延的に実現した。 正確なリーフ数を$N(v)$とすると、勝者と独立残余に対する遅延再利用は、Key$(v) = M_tau(v) - \log t(v)$ に基づいた音の停止規則を持つExactモードが得られる。 上界の$N_{ub} \ge N$のみの場合、サロゲートモードは親アンコールされたサロゲートレースを勝者の再利用なしに使用する。 我々は共有ノードDAGからプレフィックスDAGへのコンパイラ、ローカル有限性チェック、安全なダウングレードを持つ正確なカウントのためのSuffixCountDPルーチン、バリデータ側締め付け項$\kappa = \log(N/N_{ub})$、リプレイする監査可能な台帳/バリケータを追加します。 また、絶対的なLogSumExpテールバウンド、非サイクリック証明書、およびノード毎の小さなオーバーヘッドまで実現された最優先のベースラインに適合するフォールバックPRF-per-leafスキーム(NoCert)も提供します。 最後に、価格/遅延/$(\epsilon, \delta)$-aware multi-LLMコントローラとDPで訓練されたLoRAアダプタを実行時に統合する。 我々は、Mac/commodity-hardware再現可能な結果、小さなツール使用パイプライン、バリデータチェックによる監査パス、コードと台帳の提供を報告した。

関連論文リスト

• $\mathrm{TIME}[t]\subseteq \mathrm{SPACE}[O(\sqrt{t})]$ via Tree Height Compression [0.0]
  Algebraic Replay Engineは、ポインターレスDSSとインデックスなしストリーミングとともに、一定の大きさのフィールド上の一定度マップを持つ。 S(b)=O(b+t/b)$は、残余乗法的ポリログ因子を持たない$O(sqrtt)$空間を与える。
  論文  参考訳（メタデータ） (2025-08-20T16:27:53Z)
• Restarted Bayesian Online Change-point Detection for Non-Stationary Markov Decision Processes [12.229154524476405]
  我々は、Restarted Bayesian Online Change-Point Detectionアルゴリズム(R-BOCPD)の変種を導入する。 多項分布から標本化された状態遷移カーネルを用いたMPP用UCRL2アルゴリズムの改良版を提案する。 我々は,R-BOCPD-UCRL2が$Oleft(D O sqrtA T K_T logleft (fracTdelta right) + fracK_Tdeltaminlimits_ell の好意的な後悔境界を享受していることを示す。
  論文  参考訳（メタデータ） (2023-04-01T05:26:41Z)
• On the Unlikelihood of D-Separation [69.62839677485087]
  解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。 PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。 UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
  論文  参考訳（メタデータ） (2023-03-10T00:11:18Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation [99.59319332864129]
  最近提案された2つの線形MDP仮定で対数的後悔が達成可能であることを示す。 我々の知る限り、これらは線型関数近似を持つRLに対する最初の対数的後悔境界である。
  論文  参考訳（メタデータ） (2020-11-23T17:25:00Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。