🤖 AI

The Value of a Prompt: An LLM-Relative Kolmogorov-Complexity Approach

This paper proposes an efficiently estimable metric for quantifying the economic value of prompts given to Large Language Models by defining it as algorithmic mutual information based on a novel LLM-relative probabilistic Levin–Kolmogorov complexity ( $pKt$ ), which captures how much a prompt reduces the computational effort or increases the probability of generating a target artifact.

Original authors: Rafael Pass

Published 2026-08-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Rafael Pass

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the modern economy of artificial intelligence, a new kind of currency is emerging, one that is not measured in dollars or tokens, but in the quality of the questions we ask. Large language models have become powerful engines capable of generating proofs, writing code, or designing new materials, yet they do not operate in a vacuum. They require a spark from a human, a prompt, to begin their work. For years, the industry has focused almost exclusively on the output: how good is the story, how correct is the code, how elegant is the design. But as these machines become more capable, the central economic question is shifting. It is no longer just about what the machine can produce, but about what value remains in the human input that guided it. If a person provides a hint, a critique, or a partial solution, how much did that specific input actually help the machine reach its goal?

This is a difficult problem because a short, clever hint can be worth more than a long, rambling instruction, and a wrong hint can be worse than no hint at all. Simply counting the words or characters in a prompt fails to capture its true worth. To solve this, researchers have turned to a field of mathematics called algorithmic information theory, which traditionally measures the complexity of an object by asking how much information is needed to describe it. The researchers in this study asked a new question: what if we measure the complexity not against a perfect, theoretical computer, but against the specific artificial intelligence model doing the work? They realized that to truly value a human's contribution, we must account for the machine's own "thinking" process. Modern models often pause to generate a chain of reasoning before giving an answer, and a good prompt might save the machine from having to think as long, or it might steer that thinking in a more productive direction.

The researchers developed a new way to measure this value by treating the prompt as a tool that reduces the effort required for the machine to succeed. They imagined a scenario where a machine tries to recreate a specific result, like a mathematical proof, first on its own and then with a human's hint. They measured the difference not just by how much more likely the machine was to get the right answer, but by how much "thinking time" it saved. In their framework, the machine's internal reasoning steps are treated like a random path it must walk. A valuable prompt is one that makes the correct path much shorter or much more obvious, effectively reducing the number of steps the machine needs to take to find the solution. They defined this value in terms of a "token cost," which is a way of counting the computational effort the machine expends. If a prompt makes the machine's job twice as easy, it is worth a certain amount of value; if it makes the job a thousand times easier, the value is much higher.

To test their ideas, the team ran a series of experiments using a standard set of grade-school math problems. They asked a large language model to solve these problems, sometimes giving it the first step of the solution as a hint and sometimes letting it start from scratch. They found that simply looking at the probability of the model getting the right answer was not enough. In several cases, supplying the correct first step initially made the final answer seem less likely at the very beginning, because the model had not yet engaged its reasoning process. However, once the model was allowed to "think" and generate its own reasoning steps, the hint proved to be incredibly valuable. It guided the model's thinking process so effectively that it reached the correct answer much faster and with far less effort than it would have on its own. This showed that a prompt's true value often lies in how it shapes the machine's internal reasoning, not just in the immediate words it produces.

The study also revealed that the value of a prompt is not a single, fixed number. It depends on the specific path the machine takes. Sometimes a hint helps the machine in most situations, but in rare cases, it might lead it down a dead end. The researchers found that by looking at the "median" outcome—the typical result rather than the best or worst case—they could get a reliable measure of value. They discovered that for some problems, a correct hint from a human was actually harmful or useless for the specific model they were testing, suggesting that what looks like a good idea to a person might be redundant or confusing for an artificial intelligence. This highlights that the value of human input is deeply tied to the specific machine it is talking to and the way that machine processes information.

Ultimately, this work provides a rigorous way to quantify the contribution of a human in an age where machines do the heavy lifting. It moves beyond the idea that the machine is the sole creator and recognizes that the human's role is to provide the efficient path through the vast space of possibilities. By measuring how much a prompt saves in terms of the machine's thinking time and effort, we can begin to understand the true economic worth of human guidance. The researchers showed that this value can be calculated and estimated, offering a new lens through which to view the partnership between human and machine. As artificial intelligence becomes more integrated into our lives, understanding the value of the prompts we give it will be essential for knowing where the real work is being done and who deserves credit for the results.

Technical Summary: The Value of a Prompt: An LLM-Relative Kolmogorov-Complexity Approach

1. Problem Statement

As Large Language Models (LLMs) become central to creating valuable artifacts (proofs, code, designs, hypotheses), a critical economic question arises: How do we measure the value of the human input (the prompt) provided to the model?

Traditional metrics, such as token count, fail to capture value because a short hint can be decisive while a long prompt may be irrelevant. A robust measure must satisfy two criteria:

Comparative Difficulty: It must compare the difficulty of producing an artifact $z$ with and without the prompt $p$ .
Computational Trade-off: It must account for the fact that a model without a prompt can compensate by "thinking" longer. Therefore, the measure must charge for this additional computation, crediting the prompt not just for increasing the probability of the output, but for reducing the computational effort required to find it.

Existing algorithmic information theory (Kolmogorov complexity) is uncomputable and ignores computational time. Resource-bounded variants are often hard to compute. Furthermore, classical mutual information does not naturally handle the "thinking" process (Chain of Thought) inherent in modern LLMs.

2. Methodology

The paper proposes an LLM-relative notion of probabilistic Levin–Kolmogorov complexity, denoted as $\tilde{pKt}$ , to define prompt value. The approach evolves from non-thinking models to models with explicit thinking stages.

2.1 Non-Thinking LLMs (Warm-up)

For autoregressive models that generate output directly without a separate thinking stage:

LLM-Relative Complexity: The universal Turing machine is replaced by the specific LLM $M$ . A "program" is defined as a binary string representing the sampling randomness (a dyadic interval) that forces the model to output a specific string $z$ .
A-Priori Complexity: To make this efficiently computable, the author uses the log-probability of the output: $\tilde{K}_M(z|y) = -\log_2 P_M(z|y)$ .
Prompt Value: Defined as the difference in a-priori complexity: $\tilde{Val}_M(p; z) = \tilde{K}_M(z) - \tilde{K}_M(z|p)$ . This is equivalent to the log-likelihood ratio (Pointwise Mutual Information), indicating how many times more likely $z$ is with prompt $p$ than without.

2.2 LLMs with Thinking

Modern LLMs often generate a "thinking route" $H$ (Chain of Thought) before emitting the final artifact $z$ . This introduces two challenges:

Randomness of Thought: The thinking route $H$ is stochastic. Simply averaging over all possible thoughts can be skewed by rare, highly successful paths.
Computation Savings: A good prompt might not just increase probability at a fixed effort; it might eliminate the need for long thinking sequences.

The Proposed Solution:

Realized-Thought Levin Complexity: For a fixed realized thinking route $H$ , the complexity of $z$ is defined by minimizing the sum of the description length (log-probability of $z$ given $H$ ) and the logarithm of the cost of the thinking prefix.
$\tilde{Kt}^\kappa_M(z | y; H) := \min_{t} \left( -\log_2 P_M(z | y H_{\le t} \text{EOT}) + \log_2 \kappa(t) \right)$
Here, $\kappa(t)$ is a token-equivalent cost function for $t$ thinking tokens. The minimization over $t$ allows the model to stop thinking early if the probability of success is high enough to offset the cost.
Probabilistic Complexity ( $\tilde{pKt}$ ): Since $H$ is random, the author defines the complexity as the median (or $\delta$ -quantile) of the realized-thought complexities over many sampling rollouts. This avoids sensitivity to rare, "lucky" thinking paths.
$\tilde{pKt}^\kappa_{M,\delta}(z | y) := \text{med}_\delta \left[ \tilde{Kt}^\kappa_M(z | y; H_y) \right]$
Prompt Value: The final value is the difference in these probabilistic complexities:
$\tilde{Val}^\kappa_{M,\delta}(p; z) = \tilde{pKt}^\kappa_{M,\delta}(z) - \tilde{pKt}^\kappa_{M,\delta}(z | p)$

3. Key Contributions

LLM-Relative Complexity Framework: The paper adapts Kolmogorov and Levin complexity to the specific architecture of LLMs, treating the model itself as the reference machine and its sampling randomness as the program tape.
Handling "Thinking": It introduces a novel method to value prompts for models with Chain of Thought by treating the realized thought as the random tape and minimizing a Levin-style objective (description length + log time) over the thinking prefix.
Efficient Estimability: Unlike classical resource-bounded Kolmogorov complexity, the proposed measure is efficiently estimable. The paper provides a protocol to estimate the median complexity using a polynomial number of rollouts, with high-probability bounds on the error.
Economic Interpretation (Token Cost): The author proves a fundamental theorem: $2^{\tilde{pKt}}$ $2^{\tilde{p K t}}$ corresponds exactly to the median token cost of reproducing the artifact in a specific experiment.
- If a prompt has a value of $b$ bits, it means reproducing the artifact without the prompt typically costs $2^b$ times more in token-equivalent units than reproducing it with the prompt.
Distinction from Prior Work: The paper clarifies that while the "no-thinking" component aligns with Pointwise Mutual Information (PMI) and recent "human contribution" scores (e.g., Xie et al.), the explicit handling of computation and thinking is the novel contribution.

4. Experimental Results

The author evaluated the measure on 12 problems from the GSM8K dataset (grade-school math word problems) using the DeepSeek-R1-Distill-Qwen-1.5B model.

Thinking Reverses Verdicts: In several cases, supplying a correct first step (the prompt) initially made the final answer less probable at $t=0$ (without thinking). However, once the thinking process was incorporated, the prompt value became positive. This demonstrates that a non-thinking, probability-only metric can yield the opposite qualitative verdict compared to the proposed thinking-aware metric.
Acceleration vs. Steering: The results distinguished between prompts that merely "accelerate" computation (allowing the model to reach a good state faster, which is valuable under "generated-thought" costs but less so under "prefix-prefill" costs) and prompts that "steer" the model to a fundamentally better state (valuable under both cost conventions).
Correctness $\neq$ Value: A correct partial solution from a human reference was not always valuable. In some cases, it was redundant or induced unfavorable continuations, resulting in negative or negligible prompt value.
Distribution Dependence: The value of a prompt varied significantly across different quantiles ( $\delta$ ) of the rollout distribution, indicating that a prompt might help some "thought trajectories" while hindering others.

5. Significance and Claims

The paper claims to provide a theoretically grounded, efficiently estimable, and economically interpretable measure of prompt value.

Theoretical Foundation: It bridges algorithmic information theory and LLM economics, offering a formal definition of "value" that accounts for both likelihood and computational effort.
Operational Meaning: By linking the complexity measure to the median token cost of reproduction, the paper argues that prompt value is not an abstract metric but a concrete economic saving.
Modesty: The author explicitly states that the measure prices the description of the declared artifact. If the artifact definition is flawed (e.g., includes random noise), the value measure will reflect that. They also note that the framework currently values a single prompt in a fixed context and does not yet fully capture the value of adaptive, multi-turn conversational strategies or the cost of formulating the human input itself.

In summary, the paper posits that in an era of abundant AI generation, the value of human contribution lies in the reduction of the model's computational burden to achieve a specific outcome, and this reduction can be rigorously quantified using LLM-relative Levin complexity.