論文の概要: Kolmogorov Complexity Bounds for LLM Steganography and a Perplexity-Based Detection Proxy

• arxiv url: http://arxiv.org/abs/2603.21567v1
• Date: Mon, 23 Mar 2026 04:40:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-24 19:11:39.489486
• Title: Kolmogorov Complexity Bounds for LLM Steganography and a Perplexity-Based Detection Proxy
• Title（参考訳）: LLMステガノグラフィーとパープレキシティに基づく検出プロキシのためのコルモゴロフ複雑性境界
• Abstract要約: 大きな言語モデルは、テキストを書き直して隠れペイロードを埋め込むことができる。 このような埋め込みにおける情報理論のコストについて検討する。 色に基づくLCMステガノグラフィースキームによる予備実験は、理論予測を支持する。
• 参考スコア（独自算出の注目度）: 2.0305676256390934
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large language models can rewrite text to embed hidden payloads while preserving surface-level meaning, a capability that opens covert channels between cooperating AI systems and poses challenges for alignment monitoring. We study the information-theoretic cost of such embedding. Our main result is that any steganographic scheme that preserves the semantic load of a covertext~$M_1$ while encoding a payload~$P$ into a stegotext~$M_2$ must satisfy $K(M_2) \geq K(M_1) + K(P) - O(\log n)$, where $K$ denotes Kolmogorov complexity and $n$ is the combined message length. A corollary is that any non-trivial payload forces a strict complexity increase in the stegotext, regardless of how cleverly the encoder distributes the signal. Because Kolmogorov complexity is uncomputable, we ask whether practical proxies can detect this predicted increase. Drawing on the classical correspondence between lossless compression and Kolmogorov complexity, we argue that language-model perplexity occupies an analogous role in the probabilistic regime and propose the Binoculars perplexity-ratio score as one such proxy. Preliminary experiments with a color-based LLM steganographic scheme support the theoretical prediction: a paired $t$-test over 300 samples yields $t = 5.11$, $p < 10^{-6}$.
• Abstract（参考訳）: 大規模な言語モデルは、テキストを書き換えて、表面レベルの意味を保ちながら、隠れペイロードを埋め込むことができる。 このような埋め込みにおける情報理論のコストについて検討する。 我々の主な成果は、ペイロード~$P$をstegotext~$M_2$にエンコードしながら、カバーテキスト~$M_1$のセマンティックな負荷を保存している任意のステガノグラフスキームは、$K(M_2) \geq K(M_1) + K(P) - O(\log n)$を満足しなければならない。 結論として、非自明なペイロードは、エンコーダが信号の分配をいかに巧みに行うかに関わらず、ステゴテキストの厳密な複雑さを増大させる。 コルモゴロフ複雑性は計算不可能であるため、実用的なプロキシがこの予想される増加を検出できるかどうかを問う。 ロスレス圧縮とコルモゴロフ複雑性の古典的対応に基づき、言語モデルパープレクティリティは確率的状態における類似的な役割を担い、そのようなプロキシとして両眼パープレクティリティ比スコアを提案する。 1組の$t$-testが300以上のサンプルから$t = 5.11$, $p < 10^{-6}$が得られる。

関連論文リスト

• Optimal Unambiguous DNFs and Alon-Saks-Seymour [7.0223797053352]
  幅が$O(n)$だが、$0$-certificate complexity $(n2)$ の DNF を構築する。 我々はDNFを通信問題に持ち上げる定数サイズのガジェットで持ち上げる定理を証明した。 このことは、アロン・サクス・シーモア予想の最適反響につながる。
  論文  参考訳（メタデータ） (2026-08-03T17:26:54Z)
• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  我々は,包括的フィードバックに基づいて,与えられたクラスからほぼ最適なポリシーを特定することを目的とする。 ゼロ・ワンの報酬を伴うバンド型マルチクラス分類に動機付けられ、emph$s$-sparse設定に焦点をあてる。 我々は、$s$-sparseの報酬で、誘導モデルクラスは、$s$でスケールするシャープなDEC境界を認め、直接最適なレートを得ることを示す。
  論文  参考訳（メタデータ） (2026-05-28T09:12:20Z)
• Learn from your own latents and not from tokens: A sample-complexity theory [53.5821824211418]
  本研究では,関連するビューやマスキング領域の潜在表現を予測するために訓練されたネットワークについて検討する。 潜在予測は、対数的要因まで、多くのサンプルを$L$で表すことでこれを達成できることを示す。 これは、H-JEPAのような明示的な積み重ねがほとんど冗長であることを示している。
  論文  参考訳（メタデータ） (2026-05-26T22:16:42Z)
• MOOSE-Star: Unlocking Tractable Training for Scientific Discovery by Breaking the Complexity Barrier [56.250921274032066]
  MOOSE-Starは、トラクタブルなトレーニングとスケーラブルな推論を可能にする統合フレームワークである。 TOMATO-Starは、トレーニング用に108717の分解された論文(38,400GPU時間)のデータセットである。
  論文  参考訳（メタデータ） (2026-03-04T06:11:18Z)
• Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learning [19.98996237281175]
  我々は、異種エージェントインタラクションを備えたスケーラブルな協調MARLのための、$texttGMFS$, a $textbfG$raphon $textbfM$ean-$textbfF$ield $textbfS$ubsamplingフレームワークを紹介した。 相互作用強度に応じて$$エージェントをサブサンプリングすることにより、グラノン重み付き平均場を近似し、サンプルの複雑さでポリシーを学ぶ。 我々はロボット協調における数値シミュレーションによる理論の検証を行い、$textttGMFS$がほぼ最適性能を実現することを示す。
  論文  参考訳（メタデータ） (2026-02-18T05:34:07Z)
• Rate optimal learning of equilibria from data [63.14746189846806]
  マルチエージェント・イミテーション・ラーニング(MAIL)における理論的ギャップは,非対話的MAILの限界を特徴づけ,ほぼ最適なサンプル複雑性を持つ最初の対話的アルゴリズムを提示することによって解決する。 インタラクティブな設定では、報酬のない強化学習と対話型MAILを組み合わせたフレームワークを導入し、それをMAIL-WARMというアルゴリズムでインスタンス化する。 我々は,我々の理論を裏付ける数値的な結果を提供し,グリッドワールドのような環境において,行動クローンが学習に失敗する状況を示す。
  論文  参考訳（メタデータ） (2025-10-10T12:28:35Z)
• Probabilistically Tightened Linear Relaxation-based Perturbation Analysis for Neural Network Verification [83.25968588249776]
  本稿では,LiRPAに基づく手法とサンプリングに基づく手法を組み合わせることで,厳密な中間到達性集合を計算できる新しいフレームワークを提案する。 無視可能な計算オーバーヘッドでは、$textttPT-LiRPA$は推定された到達可能な集合を利用し、ニューラルネットワークの出力の上下線形境界を著しく締め付ける。
  論文  参考訳（メタデータ） (2025-07-07T18:45:53Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  我々は$f$-divergence-regularized offline policy learningを分析する。 逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。 これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
  論文  参考訳（メタデータ） (2025-02-09T22:14:45Z)
• Minimax-Optimal Multi-Agent Robust Reinforcement Learning [7.237817437521988]
  我々は、生成モデルへのアクセスを前提として、Q-FTRLアルゴリズム citepli2022minimax を有限水平設定で RMG に拡張する。 提案アルゴリズムは$varepsilon$-robust coarse correlation equilibrium (CCE) を$widetildeOleft(H3Ssum_i=1mA_iminleftH,1/Rright/varepsilon2right) のサンプル複雑性(ログファクタまで)で達成している。
  論文  参考訳（メタデータ） (2024-12-27T16:37:33Z)
• Quantum Error Correction from Complexity in Brownian SYK [0.0]
  量子符号による誤り訂正のロバスト性は、ある絡み合った状態の「相互純度」によって上限づけられる。 符号化複雑性が小さい場合、相互純度は少数の量子ビットの消去に対して$O(1)$であることを示す。 複雑性尺度の階層構造は、相互純度への補助的貢献の塔と関連づけられている。
  論文  参考訳（メタデータ） (2023-01-17T19:00:00Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization [68.8204255655161]
  本稿では,Gorbunov et al (2021) の MARINA 法が,理論的な通信複雑性の観点から最先端の手法とみなすことができることを示す。 MARINAの理論は、古典的な独立圧縮機設定を超えて、潜在的にエミュレートされた圧縮機の理論を支持するものである。
  論文  参考訳（メタデータ） (2021-10-07T09:38:15Z)

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

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