AI summaryⓘ
The authors explore how to measure the value of prompts given to large language models (LLMs) when these models create things like proofs, programs, or designs. They propose a new way to quantify prompt value using a concept called probabilistic Levin–Kolmogorov complexity, which considers how much a prompt helps the model generate a desired output faster or more easily. Their measure shows that each bit of prompt value can make producing the output about twice as efficient, either by increasing the chance of success or reducing computation time. Unlike traditional measures, their approach can be estimated efficiently. They also demonstrate that without a valuable prompt, reproducing the same output typically costs exponentially more computation.
Large Language ModelsPrompt ValueLevin-Kolmogorov ComplexityAlgorithmic Mutual InformationProbabilistic ComplexityComputational EfficiencySampling ProbabilityComputation TimeAlgorithmic Information TheoryToken Cost
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.