論文の概要: The Value of a Prompt: An LLM-Relative Kolmogorov-Complexity Approach

• arxiv url: http://arxiv.org/abs/2608.16438v1
• Date: Mon, 17 Aug 2026 11:35:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-18 19:59:03.665211
• Title: The Value of a Prompt: An LLM-Relative Kolmogorov-Complexity Approach
• Title（参考訳）: プロンプトの価値:LLM-Relative Kolmogorov-complexity Approach
• Abstract要約: 我々は$pKt$に対するアルゴリズム的相互情報としてプロンプト値を定義する。 アーティファクト$z$に対して$b$ビットの値を持つプロンプトは、$z$2b$を入手しやすくする。 アルゴリズム的相互情報の古典的概念とは対照的に,我々の手法は効率的に推定可能である。
• 参考スコア（独自算出の注目度）: 4.551855760807635
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In a world where valuable artifacts are increasingly created, completed, or processed by LLMs, the central economic question is not only what the LLM can produce, but what \emph{value} remains in the inputs (i.e., the prompts) we provide to it. Given a prompt, hint, critique, problem statement, or partial solution that helps an LLM produce an artifact $z$---a proof, program, design, or scientific hypothesis---how should we measure the value of that input? Intuitively, an input is valuable when it makes the target artifact easier for the model to generate: either by increasing its sampling probability, or by reducing the thinking time needed to find it. We propose a computational Levin--Kolmogorov complexity approach to this problem, by appropriately replacing the universal Turing machine in the classical definitions by the LLM itself. Concretely, we introduce an LLM-relative notion of \emph{probabilistic Levin--Kolmogorov complexity} $pKt$---treating the model's thinking as the random tape of the program, and charging logarithmically for it in Levin's manner---and define prompt value as algorithmic mutual information with respect to $pKt$. This captures the intuition above: a prompt having $b$ bits of value for an artifact $z$ makes $z$ $2^b$ times ``easier to obtain'', by multiplying the success probability by $2^b$, by dividing the required computation by $2^b$, or by any corresponding tradeoff between probability and computation. In contrast to the classical notion of algorithmic mutual information, ours is efficiently estimable. We additionally show that, under a natural reproduction experiment, a prompt value of \(b\) bits means that reproducing \(z\) without the prompt has median token cost \(2^b\) times that of reproducing it with the prompt.
• Abstract（参考訳）: 価値ある人工物が LLM によって作成、完成、または処理される世界において、中心的な経済問題は LLM が生成できるものだけでなく、入力(すなわち、それを提供するプロンプト)に残されるもの(emph{value})である。 プロンプト、ヒント、批判、問題ステートメント、あるいはLCMが成果物を作るのを助ける部分的なソリューションが与えられた。 直感的には、入力は、対象のアーティファクトを、サンプリング確率を増加させたり、それを見つけるのに必要な思考時間を短縮したりすることで、モデルが生成しやすくするときに有用である。 古典的定義における普遍的チューリングマシンを LLM 自身で適切に置き換えることで,この問題に対する計算的レヴィン-コルモゴロフ複雑性アプローチを提案する。 具体的には、プログラムのランダムテープとしてモデルの思考を扱い、それをレヴィンのやり方で対数的に課金し、即時値を$pKt$に関するアルゴリズム的相互情報として定義する。 a prompt has $b$ bits of value for a artifact $z$ makes $z$ $2^b$ times ``easier to obtained'', by multiplying the success probability by $2^b$, by any associated tradeoff between probability and compute。 アルゴリズム的相互情報の古典的概念とは対照的に,我々の手法は効率的に推定可能である。 また, 自然再生実験において, \(b\) ビットのプロンプト値が, プロンプトを使わずに生成した \(z\) が, プロンプトで再生した2^b\) 倍の中央値のトークンコストを持つことを示す。

関連論文リスト

• Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method [1.2799130177714182]
  量子近似カウントの2重決定版について検討する。 オラクルが$xin0,1N$にアクセスすると、$|x|=M$と$|x|=M+$を区別する。 乗法逆法を用いて、$left(maxleftsqrt(N-M)(M+)/,sqrtN/rightright)$を証明する。
  論文  参考訳（メタデータ） (2026-09-09T07:01:11Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• HSR-Enhanced Sparse Attention Acceleration [19.776342074253435]
  大規模言語モデル(LLM)における注意計算を高速化する新しい手法を提案する。 我々は,従来のSoftmaxアテンションとReLUアテンションの両方において,アテンションメカニズム内の固有空間を利用する。 提案手法は,Softmaxの注意を確実に無視できる誤差を導入するのみである。
  論文  参考訳（メタデータ） (2024-10-14T05:18:02Z)
• Can Large Language Models Play Games? A Case Study of A Self-Play Approach [61.15761840203145]
  LLM(Large Language Models)は、インターネットからの広範なデータを利用して、幅広い事前知識を格納する。 Monte-Carlo Tree Search (MCTS)は、信頼性の高い意思決定ソリューションを提供する検索アルゴリズムである。 この研究は、ターンベースのゼロサムゲームを効率的に解決するために、MCTSセルフプレイでLLMを活性化させる革新的なアプローチを導入している。
  論文  参考訳（メタデータ） (2024-03-08T19:16:29Z)
• Replicability in Reinforcement Learning [46.89386344741442]
  生成モデルにアクセス可能なディスカウント型MDPの基本設定に焦点をあてる。 ImpagliazzoらにインスパイアされたRLアルゴリズムは、高い確率で2回の実行後に全く同じポリシーを出力した場合、複製可能である。
  論文  参考訳（メタデータ） (2023-05-31T05:16:23Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• A Spectral Approach to Item Response Theory [6.5268245109828005]
  本稿では,Raschモデルに対する新しい項目推定アルゴリズムを提案する。 我々のアルゴリズムの中核は、アイテム-イムグラフ上で定義されたマルコフ連鎖の定常分布の計算である。 合成および実生活データセットの実験により、我々のアルゴリズムは、文献でよく使われている手法とスケーラブルで正確で競合することを示した。
  論文  参考訳（メタデータ） (2022-10-09T18:57:08Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes [91.38793800392108]
  本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。 上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。 我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
  論文  参考訳（メタデータ） (2020-12-15T18:56:46Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)

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

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