論文の概要: 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ステガノグラフィーとパープレキシティに基づく検出プロキシのためのコルモゴロフ複雑性境界
• Authors: Andrii Shportko,
• 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}$が得られる。

関連論文リスト

• 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)

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

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