0 cumulative citations
View corpus contextA formal measure of prompt value: an LLM-relative Levin–Kolmogorov complexity quantifies how much prompts reduce the difficulty of producing an artifact — b bits of value mean the prompt makes the artifact 2^b times more likely or saves a 2^b factor in typical token-costs — and the measure is computable from model token probabilities and rollouts.
The Value of a Prompt: An LLM-Relative Kolmogorov-Complexity Approach
The paper defines prompt value as LLM-relative algorithmic mutual information—using a realized-thought Levin–Kolmogorov complexity pKt—showing that b bits of prompt value make an artifact 2^b times easier (or typically 2^b times more token-costly to reproduce without the prompt) and gives an estimable procedure built from model next-token probabilities and rollouts.
Citation observations
Cumulative provider counts captured on specific dates; providers are never combined.
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.
Summary
Main Finding
The paper defines a principled, LLM-relative measure of the value of a prompt: the bits of algorithmic mutual information that a prompt supplies about a target artifact, where the reference machine is the LLM (including its sampling procedure) and thinking is treated as randomized computation. Concretely, for LLMs without thinking the value reduces to the log-ratio of prompted vs unprompted output probabilities (so b bits ⇒ 2^b multiplicative change in probability). For LLMs with thinking the paper introduces a probabilistic Levin–Kolmogorov complexity (pKt) that (i) treats realized internal “thinking” rollouts as the program randomness, (ii) charges for thinking via a token-equivalent cost κ(t) entered logarithmically (Levin-style), and (iii) summarizes across rollouts by a quantile (median by default). Prompt value is the difference in pKt with and without the prompt. Economically, a prompt value of b bits means reproducing the artifact without the prompt typically costs ~2^b more tokens than with it.
Key Points
- Conceptual move: replace the universal Turing machine in classical Kolmogorov/Levin complexity with the actual LLM sampling process, so program = prefix of the LLM’s random tape.
- Non-thinking LLMs:
- Define KM(x | y) as the length of the shortest binary prefix (dyadic interval) that forces the LLM to output x given context y.
- An a-priori analogue is eKM(x | y) = −log2 PM(x | y); prompt value = eKM(z) − eKM(z | p) = log2 PM(z | p)/PM(z), computable from next-token probabilities (sum of log-ratios).
- Thinking LLMs:
- Model thinking as a two-stage generation: a variable-length thinking string H (ends with EOT) followed by an output stage.
- For a realized partial-thought Hy_≤t, the description cost of z is eKM(z | y Hy_≤t EOT).
- Define realized-thought Levin complexity: Ktκ,M(z | y; Hy) = min_t { eKM(z | y Hy_≤t EOT) + log2 κ(t) }.
- Summarize across rollouts by the median (or any δ-quantile) to get pKtκ,M(z | y) := median_H [ Ktκ,M(z | y; H) ].
- Prompt value: Valκ,M(p; z) = pKtκ,M(z) − pKtκ,M(z | p).
- Interpretation: b bits of prompt value ⇒ z is 2^b times easier to obtain (multiplicative in success probability) or ~2^b times cheaper in token-cost to reproduce; the measure captures both probability increases and computation (thinking) savings.
- Estimability and computation:
- For a given rollout Hy of length S, only t ∈ {0,...,S} need be evaluated to compute Kt for that rollout; each evaluation uses next-token probabilities along z and prefixes of Hy.
- With O(ζ^−2 log(1/η)) independent rollouts one obtains a high-probability estimate of the δ-quantile (hence of pKt) to additive precision in quantile index.
- KM and the non-thinking definition are computable (polynomial-time) whenever the model’s next-token distributions are polynomial-time computable.
- Practical caveats:
- The measure prices the declared artifact z; trivial or semantically inert padding in z can concentrate value into prompts (so artifact choice / canonicalization matters).
- Remedies include using canonical representations, verifier-defined canonical outputs, or semantic re-randomization (e.g., prompt-independent rewrites) to prevent gaming.
- Relation to prior work: The non-thinking a-priori value equals the numerator used in Xie et al. (2026) “author-contribution” score; this paper provides algorithmic-information foundations and extends to charge for thinking.
Data & Methods
- The work is primarily theoretical and formal:
- Formal definitions for autoregressive LLMs, binary programs (dyadic intervals corresponding to prefixes of the model’s randomness), KM, eKM, Levin-style combination of description length and log computation time, and pKt (median/quantile over realized thinking).
- Proofs connecting KM and eKM (they differ by < 2), and showing that pKt equals the logarithm of the typical token expenditure required to reproduce z (giving the token-cost interpretation).
- Estimation protocol:
- Sample independent thinking rollouts (with and without prompt).
- For each rollout, compute realized Kt by evaluating eKM at each thinking prefix truncation and adding log2 κ(t); minimize over prefixes.
- Aggregate realized-Kt values to obtain an empirical δ-quantile (median by default).
- Complexity of estimation: each realized-Kt evaluation requires computing next-token probabilities along z for each truncated thought prefix; number of rollouts scales as O(ζ^−2 log(1/η)) to control quantile estimation error with probability ≥ 1 − η.
- Empirical illustration:
- The paper reports a small experiment on GSM8K (grade-school math problems with reference stepwise solutions); implementation and plots were produced using ChatGPT and Claude under the author’s direction. (The excerpt does not report quantitative experimental details or outcomes.)
Implications for AI Economics
- Pricing and markets for prompts:
- Gives a principled, model-relative unit (bits) for prompt value that translates to multiplicative token-cost savings (2^b). This enables contracts, payments, or marketplaces where compensation for a prompt can be linked to measurable reductions in reproduction cost or increases in generation probability.
- Attribution and compensation:
- A formal metric for human (or tool) contribution to LLM outputs supports attribution, royalty schemes, or micro-payments for “hints” that materially reduce model effort.
- Platform design and incentives:
- Platforms can measure prompt value to reward concise, high-impact prompts, or to allocate compute budgets where prompts are less effective.
- Charging for thinking (κ) and accounting for computation savings aligns incentives: creators will supply prompts that genuinely reduce model work rather than surface text that merely reproduces or encodes artifacts.
- Procurement and governance:
- Organizations contracting LLMs can compare human-in-the-loop strategies by the token-cost reductions obtained, enabling cost-benefit analysis of human effort vs. model compute.
- Risks and strategic behavior:
- Dependence on the declared artifact z creates incentives to choose representations that concentrate value in prompts (e.g., embedding semantically inert randomness). Mitigations (canonicalizers, verifiers, re-randomization) must be institutionalized to avoid gaming.
- Model-specificity: measure is relative to a particular deployed model M and its sampling; prompt markets and pricing will therefore depend on model versions and configuration.
- Operational feasibility:
- Because the measure is efficiently estimable given access to next-token probabilities and rollouts, it is implementable in practice for deployed autoregressive models (subject to API access and compute).
- Research and policy directions:
- Empirical validation of the measure across tasks and LLM families; study of canonicalization procedures and semantic re-randomization; exploration of optimal κ(t) specification (token-equivalence function) and its normative interpretation; integration into billing, auditing, or IP frameworks.
Limitations to keep in mind: dependence on the declared artifact and on the chosen κ(t) and quantile δ; requirement of access to model internals or full next-token distributions for exact computation; possible sensitivity to rare but decisive thinking rollouts unless one selects an appropriate quantile (median recommended).
Assessment
Paper Typetheoretical
Evidence Strengthn/a — This is primarily a formal/theoretical paper that develops new definitions, identities, and estimators rather than making empirical causal claims; therefore conventional empirical evidence-strength ratings do not apply.
Methods Rigorhigh — The paper provides a clear formal model of LLMs, precise definitions (LLM-relative K, a-priori complexity, realized-thought Levin Kt, pKt), algebraic identities linking the measure to token-probability ratios and token-cost medians, and an estimation protocol with sampling bounds; it acknowledges and discusses key modeling choices (artifact canonicalization, quantile selection) and computational assumptions (access to next-token probabilities). Limitations remain in some practical assumptions (full access to distributions, choice of κ, and real-world implementation details).
SamplePrimarily a theoretical development; includes a small empirical illustration using the GSM8K benchmark (grade-school math word problems with step-by-step reference solutions). The formal work assumes a fixed autoregressive LLM M with accessible next-token distributions and allows sampled 'thinking' rollouts.
Themeshuman_ai_collab productivity
GeneralizabilityRelies on strong access assumptions: requires model next-token probabilities and the ability to sample thinking rollouts (may be infeasible for closed or rate-limited APIs)., Depends on an externally chosen token-equivalent cost function κ(t); economic interpretation varies with κ., Measure is defined relative to a declared artifact z; results sensitive to how artifacts are canonicalized (padding or semantically inert additions can distort value)., Empirical validation is limited (small experiment on GSM8K); practical behavior on larger real-world tasks, multi-stage human-AI workflows, or other modalities is untested., Assumes a fixed deployed model M — does not directly address distributional shifts, model updates, or strategic behavior by model providers.
Claims (9)
| Claim | Direction | Outcome | Confidence & Evidence | Details |
|---|---|---|---|---|
| For a non-thinking LLM, the a-priori prompt-value measure equals the log base-2 likelihood ratio: fVal_M(p; z) = log2(P_M(z | p) / P_M(z)). Other | positive | Change in the LLM's probability of generating artifact z caused by prompt p |
Reading fidelity
high
Study strength
high
|
2^b times as likely
|
| For a non-thinking LLM, the program-based LLM-relative mutual information and its a-priori analogue differ by less than 2 bits. Other | null_result | Difference between program-based and a-priori LLM-relative prompt-value measures |
Reading fidelity
high
Study strength
high
|
< 2 bits
|
| For an LLM with thinking, prompt value credits a prompt both for increasing the conditional probability of the artifact after realized thinking and for reducing the amount of thinking required to obtain it. Organizational Efficiency | positive | Prompt-induced reduction in artifact-generation difficulty, combining output probability and thinking-token-equivalent cost |
Reading fidelity
high
Study strength
medium
|
not reported
|
| The proposed probabilistic a-priori Levin–Kolmogorov complexity is efficiently estimable using sampled thinking rollouts and model next-token probabilities. Other | positive | Computational estimability and statistical estimation error of the proposed prompt-value measure |
Reading fidelity
high
Study strength
medium
|
O(ζ^-2 log(1/η)) independent rollouts
|
| The exponentiated probabilistic Levin complexity equals the median token cost of reproducing an artifact through repeated independent sampling at the best prefix of a realized thinking route. Organizational Efficiency | positive | Typical token expenditure required to reproduce artifact z |
Reading fidelity
high
Study strength
high
|
not reported
|
| Under the paper's reproduction experiment, a prompt value of b bits means that reproducing the artifact without the prompt typically costs 2^b times more tokens than reproducing it with the prompt. Organizational Efficiency | positive | Ratio of typical unprompted to prompted token cost for reproducing artifact z |
Reading fidelity
high
Study strength
high
|
2^b times more tokens
|
| Using a median or other quantile over thinking rollouts makes the measure insensitive to rare, unusually successful thinking paths and provides the stated reproduction-cost interpretation. Decision Quality | positive | Robustness and interpretability of the prompt-value statistic across random thinking rollouts |
Reading fidelity
high
Study strength
medium
|
not reported
|
| The measured value of a prompt depends substantively on how the artifact is defined; semantically inert random padding can receive nearly the full description-length value even when it contributes nothing to the artifact's substantive content. Ai Safety And Ethics | mixed | Sensitivity of measured prompt value to artifact representation and irrelevant padding |
Reading fidelity
high
Study strength
medium
|
nearly the full description length of the random suffix
|
| For a uniformly random n-token artifact string, the unprompted a-priori complexity is at least n log2 |Σ| − O(log n) bits with high probability, while a prompt that reliably supplies the string can make its conditional complexity small. Other | positive | Prompt-induced reduction in description complexity for a random artifact string |
Reading fidelity
high
Study strength
medium
|
at least n log2 |Σ| − O(log n) bits
|