論文の概要: Token Complexity of Certifying Stochastic-Oracle Reliability
- arxiv url: http://arxiv.org/abs/2606.24074v1
- Date: Tue, 23 Jun 2026 02:38:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-24 22:16:48.747244
- Title: Token Complexity of Certifying Stochastic-Oracle Reliability
- Title（参考訳）: 確率的-Oracle信頼性認定におけるトークン複雑性
- Authors: Jie Wang,
- Abstract要約: 本稿では,ある領域におけるオラクルの信頼性を証明するための類似概念を考案する。
認証トークンは最小限のトークンコストであり、制御されたエラー確率を持つ。
本研究では,SPRTに基づく認証SOTMを構築し,オラクルを問合せし,バイナリの正当性スコアを計算し,ログに類似した証拠が決定しきい値を超えた場合に停止する。
- 参考スコア（独自算出の注目度）: 2.345146665577353
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Wang~\cite{Wang2026} introduced the Stochastic-Oracle Turing Machine (SOTM) framework and defined token complexity as the minimum expected cost of interacting with a stochastic oracle needed to attain a specified solution quality for a task. This paper develops an analogous notion for certifying the reliability of a stochastic oracle on a given domain. Certification token complexity is the minimum expected token cost required, with controlled error probability, to distinguish oracles that meet a target reliability level from those that fall below a lower reliability threshold. We construct an SPRT-based certification SOTM that queries the oracle, computes binary correctness scores, and stops when the accumulated log-likelihood evidence crosses a decision threshold. The SOTM halts almost surely, satisfies the desired two-sided error guarantee over the reliability regions to be certified, and yields an explicit upper bound on certification token complexity in terms of the reliability thresholds, the error bound, and the expected per-turn token cost. We then establish a matching information-theoretic lower bound: even with adaptive queries, every error-bounded certification SOTM must incur the same leading-order expected token cost as the SPRT-based construction as the prescribed error bound tends to zero. Together, these bounds characterize the leading-order certification token complexity in the small-error regime.
- Abstract（参考訳）: Wang~\cite{Wang2026} は、Stochastic-Oracle Turing Machine (SOTM) フレームワークを導入し、トークンの複雑さを定義した。
本稿では,ある領域における確率的オラクルの信頼性を証明するための類似概念を開発する。
認証トークンの複雑さは、低い信頼性閾値未満のトークンとターゲットの信頼性レベルを満たすオーラクルを区別するために、制御されたエラー確率を持つ最小のトークンコストである。
本研究では,SPRTに基づく認証SOTMを構築し,オラクルを問合せし,バイナリの正当性スコアを計算し,ログに類似した証拠が決定しきい値を超えた場合に停止する。
SOTMは、ほぼ確実に停止し、認証対象の信頼性領域に対する所望の両側エラー保証を満足させ、信頼性閾値、エラーバウンド、期待されるターン当たりトークンコストの点で、認証トークンの複雑さに明確な上限を与える。
適応的なクエリであっても、全てのエラーバウンド認証SOTMは、所定のエラーバウンダリがゼロになる傾向にあるように、SPRTベースの構築と同じ事前のトークンコストを発生させなければならない。
これらの境界は、スモールエラー体制における上位の認証トークンの複雑さを特徴付けている。
関連論文リスト
- K$α$LOS finds Consensus: A Meta-Algorithm for Evaluating Inter-Annotator Agreement in Complex Vision Tasks [4.297070083645049]
本稿では,「ローカライゼーションファースト」の原理を一般化した統一メタアルゴリズムであるK$LOSを提案する。
合意を査定する前に空間対応を解消することにより,複雑な分類問題を名目上の信頼性に変換する。
論文 参考訳（メタデータ） (2026-03-28T08:54:05Z) - Exploration in the Limit [37.0278529107694]
最小サンプルサイズに対して有効なエラー制御を必要とする緩和された定式化を導入する。
これは、弱い信号、高い所望の重要度、実験後の推論要求を含む多くの実世界の設定と整合する。
我々は、腕の指標よりも常に有効な新しい信頼シーケンスを開発し、それを用いて、フレームワークのための新しいBAIアルゴリズムを設計する。
論文 参考訳（メタデータ） (2025-12-31T19:27:59Z) - Reliable LLM-Based Edge-Cloud-Expert Cascades for Telecom Knowledge Systems [54.916243942641444]
大規模言語モデル(LLM)は、通信などの分野において、自動化の鍵となる存在として浮上している。
本研究では,問合せパイプラインによる意思決定を支援する,エッジクラウドに精通したLLMベースの知識システムについて検討する。
論文 参考訳（メタデータ） (2025-12-23T03:10:09Z) - Unsupervised Conformal Inference: Bootstrapping and Alignment to Control LLM Uncertainty [49.19257648205146]
生成のための教師なし共形推論フレームワークを提案する。
我々のゲートは、分断されたUPPよりも厳密で安定した閾値を提供する。
その結果は、ラベルのない、API互換の、テスト時間フィルタリングのゲートになる。
論文 参考訳（メタデータ） (2025-09-26T23:40:47Z) - COIN: Uncertainty-Guarding Selective Question Answering for Foundation Models with Provable Risk Guarantees [51.5976496056012]
COINは、統計的に有効な閾値を校正し、質問毎に1つの生成された回答をフィルタリングする不確実性保護選択フレームワークである。
COINはキャリブレーションセット上で経験的誤差率を推定し、信頼区間法を適用して真誤差率に高い確率上界を確立する。
リスク管理におけるCOINの堅牢性,許容回答を維持するための強いテストタイムパワー,キャリブレーションデータによる予測効率を実証する。
論文 参考訳（メタデータ） (2025-06-25T07:04:49Z) - TrustLoRA: Low-Rank Adaptation for Failure Detection under Out-of-distribution Data [62.22804234013273]
本稿では,共変量および意味的シフトの両条件下での拒絶による分類を統一し,促進する,単純な故障検出フレームワークを提案する。
キーとなる洞察は、障害固有の信頼性知識を低ランクアダプタで分離し、統合することにより、障害検出能力を効果的かつ柔軟に向上できるということです。
論文 参考訳（メタデータ） (2025-04-20T09:20:55Z) - Quantized and Asynchronous Federated Learning [22.40154714677385]
我々は,通信ボトルネックに対処する新しい手法であるQuantized Federated AsynchronousQALを開発した。
我々はQALが一様クライアントの到着を必要とせずに$mathtcalqr$dic収束を実現することを証明した。
提案手法を標準ベンチマークを用いて検証する。
論文 参考訳（メタデータ） (2024-09-30T21:22:41Z) - Formally Certified Approximate Model Counting [25.20597060311209]
本稿では、その出力近似の品質に関する保証を正式に保証した、近似モデルカウントのための最初の認証フレームワークを提案する。
i)Isabelle/HOL証明アシスタントにおけるアルゴリズムのPAC保証の静的かつ1回限りの公式な証明、(ii)証明証明書を用いた外部CNF-XORソルバに対するApproxMCの呼び出しの動的かつ1回実行による検証。
論文 参考訳（メタデータ） (2024-06-17T11:02:04Z) - Decomposing Uncertainty for Large Language Models through Input Clarification Ensembling [69.83976050879318]
大規模言語モデル(LLM)では、不確実性の原因を特定することが、信頼性、信頼性、解釈可能性を改善するための重要なステップである。
本稿では,LLMのための不確実性分解フレームワークについて述べる。
提案手法は,入力に対する一連の明確化を生成し,それらをLLMに入力し,対応する予測をアンサンブルする。
論文 参考訳（メタデータ） (2023-11-15T05:58:35Z) - Binary Classification with Confidence Difference [100.08818204756093]
本稿では,信頼性差分法 (ConfDiff) という,弱教師付き二項分類問題について考察する。
本稿では,この問題に対処するためのリスク一貫性のあるアプローチを提案し,推定誤差が最適収束率と一致することを示す。
また,整合性や収束率も証明されたオーバーフィッティング問題を緩和するためのリスク補正手法も導入する。
論文 参考訳（メタデータ） (2023-10-09T11:44:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。