論文の概要: Checking Leakage Witnesses versus Certifying Bounded Non-Leakage
- arxiv url: http://arxiv.org/abs/2609.32134v1
- Date: Sat, 26 Sep 2026 01:40:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-07 19:32:41.405031
- Title: Checking Leakage Witnesses versus Certifying Bounded Non-Leakage
- Title（参考訳）: 漏洩点検と非漏洩点検
- Abstract要約: 言語モデル監査はリークがなく、非推論の認定に必要なものは何か?
実行可能リークおよび復号化ルールの下で、宣言されたプロンプトドメイン以上を保証します。
一般的な有界時間評価器では、供給されるリーク実行はチェック可能であり、リーク存在はNP完全である。
厳密な証明は、固定された有理切断毎に$(0,1)$で$coNPPP$-completeである。
- 参考スコア（独自算出の注目度）: 3.278446761115315
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: When a language-model audit finds no leak, what is needed to certify non-leakage? We study guarantees over a declared prompt domain under an executable leakage criterion and decoding rule. For general bounded polynomial-time evaluators, a supplied leaking execution is polynomial-time checkable, while leak existence is \NP-complete and deterministic certification is \coNP-complete. Exact stochastic certification is $\coNP^{\PP}$-complete at every fixed rational cutoff in $(0,1)$. Restricting the computation can change these bounds. For example, certification is in \coNP\ when all randomness is a terminal draw from an efficiently computed finite probability table. Attention models admit polynomial-time certification when local dependency windows of logarithmic length precede one global head, given deterministic decoding, fixed vocabulary, exact rational weighted means, a direct binary affine readout and finite-automaton prompt domains. A construction with two global layers instead makes certification \coNP-complete over template domains, with one head per layer, polynomial width, logarithmic precision and an inverse-polynomial logit margin. Planted-secret experiments measure what finite audits miss relative to complete references. Among 30 secret--model-state pairs that leak under greedy single-prompt execution on their secret's 4,096-prompt domain, uniformly selecting 256 recorded evaluations per pair misses every leak for an expected $41.06\%$ of these pairs. Batched and single-prompt checks disagree on one complete-domain decision among all 48 fine-tuned pairs, while a same-order repeat reproduces every single-prompt output. These results distinguish computational conditions for certification from the coverage and execution conditions needed to interpret a negative audit.
- Abstract（参考訳）: 言語モデル監査がリークを発見できない場合、非推論の認定には何が必要か?
本研究では,実行可能リーク基準と復号規則の下で宣言されたプロンプトドメインの保証について検討する。
一般の有界多項式時間評価器では、供給されるリーク実行は多項式時間チェック可能であり、リーク存在はNP完全であり、決定論的証明はcoNP完全である。
具体的な確率的証明は$\coNP^{\PP}$-complete at every fixed rational cutoff in $(0, 1)$である。
計算の制限は、これらの境界を変更できる。
例えば、すべてのランダム性が効率よく計算された有限確率テーブルからの終端引であるとき、認証は \coNP\ に含まれる。
アテンションモデルは、決定論的復号化、固定語彙、正確な有理重み付け手段、直接二分アフィン読み出し、有限オートマトンプロンプトドメインが与えられたグローバルヘッドに、対数長の局所依存ウィンドウが先行する場合に多項式時間認証を認める。
代わりに、2つのグローバル層による構成は、テンプレートドメイン上での認証を 'coNP-complete' とし、各層毎の1つのヘッド、多項式幅、対数精度、逆多項式対数マージンを持つ。
植物秘密の実験は、完全な参照に対して有限監査が見逃すものを測定する。
シークレットの4,096-プロンプトドメインでgreedyの単一プロンプト実行中にリークする30のシークレット-モデル-ステートペアのうち、ペア毎に256のレコード評価を均一に選択すると、これらのペアの41.06\%が予想されるリークが失われる。
バッチされた単発チェックと単発チェックは、48個の細調整されたペアのうち1つの完全なドメイン決定に一致せず、同じ順序のリピートは全単発出力を再現する。
これらの結果は、負の監査を解釈するために必要なカバレッジと実行条件から、認証のための計算条件を区別する。
関連論文リスト
- On the SoS Certifiability of Log-Concave Distributions [51.56484100374058]
圏 $(Cm)m|v|m - mathbbE_Xsim Plangle X,vranglem$ は、すべての偶数 mge2$ に対する平方の和であり、$C>0$ は普遍定数である。
これにより、コタリとシュタインハルト(arXiv:1711.07465)の定理におけるポアンカレ定数への依存を排除し、対数凹面分布の最適モーメント境界を回復する。
論文 参考訳（メタデータ） (2026-09-24T16:48:02Z) - Certified Inference and Training for Deep Equilibrium Networks: A Continuation Framework with Polynomial Complexity Guarantees [0.0]
我々は、Deep equilibrium Network(DEQ)における推論とトレーニングのための認定された継続フレームワークを開発する。
推論のために、入力ホモトピーは供給された開始根から平衡を選択し、丸いトラッカーが定量的条件下でそれに従う。
訓練のために、プログラム可能な休眠可能な双線形ランクワンチャネルは、出力保存された残留整列修復を提供する。
論文 参考訳（メタデータ） (2026-09-15T01:15:58Z) - A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。
我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
論文 参考訳（メタデータ） (2026-09-09T10:13:43Z) - Memorization Is Not Extraction: Tight Differential-Privacy Bounds and Audit Blind Spots [9.539275654775706]
大規模言語モデルの記憶は、形式的関係が不明な定義の動物園を通じて測定される。
差分プライバシー(DP)は,これらすべてに対して同時にプロキシとして扱われることを示す。
論文 参考訳（メタデータ） (2026-08-27T23:28:08Z) - Training Under Challenge: Executable Certificates and Challenge-Closed Optimality for Neural Networks [20.854288216118423]
平坦なトレーニング曲線は、ニューラルネットワークがグローバルな最適値に達したか、ローカルに閉じ込められたか、表現に制限されたか、あるいはトレーナーにミスマッチしているかを明らかにしない。
このフレームワークでは、事前宣言されたアーキテクチャ検証手順が、同じ認定クラスで完全な代替品を構築し、同じ目的を再評価する。
逆フロンティアを証明する: カバー範囲がなければ、一階のReLUトレーナーは、非球面点に収束しながら、無限に多くの正確な条件付き頭部に到達できる。
論文 参考訳（メタデータ） (2026-08-12T23:37:57Z) - Sub-Quadratic Bisimulation Metrics via Approximate Nearest Neighbors: Coverage-Augmented Guarantees and Computable Two-Sided Certificates [1.2891210250935148]
我々は,境界遷移をサポートするMPPに対して,証明書を搬送するサブクワッドラティックな方法を提案する。
近似アレスト近傍指数は、正確に制限された演算子によって更新されたペアを選択する。
ローカルインデックスの品質だけでは、グローバルエラーを制御できない。
論文 参考訳（メタデータ） (2026-08-07T03:32:40Z) - AI-Assisted Discovery of Convex Relaxations via Dual Agents [56.60366723277675]
すべての許容関数に対して下界が成り立ち、より強い境界を与える凸緩和から従うことを示す。
理論は各エージェントを検証し、反例を検索し、報告されたすべての境界はインターバルにおける明示的な二重実現可能な点によって認証される。
論文 参考訳（メタデータ） (2026-06-30T06:10:25Z) - Correction and Corruption: A Two-Rate View of Error Flow in LLM Protocols [51.56484100374058]
そこで本研究では,単一プロトコルステップを正確なマッチングタスクで監査するためのペアアウトカム計測インタフェースを提案する。
各インスタンスについて、インターフェースはベースラインの正当性ビットと後ステップの正当性ビットを記録する。
これらのレートは精度の変化を予測し、種、混合物、パイプライン間でテスト可能な再利用可能な経験的インターフェースを定義する。
論文 参考訳（メタデータ） (2026-04-20T13:25:40Z) - Reinforcement Learning with Verifiable yet Noisy Rewards under Imperfect Verifiers [90.50039419576807]
RLVR(Reinforcement Learning with Verifiable Rewards)は、人為的なラベル付けを避けるために、自動検証に対するポリシーを訓練する。
認証ハッキングの脆弱性を軽減するため、多くのRLVRシステムはトレーニング中にバイナリ$0,1$の報酬を破棄する。
この選択にはコストがかかる:textitfalse negatives(正しい回答、FNを拒絶)とtextitfalse positives(間違った回答、FPを受け入れる)を導入する。
論文 参考訳（メタデータ） (2025-10-01T13:56:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。