The Value of a Prompt: An LLM-Relative Kolmogorov-Complexity Approach
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 2b times ``easier to obtain'', by multiplying the success probability by 2b, by dividing the required computation by 2b, 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 2b times that of reproducing it with the prompt.
Related
- Maximal Kolmogorov Complexity in a Hamming Ball
- On the Adaptive Covering Complexity of Strings: Unifying Relative and Self-Referential Compression
- Exponential rate of convergence of relative value iteration algorithms for ergodic controls of diffusions
- Exact oracle complexity for function-value suboptimality under weighted initial conditions
- The Complexity of Approximating the Value in Revealing POMDPs with Long-Run Average Objectives
BibTeX
@misc{pass2026value,
title = {{The Value of a Prompt: An LLM-Relative Kolmogorov-Complexity Approach}},
author = {Rafael Pass},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.16438},
eprint = {2608.16438},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.16438},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Value of a Prompt: An LLM-Relative Kolmogorov-Complexity Approach
AU - Rafael Pass
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2608.16438
UR - https://arxiv.org/abs/2608.16438
AB - 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.
ER -