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

Rafael Pass

Source-linked AI summary

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

Rafael Pass

arXiv:2608.16438v1Aug 17, 2026cs.AIcs.CCcs.IT

TL;DR

The paper asks how to measure a prompt’s contribution to an LLM-produced artifact relative to what the model could produce without it. It introduces an LLM-relative prompt-value measure that accounts for artifact likelihood and thinking effort, and shows that conclusions can reverse when thinking is included and vary with rollout quantile and cost convention.

Problem
The paper asks how to measure a prompt’s contribution to an LLM-produced artifact relative to what the same model could produce without it, beyond prompt length.
Method
The paper defines LLM-relative prompt value using probabilistic Levin–Kolmogorov complexity, crediting both artifact-likelihood changes and reductions in required thinking.
Results
The GSM8K illustration shows that non-thinking likelihood comparisons can reverse after incorporating thinking, with value depending on rollout quantile and thinking-cost convention.
Takeaways & Limitations
Prompt usefulness should be evaluated across rollout distributions and with thinking costs included, since a prompt’s value can differ across quantiles and cost conventions.
Takeaways & Limitations
The measure assumes the artifact is specified exogenously, leaving semantic re-randomization and evaluation of surface-form invariance for future work.

Abstract

from arXiv · show

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.

1 Introduction

The paper defines prompt value as LLM-relative algorithmic mutual information, measuring how much an input helps produce a declared artifact while accounting for probability and computation. Its realized-thought Levin complexity is efficiently estimable and gives prompt value a token-reproduction interpretation, subject to careful artifact specification.

Motivation: Prompt value compares how difficult the same LLM finds an artifact with and without an externally supplied input, rather than measuring prompt length.A short hint may be decisive, while a long prompt may be irrelevant or harmful.
LLM-relative complexity: The LLM-relative measure defines value as the reduction in complexity, ValM(p; z) := KM(z) − KM(z | p), when the model’s sampling randomness specifies the program.For the a-priori analog, a score of b means the prompt makes z 2^b times as likely to be output.
Realized-thought Levin complexity: Realized-thought Levin complexity treats thinking as program randomness and charges logarithmically for computation, capturing probability–computation tradeoffs in prompt value.This replaces direct resource-bounded complexity with a probabilistic Levin–Kolmogorov approach relative to the LLM.
Efficient estimation: The measure is efficiently estimable: for a thinking route of length S, its complexity requires evaluating only truncations t = 0, . . . , S.The empirical estimate uses O(ζ−2 log(1/η)) independent rollouts per side.
Reproduction interpretation: A prompt value of b means reproducing the artifact without the prompt typically costs 2^b times more tokens than reproducing it with the prompt.The pKt complexity is the logarithm of the typical token expenditure for reproducing z in context y.
Artifact definition: Prompt value depends substantively on the declared artifact, because random strings copied reliably by a prompt can receive nearly their full description length as value.The paper therefore highlights artifact specification as a modeling limitation and discusses semantic re-randomization as future work.

2 Prompt Value for Non-Thinking LLMs: A Warm-Up

For non-thinking autoregressive LLMs, prompt value is defined as algorithmic mutual information under LLM-relative complexity and admits an efficient likelihood-ratio evaluation. Program-based and a-priori-based formulations coincide up to additive constants, while prompt value may be negative or large for short triggers.

LLM-relative model: An autoregressive LLM generates finite outputs by sampling tokens from next-token distributions until EOS, with fixed background context absorbed into the reference model.The model is assumed to terminate almost surely with finite expected output length.
LLM-relative complexity: LLM-relative programs encode sampling randomness, and a program forcing output x can be evaluated in polynomial time when next-token distributions are polynomial-time computable.Recovery uses one next-token-distribution evaluation per emitted token.
Prompt-value definitions: Prompt value is algorithmic mutual information under LLM-relative complexity, with an a-priori formulation based on the log-measure of sampling randomness producing the output.The a-priori formulation addresses the practical unavailability of exact full next-token distributions through typical LLM APIs.
Algorithmic semantics: Program-based and a-priori-based prompt values coincide up to an additive constant, and the likelihood-ratio form applies when the artifact has positive probability with and without the prompt.Theorem 2.6 states that the reported quantities track algorithmic values within two bits.
Interpretation: Prompt value can be negative, while a one-token trigger can increase the probability of a long output by hundreds of bits.These behaviors distinguish the LLM-relative notion from universal-machine algorithmic information.
Efficient evaluation: 2(n + 1) queries and O(n) arithmetic operations compute prompt value exactly from exact next-token log probabilities, while additive error ρ yields total error at most 2(n + 1)ρ.Approximate log probabilities also suffice to approximate a-priori complexity and prompt value.

3 Thinking and the prompt value

This section models LLM thinking as a two-stage process and defines LLM-relative Levin complexity by combining artifact description length with token-equivalent computation. It then summarizes randomized thinking by quantiles and defines prompt value as algorithmic mutual information, crediting both increased conditional probability and reduced thinking cost.

3.1 LLMs with thinking: An LLM with thinking first samples a thinking route until EOT or EOS, then generates the output conditioned on that route.A rollout is the sampled route before the stopping token; the output stage runs in context y Hy EOT.
3.1 LLMs with thinking: The framework extends to external oracles by treating calls and responses as the realized interaction transcript, requiring restartable rollouts and token-equivalent cost accounting.The formal treatment that follows restricts attention to thinking without external oracle calls.
3.2 Realized-thought Levin complexity: Token-equivalent time is a nondecreasing cost function for thinking tokens, with generated-thought accounting charging prefill, decoding, EOT, and artifact generation.A representative implementation normalizes cpre = 1 and uses cdec = 32.
3.2 Realized-thought Levin complexity: The prefix-prefill convention replays a fixed realized thought before fresh reproduction attempts and yields the per-attempt token-cost interpretation used later.Unlike generated-thought accounting, it treats the realized thinking prefix as already available.
3.2 Realized-thought Levin complexity: Realized-thought Levin complexity minimizes description length plus log running time over truncations of a fixed thinking route.Only t = 0, . . . , S need be evaluated because later truncations do not improve the objective.
3.3 Probabilistic Levin complexity: a median over random realized thoughts: Probabilistic Levin complexity treats thinking as the model’s random tape and summarizes realized-thought complexity using a lower δ-quantile over random rollouts.The typical choice is the median, δ = 1/2.
3.4 The prompt value: Prompt value is algorithmic mutual information with respect to probabilistic Levin complexity, crediting prompts for increasing artifact probability or eliminating thinking costs.Without a hint, the unprompted side may compensate by thinking longer, at a price.
3.5 Canonical targets and verified acceptance: For canonical targets, acceptance complexity equals log2 Cy(Hy), so its median over rollouts is determined by the median τy of Cy(Hy).This connects verified acceptance to the probabilistic complexity framework.

4 Estimation

Section 4 gives a rollout-based protocol for estimating g pKt and prompt value from prompted and unprompted contexts. Theorem 4.1 provides simultaneous quantile guarantees with high probability, while polynomial runtime follows under stated evaluation assumptions.

Guarantee: The estimator is efficiently estimable: polynomially many rollouts produce an empirical median lying, with high probability, between quantiles arbitrarily close to the population median.Applying the guarantee with and without the prompt gives bounds on the prompt-value estimate.
Protocol: The protocol runs k independent complete thinking rollouts for each context y ∈ {p, ϵ}, evaluates every truncation, and records each routewise minimum.The input is artifact z, prompt p, model M, token-equivalent time function κ, quantile level δ, and k rollouts per side.
Protocol: For each context, the estimator bm y k is the empirical lower δ-quantile, namely the ⌈δk⌉-th smallest observed routewise value.The procedure computes this statistic separately for y ∈ {ϵ, p}.
Guarantee: With probability at least 1 −4 exp(−2kζ2), Theorem 4.1 simultaneously bounds the empirical estimates for y ∈ {p, ϵ} within ζ-offset population quantiles.Subtracting the prompted interval from the unprompted interval yields the corresponding prompt-value interval whenever it is defined.
Efficiency: Under polynomial-time next-token sampling, artifact-probability evaluation, and κy,z(t) evaluation and comparison, the protocol runs in time polynomial in k, T, |p|, and |z|.Here, T is the maximum thinking time attained by the model in the protocol on inputs p and ϵ.

5 Prompt value and token-equivalent reproduction cost

The section defines token-equivalent reproduction cost by repeatedly sampling fresh output stages until recovering an artifact, then shows that prompt value equals the typical cost ratio with and without the prompt. It also interprets realized-thought complexity as reproduction cost and discusses alternative implementation-dependent cost conventions.

Reproduction experiment: Reproduction repeatedly runs a fresh output stage after fixing a thinking route, charging κ(|H|) token-equivalent units per attempt until the artifact is recovered.Attempts are independent and succeed with probability Gy(z | H).
Reproduction experiment: TokenCost_y(z; H) is the expected expenditure conditional on route H, while its quantiles are taken over thinking routes generated by random rollouts.The best-prefix reproduction cost minimizes TokenCost_y(z; H≤t) over truncations t.
Complexity interpretation: Realized-thought complexity is identified with reproduction cost for every context, artifact, and rollout thinking string.This follows by comparing the realized-thought complexity definition with the reproduction-cost theorem.
Token-cost characterization: For every δ ∈ (0, 1], g pKt equals the δ-quantile of token-equivalent reproduction costs over random-rollout thinking routes.The quantile medδ is taken over the thinking route Hy generated by a random rollout in context y.
Prompt value: A prompt value of b bits means reproducing the artifact without the prompt typically costs 2^b times more token-equivalent units than with it.Thus exponentiated prompt value is the ratio of typical reproduction costs without and with the prompt.
Cost conventions: The prefix-prefill convention treats the realized thought as already available, while broader functions F can encode distinct costs for generating, replaying, retaining, and reusing thoughts.The Levin objective is one choice among more general combinations of success probability and computation.

6 An Experimental Illustration

The experiment applies LLM-relative prompt value to twelve GSM8K problems, showing that accounting for thinking and quantiles reveals effects missed by probability-only evaluation. Results distinguish computational acceleration from steering and show that correct partial solutions can help, harm, or have distribution-dependent value.

Protocol: The experiment evaluates prompt value on twelve GSM8K problems using 64 independent prompted and unprompted rollouts per problem.The model is DeepSeek-R1-Distill-Qwen-1.5B, with the reference first step supplied inside the open thinking block as partial computation.
Results: Six of twelve reference-step prompts have positive estimated value at all three marked quantiles, δ ∈ {0.2, 0.5, 0.8}.The remaining six range from harmful to negligible or mixed under the default generated-thought convention.
Thinking versus probability: In five of six consistently positive cases, prompting initially lowers gold-artifact probability at t = 0, yet generated-thought value is positive at all three quantiles.This reversal shows why thinking and computation must be incorporated rather than using probability-only prompt value.
Acceleration versus steering: For several cases, generated-thought value is positive while prefix-prefill value is close to zero, consistent with prompts accelerating recoverable computation.A substantial advantage persists under prefix-prefill accounting in other cases, consistent with steering toward states assigning greater artifact probability.
Distribution dependence: Several prompt-value profiles cross zero as δ varies, showing that the same prompt can help one rollout-distribution segment while hurting another.Reporting value as a function of δ exposes heterogeneity that a single median quantile can miss.

7 Related work

The framework builds on classical algorithmic information and Levin’s resource-bounded complexity, adapting probabilistic Kolmogorov complexity to an LLM-relative setting. It also connects prompt scoring to PMI, distinguishes prompt-specific artifact value from template selection, and relates its reproduction comparison to computational-information and simulation perspectives.

Algorithmic information, resource bounds, and compression: The framework draws on Kolmogorov algorithmic information, a-priori complexity, and Levin’s Kt complexity, which combines program length with logarithmic running time.These classical ingredients motivate measuring both description length and computation.
Probabilistic and randomized Kolmogorov complexity: Its probabilistic complexity follows random-tape Kolmogorov-complexity work but replaces the universal Turing machine with an LLM and Kt with its a-priori companion.The realized thought is represented as arising from an underlying uniformly random tape.
PMI and prompt scoring: The no-thinking prompt-value expression log2 PM(z | p)/PM(z) has the exact algebraic form of pointwise mutual information.This connects the framework to PMI’s information-theoretic and computational-linguistics origins.
PMI and prompt scoring: Unlike template-selection methods that average across task instances, the framework measures the value of a particular prompt for producing a particular artifact.Sorensen et al. maximize mutual information between task inputs and outputs over an unlabeled evaluation distribution.
Value of information, costly computation, and AI economics: The prompt-comparison experiment follows simulation ideas from zero-knowledge proofs and the value-of-computational-information framework, whose evaluation uses an explicit utility function.The related framework gives a utility-dependent characterization of valuable information.

8 Conclusions and Future Work

The paper defines an LLM-relative prompt value that captures both artifact-likelihood changes and thinking reductions, with estimable quantiles and an operational reproduction-cost interpretation. It identifies open questions about adaptive conversations and evaluating artifact value beyond production difficulty.

Conclusions: The framework credits both changes in artifact likelihood and reductions in required thinking, estimates value quantiles from sampled routes, and interprets them through reproduction cost.Prompt value combines probability and computation effects rather than measuring likelihood alone.
Conclusions: The GSM8K illustration shows that admitting thinking can reverse a non-thinking likelihood comparison, with value depending on rollout quantile and thinking-cost accounting.The result depends jointly on the selected rollout quantile and the way thinking is priced.
The value of conversation: For realized multi-turn conversations, sequentially valuing each human input conditional on its transcript and summing increments provides ex post accounting of contributions.This accounting excludes the computation used to formulate inputs and the adaptivity of the human strategy.
The value of conversation: Measuring adaptive human contributions under limited access to the policy producing observed messages is an open question.Interactive Turing-machine approaches address the general problem but are less suitable when evaluators observe messages without the adaptive policy.
The value of an artifact: The framework measures prompt value for a declared artifact, while unprompted production difficulty cannot by itself represent artifact value because random strings may be difficult yet substantively worthless.Semantic re-randomization through prompt-independent meaning-preserving rewrites is proposed as future work, potentially aggregated across independent rewrites.

A Proof of Theorem 2.6

The proof establishes dyadic interval bounds and applies them to the probability interval associated with an output. This yields that model-relative complexity differs from surprisal by less than 2 bits, and differences of these discrepancies lie between −2 and 2.

Dyadic interval lemmas: Every positive-length half-open interval in [0,1) contains a dyadic subinterval longer than one quarter of its length.The proof selects the largest dyadic scale below the interval length and constructs a contained interval at that scale.
Dyadic interval lemmas: For any positive-length interval J, the shortest contained dyadic interval has length K(J) between −log2|J| and −log2|J|+2.The lower bound follows from containment, while the upper bound follows from the dyadic subinterval lemma.
Theorem 2.6: Applying the interval bound to Iy(z), whose length is PM(z | y), proves 0 ≤ KM(z | y) + log2 PM(z | y) < 2.The proof identifies KM(z | y) with K(Iy(z)) and uses the interval length q := PM(z | y).
Theorem 2.6: For each context y, KM(z | y) equals −log2 PM(z | y) plus a discrepancy γy(z) in [0, 2).This representation is obtained directly from part (i).
Theorem 2.6: The difference between two such discrepancies lies in (−2, 2), proving the theorem’s second claimed bound.The result follows because subtracting two numbers from [0, 2) produces a value strictly between −2 and 2.