Paper deep dive
The Value of a Prompt: An LLM-Relative Kolmogorov-Complexity Approach
Rafael Pass
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 8/23/2026, 2:08:52 AM
Summary
The paper introduces a computational framework for measuring the value of prompts provided to Large Language Models (LLMs) using an LLM-relative probabilistic Levin-Kolmogorov complexity (pKt). The authors define prompt value as algorithmic mutual information with respect to pKt, which quantifies how much a prompt reduces the computational cost (token expenditure) or increases the probability of generating a specific artifact. The approach accounts for 'thinking' processes in LLMs by treating thinking tokens as random tape and charging logarithmically for computation time. The paper demonstrates that this measure is efficiently estimable and provides an economic interpretation where prompt value corresponds to the ratio of median token costs with and without the prompt.
Entities (9)
Relation Signals (7)
Rafael Pass → authored → The Value of a Prompt: An LLM-Relative Kolmogorov-Complexity Approach
confidence 100% · Title and author line in the paper header.
pKt → defines → Prompt Value
confidence 95% · define prompt value as algorithmic mutual information with respect to pKt.
pKt → accountsfor → thinking process
confidence 90% · treating the model's thinking as the random tape of the program, and charging logarithmically for it in Levin's manner
Prompt Value → measures → computational savings
confidence 90% · a prompt having b bits of value... makes z 2^b times 'easier to obtain'... by dividing the required computation by 2^b
GSM8K → usedin → Experiment
confidence 90% · Section 6 reports a small experiment on GSM8K
ChatGPT → usedby → Rafael Pass
confidence 85% · large language models, principally ChatGPT and Claude, were extensively used in drafting, revising, and editing this manuscript
LLM → uses → thinking process
confidence 85% · We model such an LLM as a two-stage autoregressive process... the model first generates a finite string Hy of thinking tokens
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2608.16438v1
- Canonical: https://arxiv.org/abs/2608.16438v1
Trouble viewing inline? Open PDF directly →
Full Text
93,739 characters extracted from source content.
Expand or collapse full text
The Value of a Prompt: An LLM-Relative Kolmogorov-Complexity Approach Rafael Pass Note: Rafael Pass is supported in part by AFOSR Award FA9550-24-1-0267, ISF Award 2338/23 and ERC Advanced Grant KolmoCrypt - 101142322. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government, the AFOSR, the European Union or the European Research Council Executive Agency. Affiliation: Cornell Tech, Technion, TAU August 17, 2026 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 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 probabilistic Levin–Kolmogorov complexity pKtpKt—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 pKtpKt. This captures the intuition above: a prompt having b bits of value for an artifact z makes z 2b2^b times “easier to obtain”, by multiplying the success probability by 2b2^b, by dividing the required computation by 2b2^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 2b2^b times that of reproducing it with the prompt. 1 Introduction Suppose a large language model (LLM) produces a valuable artifact, represented for our purposes by a string z—for example, a proof of a mathematical theorem, a computer program, a design, a drug, or a scientific hypothesis. The LLM operates in some fixed deployment context and receives an additional input, referred to as the prompt p.11 1 We use “prompt” broadly to mean any type of input supplied externally, whether by a human or another resource. For instance, if an LLM were directly connected to a human brain, the resulting brain signals could be viewed as the “prompt.” The prompt might be a hint, critique, example, or partial solution. A natural question arises: How much value did the prompt contribute to the final artifact, relative to what the same LLM could have produced without it? This is increasingly an economic question. As LLM capabilities become abundant, the value of human contributions may lie in choosing the right input to provide to the model. Simply measuring the length of that input—for example, by its token count—does not capture its value: a short hint can be decisive, whereas a long prompt can be irrelevant or even harmful. Rather, a useful measure should (1) compare the difficulty of producing the artifact with and without the input, and (2) allow the model without the additional input to compensate by thinking longer, while charging it for that additional thinking. In this respect, we follow the value-of-computation perspective of Halpern and Pass [13, 14] and the simulation paradigm underlying zero-knowledge proofs, which asks what can be efficiently generated without access to the information in question [12]. Said plainly, we seek a notion of value that measures how much the prompt “helped” the LLM produce the artifact, while taking computation into account. In this work, we introduce such a measure of prompt value. 1.1 From Kolmogorov complexity to an LLM-relative measure Classical algorithmic information theory provides a natural starting point. Fix a universal Turing machine U, and let KU(x)K_U(x) denote the Kolmogorov complexity of x [31, 18, 3]: the length of the shortest program π that generates x (i.e., U(π)=xU(π)=x). Define KU(x∣y)K_U(x y) analogously, with y supplied as auxiliary input (in other words, the shortest program that generates x given y). Following Kolmogorov, the algorithmic information [36, 21] that p provides about z is IU(p:z):=KU(z)−KU(z∣p).I_U(p:z)\;:=\;K_U(z)-K_U(z p). (1) Thus, IU(p:z)I_U(p:z) is the number of bits saved in describing z once p is available, making it a natural measure of the value of the prompt p for z. Two difficulties prevent direct use of this measure. First, Kolmogorov complexity is uncomputable. Second, it ignores the computational complexity of the program π, which makes it unsuitable for capturing “computational gains”. The standard resource-bounded response to the second difficulty is time-bounded Kolmogorov complexity [18, 17, 15, 30]: For a time limit T, KUT(z∣p):=minπ:U(π,p)=zTU(π,p)≤T|π|.K^T_U(z p)\;:=\; _ subarraycπ:\;U(π,p)=z\\ T_U(π,p)≤ T subarray|π|. (2) Levin’s KtKt complexity [20] combines description length and execution time into one quantity: KtU(z∣p):=minπ:U(π,p)=z|π|+log2TU(π,p).Kt_U(z p)\;:=\; _π:\;U(π,p)=z \|π|+ _2T_U(π,p) \. (3) Unfortunately, resource bounds do not make these notions easy to compute (although computable): Allender et al. give worst-case hardness results for resource-bounded Kolmogorov complexity [1]. Liu and Pass connect average-case hardness of time-bounded Kolmogorov complexity to one-way functions, including (conditional) equivalences on samplable distributions [22, 23, 24]. These results indicate that resource-bounding alone does not make the notion efficiently computable. Dealing with Non-thinking LLMs: LLM-Relative Kolmogorov Complexity As a warm-up, we first provide a notion of prompt value for LLMs without thinking. By this we mean an autoregressive model that, given a context y, directly generates its output one token at a time: each token is sampled from a distribution determined by y and the previously generated tokens, and generation ends when the model emits a distinguished end-of-sequence token (EOS)(EOS). In other words, there is no separate “thinking stage” preceding the output. Our first step is to make the above-mentioned algorithmic-mutual-information approach efficiently computable by fixing the reference machine to be the actual LLM production process. When the question is what an input contributed to this process, the process itself is the natural reference machine. Given a fixed LLM, a “program” is a specification of the model’s sampling randomness, which fully determines its output; we specify the randomness in binary as a real number in [0,1)[0,1), and the length of a program is the length of the shortest prefix of this number that forces the output. Write KM(x∣y)K_M(x y) for the length of the shortest such program forcing x in context (i.e., given prompt) y, and define ValM(p,z):=KM(z)−KM(z∣p)Val_M(p;z):=K_M(z)-K_M(z p) as the LLM-relative mutual information. Alongside it, we use an LLM-relative notion of a-priori complexity, the classical companion of program length in algorithmic information theory [36, 21]: K~M(x∣y):=−log2PM(x∣y) K_M(x y):=- _2P_M(x y), where PM(x∣y)P_M(x y) denotes the probability that M outputs x given the prompt y, and define the value Val~M(p,z):=K~M(z)−K~M(z∣p) Val_M(p;z):= K_M(z)- K_M(z p) as the a-priori LLM-relative analog of mutual information. As we show in Section 2, 0≤KM(x∣y)−K~M(x∣y)<20≤ K_M(x y)- K_M(x y)<2; hence the a-priori analog closely approximates the program-based notion of LLM-relative mutual information: |ValM(p,z)−Val~M(p,z)|<2 |Val_M(p;z)- Val_M(p;z) |<2. Moreover, by definition, Val~M(p,z)=log2PM(z∣p)PM(z), Val_M(p;z)= _2 P_M(z p)P_M(z), which can be computed directly by summing the base-two log-ratios of the model’s prompted and unprompted next-token probabilities along z. In essence, Val~M(p,z) Val_M(p;z) has exactly the algebraic form of pointwise mutual information [10, 6]; this recovers a non-normalized variant of the “author-contribution” score of [35]. Thus, a score of b means that the prompt makes z 2b2^b times as likely to be output by the LLM as without the additional prompt. For these reasons, we take the a-priori notion as the basis for our notion of prompt value. The problem with thinking. Valuing prompts for an LLM with thinking is more complicated. We model such an LLM as a two-stage autoregressive process. Given a context y, the model first generates a finite string HyH^y of thinking tokens and then emits a distinguished end-of-thinking token EOTEOT, which marks the transition to the output stage. The model then generates its output and terminates it with the end-of-sequence token EOSEOS. For any finite thinking string H, write Gy(z∣H):=PM(z∣yHEOT)G_y(z H):=P_M(z y\,H\,EOT) for the probability that the output stage emits the artifact z followed by EOSEOS. Thinking changes the valuation problem in two ways. First, the direct calculation above no longer yields the overall probability that M produces z, because this probability must also average over the potentially long, random thinking route H: in context y, it is Hy[Gy(z∣Hy)].E_H^y\! [G_y(z H^y) ]. Although this yields a natural notion of prompt value, it is not the approach we consider here: it averages together realized thoughts and can be substantially influenced by rare, unusually successful routes.22 2 The marginal probability can be estimated without waiting for a rollout to emit z, by averaging the conditional probabilities Gy(z∣Hy)G_y(z H^y) over sampled thoughts. Each conditional probability can itself be computed directly from the model’s next-token probabilities along z. Nevertheless, obtaining a reliable multiplicative estimate when the marginal is extremely small may require a correspondingly large number of samples. We instead view the realized thinking as the random tape of the program, measure the conditional difficulty of producing z relative to that tape, and then take the median over the model’s thinking randomness. The resulting quantity captures the difficulty on a typical realized thought and is insensitive to the one thought in a billion that happens to stumble upon the decisive idea. A second issue is that comparing the two contexts at a common truncation index t misses the principal way many inputs help: a good hint does not merely make the answer more probable at fixed effort, but may remove or lessen the need to think. To capture this computation saving, the prompted and unprompted processes must therefore be allowed to use different amounts of thinking—in particular, the unprompted baseline may need to think longer—and each must be charged for the computation it uses. The resulting comparison credits a prompt both when it increases the conditional probability of the output and when it reduces the computation needed to obtain it. Our approach: realized-thought Levin complexity. Roughly speaking, we solve the first problem by viewing thinking not as part of the description of the program, but rather as randomness for the program; that is, we consider a probabilistic notion of Kolmogorov complexity in the spirit of [11], though defined somewhat differently. We solve the second one by considering Levin’s notion of KtKt-complexity [20] (and thus “charging” logarithmically for the computation): in essence, we consider an LLM-relative notion of probabilistic (a-priori) Levin-Kolmogorov complexity pKtpKt, and our measure is simply algorithmic mutual information defined w.r.t. it. Concretely, fix the artifact z—in the motivating scenario, the output of a prompted run. Sample a thinking rollout: let the model think freely until it emits a stop token, writing HyH^y for the realized thinking and H≤tyH^y_≤ t for the first t tokens; think of this as sampling randomness for the program. Next, note that summing the negative base-two logarithms of the model’s next-token probabilities along z, including the probability of termination after z, computes exactly the a-priori complexity K~M(z∣yH≤tyEOT)=−log2PM(z∣yH≤tyEOT) K_M (z y\,H^y_≤ t\,EOT )=- _2P_M (z y\,H^y_≤ t\,EOT ) of the artifact for a model that has already thought H≤tyH^y_≤ t (and recall that a-priori complexity corresponds to our notion of program length). We next charge thinking through an externally specified “token-equivalent” cost function κ(t)κ(t) and define the realized-thought Levin complexity of z in context y along the thinking route HyH^y, Kt~Mκ(z∣y;Hy):=mint∈ℕ0K~M(z∣yH≤tyEOT)⏟“description length”+log2κ(t)⏟log running time, Kt^κ_M (z y;\,H^y )\;:=\; _t _0 \ K_M (z y\,H^y_≤ t\,EOT )_``description length"\;+\; _2κ(t)_log running time \, (4) (i.e., we employ Levin’s combination of description length and log running time, in analogy with the Levin’s KtKt notion, Kt(x)=mintKt(x)+log2tKt(x)= _t\K^t(x)+ _2t\). The above quantity is random through the sampled rollout HyH^y. We summarize this randomness by taking the median over the model’s thinking, defining an LLM-relative notion of probabilistic (a-priori) Levin–Kolmogorov complexity: pKt~Mκ(z∣y):=med[Kt~Mκ(z∣y;Hy)]. pKt^κ_M (z y )\;:=\; [\, Kt^κ_M (z y;\,H^y )\, ]. (5) The prompt value is then simply algorithmic mutual information with respect to it, Val~Mκ(p,z):=pKt~Mκ(z)−pKt~Mκ(z∣p), Val^κ_M(p;z)\;:=\; pKt^κ_M(z)\;-\; pKt^κ_M(z p), (6) in exact analogy with the LLM-relative mutual information Val~M=K~M(z)−K~M(z∣p) Val_M= K_M(z)- K_M(z p) of the no-thinking case, and with pKt~ pKt in place of K~ K as the notion of description length. Note that a prompt is now credited both when it (1) makes the artifact more probable given the thinking realized and (2) when it eliminates thinking that the unprompted side must otherwise pay for; and the unprompted side can compensate for a missing hint by thinking longer, at a price. As we show, this measure is efficiently estimable in the following sense. For any sampled thinking route, the realized-thought Levin complexity is computed exactly from the model’s next-token probabilities at each truncation of the realized thinking: although the minimization in (17) ranges over all of ℕ0N_0, only t=0,…,St=0,…,S need be evaluated for a thinking route of length S, since every t>St>S is weakly dominated by t=St=S. Moreover, with O(ζ−2log(1/η))O(ζ^-2 (1/η)) independent rollouts per side, the empirical δ-quantile lies, with probability at least 1−η1-η, between the (δ−ζ)(δ-ζ)- and (δ+ζ)(δ+ζ)-quantiles of the true distribution. Applying this guarantee with and without the prompt yields corresponding bounds on the prompt-value estimate. An economic interpretation of prompt value: token-cost savings. We finally consider an economic notion of token cost for generating an artifact z given a prompt y. We first define the cost of reproducing an artifact z given an input y and a realized thinking route H by the expenditure of an experiment: sample repeated independent attempts, conditional on y and H, until z is reproduced. Each attempt is assigned the declared thinking-token-equivalent charge κ(|H|)κ(|H|), so the expected cost of the repeated sampling process is TokenCosty(z,H):=[Nκ(|H|)]TokenCost_y(z;H):=E[Nκ(|H|)]. Writing TokenCosty∗(z,Hy):=min0≤t≤|Hy|TokenCosty(z,H≤ty)TokenCost^*_y(z;H^y):= _0≤ t≤|H^y|TokenCost_y(z;H^y_≤ t) for the cost at the best prefix of the realized thinking, we show that 2pKt~Mκ(z∣y)=med[TokenCosty∗(z,Hy)];2^\, pKt^κ_M(z y)\;=\; [\,TokenCost^*_y(z;H^y)\, ]; that is, the pKtpKt-complexity notion is the logarithm of the typical token expenditure of reproducing z in context y. Prompt value is then, by definition, a ratio of such costs, 2Val~Mκ(p,z)=med[TokenCostϵ∗(z,Hϵ)]med[TokenCostp∗(z,Hp)],2^\, Val^κ_M(p;z)\;=\; [TokenCost^*_ε(z;H^ε) ] [TokenCost^*_p(z;H^p) ], so a prompt value of b means that reproducing the artifact without the prompt typically costs 2b2^b times more tokens than with it. Medians, δ-quantiles, and why not expectations? The median reports the typical realization, insensitive to the one thought in a billion that stumbles onto the decisive idea; thus, the median is arguably a more relevant statistic than expectation in our context. Using a quantile rather than an expectation is also important for the cost interpretation: quantiles commute with exponentiation, whereas expectations do not. Nothing hinges on the median in particular: every δ-quantile yields a complexity notion satisfying the same cost identity, and we more generally define pKt~M,δκ pKt^κ_M,δ by replacing the median by the δ-quantile of the distribution. What counts as the “artifact”. Our measure is defined relative to a declared artifact z, and the choice of what counts as the artifact is a substantive modeling decision. Otherwise, it is easy to manufacture artifacts and prompts having large prompt value. For instance, let z be a string of n tokens drawn uniformly at random, and let p supply z in a form that causes the model to reproduce it reliably. For a typical such string, K~M(z) K_M(z) is at least nlog2|Σ|−O(logn)n _2| |-O( n) bits with high probability, whereas K~M(z∣p) K_M(z p) is small. The prompt therefore receives nearly the full description length of the target even though the target is merely a random string. The same construction can be attached to a genuine artifact. Suppose that an LLM, without a prompt, produces a proof z⋆z of a conjecture of Erdős. Let r be a random string and declare the scored artifact to be z=z⋆∥rz=z \|r, with r embedded as semantically inert text so that z remains a valid presentation of the proof. Now supply r in a form that causes the model to reproduce it reliably. Without the prompt, the random suffix typically contributes roughly |r|log2|Σ||r| _2| | bits of description length; once it is supplied, reproducing it is cheap. The prompt therefore collects nearly the full value of the suffix even though it played no role in producing the mathematical content z⋆z . The measure is nevertheless behaving as intended: it prices the description of the declared artifact. The burden therefore falls on the declaration of what constitutes that artifact. When possible, a simple remedy is to take z to be a canonical representation of the produced object rather than the particular string the model happened to emit. When a verifier for the “artifact class” is available, this is immediate: let z be the verifier’s canonical verdict, and require the object itself to appear in the realized thinking. Semantically inert padding then cannot appear in z; see Section 3.5. When no suitable canonicalization or verifier is available, one possible approach is semantic re-randomization: apply a declared, prompt-independent rewriting procedure (e.g., use an LLM) that preserves the artifact’s semantic content while varying its surface form, and evaluate the prompt after this transformation. The hope is that semantically inert padding will not survive such rewriting, so that a prompt supplying only noise receives no value, whereas a prompt supplying a substantive idea remains useful across different renderings. We leave the formalization and evaluation of semantic re-randomization for future work; throughout this paper, we simply assume that the artifact is specified exogenously. Relation to prior work by Xie et al. A recent work by Xie et al. [35] introduces a measure of human contribution in AI-assisted content generation and evaluates it experimentally. Our no-thinking value is an unnormalized version of their score (they additionally divide by the output’s self-information); our treatment thus provides an algorithmic-information theoretic foundation of that numerator. We emphasize that their score contains no explicit charge for thinking or computation; dealing with thinking is our main contribution. Paper outline. Section 2 develops our no-thinking notion and provides its algorithmic foundation. Section 3 introduces the thinking process, rollouts, realized-thought Levin complexity, our probabilistic Levin complexity notion pKt~Mκ pKt^κ_M and our final notion of prompt value. Section 4 gives the estimation protocol and its guarantee. Section 5 supplies the economics, defining the cost of reproducing an artifact by the expenditure of an experiment and showing that 2pKt~2 pKt is exactly the typical such cost, so that the prompt value is a ratio of typical costs. Section 6 reports a small experiment on GSM8K, a benchmark dataset of grade-school mathematics word problems with step-by-step reference solutions, and Section 7 discusses related work. Use of AI. While the ideas are my own, large language models, principally ChatGPT and Claude, were extensively used in drafting, revising, and editing this manuscript (including in expanding proof sketches into complete proofs). Claude and ChatGPT also implemented the experiments and produced the plots (based on my directions). I take full responsibility for any errors and oversights. 2 Prompt Value for Non-Thinking LLMs: A Warm-Up This section develops a notion of prompt value for non-thinking LLMs; it serves as a warm-up for our actual notion that deals also with LLMs with thinking. We start by defining a notion of a (non-thinking) LLM: Definition 2.1 (Autoregressive LLM). Fix a finite token alphabet Σ and a distinguished end-of-sequence token EOS∉ΣEOS∉ , and let Γ:=Σ∪EOS := ∪\EOS\. An autoregressive LLM M specifies, for every context c∈Σ∗c∈ ^*, a probability distribution PM(⋅∣c)∈Δ(Γ)P_M(· c)∈ ( ) over the next token. A finite output is a string x=(x1,…,xn)∈Σ∗x=(x_1,…,x_n)∈ ^*, generated by emitting x1,…,xnx_1,…,x_n and then EOSEOS; its probability in context y∈Σ∗y∈ ^* is PM(x∣y):=(∏i=1nPM(xi∣yx<i))PM(EOS∣yx),x<i:=(x1,…,xi−1).P_M(x y):= ( _i=1^nP_M(x_i yx_<i) )P_M(EOS yx), x_<i:=(x_1,…,x_i-1). (7) We assume proper termination: for every context y, repeated next-token sampling emits EOSEOS almost surely, with a finite expected number of tokens before termination. Any fixed background context—chat template, task preamble, or deployment-specific instruction—may be absorbed into the definition of the reference model M. Write ϵε for the empty additional prompt and abbreviate PM(⋅):=PM(⋅∣ϵ)P_M(·):=P_M(· ε). Thus PM(⋅)P_M(·) denotes the model’s output distribution under the fixed background with no additional prompt, whereas PM(⋅∣p)P_M(· p) denotes the distribution of the same model under the same background after receiving the additional prompt p. We use the same convention for all complexity quantities below: an omitted conditioning context means conditioning on ϵε. An LLM-relative notion of Kolmogorov complexity. In ordinary Kolmogorov complexity, a universal Turing machine is the machine that interprets and executes programs. Here we instead use the LLM (together with its sampling procedure) as the underlying machine. A program specifies the randomness used to sample from the LLM and thereby determines its execution. We represent the complete sampling randomness by a real number ω∈[0,1)ω∈[0,1), written in binary; a finite binary program specifies an initial segment of that binary expansion, and hence a dyadic subinterval of possible values of ω. Definition 2.2 (Output intervals and binary programs). Fix a total order on Γ . For an output x∈Σ∗x∈ ^* write x¯:=xEOS x:=x\,EOS, and order outputs by the lexicographic order on the strings x¯ x induced by the order on Γ . The output interval of x in context y is Iy(x):=[FM(x∣y),FM(x∣y)+PM(x∣y)),FM(x∣y):=∑x′:x¯′<x¯PM(x′∣y).I_y(x):= [\,F_M(x y),\;F_M(x y)+P_M(x y)\, ), F_M(x y):=\!\! _x \,:\, x < x\!\!P_M(x y). (8) A binary program is a finite string π∈0,1∗π∈\0,1\^*; with m:=|π|m:=|π| and N(π):=∑j=1mπj2m−jN(π):= _j=1^m _j2^m-j, it names the dyadic interval Dπ:=[N(π)2m,N(π)+12m),D_π:= [ N(π)2^m, N(π)+12^m ), (9) so that Dϵ=[0,1)D_ε=[0,1) for the empty program and |Dπ|=2−|π||D_π|=2^-|π|. A binary program π forces output x under context y if Dπ⊆Iy(x)D_π I_y(x). A binary program can be evaluated efficiently whenever M’s next-token distributions are efficiently computable. Given π∈0,1∗π∈\0,1\^*, let ωπ:=N(π)2|π| _π:= N(π)2^|π| be the left endpoint of DπD_π. Starting from the interval [0,1)[0,1), run the model’s sampler deterministically using ωπ _π as its sampling randomness. After each generated prefix, compute M’s next-token distribution, partition the current interval in the fixed token order into consecutive left-closed, right-open subintervals having the corresponding relative lengths, emit the token whose subinterval contains ωπ _π, and continue with that subinterval until EOSEOS is emitted. (In essence, this is an instance of the standard arithmetic-decoding procedure [34].) If Dπ⊆Iy(x)D_π I_y(x), then ωπ∈Iy(x) _π∈ I_y(x), so the procedure recovers x. It uses one next-token-distribution evaluation per emitted token. Consequently, whenever M’s next-token distributions are polynomial-time computable, x can be recovered from M, y, and π in time polynomial in |y|+|π|+|x||y|+|π|+|x|. Thus our LLM-relative programs are efficiently evaluable whenever M’s next-token distributions are. We are now ready to state the notion of LLM-relative K-complexity, and the notion of algorithmic prompt value for non-thinking LLMs: Definition 2.3 (LLM-relative K-complexity and non-thinking prompt value). Define KM(x∣y):=min|π|:Dπ⊆Iy(x),K_M(x y):= \|π|:D_π I_y(x)\, (10) with value ∞ if no such π exists. For a prompt p∈Σ∗p∈ ^* and an artifact string z∈Σ∗z∈ ^*, define the non-thinking program-based prompt value ValM(p,z):=KM(z)−KM(z∣p).Val_M(p;z):=K_M(z)-K_M(z p). (11) That is, the (program-based) prompt value is simply the notion of algorithmic mutual information using LLM-relative K-complexity. Given access to M’s full next-token distributions, KM(x∣y)K_M(x y) is computable in polynomial time.33 3 First compute Iy(x)I_y(x) by successive interval refinement, the standard construction underlying arithmetic coding [34]: Starting from Jϵ=[0,1)J_ε=[0,1), process the tokens of xEOSx\,EOS in order. After a prefix u, partition JuJ_u, in the fixed order on Γ , into subintervals whose relative lengths are the probabilities PM(a∣yu)P_M(a yu), and let JuaJ_ua be the subinterval corresponding to the next token a. The interval obtained after processing xEOSx\,EOS is exactly Iy(x)I_y(x). Now write Iy(x)=[a,b)I_y(x)=[a,b). For each m∈ℕ0m _0, let km:=⌈2ma⌉k_m:= 2^ma . Note that the interval [km2−m,(km+1)2−m) [k_m2^-m,(k_m+1)2^-m ) is the leftmost dyadic interval of length 2−m2^-m whose left endpoint is at least a. Therefore, some dyadic interval of length 2−m2^-m is contained in [a,b)[a,b) if and only if (km+1)2−m≤b(k_m+1)2^-m≤ b. Let m⋆:=minm∈ℕ0:(km+1)2−m≤bm := \m _0:(k_m+1)2^-m≤ b \. Then KM(x∣y)=m⋆K_M(x y)=m , and the m⋆m -bit representation of km⋆k_m is a shortest program forcing x. and hence so is program-based prompt value as well. This computation, however, requires the model’s full next-token distributions without approximation, which are typically unavailable through an LLM API. To address this issue, we consider a common variant of Kolmogorov complexity, a-priori complexity [36, 21]: the log-measure of the set of sampling randomness that produces the output. We again provide an LLM-relative notion of this. Definition 2.4 (A priori LLM-relative complexity and measured value). For a context y and string z, define K~M(z∣y):=−log2PM(z∣y), K_M(z y):=- _2P_M(z y), (12) with K~M(z∣y):=∞ K_M(z y):=∞ if PM(z∣y)=0P_M(z y)=0. For a prompt p and string z, the non-thinking prompt value is Val~M(p,z):=K~M(z)−K~M(z∣p). Val_M(p;z):= K_M(z)- K_M(z p). (13) By expanding out the definition, we directly get: Corollary 2.5 (Likelihood-ratio form). If z has positive probability under both ϵε and p, then for z=(z1,…,zn)z=(z_1,…,z_n), Val~M(p,z)=log2PM(z∣p)PM(z)=∑i=1nlog2PM(zi∣pz<i)PM(zi∣z<i)+log2PM(EOS∣pz)PM(EOS∣z). Val_M(p;z)= _2 P_M(z p)P_M(z)= _i=1^n _2 P_M(z_i p\,z_<i)P_M(z_i z_<i)+ _2 P_M(EOS p\,z)P_M(EOS z). (14) Note that Val~M Val_M has exactly the algebraic form of the pointwise-mutual-information (PMI) functional [10, 6], applied to the model’s prompted and unprompted distributions, and can be thought of as a non-normalized version of the score of [35]. The main result of this section is that the two notions of LLM-relative K-complexity (program-based and a-priori-based) and thus also the two notions of prompt value, coincide up to an additive constant, much like standard a-priori complexity and (prefix) Kolmogorov complexity [36]. Theorem 2.6 (Algorithmic semantics of prompt value). (i) For every context y and string z with PM(z∣y)>0P_M(z y)>0, 0≤KM(z∣y)−K~M(z∣y)< 2.0\;≤\;K_M(z y)- K_M(z y)\;<\;2. (15) (i) Consequently, for every prompt p and exact string z in the support of both distributions, |ValM(p,z)−Val~M(p,z)|<2. |Val_M(p;z)- Val_M(p;z) |<2. (16) The formal proof is given in Appendix A. For a proof sketch, recall that we associate with an output z an interval Iy(z)⊆[0,1)I_y(z) [0,1) whose length is PM(z∣y)P_M(z y), and that a binary program π forces z when its dyadic interval DπD_π, of length 2−|π|2^-|π|, lies entirely inside Iy(z)I_y(z). The lower bound in part (i) follows because DπD_π cannot be longer than Iy(z)I_y(z). For the upper bound, the proof rounds the left endpoint of Iy(z)I_y(z) to a dyadic grid and its length down to an inverse power of two; the resulting two factor-22 losses suffice. Part (i) then follows by taking differences. Remark 2.7 (Differences with standard algorithmic mutual information). Two disanalogies with universal-machine algorithmic information are noteworthy. First, non-thinking prompt value can be (very) negative: the conditional distribution is the model’s actual behavior under the prompt, and the model cannot be assumed to ignore a misleading input at constant cost. Second, a very short input can carry a very large value: a one-token trigger may raise the probability of a long output by hundreds of bits. This second phenomenon is similar to what happens with time-bounded Kolmogorov complexity, where getting a short key may unlock a long encrypted message [25]. We observe that K~M K_M, and hence non-thinking prompt value, can be efficiently computed from the model’s next-token log probabilities along zEOSz\,EOS. Moreover, in contrast to KMK_M, approximate log probabilities suffice to approximate these quantities: if every next-token log probability is known within additive error η, then K~M(z∣y) K_M(z y) is determined within additive error |zEOS|η|z\,EOS|η, and the resulting prompt value within additive error 2|zEOS|η2|z\,EOS|η. Theorem 2.8 (Efficient evaluation of non-thinking prompt value). Let z=(z1,…,zn)z=(z_1,…,z_n) have positive probability under both ϵε and p. Given exact next-token log probabilities, Val~M(p,z) Val_M(p;z) can be computed exactly using 2(n+1)2(n+1) queries and O(n)O(n) arithmetic operations. More generally, if each queried log probability is approximated within additive error ρ, the same computation approximates Val~M(p,z) Val_M(p;z) within 2(n+1)ρ2(n+1)ρ. Proof. By (14), Val~M(p,z) Val_M(p;z) is a signed sum of the prompted and unprompted log probabilities of the n tokens of z and the final EOSEOS, giving 2(n+1)2(n+1) terms. The exact claim follows by summing them, and the approximation claim follows from the triangle inequality. ∎ In the sequel, we take Val~M Val_M as the starting point for our notion of prompt value for LLMs with thinking, with Theorem 2.6 guaranteeing that the reported quantities track the algorithmic (program-based) values within two bits. 3 Thinking and the prompt value We move on to consider LLMs with thinking. 3.1 LLMs with thinking We start by formalizing a thinking LLM. Informally, an LLM with thinking operates in two stages. It first generates a thinking route H, stopping when it emits a distinguished end-of-thinking token EOTEOT (or EOSEOS). It then generates its output conditioned on the realized route H. Definition 3.1 (LLM with thinking). An LLM with thinking consists of an autoregressive LLM M, as in Definition 2.1, together with a distinguished end-of-thinking token EOT∈ΣEOT∈ . In context y, the thinking stage samples tokens autoregressively from M until either EOTEOT or EOSEOS is emitted. Let HyH^y denote the tokens generated before this stop token, which is not included in HyH^y; we call one execution of the thinking-stage sampler a rollout, and call the resulting token sequence HyH^y its thinking route. After the thinking stage, the output stage runs M in context yHyEOTy\,H^y\,EOT and generates an output terminating with EOSEOS. (Thus, even if the thinking stage stopped at EOSEOS, the declared two-stage process proceeds by appending EOTEOT and running the output stage.) Write S:=|Hy|S:=|H^y|, and, for t∈ℕ0t _0, let H≤tyH^y_≤ t be the first mint,S \t,S\ tokens of HyH^y. For any finite thinking route HyH^y, define the output-stage probability Gy(z∣Hy):=PM(z∣yHyEOT).G_y(z H^y):=P_M(z y\,H^y\,EOT). External oracle calls. The same treatment extends to thinking processes that interact with external tools or oracles. In this case, HyH^y denotes the realized interaction transcript, including both the calls and their responses, and its distribution is induced by the combined LLM–oracle process. We never evaluate the probability of HyH^y itself; at each prefix, we evaluate only the probability of producing z conditional on that realized transcript. Thus the oracle responses need not be generated autoregressively by M. We require only sampling access, not likelihood access, to the oracle. The combined LLM–oracle process must be independently restartable across rollouts. The only additional ingredient is cost accounting. The token-equivalent time function introduced below should charge for the oracle calls as well as for the LLM’s computation. Formally, one may allow the cost to depend nondecreasingly on the realized transcript prefix. Equivalently, one may pad the accounting timeline of each oracle call with a number of virtual thinking tokens corresponding to its declared token-equivalent cost. These virtual tokens are used only for accounting and are not supplied to the model. Under this interpretation, the definitions and results below apply unchanged. For simplicity, we restrict the subsequent formal treatment to thinking without external oracle calls. 3.2 Realized-thought Levin complexity We proceed to formalizing an LLM-relative notion of Levin-complexity [20] for LLMs with thinking. Towards this goal, we start by providing a notion of realized-thought Levin complexity, for a fixed (i.e., realized) thinking route H. (Looking forward, in Section 3.3, we take H to be a random variable (over thinking) and summarize it by its median, obtaining the complexity notion pKt~Mκ pKt^κ_M; the prompt value is then algorithmic mutual information with respect to that notion.) Charging thinking requires a declared unit of “running-time”; we count time in “thinking-token” equivalent units through an externally specified cost function: Definition 3.2 (Token-equivalent time). A token-equivalent time function is a family κy,z:ℕ0→[1,∞) _y,z:N_0→[1,∞), indexed by contexts y and artifacts z, nondecreasing in t. When y and z are clear from context, we write simply κ(t)κ(t). κ(t)κ(t) is simply the declared token-equivalent cost assigned to a production that uses t tokens of thinking in context y. A natural choice is the generated-thought cost κy,zgen(t)=cpre|y|+cdec(t+1+|zEOS|). _y,z^gen(t)=c_pre|y|+c_dec (t+1+ |z\,EOS | ). Here cprec_pre is the cost per token processed during prefill, cdecc_dec is the cost per sequentially generated token, and the additional 11 accounts for EOTEOT. This convention charges for prefilling the supplied context and then sequentially generating the thinking, EOTEOT, and the artifact. Because prefill processes many tokens in parallel whereas decoding is sequential, cdec/cprec_dec/c_pre can naturally be much larger than one. (In Section 6 we normalize cpre=1c_pre=1, use cdec=32c_dec=32 as a representative default, and report sensitivity to this choice.) Another simple choice is the prefix-prefill cost κy,zpre(t)=cpre(|y|+t+1)+cdec|zEOS|. _y,z^pre(t)=c_pre (|y|+t+1 )+c_dec |z\,EOS |. This convention treats the realized thinking prefix as already available and re-executes it as part of the prefill, rather than charging for generating it token by token. It is therefore less direct as an accounting of the original online production of the thought. It nevertheless has an especially natural token-cost interpretation: Section 5 shows that it is the per-attempt cost arising when a fixed realized thought is replayed before fresh attempts to reproduce the artifact. We now state the notion of LLM-relative realized-thought Levin complexity: Definition 3.3 (Realized-thought Levin complexity). Fix a model M and a token-equivalent time function κ. For a context y, an artifact z, and a thinking route HyH^y, define Kt~Mκ(z∣y;Hy):=mint∈ℕ0K~M(z∣yH≤tyEOT)+log2κ(t), Kt^κ_M (z y;\,H^y )\;:=\; _t _0 \ K_M (z y\,H^y_≤ t\,EOT )\;+\; _2κ(t) \, (17) In other words, given a fixed thinking route HyH^y, we consider exactly Levin’s combination of description length and running time from the notion of KtKt-complexity [20]: description length plus log running time, minimized over time. Note that although the minimization ranges over all of ℕ0N_0, it suffices to consider t=0,…,St=0,…,S: H≤ty=HyH^y_≤ t=H^y for every t≥St≥ S, so the conditional-complexity term is constant over these choices, while κ(t)≥κ(S)κ(t)≥κ(S) by monotonicity; thus, no t>St>S can improve upon t=St=S, and the minimum can be computed by evaluating the S+1S+1 truncations t=0,…,St=0,…,S. A program-based companion replaces a-priori complexity by program length: KtMκ(z∣y;Hy):=mint∈ℕ0KM(z∣yH≤tyEOT)+log2κ(t).Kt^κ_M (z y;\,H^y )\;:=\; _t _0 \K_M (z y\,H^y_≤ t\,EOT )+ _2κ(t) \. 3.3 Probabilistic Levin complexity: a median over random realized thoughts So far, the complexity has been defined relative to a particular realized thinking route. Viewing the thinking as the random tape of the program (or, equivalently, representing it by the random bits that cause the LLM to generate that route), we now define an LLM-relative notion of probabilistic Levin–Kolmogorov complexity in the spirit of [11]. Namely, we summarize over the model’s thinking randomness by taking a δ-quantile of the resulting realized-thought KtKt-complexity. The resulting notion is an LLM-relative, a-priori KtKt counterpart of probabilistic time-bounded Kolmogorov complexity. For δ∈(0,1]δ∈(0,1] and a random variable X taking values in [0,∞][0,∞], write medδ[X]:=infa∈[0,∞]:Pr[X≤a]≥δ _δ[X]:= \a∈[0,∞]: [X≤ a]≥δ\ for its lower δ-quantile. Definition 3.4 (LLM-relative probabilistic Levin complexity). Fix a model M, a token-equivalent time function κ, and a level δ∈(0,1]δ∈(0,1]. For a context y and artifact z, the probabilistic (a-priori) Levin complexity of z given y at level δ is pKt~M,δκ(z∣y):=medδ[Kt~Mκ(z∣y;Hy)], pKt^κ_M,δ (z y ):= _δ [ Kt^κ_M (z y;\,H^y ) ], (18) where the quantile is taken over the distribution of the thinking route HyH^y induced by a random rollout of M in context y. The program-based companion pKtM,δκ(z∣y)pKt^κ_M,δ(z y) is defined analogously instead using KtMκKt^κ_M. Whenever δ is clear from context, we suppress it from the notation; we typically consider the median δ=1/2δ=1/2. 3.4 The prompt value We define prompt value as algorithmic mutual information with respect to pKt~Mκ pKt^κ_M, exactly as Val~M Val_M was with respect to K~M K_M in Section 2. Definition 3.5 (Prompt value). Fix a model M, a token-equivalent time function κ, a level δ∈(0,1]δ∈(0,1], a prompt p∈Σ∗p∈ ^*, and an artifact z∈Σ∗z∈ ^*. Whenever pKt~M,δκ(z) pKt^κ_M,δ(z) and pKt~M,δκ(z∣p) pKt^κ_M,δ(z p) are both finite, the prompt value of the prompt p for the artifact z is Val~M,δκ(p,z):=pKt~M,δκ(z)−pKt~M,δκ(z∣p), Val^κ_M,δ(p;z)\;:=\; pKt^κ_M,δ(z)- pKt^κ_M,δ(z p), (19) and ValM,δκ(p,z):=pKtM,δκ(z)−pKtM,δκ(z∣p)Val^κ_M,δ(p;z):=pKt^κ_M,δ(z)-pKt^κ_M,δ(z p) is its program-based companion. A prompt is therefore credited both when it makes the artifact more probable given the realized thinking and when it eliminates thinking that the unprompted side must otherwise pay for; and the unprompted side can compensate for a missing hint by thinking longer, at a price. As before, the a-priori and program-based version differ by at most 2: Proposition 3.6 (Program semantics of pKt~ pKt and of the prompt value). Fix M, κ and δ∈(0,1]δ∈(0,1]. For every context y and artifact z, the program-based and a-priori complexities are finite together, and whenever they are finite: 0≤pKtM,δκ(z∣y)−pKt~M,δκ(z∣y)≤ 2.0\;≤\;pKt^κ_M,δ(z y)- pKt^κ_M,δ(z y)\;≤\;2. Consequently, whenever the two complexities of Definition 3.5 are finite, |ValM,δκ(p,z)−Val~M,δκ(p,z)|≤ 2. |Val^κ_M,δ(p;z)- Val^κ_M,δ(p;z) |\;≤\;2. Proof. For each t∈ℕ0t _0, let ct:=yH≤tyEOTc_t:=y\,H^y_≤ t\,EOT. By Theorem 2.6(i), KM(z∣ct)K_M(z c_t) and K~M(z∣ct) K_M(z c_t) are finite together and satisfy K~M(z∣ct)≤KM(z∣ct)<K~M(z∣ct)+2. K_M(z c_t)≤ K_M(z c_t)< K_M(z c_t)+2. Adding log2κ(t) _2κ(t) preserves these inequalities pointwise in t. Since the relevant minima are attained, minimization preserves the strict upper bound: Kt~Mκ(z∣y;Hy)≤KtMκ(z∣y;Hy)<Kt~Mκ(z∣y;Hy)+2, Kt^κ_M(z y;H^y)≤ Kt^κ_M(z y;H^y)< Kt^κ_M(z y;H^y)+2, with the two quantities finite together. Taking lower quantiles preserves the weak inequalities, but may turn the strict upper bound into equality44 4 More generally, if X(ω)≤Y(ω)X(ω)≤ Y(ω) for every outcome ω (or merely almost surely), then Pr[X≤a]≥Pr[Y≤a] [X≤ a]≥ [Y≤ a] for every a. Hence a:Pr[Y≤a]≥δ⊆a:Pr[X≤a]≥δ\a: [Y≤ a]≥δ\ \a: [X≤ a]≥δ\, and taking infima gives medδ[X]≤medδ[Y] _δ[X]≤ _δ[Y].; hence pKt~M,δκ(z∣y)≤pKtM,δκ(z∣y)≤pKt~M,δκ(z∣y)+2, pKt^κ_M,δ(z y) ^κ_M,δ(z y)≤ pKt^κ_M,δ(z y)+2, again with the two quantities finite together. Finally, ValM,δκ(p,z)−Val~M,δκ(p,z)=(pKtM,δκ(z)−pKt~M,δκ(z))−(pKtM,δκ(z∣p)−pKt~M,δκ(z∣p)).Val^κ_M,δ(p;z)- Val^κ_M,δ(p;z)= (pKt^κ_M,δ(z)- pKt^κ_M,δ(z) )- (pKt^κ_M,δ(z p)- pKt^κ_M,δ(z p) ). Each parenthesized term lies in [0,2][0,2], so their difference has absolute value at most 22. ∎ 3.5 Canonical targets and verified acceptance The exact-string requirement on z is a modelling choice about what constitutes the “artifact” z relative to which we are measuring the prompt’s value. If one wishes to price a class of acceptable artifacts rather than a string—“the route contains a proof the verifier accepts”—one declares a machine that thinks and then emits a canonical verdict, and takes z to be that verdict. Concretely, let :Σ∗→0,1V: ^*→\0,1\ be an efficiently computable predicate on the transcript preceding EOTEOT. Extend the declared machine with a verdict step that, after the realized transcript yHyH, emits ACC if (yH)=1V(yH)=1 and REJ otherwise, and then emits EOSEOS. Under this type of “verified artifacts”, the measure takes a particularly simple form. Since the verdict step is deterministic, PM(ACC∣yH≤tEOT)P_M( ACC y\,H_≤ t\,EOT) is 11 on accepting prefixes and 00 on rejecting ones, and hence K~M(ACC∣yH≤tEOT)∈0,∞ K_M( ACC y\,H_≤ t\,EOT)∈\0,∞\. Define the “acceptance cost” of a route H by Cy(H):=minκ(t):t∈ℕ0,(yH≤t)=1,min∅:=∞.C_y(H):= \κ(t):t _0,\ V(yH_≤ t)=1\, :=∞. It follows that Kt~Mκ(ACC∣y;Hy)=log2Cy(Hy) Kt^κ_M( ACC y;H^y)= _2C_y(H^y). Writing τy _y for the median of Cy(Hy)C_y(H^y) over rollouts in context y, we thus get pKt~Mκ(ACC∣y)=log2τy,Val~Mκ(p,ACC)=log2τϵτp, pKt^κ_M( ACC y)= _2 _y, Val^κ_M(p; ACC)= _2 _ε _p, (20) whenever the two medians are finite. 4 Estimation We observe that pKt~ pKt is efficiently estimable in the following sense: the empirical median obtained from polynomially many rollouts lies, with high probability, between quantiles arbitrarily close to the population median. Applying this guarantee with and without the prompt yields corresponding bounds on the prompt-value estimate. Protocol. Fix a model M, a token-equivalent time function κ, a level δ∈(0,1]δ∈(0,1], and a number k∈ℕk of rollouts per side. Input: artifact z and prompt p. 1. For each context y∈p,ϵy∈\p,ε\, perform k independent complete thinking rollouts, producing routes Hy,(1),…,Hy,(k)H^y,(1),…,H^y,(k) with respective lengths Sy,(1),…,Sy,(k)S^y,(1),…,S^y,(k). For each route i, evaluate every truncation t=0,…,Sy,(i)t=0,…,S^y,(i) and form its routewise minimum Kt~y,(i) Kt^\,y,(i) according to (17). 2. For each y∈ϵ,py∈\ε,p\, let m^ky m_k^\,y be the empirical lower δ-quantile55 5 That is, the ⌈δk⌉ δ k -th smallest of the k observed values. of Kt~y,(1),…,Kt~y,(k) Kt^\,y,(1),…, Kt^\,y,(k), and output Val^M,δ,kκ(p,z):=m^kϵ−m^kp. Val^κ_M,δ,k(p;z):= m_k^\,ε- m_k^\,p. For δ∈(0,1)δ∈(0,1) and |ζ|<minδ,1−δ|ζ|< \δ,1-δ\, define the ζ-offset prompt value by Val~M,δ;ζκ(p,z):=pKt~M,δ+ζκ(z)−pKt~M,δ−ζκ(z∣p). Val^κ_M,δ;ζ(p;z):= pKt^κ_M,δ+ζ(z)- pKt^κ_M,δ-ζ(z p). Thus Val~M,δ;0κ=Val~M,δκ Val^κ_M,δ;0= Val^κ_M,δ, and Val~M,δ;ζκ Val^κ_M,δ;ζ is nondecreasing in ζ. Theorem 4.1 (Efficient estimation of pKt~ pKt and prompt value). Run the preceding protocol with k∈ℕk and δ∈(0,1)δ∈(0,1). For every ζ∈(0,minδ,1−δ)ζ∈(0, \δ,1-δ\), with probability at least 1−4exp(−2kζ2)1-4 (-2kζ^2), simultaneously for y∈p,ϵy∈\p,ε\, m^ky∈[pKt~M,δ−ζκ(z∣y),pKt~M,δ+ζκ(z∣y)]. m_k^\,y∈ [ pKt^κ_M,δ-ζ(z y), pKt^κ_M,δ+ζ(z y) ]. Consequently, with the same probability and whenever the interval is defined, Val^M,δ,kκ(p,z)∈[Val~M,δ;−ζκ(p,z),Val~M,δ;ζκ(p,z)]. Val^κ_M,δ,k(p;z)∈ [ Val^κ_M,δ;-ζ(p;z), Val^κ_M,δ;ζ(p;z) ]. If next-token sampling from M, evaluation of the artifact probabilities, and evaluation and comparison of κy,z(t) _y,z(t) can be performed in time polynomial in their input lengths, then the protocol runs in time polynomial in k, T, |p||p|, and |z||z|, where T is the maximum thinking time attained by M in the protocol on inputs p and ϵε. Proof. Fix y∈p,ϵy∈\p,ε\, let Xy:=Kt~Mκ(z∣y;Hy)X_y:= Kt^κ_M(z y;H^y), and set q−:=pKt~M,δ−ζκ(z∣y),q+:=pKt~M,δ+ζκ(z∣y).q_-:= pKt^κ_M,δ-ζ(z y), q_+:= pKt^κ_M,δ+ζ(z y). The k routewise values used to compute m^ky m_k^\,y are independent copies of XyX_y. By the definition of a lower quantile,66 6 Recall, for qα:=infa:Pr[X≤a]≥αq_α:= \a: [X≤ a]≥α\, one has Pr[X<qα]≤α≤Pr[X≤qα] [X<q_α]≤α≤ [X≤ q_α]. Pr[Xy<q−]≤δ−ζ,Pr[Xy≤q+]≥δ+ζ. [X_y<q_-]≤δ-ζ, [X_y≤ q_+]≥δ+ζ. If m^ky<q− m_k^\,y<q_-, then at least ⌈δk⌉ δ k samples are strictly below q−q_-, so by the Chernoff bound77 7 Recall, for independent Bernoulli random variables B1,…,BkB_1,…,B_k, the additive Chernoff bound states Pr[∑iBi−[∑iBi]≥ζk]≤exp(−2kζ2) [ _iB_i-E[ _iB_i]≥ζ k]≤ (-2kζ^2) and Pr[[∑iBi]−∑iBi≥ζk]≤exp(−2kζ2) [E[ _iB_i]- _iB_i≥ζ k]≤ (-2kζ^2) [4]. this event is bounded by exp(−2kζ2) (-2kζ^2). Similarly, if m^ky>q+ m_k^\,y>q_+, then fewer than ⌈δk⌉ δ k samples are at most q+q_+, and Chernoff again bounds this event by exp(−2kζ2) (-2kζ^2). Thus the containment fails for a given y with probability at most 2exp(−2kζ2)2 (-2kζ^2). A union bound over y∈p,ϵy∈\p,ε\ gives the stated probability. On this simultaneous event, subtracting the interval for y=py=p from the interval for y=ϵy=ε gives m^kϵ−m^kp∈[pKt~M,δ−ζκ(z)−pKt~M,δ+ζκ(z∣p),pKt~M,δ+ζκ(z)−pKt~M,δ−ζκ(z∣p)]. m_k^\,ε- m_k^\,p∈ [ pKt^κ_M,δ-ζ(z)- pKt^κ_M,δ+ζ(z p),\; pKt^κ_M,δ+ζ(z)- pKt^κ_M,δ-ζ(z p) ]. By the definitions of Val^M,δ,kκ Val^κ_M,δ,k and Val~M,δ;ζκ Val^κ_M,δ;ζ, this is exactly the claimed prompt-value interval. For the running time, every sampled thinking route has at most T+1T+1 relevant truncations. The protocol evaluates the artifact probability and κy,z(t) _y,z(t) at each truncation and minimizes over them. Suppressing the fixed background context, every evaluation processes at most |p|+T+1+|zEOS||p|+T+1+|z\,EOS| tokens. Under the stated assumptions, these evaluations, the minimizations, and the two empirical-quantile computations take time polynomial in the claimed parameters. ∎ Remark 4.2 (Transformer implementation). For a transformer with an append-only KV cache, the cache for every earlier thinking prefix is an initial segment of the cache for the complete route, so that prefix need not be recomputed. Suppressing the fixed background context, the protocol can therefore be implemented using O(k|p|+k(T+1)(1+|z|))O\! (k|p|+k(T+1) (1+|z| ) ) model-token evaluations. 5 Prompt value and token-equivalent reproduction cost We here consider an economic interpretation of our notions. We first define the cost of reproducing an artifact through an experiment that, given a fixed thinking route, repeatedly prepares the output stage from that route and samples it with fresh randomness until it recovers the artifact. Each attempt is assigned the token-equivalent charge specified by the declared cost function κ. We then show that 2pKt~Mκ(z∣y)2 pKt^κ_M(z y) is exactly the typical such cost in context y, where typicality is taken over the distribution of thinking routes induced by random rollouts, so that exponentiated prompt value is the ratio of the typical costs without and with the prompt. Definition 5.1 (Reproduction experiment and token cost). Fix a model M and a token-equivalent time function κ. Let y be a context, z an artifact, and H a thinking string. Write g:=Gy(z∣H)g:=G_y(z H). The reproduction experiment for z given H makes independent, identically distributed attempts. Each attempt is charged κ(|H|)κ(|H|) token-equivalent units, and a fresh output stage is run in the context yHEOTy\,H\,EOT. An attempt succeeds if its output is exactly z, which occurs with probability g. The experiment halts at the first success, at index N, and the token-equivalent reproduction cost of z given H is its expected total expenditure TokenCosty(z,H):=[Nκ(|H|)]TokenCost_y(z;H):=E[Nκ(|H|)]. For a thinking route H with truncations H≤tH_≤ t, the best-prefix reproduction cost is TokenCosty∗(z,H):=min0≤t≤|H|TokenCosty(z,H≤t)TokenCost^*_y(z;H):= _0≤ t≤|H|TokenCost_y(z;H_≤ t). Thus TokenCosty(z,H)TokenCost_y(z;H) is the expected expenditure conditional on the fixed route H; the quantiles below are taken over routes sampled from random rollouts. Theorem 5.2 (Reproduction cost). Fix M and κ. For every context y, artifact z, and thinking string H, TokenCosty(z,H)=κ(|H|)Gy(z∣H), _y(z;H)= κ(|H|)G_y(z H), with the right-hand side interpreted as +∞+∞ when Gy(z∣H)=0G_y(z H)=0. Proof. Fix H and write g:=Gy(z∣H)g:=G_y(z H). If g=0g=0, both TokenCosty(z,H)TokenCost_y(z;H) and κ(|H|)/gκ(|H|)/g are defined to be infinite, so assume g>0g>0. Because each attempt uses fresh output-stage randomness while keeping H fixed, the attempts are independent and each succeeds with probability g. Thus N is geometric with parameter g, and [N]=1/gE[N]=1/g. Since each attempt incurs the charge κ(|H|)κ(|H|), the total charge is Nκ(|H|)Nκ(|H|). Therefore TokenCosty(z,H)=[Nκ(|H|)]=κ(|H|)[N]=κ(|H|)g.TokenCost_y(z;H)=E\! [Nκ(|H|) ]=κ(|H|)E[N]= κ(|H|)g. ∎ Proposition 5.3 (Realized-thought complexity as reproduction cost). Fix M and κ. For every context y, artifact z, and rollout HyH^y, 2Kt~Mκ(z∣y;Hy)=TokenCosty∗(z,Hy).2^\, Kt^κ_M(z y;\,H^y)\;=\;TokenCost^*_y(z;H^y). (21) Proof. Let S=|Hy|S=|H^y|. Comparing Definition 3.3 with Theorem 5.2, and using that exponentiation is increasing, gives 2Kt~Mκ(z∣y;Hy) 2^\, Kt^κ_M(z y;H^y) =min0≤t≤S2−log2Gy(z∣H≤ty)+log2κ(t) = _0≤ t≤ S2^\,- _2G_y(z H^y_≤ t)+ _2κ(t) =min0≤t≤Sκ(t)Gy(z∣H≤ty) = _0≤ t≤ S κ(t)G_y(z H^y_≤ t) =min0≤t≤STokenCosty(z,H≤ty)=TokenCosty∗(z,Hy). = _0≤ t≤ STokenCost_y(z;H^y_≤ t)=TokenCost_y^*(z;H^y). ∎ Theorem 5.4 (pKt~ pKt and prompt value as typical token costs). Fix M, κ, and δ∈(0,1]δ∈(0,1]. For every context y and artifact z, 2pKt~M,δκ(z∣y)=medδ[TokenCosty∗(z,Hy)],2^\, pKt^κ_M,δ(z y)\;=\; _δ [\,TokenCost^*_y(z;H^y)\, ], where medδ _δ is taken over the distribution of the thinking route HyH^y generated by a random rollout of M in context y. Consequently, every prompt p and artifact z such that both complexities in Definition 3.5 are finite, 2Val~M,δκ(p,z)=medδ[TokenCostϵ∗(z,Hϵ)]medδ[TokenCostp∗(z,Hp)].2^\, Val^κ_M,δ(p;z)\;=\; _δ [TokenCost^*_ε(z;H^ε) ] _δ [TokenCost^*_p(z;H^p) ]. Proof. Lower quantiles commute with continuous strictly increasing transformations.88 8 That is, medδ[φ(X)]=φ(medδ[X]) _δ[ (X)]= ( _δ[X]) for continuous strictly increasing φ , with the same identity on the extended real line when φ(+∞)=+∞ (+∞)=+∞. Applying this fact to φ(x)=2x (x)=2^x and using Proposition 5.3 gives 2pKt~M,δκ(z∣y) 2^\, pKt^κ_M,δ(z y) =2medδ[Kt~Mκ(z∣y;Hy)] =2^\, _δ\! [ Kt^κ_M(z y;H^y) ] =medδ[2Kt~Mκ(z∣y;Hy)] = _δ\! [2^\, Kt^κ_M(z y;H^y) ] =medδ[TokenCosty∗(z,Hy)]. = _δ [TokenCost_y^*(z;H^y) ]. Exponentiating Definition 3.5 and applying this identity to its two terms gives the ratio. ∎ The theorem gives prompt value its token-cost meaning: a value of Val~Mκ(p,z)=b Val^κ_M(p;z)=b means that reproducing this artifact without the prompt typically costs 2b2^b times more token-equivalent units than with it. On the cost function and more general notions of Kt~ Kt The two cost conventions introduced above admit the following operational interpretations. Under the “prefix-prefill” cost convention, κpreκ^pre, the realized thought is treated as already available: each attempt freshly prefills yHEOTy\,H\,EOT and then runs the output stage with fresh randomness. This convention is natural when the thought is already available, and is a good amortized approximation when many reproduction attempts are expected. Under the “generated-thought” cost convention, κgenκ^gen, each attempt instead reruns the thinking stage with the same thinking-stage randomness, thereby regenerating the same route H sequentially before running the output stage with fresh randomness. This convention is natural when each attempt must reproduce the complete online computation, and is closer to the total cost when only a few attempts are expected and the cost of initially generating the thought cannot be amortized. Both cost conventions are stylized approximations of the implementation-dependent cost of running an LLM. More generally, Levin’s objective function is only one particular way of combining success probability and computation. Let F:[0,1]×[1,∞)⟶ℝ¯,F(0,c)=+∞F:[0,1]×[1,∞) R, F(0,c)=+∞ be any declared function that is nonincreasing in its first argument and nondecreasing in its second, and define Kt~MF,κ(z∣y;Hy):=mint∈ℕ0F(Gy(z∣H≤ty),κ(t)). Kt^F,κ_M(z y;H^y):= _t _0F\! (G_y(z H^y_≤ t),κ(t) ). The usual Levin objective corresponds to FLev(g,c)=−log2g+log2c=log2cg.F_Lev(g,c)=- _2g+ _2c= _2 cg. Other choices of F can encode more detailed production costs, including different charges for initially generating a thought, replaying it, retaining a KV cache, or making subsequent output attempts. In particular, if T(g,c)T(g,c) denotes the expected token cost of an explicitly specified production procedure with success probability g and computational charge c, one may take F(g,c)=log2T(g,c)F(g,c)= _2T(g,c).99 9 For example, suppose the first attempt sequentially generates the fixed thinking route and costs κgen(t)κ^gen(t), while each subsequent attempt freshly prefills that route and costs κpre(t)κ^pre(t). If N is geometric with success probability g, the expected total cost is [κgen(t)+(N−1)κpre(t)]=κgen(t)+(1g−1)κpre(t).E\! [κ^gen(t)+(N-1)κ^pre(t) ]=κ^gen(t)+ ( 1g-1 )κ^pre(t). Taking the logarithm of this expression gives the corresponding choice of F. We focus on the Levin choice because it is simple and yields the exact reproduction-cost interpretation above; richer cost aggregators can be used when a more detailed implementation-specific accounting is desired. 6 An Experimental Illustration We illustrate the measure on twelve problems from GSM8K, a dataset of grade-school mathematics word problems with step-by-step natural-language reference solutions [7]. The experiment illustrates, on a small scale, why thinking and computation must be incorporated rather than using only the probability-based, non-thinking prompt value of Section 2. It also illustrates why prompt value is naturally indexed by a quantile: the same prompt may help one part of the rollout distribution while hurting another. (The experiment is intended as an illustration of the measure, not as a population-level evaluation of prompting on GSM8K.) Problems and prompts. We sample 100100 problems without replacement from the GSM8K training split and retain the first twelve whose reference solutions contain at least three newline-delimited steps. For each problem q, the prompt p is the first reference step, with GSM8K calculator annotations such as <<2*300=600>> removed. For example, the first selected problem, gsm8k#4205, is: While at the lake, Cohen saw 300 fish-eater birds that had migrated into the area recently walking by the lake, eating the fish they had caught. The number of birds at the lake doubled on the second day and reduced by 200 on the third day. How many fish-eater birds did Cohen see in the three days? The canonical answer is 13001300, and the first reference step is: Since there were 300 fish-eater birds in the lake on the first day, the number doubled to 2∗300=6002*300=600 birds on the second day. The accompanying online notebook1010 10 https://w.kaggle.com/code/rafaelpass/the-value-of-a-prompt provides the complete code needed to reproduce the problem selection, sampled routes, scoring output, and figures. Protocol. The underlying model is deepseek-ai/DeepSeek-R1-Distill-Qwen-1.5B [8]. We load the model in FP16, a standard GPU-inference configuration, and convert its logits to FP32 before computing probabilities. Following DeepSeek’s benchmark configuration, we use temperature 0.60.6 and draw 6464 independent rollouts for every problem in each of two conditions. DeepSeek’s configuration uses top-p=0.95p=0.95, which discards low-probability tokens outside the sampling nucleus and renormalizes the remaining distribution. We instead set top-p=1p=1, so that no such truncation occurs and every token remains in the support of the sampling distribution. Both conditions (prompted and unprompted) contain the same GSM8K question and answer instruction: “Give the final answer as a single number on the last line, in the form ANSWER: <number>.” After the question, the model context ends with <think>, the model’s start-of-thinking marker. In the condition y=ϵy=ε, we sample the model’s thinking immediately. In the condition y=py=p, we first append the reference step after <think> and then sample the model’s continuation. Thus the reference step is supplied as partial computation.1111 11 In a preliminary comparison, supplying the same reference step in the “user turn” had much less effect on the model’s success. In that placement, the model may treat the step as an assertion to verify or re-derive. We instead prefill it inside the open thinking block so that the model can continue from it as already supplied partial computation, which is the intervention we wish to value. We next sample a thinking route H, stopping when the model emits EOTEOT or EOSEOS, or when an experimental horizon is reached.1212 12 In our experiment set-up, the experimental horizon is set to 18001800 thinking tokens; all sampled rollouts terminate before reaching it. For each possible stopping time t, we retain H≤tH_≤ t, append EOTEOT, and supply the fixed field ANSWER:. The artifact z is the continuation consisting of a leading space followed by the canonical gold numeral; we evaluate the probability of emitting z and then EOSEOS. (The fixed ANSWER: field is excluded from the thinking token count going into cost κ.) Cost conventions and the estimator. We evaluate both token-equivalent cost conventions introduced after Definition 3.2. Recall that κgenκ^gen charges the supplied context at the prefill rate and the thinking prefix and artifact at the sequential-decoding rate, whereas κpreκ^pre charges the supplied context and thinking prefix at the prefill rate and only the artifact at the sequential-decoding rate. We normalize cpre=1c_pre=1, use cdec=32c_dec=32 as the default, and examine sensitivity over a sampled grid with cdec∈[8,256]c_dec∈[8,256]. For every rollout HyH^y, we evaluate every truncation index t=0,…,|Hy|t=0,…,|H^y| and first minimize the objective defining Kt~Mκ(z∣y;Hy) Kt^κ_M(z y;H^y) over t. We then let m^64y m_64^\,y denote the empirical lower δ-quantile of the 6464 routewise minima for y∈ϵ,py∈\ε,p\. Following the protocol of Section 4, the reported prompt-value estimate is Val^M,δ,64κ(p,z)=m^64ϵ−m^64p, Val^κ_M,δ,64(p;z)= m_64^\,ε- m_64^\,p, the empirical counterpart of Val~M,δκ(p,z) Val^κ_M,δ(p;z). 6.1 Results and observations For presentation, we divide the twelve problems into two cohorts under the generated-thought convention with cdec=32c_dec=32. The first contains the six problems whose estimated prompt value is positive at all three marked quantiles, δ∈0.2,0.5,0.8δ∈\0.2,0.5,0.8\; the second contains the remaining six. Thinking can reverse the non-thinking verdict. Figure 1 isolates the probability component of the measure for the cohort positive at all three marked quantiles. In five of the six cases, supplying the correct first step initially makes the gold artifact less likely at t=0t=0 (and in the sixth one only slightly improves). Nevertheless, once thinking is incorporated, the generated-thought prompt value is positive at all three marked quantiles. The curves show the source of this reversal: the prompted condition reaches favorable artifact probabilities after shorter thinking prefixes. Thus the non-thinking probability-based value of Section 2, including the corresponding criterion of [35], can give the opposite qualitative verdict. Figure 1: Probability-only artifact-description-length profiles for the six cases positive at all three marked quantiles. Columns correspond to δ∈0.2,0.5,0.8δ∈\0.2,0.5,0.8\; blue denotes the unprompted condition and orange the prompted condition. Each curve is the pointwise empirical lower δ-quantile of −log2PM(z∣y,H≤ty,EOT)- _2P_M(z y,H^y_≤ t,EOT), without a computational charge. Stars mark the minimizing t’s in the generated-thought Kt~ Kt objective for the rollouts defining the displayed empirical quantiles. Acceleration v.s. Steering: Figure 2 evaluates the cohort positive at all three marked quantiles under both cost conventions. For several cases, the generated-thought value is positive while the prefix-prefill value is close to zero. This attenuation is consistent with the prompt primarily accelerating computation that the unprompted model can recover by using a longer thinking prefix once that prefix is charged only at the cheaper prefill rate. In other cases, a substantial advantage persists under prefix-prefill accounting. Together with the description-length curves in Figure 1, this persistence suggests that, the gain is not explained solely by avoiding sequential thinking. It is instead consistent with the prompt steering the model toward a state that assigns greater probability to the artifact. Figure 2: Prompt-value profiles for the cohort positive at all three marked quantiles under generated-thought accounting (solid green) and prefix-prefill accounting (dashed purple), with cdec=32c_dec=32. Circles and squares mark δ∈0.2,0.5,0.8δ∈\0.2,0.5,0.8\, and positive values favor the prompted condition. The green and purple shaded regions are the corresponding pointwise envelopes over the sampled cdec∈[8,256]c_dec∈[8,256] grid; they are cost-sensitivity envelopes, not confidence bands. Vertical scales vary by panel. A correct partial solution need not be valuable. Under the default generated-thought convention, the first reference step has positive estimated value at all three marked quantiles in six of the twelve cases. Figure 3 shows that, among the remaining six, the effects range from harmful to negligible or mixed. This is not surprising: a correct step from a human reference solution was not designed as an optimal prompt for this model and may be redundant or induce an unfavorable continuation. Correctness of the supplied reasoning therefore does not by itself imply positive prompt value. Prompt value is distribution-dependent. Several generated-thought profiles in Figure 3 cross zero as δ varies, and the crossings occur in both directions. The same prompt can therefore help one part of the rollout distribution while hurting another, so its value at the median need not describe its effect elsewhere in the distribution. Reporting prompt value as a function of δ, rather than at a single quantile, makes this heterogeneity visible. Figure 3: Prompt-value profiles for the remaining six problems under generated-thought accounting (solid green) and prefix-prefill accounting (dashed purple), with cdec=32c_dec=32. Circles and squares mark δ∈0.2,0.5,0.8δ∈\0.2,0.5,0.8\, and positive values favor the prompted condition. The green and purple shaded regions are the corresponding pointwise envelopes over the sampled cdec∈[8,256]c_dec∈[8,256] grid; they are cost-sensitivity envelopes, not confidence bands. Vertical scales vary by panel. 7 Related work Algorithmic information, resource bounds, and compression. Our starting point is Kolmogorov’s classical notion of algorithmic information [18, 36]; see [21] for a modern treatment. A second classical ingredient is a-priori complexity: For a universal prefix machine U, let mU(x)m_U(x) denote the probability that U outputs x when its input bits are sampled uniformly. Levin’s coding theorem identifies −log2mU(x)- _2m_U(x), up to an additive constant, with the prefix-free Kolmogorov complexity of x [36, 21]. Thus two classical views of complexity—the length of a shortest prefix-free program and the negative logarithm of universal generation probability—agree up to an additive constant. Our program-based and a-priori LLM-relative notions instantiate these two classical views for a fixed model, and the relationship between them established in Theorem 2.6 is the corresponding fixed-model analogue of the coding theorem. To incorporate computation, we draw on Levin’s KtKt complexity, which combines program length with the logarithm of running time [20]. The use of next-symbol probabilities from neural language models for lossless compression predates modern LLMs [29]; recent LLM-based examples include [33, 9]. Probabilistic and randomized Kolmogorov complexity. Our pKt~Mκ pKt^κ_M is the model-relative analog of a line of work on Kolmogorov complexity “relative to a random tape”. In particular, Goldberg, Kabanets, Lu and Oliveira define the probabilistic time-bounded Kolmogorov complexity pKδt(x)pK^t_δ(x) by pKδt(x)=mink:Prr[Kt(x∣r)≤k]≥δ,pK^t_δ(x)= \k: _r\! [K^t(x r)≤ k ]≥δ \, where the probability is over the random tape r [11]. Thus, pKδt(x)pK^t_δ(x) is simply the δ-quantile of the random variable Kt(x∣r)K^t(x r). Equivalently, one first fixes the random tape, then computes the shortest description relative to that tape, and finally takes a δ-quantile over the randomness. One may regard the realized thought HyH^y as generated from an underlying uniformly random tape r. Under this representation, our definition has exactly the same structure as pKδtpK^t_δ; our specializations are that the reference machine is the LLM rather than a universal Turing machine, and that we use the a-priori companion of KtKt complexity in place of KtK^t. This notion is to be contrasted with randomized Kolmogorov complexity rKtrK^t [26], where the program is fixed before the randomness and must succeed with high probability over it; perhaps surprisingly, this notion is less amenable for our purposes. PMI and prompt scoring. As mentioned, the likelihood-ratio expression log2PM(z∣p)/PM(z) _2P_M(z p)/P_M(z) obtained in our non-thinking prompt value has the exact algebraic form of pointwise mutual information (PMI); PMI originates in classical information theory with Fano [10] and was popularized in computational linguistics by Church and Hanks as a measure of association between particular word pairs [6]. As discussed, Xie et al. study the closely related problem of measuring human contribution in AI-assisted content generation [35]. For a human input x and LLM output string y, they define “self-information” and “conditional self-information” by I(y)=−logpθ(y)I(y)=- p_θ(y) and I(y∣x)=−logpθ(y∣x)I(y x)=- p_θ(y x), and use the normalized “contribution score” ϕ=(I(y)−I(y∣x))/I(y)φ= (I(y)-I(y x) )/I(y). The unnormalized numerator I(y)−I(y∣x)=log(pθ(y∣x)/pθ(y))I(y)-I(y x)= (p_θ(y x)/p_θ(y) ) is exactly PMI and thus coincides with the no-thinking case of our framework. Sorensen et al. use Shannon mutual information to select prompt templates, maximizing mutual information between task inputs and model outputs over an unlabeled evaluation distribution [32]. Their objective ranks templates by averaging across task instances, whereas ours measures the value of a particular prompt for producing a particular artifact. Relationship with watermarking schemes. The view that sampling randomness can be coupled to generated text has precedents in language-model watermarking, where distribution-preserving and cryptographic schemes map random keys or streams through autoregressive samplers [19, 5]. Our dyadic-program construction is not a watermarking method, but it uses the same basic fact that an autoregressive model together with a random real determines a generated string. Value of information, costly computation, and AI economics. Classical value-of-information theory measures the improvement in expected utility obtained from observing a signal [16], while work on bounded rationality treats computation itself as costly [28]. Our approach follows most directly the value of computational information perspective of Halpern and Pass [13, 14]. In their framework, an explicit utility function evaluates both the action (i.e., the outcome) produced and the computation used to produce it; information may therefore be valuable not only because it improves the outcome, but also because it saves computation. Our measure specializes this perspective to a fixed LLM M and fixed artifact z: rather than assigning an external utility to z, it measures how much the prompt reduces the model-relative cost of producing z. Our comparison between what can be produced with and without the prompt also follows the simulation paradigm underlying zero-knowledge proofs [12]. Halpern and Pass relate this perspective to their framework for valuing computational information and conversation, notably through the notion of precise zero knowledge introduced by Micali and Pass [27, 13]. Their framework gives a general, utility-dependent characterization of when information is valuable, but its evaluation involves optimizing expected utility over possible algorithms and it does not provide a general efficient estimator. Our fixed-model notion is narrower, but this narrowing is what enables efficiently estimability. More broadly, our work is motivated by the question of where human value lies as AI makes “creation” cheap. Catalini, Hui, and Wu provide a complementary answer, emphasizing human verification—the scarce capacity to check, audit, and assume responsibility for AI-generated outputs [2]. We focus on another form of human contribution: providing an input that helps the model produce an artifact, and ask how the value of that input can be measured. 8 Conclusions and Future Work We defined an LLM-relative prompt value that credits both changes in artifact likelihood and reductions in required thinking, showed how to estimate its quantiles from sampled routes, and gave it an operational reproduction-cost interpretation. The GSM8K illustration shows that a non-thinking likelihood comparison can reverse once thinking is admitted, and that the resulting value depends both on the rollout quantile and on how thinking is costed. The value of conversation. Our framework values a single prompt supplied in a fixed context. For a realized multi-turn conversation, one can apply the measure sequentially, valuing each human input conditional on the transcript at which it arrives and summing the resulting increments. This provides an ex post accounting of the realized contributions. It does not, however, account for the computation used to formulate those inputs or for the adaptivity of the human’s strategy, and therefore need not capture the value of access to the underlying conversational policy. Halpern and Pass address this more general question by specifying an interactive Turing machine that conducts the conversation [13]. That approach is less suitable in our setting, where the evaluator generally observes the human’s messages but has no description of the adaptive policy that produced them. Defining and measuring the value of adaptive human contributions under such limited access is an intriguing open question. The value of an artifact. Our framework measures the value of a prompt for producing a declared artifact. A related question is whether it can help evaluate the artifact itself. The unprompted quantity pKt~M,δκ(z∣ϵ) pKt^κ_M,δ(z ε) measures how difficult z is for the reference LLM to produce, but this cannot by itself be interpreted as the artifact’s value: a random string may have high production difficulty while having no substantive value. One possible direction is semantic re-randomization: apply a declared, prompt-independent procedure—for example, instruct another LLM to rewrite z while preserving its meaning—and compute the unprompted complexity of the resulting rewrite. One might aggregate this quantity over several independent rewrites, with the hope that semantically inert details disappear while the difficulty of the underlying content remains. We leave an exploration of this for future work. 9 Acknowledgments I am very grateful to Noam Mazor for helpful discussions. As mentioned above, I am also very grateful to ChatGPT and Claude for extensive discussions, drafting, editing, reviewing and, notably, implementing all the experiments. References [ABK+06] E. Allender, H. Buhrman, M. Koucký, D. van Melkebeek, and D. Ronneburger (2006) Power from random strings. SIAM Journal on Computing 35 (6), p. 1467–1493. Cited by: §1.1. [CHW26] C. Catalini, X. Hui, and J. Wu (2026) Some simple economics of AGI. Note: MIT Sloan Research Paper External Links: 2602.20946, Document, Link Cited by: §7. [CHA66] G. J. Chaitin (1966) On the length of programs for computing finite binary sequences. Journal of the ACM 13 (4), p. 547–569. Cited by: §1.1. [CHE52] H. Chernoff (1952) A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics 23 (4), p. 493–507. External Links: Document Cited by: footnote 7. [CGZ24] M. Christ, S. Gunn, and O. Zamir (2024) Undetectable watermarks for language models. In Proceedings of COLT, Cited by: §7. [CH90] K. W. Church and P. Hanks (1990) Word association norms, mutual information, and lexicography. Computational Linguistics 16 (1), p. 22–29. Cited by: §1.1, §2, §7. [CKB+21] K. Cobbe, V. Kosaraju, M. Bavarian, M. Chen, H. Jun, L. Kaiser, M. Plappert, J. Tworek, J. Hilton, R. Nakano, C. Hesse, and J. Schulman (2021) Training verifiers to solve math word problems. External Links: 2110.14168 Cited by: §6. [DEE25] DeepSeek-AI (2025) DeepSeek-R1: incentivizing reasoning capability in LLMs via reinforcement learning. External Links: 2501.12948, Link Cited by: §6. [DRD+24] G. Delétang, A. Ruoss, P. Duquenne, E. Catt, T. Genewein, C. Mattern, J. Grau-Moya, L. K. Wenliang, M. Aitchison, L. Orseau, M. Hutter, and J. Veness (2024) Language modeling is compression. In Proceedings of ICLR, Cited by: §7. [FAN61] R. M. Fano (1961) Transmission of information: a statistical theory of communications. MIT Press. Cited by: §1.1, §2, §7. [GKL+22] H. Goldberg, V. Kabanets, Z. Lu, and I. C. Oliveira (2022) Probabilistic Kolmogorov complexity with applications to average-case complexity. In 37th Computational Complexity Conference (C 2022), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 234, p. 16:1–16:60. External Links: Document, Link Cited by: §1.1, §3.3, §7. [GMR89] S. Goldwasser, S. Micali, and C. Rackoff (1989) The knowledge complexity of interactive proof systems. SIAM Journal on Computing 18 (1), p. 186–208. External Links: Document Cited by: §1, §7. [HP11] J. Y. Halpern and R. Pass (2011) I don’t want to think about it now: decision theory with costly computation. External Links: 1106.2657, Document, Link Cited by: §1, §7, §7, §8. [HP15] J. Y. Halpern and R. Pass (2015) Algorithmic rationality: game theory with costly computation. Journal of Economic Theory 156, p. 246–268. External Links: Document Cited by: §1, §7. [HAR83] J. Hartmanis (1983) Generalized Kolmogorov complexity and the structure of feasible computations. In Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS), p. 439–445. Cited by: §1.1. [HOW66] R. A. Howard (1966) Information value theory. IEEE Transactions on Systems Science and Cybernetics 2 (1), p. 22–26. Cited by: §7. [KO86] K. Ko (1986) On the notion of infinite pseudorandom sequences. Theoretical Computer Science 48, p. 9–33. Cited by: §1.1. [KOL65] A. N. Kolmogorov (1965) Three approaches to the quantitative definition of information. Problems of Information Transmission 1 (1), p. 1–7. Cited by: §1.1, §1.1, §7. [KTH+24] R. Kuditipudi, J. Thickstun, T. Hashimoto, and P. Liang (2024) Robust distortion-free watermarks for language models. Transactions on Machine Learning Research. External Links: Link Cited by: §7. [LEV73] L. A. Levin (1973) Universal sequential search problems. Problems of Information Transmission 9 (3), p. 265–266. Cited by: §1.1, §1.1, §3.2, §3.2, §7. [LV08] M. Li and P. Vitányi (2008) An introduction to Kolmogorov complexity and its applications. Third edition, Springer. Cited by: §1.1, §1.1, §2, §7. [LP20] Y. Liu and R. Pass (2020) On one-way functions and Kolmogorov complexity. In Proceedings of the 61st IEEE Symposium on Foundations of Computer Science (FOCS), p. 1243–1254. Cited by: §1.1. [LP21] Y. Liu and R. Pass (2021) On the possibility of basing cryptography on ≠ EXP≠ BPP. In Advances in Cryptology – CRYPTO 2021, p. 11–40. Cited by: §1.1. [LP23] Y. Liu and R. Pass (2023) One-way functions and hardness of (probabilistic) time-bounded Kolmogorov complexity w.r.t. samplable distributions. In Advances in Cryptology—CRYPTO 2023, p. 645–673. Cited by: §1.1. [LM93] L. Longpré and S. Mocas (1993) Symmetry of information and one-way functions. Information Processing Letters 46 (2), p. 95–100. Cited by: Remark 2.7. [LOS21] Z. Lu, I. C. Oliveira, and R. Santhanam (2021) Pseudodeterministic algorithms and the structure of probabilistic time. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, p. 303–316. External Links: Document, Link Cited by: §7. [MP06] S. Micali and R. Pass (2006) Local zero knowledge. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, STOC ’06, p. 306–315. External Links: Document Cited by: §7. [RW91] S. Russell and E. Wefald (1991) Do the right thing: studies in limited rationality. MIT Press. Cited by: §7. [SH96] J. Schmidhuber and S. Heil (1996) Sequential neural text compression. IEEE Transactions on Neural Networks 7 (1), p. 142–146. External Links: Document Cited by: §7. [SIP83] M. Sipser (1983) A complexity theoretic approach to randomness. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC), p. 330–335. Cited by: §1.1. [SOL64] R. J. Solomonoff (1964) A formal theory of inductive inference, part I. Information and Control 7 (1), p. 1–22. Cited by: §1.1. [SRR+22] T. Sorensen, J. Robinson, C. Rytting, A. Shaw, K. Rogers, A. Delorey, M. Khalil, N. Fulda, and D. Wingate (2022) An information-theoretic approach to prompt engineering without ground truth labels. In Proceedings of ACL, Cited by: §7. [VNK+23] C. S. K. Valmeekam, K. Narayanan, D. Kalathil, J. Chamberland, and S. Shakkottai (2023) LLMZip: lossless text compression using large language models. arXiv preprint arXiv:2306.04050. External Links: Link Cited by: §7. [WNC87] I. H. Witten, R. M. Neal, and J. G. Cleary (1987) Arithmetic coding for data compression. Communications of the ACM 30 (6), p. 520–540. Cited by: §2, footnote 3. [XQY+26] Y. Xie, T. Qi, J. Yi, X. Yang, R. Whalen, J. Huang, Q. Ding, Y. Xie, X. Xie, and F. Wu (2026) Measuring human contribution in AI-assisted content generation. In Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), San Diego, California, United States, p. 6168–6190. External Links: Document, Link Cited by: §1.1, §1.1, §2, §6.1, §7. [ZL70] A. K. Zvonkin and L. A. Levin (1970) The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russian Mathematical Surveys 25 (6), p. 83–124. Cited by: §1.1, §1.1, §2, §2, §7. Appendix A Proof of Theorem 2.6 We start with two simple facts about dyadic subintervals. Lemma A.1 (Dyadic subinterval lemma). Every half-open interval J=[a,b)⊆[0,1)J=[a,b) [0,1) of positive length ℓ=b−a =b-a contains a dyadic interval DπD_π of length greater than ℓ/4 /4. Proof. Let j≥0j≥ 0 be the largest integer such that 2−j>ℓ22^-j> 2 and set s:=2−(j+1)s:=2^-(j+1). By maximality of j, s≤ℓ2s≤ 2 while 2s=2−j>ℓ/22s=2^-j> /2, so s>ℓ4s> 4. Now let k:=⌈a/s⌉k:= a/s . Then ks≥aandks<a+s.ks≥ a ks<a+s. Hence (k+1)s<a+2s≤a+ℓ=b.(k+1)s<a+2s≤ a+ =b. Therefore [ks,(k+1)s)⊆[a,b).[ks,(k+1)s) [a,b). Moreover, (k+1)s<b≤1(k+1)s<b≤ 1, so 0≤k<2j+10≤ k<2^j+1; hence k has a (j+1)(j+1)-bit representation π and [ks,(k+1)s)=Dπ[ks,(k+1)s)=D_π. This is a dyadic interval of length s>ℓ/4s> /4. ∎ Lemma A.2 (Dyadic interval bound). Let J=[a,b)⊆[0,1)J=[a,b) [0,1) be a half-open interval of positive length |J|=b−a|J|=b-a. Define K(J):=min|π|:Dπ⊆JK(J):= \|π|:D_π J\. Then −log2|J|≤K(J)<−log2|J|+2.- _2|J|\;≤\;K(J)\;<\;- _2|J|+2. (22) Proof. For the lower bound, suppose Dπ⊆JD_π J. Then 2−|π|=|Dπ|≤|J|2^-|π|=|D_π|≤|J|; taking −log2- _2 gives |π|≥−log2|J||π|≥- _2|J|. Since this holds for every valid π, it holds for K(J)K(J). For the upper bound, Lemma A.1 gives a dyadic interval Dπ⊆JD_π J with |Dπ|>|J|/4|D_π|>|J|/4, hence 2−|π|>|J|⋅2−22^-|π|>|J|· 2^-2; taking −log2- _2 gives |π|<−log2|J|+2|π|<- _2|J|+2, and therefore K(J)≤|π|<−log2|J|+2K(J)≤|π|<- _2|J|+2. ∎ Returning to the Proof of Theorem 2.6 Proof of Theorem 2.6. For part (i), fix a context y and write q:=PM(z∣y)>0q:=P_M(z y)>0. By (8), the interval J:=Iy(z)J:=I_y(z) has length q, and by Definition 2.3, KM(z∣y)=K(J)K_M(z y)=K(J). Lemma A.2 gives −log2q≤KM(z∣y)<−log2q+2,- _2q\;≤\;K_M(z y)\;<\;- _2q+2, and adding log2q _2q throughout yields 0≤KM(z∣y)+log2q<20≤ K_M(z y)+ _2q<2, which is (15). For part (i), by part (i), there is, for each context y, a number γy(z)∈[0,2) _y(z)∈[0,2) such that KM(z∣y)=−log2PM(z∣y)+γy(z)K_M(z y)=- _2P_M(z y)+ _y(z). Therefore ValM(p,z)=Val~M(p,z)+γϵ(z)−γp(z),Val_M(p;z)= Val_M(p;z)+ _ε(z)- _p(z), and the difference of two numbers in [0,2)[0,2) lies in (−2,2)(-2,2), proving (16). ∎