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

What the math gives to ML

The paper provides a principled way to measure prompt value as the reduction in resource-bounded description complexity of a target artifact, rather than merely measuring likelihood under one decoding run. Its transferable asset is the Levin-style probability/computation tradeoff: a prompt is useful if it increases success probability, reduces generation computation, or exchanges one for the other by a quantifiable number of bits. This suggests a prompt-selection and training objective that scores prompts by paired reductions in artifact-generation cost across compute budgets, with token-level likelihood used as a cheap estimator and actual reproduction trials used for calibration. The main limitation is that the extracted mathematics does not include the paper's full pKt estimator, so the proposed implementation uses the displayed time-bounded complexity definition and an explicit empirical surrogate.