Search papers, labs, and topics across Lattice.
This paper introduces a novel approach to quantifying the value of prompts in the context of large language models (LLMs) using a probabilistic Levin鈥揔olmogorov complexity framework. By defining prompt value as algorithmic mutual information relative to LLMs, the authors demonstrate that a prompt with \(b\) bits of value can significantly ease the generation of an artifact \(z\), either by enhancing its sampling probability or reducing the computational effort required. The key finding reveals that the median token cost for reproducing \(z\) without the prompt is \(2^b\) times higher than with it, offering a concrete measure of prompt effectiveness.
A prompt's value can exponentially reduce the cost of generating complex artifacts, revealing a new dimension of efficiency in LLM interactions.
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.
