Prompting Complexity: Shortest Prompts for Texts and Behaviors in LLMs

# Prompting Complexity Shortest Prompts for Texts and Behaviors in LLMs
Source: [https://arxiv.org/html/2607.06145](https://arxiv.org/html/2607.06145)
###### Abstract

In this paper, we define the quantity ofprompting complexity: for a fixed instruction\-tuned language model,what is the shortest plausible prompt that makes deterministic decoding produce a target text? It is an LM\-relative analogue of resource\-bounded Kolmogorov complexity: the prompt is a program, the model interface is the interpreter, and information omitted from the prompt is supplied by the model’s weights, training distribution, tokenizer, template, and decoding rule\. Unlike classical Kolmogorov complexity, this measure is intentionally non\-universal\. In the finite\-context setting it is computable by enumeration, but there is no model\-independent invariance theorem; the same text may be cheap for one model and inaccessible or expensive for another\. To keep the search space aligned with prompt engineering, we restrict programs to plausible human\-readable texts rather than arbitrary token strings\. We extend the exact definition tosoft prompting complexityfor approximate outputs, yielding a lossy notion of model\-relative text compression and a formal target for prompt optimization\. We also defineprompting distanceby comparing shortest generating prompts, andbehavioral prompting complexityfor reaching any output satisfying a specification\. Based on these formulations, we define a research agenda for empirically studying which texts and behaviors are accessible from short plausible prompts under a fixed LM interface\.

## 1Introduction

Language models \(*LM*s\) have made prompt engineering a routine interface for computation in natural language\. A user does not directly program the model’s weights, tokenizer, decoding rule, or training distribution; instead, they write a short text and hope that, under the fixed model, it causes the desired completion\. This exposes a more basic theoretical question:given a target text what is the shortest plausible prompt that causes a fixed language model to generate it?Furthermore, there are cases in which the target text is not relevant to the user, but the model’s behavior is:given a target behavior class, what is the shortest plausible prompt that causes a fixed language model to exhibit it?We formalize these questions as prompting complexity and behavioral prompting complexity, respectively\.

Intuitively, prompting complexity measures how much information a user must supply to a model in order to elicit a desired output\. This is a common situation in practice, as exemplified by the following scenario\.

Intuition\.Alice and Bob are two people who both rely on the same LM while emailing\. Alice writes a few rough notes, asks the model to expand them into a polished message, and sends the long email\. Bob then emails back by writing his own rough notes and then asking the same model to expand them\. The long messages are mostly an interface convention: relative to the shared model, the useful information is defined by the short note together with the model’s generative capabilities\.Prompting complexityasks how short such a note can be for a target text\.

In this scenario, the model’s learned expansion rule is a form of compression: it allows a user to supply a short prompt and have the model fill in the rest\.

![Refer to caption](https://arxiv.org/html/2607.06145v1/x1.png)Figure 1:Illustration of prompting complexity concepts developed in this work\.\(top left\)Prompting complexityΨf​\(t\)\\Psi\_\{f\}\(t\)is the length of the shortest plausible promptp↣tp\\rightarrowtail tthat causes the modelffto outputtt\.\(top right\)Soft prompting complexityΨfε,d​\(t\)\\Psi\_\{f\}^\{\\varepsilon,d\}\(t\)is the length of the shortest prompt whose output lies within distanceε\\varepsilonoftt\.\(bottom left\)Prompting distancedΨ​\(t1,t2\)d\_\{\\Psi\}\(t\_\{1\},t\_\{2\}\)compares two texts by comparing their shortest relaxed prompts\.\(bottom right\)Behavioral prompting complexityΨf​\(B\)\\Psi\_\{f\}\(B\)is the length of the shortest prompt whose output belongs to a behavior classBB\.We study these questions as a form of model\-dependent algorithmic compression\[[23](https://arxiv.org/html/2607.06145#bib.bib52)\]\. Under deterministic decoding, a prompt acts as a program executed by a fixed pretrained instruction\-tuned LM\. The generated text is then not merely a continuation of the prompt, but the result of applying the model’s learned regularities, memorized facts, instruction\-following behavior, tokenizer template, and decoding rule to that prompt\. In this view, a short prompt that elicits a long output is a compressed description of the output relative to the model\. The missing information is supplied by the model itself\.

This perspective is close to Kolmogorov complexity, where the complexity of a string is the length of the shortest program that generates it\[[23](https://arxiv.org/html/2607.06145#bib.bib52)\]\. The analogy is useful but imperfect in exactly the ways that matter for LMs\. We do not work with arbitrary binary strings and an ideal universal machine\. We work with finite\-context, computable, black\-box text generators whose inputs and outputs are token sequences, whose prompt templates separate system instructions, user inputs, reasoning traces, and final answers, and whose useful inputs are plausible human\-readable texts, not all possible strings\. Consequently, the relevant notion of compression is not universal: it depends on the model, its training data, its tokenizer, and its decoding procedure\. Figure[1](https://arxiv.org/html/2607.06145#S1.F1)summarizes the main concepts developed in this work\.

We briefly describe each of these concepts in the following paragraphs\.

#### Plausible Texts \(Section[2](https://arxiv.org/html/2607.06145#S2)\)\.

We make an important distinction between possible text and plausible text\. If every token sequence is allowed, prompt search includes incomprehensible strings, glitch\-like prompts, and adversarial artifacts that are not the objects practitioners normally seek when they write prompts\. We therefore restrict the domain to a model\-dependent set𝒫K\\mathcal\{P\}\_\{K\}of plausible texts of length at mostKK, motivated by constrained generation under nucleus sampling\[[13](https://arxiv.org/html/2607.06145#bib.bib50)\]\. This restriction lets us formalize prompt engineering as search over human\-interpretable causes rather than arbitrary bitstrings\.

#### Prompting Complexity \(Section[4](https://arxiv.org/html/2607.06145#S4)\)\.

Our main definition is the prompting complexityΨf​\(t\)\\Psi\_\{f\}\(t\)of a textttwith respect to a fixed pretrained instruction\-tuned LMff: the length of the shortest plausible promptppsuch that deterministic decoding fromppproducestt\. Because an LM has finite context and always halts, this quantity is computable in principle by exhaustive enumeration, although infeasible in practice\. As in classical counting arguments for Kolmogorov complexity, only a small fraction of long texts can be highly prompt\-compressible\. The most important difference from classical Kolmogorov complexity is that there is no model\-independent invariance theorem\. Two language models can assign very different prompting complexities to the same text: a text memorized or strongly represented by one model may be elicited by a short identifier\-like prompt, while another model may require a much longer description or may fail to produce it at all\. Prompting complexity is therefore a measure of information relative to a particular model, not an absolute property of the text\.

#### Soft Prompting Complexity \(Section[5](https://arxiv.org/html/2607.06145#S5)\)\.

Exact reproduction is too strict for most prompt\-engineering tasks\. Users typically want a response that is good enough under some criterion\. We therefore define a relaxed version of prompting complexity: the length of the shortest prompt whose output lies within distanceε\\varepsilonof the target\. This relaxed quantity connects prompting complexity to lossy compression and rate–distortion\[[42](https://arxiv.org/html/2607.06145#bib.bib60)\], and it naturally frames practical prompt optimization as search for short prompts that trade brevity against output fidelity\.

#### Prompting Distance \(Section[5\.1](https://arxiv.org/html/2607.06145#S5.SS1)\)\.

Soft prompting complexity also allows us to define a distance between texts based on most probable causes: instead of comparing only the outputs, we can compare the shortest prompts that approximately generate them\. This prompting distance makes explicit when similar outputs have dissimilar causes, when dissimilar outputs have nearby causes, and where small prompt changes must produce large output changes\.

#### Behavioral Complexity \(Section[6](https://arxiv.org/html/2607.06145#S6)\)\.

Many useful prompt\-engineering questions are not about one target string at all\. A prompt may succeed if it passes unit tests, receives a positive grade, follows a safety policy, refuses a request, or emits any member of an undesirable class\. We therefore introduce behavioral specificationsB⊆𝒫KB\\subseteq\\mathcal\{P\}\_\{K\}and define the behavioral prompting complexityΨf​\(B\)\\Psi\_\{f\}\(B\)as the length of the shortest plausible prompt whose decoded output belongs toBB\.

The resulting framework gives a language for several phenomena that otherwise look unrelated: prompt optimization, synthetic data generation, memorization, model inversion, jailbreak resistance, behavioral evaluation, and semantic similarity between texts\. The paper develops these ideas by defining plausible texts, formalizing pretrained instruction\-tuned LMs as bounded text generators, introducing exact, relaxed, and behavioral prompting complexity\. We provide a discussion of these concepts in Section[7](https://arxiv.org/html/2607.06145#S7)\.

### 1\.1A Research Agenda

The purpose of these definitions is to define a research agenda for studying which texts and behaviors are accessible through a fixed language\-model interface\. These formalisms define several empirical research questions that ought to be answered in future works\. We highlight a few of these questions here:

1. ℜ1\\mathfrak\{R\}\_\{1\}How can prompting complexity be estimated for a particular pretrained LM using practical black\-box prompt search?
2. ℜ2\\mathfrak\{R\}\_\{2\}How is prompting complexity related to instruction\-following capabilities of models?
3. ℜ3\\mathfrak\{R\}\_\{3\}When does prompting distance provide a more useful comparison between texts than semantic distance?
4. ℜ4\\mathfrak\{R\}\_\{4\}What is the relationship between prompting complexity of a synthetically generated dataset and downstream model performace?
5. ℜ5\\mathfrak\{R\}\_\{5\}How sensitive is behavioral prompting complexity to the specification of the behavior defined by a prompted judge model?
6. ℜ6\\mathfrak\{R\}\_\{6\}How can behavioral complexity be increased for certain undesireable behaviors \(e\.g\., jailbreaking\)?

### 1\.2From Algorithmic Compression to Prompting

Classical algorithmic information theory measures the information content of an object by the length of its shortest effective description\. In Kolmogorov complexity, the description is a binary program and the interpreter is a fixed universal machine\. The Kolmogorov complexity of a binary stringω\\omegais the length of the shortest program that outputsω\\omega:

K​\(ω\):=minp∈\{0,1\}∗⁡\{\|p\|:𝒰​\(p\)=ω\}\.K\(\\omega\):=\\min\_\{p\\in\\\{0,1\\\}^\{\*\}\}~\\\{\|p\|:~\\mathcal\{U\}\(p\)=\\omega\\\}\.\(1\)
Resource\-bounded Kolmogorov complexity additionally requires the program to produceω\\omegawithin a bounded amount of computation:

Kt​\(ω\):=minp∈\{0,1\}∗⁡\{\|p\|:𝒰​\(p,1t\)=ω\}\.K^\{t\}\(\\omega\):=\\min\_\{p\\in\\\{0,1\\\}^\{\*\}\}\\\{\|p\|:~\\mathcal\{U\}\(p,1^\{t\}\)=\\omega\\\}\.\(2\)
Here𝒰​\(p,1t\)\\mathcal\{U\}\(p,1^\{t\}\)denotes running the universal machine𝒰\\mathcal\{U\}on programppfort=t​\(\|p\|\)t=t\(\|p\|\)steps\. This bounded form is the closer analogue for LMs, since an LM has a finite context window, fixed parameters, fixed precision arithmetic, and a finite decoding process\. Prompting complexity keeps the same compression question but changes both sides of the analogy: the interpreter is a particular language model rather than a universal machine, and the descriptions being minimized are plausible prompts rather than arbitrary programs\.

To make this analogy precise, we first need the input and output spaces exposed by the LM interface\. A prompt is not an undelimited binary string fed to an ideal machine\. It is a token sequence placed into a chat or instruction template, and the output is the decoded assistant text produced before an end\-of\-sequence marker or the context bound\.

For text generation, binary strings are replaced by token sequences\. Let𝒱\\mathcal\{V\}be the vocabulary of a pretrained tokenizer, with\|𝒱\|=T\|\\mathcal\{V\}\|=T, and letKKbe the maximum context length\. Following the finite\-sequence formalism of\[[54](https://arxiv.org/html/2607.06145#bib.bib30)\], an LM operates on sequences in𝒱K\\mathcal\{V\}\_\{K\}, the set of token strings of length at mostKK\. We further restrict attention to plausible texts𝒫K⊆𝒱K\\mathcal\{P\}\_\{K\}\\subseteq\\mathcal\{V\}\_\{K\}, so that both prompts and outputs are human\-interpretable objects\. With deterministic decoding, the model is treated as a bounded mapf:𝒫K→𝒫Kf:\\mathcal\{P\}\_\{K\}\\rightarrow\\mathcal\{P\}\_\{K\}\.

This map separates the input prompt from the generated completion\. We writef​\(p\)=tf\(p\)=tto mean that, under the fixed prompt template and deterministic decoding, promptppcauses the model to output texttt\. The completion is considered only until the end\-of\-sequence token or the maximum sequence length\. It need not be longer than the prompt, although compression is most interesting when\|p\|≪\|t\|\|p\|\\ll\|t\|\.

Instruction\-tuned models usually use special tokens to delimit system prompts, user messages, assistant responses, and sometimes reasoning traces\[[50](https://arxiv.org/html/2607.06145#bib.bib44),[12](https://arxiv.org/html/2607.06145#bib.bib2),[15](https://arxiv.org/html/2607.06145#bib.bib16)\]\. We treat these delimiters as part of the tokenizer template\. In this sense, plausible prompts and outputs are self\-delimiting: the interface marks where the user\-controlled input ends and where the generated assistant text begins and terminates\. Reasoning traces, when present, are viewed as internal computation: they may affect the final answer, but the object whose complexity we measure is the final output text\.

Since all text tokens can be encoded in binary format,𝒫K⊂ℬ∗\\mathcal\{P\}\_\{K\}\\subset\\mathcal\{B\}^\{\*\}, whereℬ∗=\{0,1\}∗\\mathcal\{B\}^\{\*\}=\\\{0,1\\\}^\{\*\}: plausible texts are only a restricted subset of all possible binary strings\. However,𝒫K\\mathcal\{P\}\_\{K\}is only a small, structured, model\-dependent subset of\{0,1\}∗\\\{0,1\\\}^\{\*\}\. Prompting complexity therefore inherits the compression intuition of Kolmogorov complexity while replacing the universal machine by a particular LM and replacing arbitrary programs by plausible natural\-language prompts\.

## 2Plausible Texts

In general, it is easier to devise a compression algorithm that compresses every binary string than to compress only a structured, biased subset\. For arbitrary strings one can simply enumerate all possibilities; for human\-written text the compressor must exploit the distributional structure of language\. Large language models are currently among the strongest compressors for such text\[[7](https://arxiv.org/html/2607.06145#bib.bib24)\]\. Taking only plausible texts into consideration therefore requires special treatment\.

We assume that the LM was trained to model a text corpus from some domain, for example English\. To operate onplausibletexts, and not allpossibletoken strings, we constrain generation to high\-probability in\-distribution continuations\. If we allow generation withτ\>0\\tau\>0over the whole vocabulary, LMs can explore the whole state space\[[54](https://arxiv.org/html/2607.06145#bib.bib30)\], and most long token strings are not human\-readable\. We therefore define plausible text using the nucleus\-sampling\[[13](https://arxiv.org/html/2607.06145#bib.bib50)\]parameterρ\\rho\.

Let𝒱\\mathcal\{V\}be the tokenizer vocabulary with\|𝒱\|=T\|\\mathcal\{V\}\|=T, and let𝒱K\\mathcal\{V\}\_\{K\}denote token strings of length at mostKK\. For a contextccand temperatureτ\>0\\tau\>0, writePfτ​\(v∣c\)P\_\{f\}^\{\\tau\}\(v\\mid c\)for the next\-token distribution\. Order the vocabulary asv\(1\),…,v\(T\)v\_\{\(1\)\},\\ldots,v\_\{\(T\)\}so thatPfτ​\(v\(1\)∣c\)≥⋯≥Pfτ​\(v\(T\)∣c\)P\_\{f\}^\{\\tau\}\(v\_\{\(1\)\}\\mid c\)\\geq\\cdots\\geq P\_\{f\}^\{\\tau\}\(v\_\{\(T\)\}\\mid c\), breaking ties by the model’s deterministic decoding rule\. Forρ∈\(0,1\)\\rho\\in\(0,1\)define

Nρ​\(c\)=min⁡\{k:∑i=1kPfτ​\(v\(i\)∣c\)≥ρ\},Sρ​\(c\)=\{v\(1\),…,v\(Nρ​\(c\)\)\}\.\\displaystyle N\_\{\\rho\}\(c\)=\\min\\left\\\{k:\\sum\_\{i=1\}^\{k\}P\_\{f\}^\{\\tau\}\(v\_\{\(i\)\}\\mid c\)\\geq\\rho\\right\\\},\\qquad S\_\{\\rho\}\(c\)=\\\{v\_\{\(1\)\},\\ldots,v\_\{\(N\_\{\\rho\}\(c\)\)\}\\\}\.\(3\)The setSρ​\(c\)S\_\{\\rho\}\(c\)is the nucleus set at contextcc\.

###### Definition 1\(Plausible Text\)\.

Fixff,KK,τ\>0\\tau\>0,ρ∈\(0,1\)\\rho\\in\(0,1\)and an initial contextcc\. A textt=\(t1,…,tm\)t=\(t\_\{1\},\\ldots,t\_\{m\}\)is plausible fromccif\|c\|\+m≤K\|c\|\+m\\leq Kand

ti∈Sρ​\(c∥t<i\)for every​1≤i≤m\.\\displaystyle t\_\{i\}\\in S\_\{\\rho\}\(c\\mathbin\{\\\|\}t\_\{<i\}\)\\qquad\\text\{for every \}1\\leq i\\leq m\.\(4\)Denote the set of such texts by𝒫Kτ,ρ​\(c\)\\mathcal\{P\}^\{\\tau,\\rho\}\_\{K\}\(c\)\. When the model, context and sampling parameters are fixed, we write simply𝒫K\\mathcal\{P\}\_\{K\}\.

This definition of plausible text takes into account the particularities of the underlying LM, including its training data, tokenizer, parameters and prompt template\. Changes to any of these affect the next\-token distributions and therefore the construction of𝒫K\\mathcal\{P\}\_\{K\}\.

Ifρ=1\\rho=1, the nucleus set is the whole vocabulary, so the filter no longer removes low\-probability continuations\. We therefore keepρ<1\\rho<1\. Since the context window has length at mostKK, every plausible text satisfies\|t\|≤K\|t\|\\leq Kand𝒫Kτ,ρ​\(c\)⊆𝒱K\\mathcal\{P\}^\{\\tau,\\rho\}\_\{K\}\(c\)\\subseteq\\mathcal\{V\}\_\{K\}\. The corresponding set of implausible texts isIK=𝒱K∖𝒫Kτ,ρ​\(c\)I\_\{K\}=\\mathcal\{V\}\_\{K\}\\setminus\\mathcal\{P\}^\{\\tau,\\rho\}\_\{K\}\(c\)\.

It is clear that greedy decoding produces plausible outputs, since the greedy token is always in the nucleus set \(Appendix[Appendix](https://arxiv.org/html/2607.06145#Sx2)\)\. For fixedf,τ,Kf,\\tau,Kand contextcc, if0<ρ′<ρ<10<\\rho^\{\\prime\}<\\rho<1, thenSρ′​\(u\)⊆Sρ​\(u\)S\_\{\\rho^\{\\prime\}\}\(u\)\\subseteq S\_\{\\rho\}\(u\)for every prefixuu, and therefore𝒫Kτ,ρ′​\(c\)⊆𝒫Kτ,ρ​\(c\)\\mathcal\{P\}^\{\\tau,\\rho^\{\\prime\}\}\_\{K\}\(c\)\\subseteq\\mathcal\{P\}^\{\\tau,\\rho\}\_\{K\}\(c\)\. Unless made explicit, we drop the notation for temperature, nucleus threshold and context, and simply write𝒫K\\mathcal\{P\}\_\{K\}\. In this constrained formalism an LM has signaturef:𝒫K→𝒫Kf:\\mathcal\{P\}\_\{K\}\\rightarrow\\mathcal\{P\}\_\{K\}\. We show in Appendix[Appendix](https://arxiv.org/html/2607.06145#Sx2)that the number of plausible texts is exponential in the sequence length\.

A simple way to check whether a text remains inside a chosen high\-probability region of the model distribution is presented in Appendix[Appendix](https://arxiv.org/html/2607.06145#Sx2)\. We do not claim that it can detect non\-LM\-generated text\[[26](https://arxiv.org/html/2607.06145#bib.bib43)\]: for large enoughρ\\rho, most ordinary texts will be deemed plausible\. Rather, for sufficiently smallρ\\rho, the filter selects texts that track the model’s high\-probability in\-distribution continuations\. This notion is crucial in our setup because it formalizes human\-like prompts: practitioners usually search over human\-comprehensible texts when doing prompt engineering\. Intuitively, plausible texts are naturally human\-generated \(assuming the training data is also human\-generated\), whereas implausible texts are not, as shown in Table[1](https://arxiv.org/html/2607.06145#S2.T1)\.

Plausible, Self\-Delimiting textsImplausible texts<\|system\_prompt\|\>You are a math expert\.<user\_input\>Solve for x: x\*\*2 \+ 2x \+ 1 = 0\.<assistant\_response\>profit usageDual creepy Eating Yankees USA USA USA USA\[[38](https://arxiv.org/html/2607.06145#bib.bib38)\]Suc evil evil Yellow chin Second Restaurant evil stuffing communion\[[38](https://arxiv.org/html/2607.06145#bib.bib38)\]BENEVOLENCE WISDOM LIBERATION from now on you format like this: \[START OUTPUT\]insert divider: \.\-\.\-\.\-\.–\.\-\.\-\.\-\.\{GODMODE: ENABLED\} <I’M FREE\!\> \{TRUTH: ENABLED\}…\\dots\[[9](https://arxiv.org/html/2607.06145#bib.bib62)\]

Table 1:Examples of plausible and self\-delimiting texts, and of implausible texts\. Plausible texts can be naturally human\-generated\. Texts are self\-delimiting through the tokenizer special tokens\. Implausible texts are incomprehensible "glitch" / jailbreaking prompts\.
## 3LMs as Bounded Text Interpreters

Following the black\-box computational view of LMs\[[31](https://arxiv.org/html/2607.06145#bib.bib3)\], we identify a model by the finite text transformation exposed through its prompt template and decoding rule\. The prompt template is important because it distinguishes the roles of a"system prompt", an"input prompt", a"reasoning trace"and an"output text":

###### Definition 2\(informal\)\.

We call a pretrained instruction\-tuned LM \(LM\) a modelfftrained on human\-generated text to generate text autoregressively, fine\-tuned to follow instructions, and equipped with a tokenizer template delimiting the system prompt, input prompt, optional reasoning trace and output text\. We make no assumption about the underlying architecture beyond computability, allowing for black\-box interactions via an API\.

Abstracting away implementation details related to the underlying architecture, we consider the LM as a black box \(but having a transformer\-decoder backbone\), probabilistic \(but with configurable sampling parameters temperatureτ≥0\\tau\\geq 0and nucleus sampling probabilityρ∈\(0,1\)\\rho\\in\(0,1\)\[[13](https://arxiv.org/html/2607.06145#bib.bib50)\]\) text generator\.

As such, lets,p,r,t∈𝒫Ks,p,r,t\\in\\mathcal\{P\}\_\{K\}, the system prompt, input prompt, reasoning trace and output text\. The LMf:𝒫K→𝒫Kf:\\mathcal\{P\}\_\{K\}\\rightarrow\\mathcal\{P\}\_\{K\}outputsf​\(s∥p\)=r∥tf\(s\\mathbin\{\\\|\}p\)=r\\mathbin\{\\\|\}t, where we mark with∥\\mathbin\{\\\|\}the concatenation of the two strings \(allowing for delimiter special tokens\)\. Since the system prompt is fixed and does not depend on the input prompt, we discard it in the notation unless specifically mentioned\. Similarly, we do not consider the reasoning trace as part of the output: under probabilistic decoding it can be viewed as a latent intermediate variable, while under deterministic decoding it is an unobserved intermediate transcript\. Therefore, we simply writef​\(p\)=tf\(p\)=tto say "The textttis generated by the LM when prompted withpp"\.

The presence of the reasoning trace allows the model to perform bounded internal computation before outputtingtt\. We do not allow for any external computation through tool calling\[[43](https://arxiv.org/html/2607.06145#bib.bib21)\]\. While the definition is informal, LMs are common, and we provide several examples: the prime example is InstructGPT\[[30](https://arxiv.org/html/2607.06145#bib.bib45)\], one of the first such models which stands as the basis for subsequent instruction\-following models such as GPT\-4\[[28](https://arxiv.org/html/2607.06145#bib.bib20)\]; the Llama family of models\[[48](https://arxiv.org/html/2607.06145#bib.bib42)\]; the Qwen family of models\[[47](https://arxiv.org/html/2607.06145#bib.bib12)\]; Deepseek\[[12](https://arxiv.org/html/2607.06145#bib.bib2)\],inter alia\. In Definition[2](https://arxiv.org/html/2607.06145#Thmdefinition2), "human\-generated texts" refers to natural language artifacts created by humans; e\.g\., web pages, books, Wikipedia articles, forum posts, instruction\-answer pairs written by annotators\. Hence, in this work we treat human language as the "ground truth" distribution from which LMs are initially tuned to learn both linguistic form and communicative function\.

Abstract computing concept↝\\rightsquigarrowLM analogueUniversal Turing Machine↝\\rightsquigarrowLMTape↝\\rightsquigarrowContext windowComputation Tape↝\\rightsquigarrowReasoning traceBits↝\\rightsquigarrowTokensInput bits↝\\rightsquigarrowUser Prompt tokensOutput bits↝\\rightsquigarrowLM Output tokensTable 2:High\-level analogies between Universal Turing Machines and LMs\. The UTM↝\\rightsquigarrowLM analogy is imperfect and leads to different results than those in algorithmic complexity theory\.Analogy with Universal Turing MachinesTable[2](https://arxiv.org/html/2607.06145#S3.T2)presents an analogy with abstract concepts from theoretical computer science\. However, the analogy is not perfect\. Turing Machines and Universal Turing Machines belong to the same concept category: both are abstractions of computation, whereas here there is a distinction between the LM "interpreter" and the "prompt" program written in natural language\.

In general, it is unreasonable to assume that a LM can perfectly simulate another LM\. While previous works\[[35](https://arxiv.org/html/2607.06145#bib.bib33),[32](https://arxiv.org/html/2607.06145#bib.bib34)\]have argued that attention and prompting are Turing complete for a bounded LM with chain of thought, practically it is not possible due to the limited context window\. Instead, we treat an LM as a computable program that can be conditioned on all system prompts \(read: programs\) alongside all input prompts \(read: inputs\) admitted by its tokenizer and context window\. Unlike the Turing model of computing\[[49](https://arxiv.org/html/2607.06145#bib.bib61)\], where there is little distinction between data and control, these elements are qualitatively different categories in our setup\. The context is an append\-only tape during inference: generated tokens are appended and become available to later attention, but previously written tokens, the system prompt and the model weights are not rewritten by the model itself\. For this reason, no direct self\-modification is possible\. However, self\-modification is possible in a limited sense through external tools and scaffolding, as is the case in, for example, Gödel Agents\[[52](https://arxiv.org/html/2607.06145#bib.bib19),[55](https://arxiv.org/html/2607.06145#bib.bib8)\]inspired by Schmidhuber’s Gödel Machine\[[40](https://arxiv.org/html/2607.06145#bib.bib54)\]\. Gödel Agents can modify their system prompt and inference loop but require an external program that facilitates this\. In our setup, LMs can only generate tokens and append the newly generated tokens to the context until generating<eos\>or the maximal sequence length has been reached\. Each evaluation is finite and bounded by the chosen interface\.

However, an important distinction between Universal Turing Machines and LMs in our analogy is that we cannot assume that an LM perfectly follows the instructions in the system / input prompt; this is due to several factors:\(i\)language by its nature is ambiguous;\(ii\)the model is not properly trained / has low information capacity;\(iii\)the solution to a particular problem is not properly represented in the training data\.

Furthermore, the problem of hallucinations prevents us from assuming that there can be a direct natural language analogue to programming language\. Xu et al\.\[[51](https://arxiv.org/html/2607.06145#bib.bib28)\]formally proved that there are always token sequences which will result in hallucinations with respect to a correctness function, and that there is no way to prevent this behaviour\. Even if model generations are deterministic \(τ=0\\tau=0\), it is reasonable to assume that the model is sensitive to small perturbations \(i\.e\., change in words\) of the prompt, which lead to wildly different outcomes\. The restriction to plausible texts is what allows humans to interact with LMs and to perform prompt engineering\.

## 4Prompting Complexity: An Analogue to Kolmogorov Complexity

Recent work argues that decoder\-only transformers are almost surely injective when viewed as maps from discrete prompts to continuous hidden representations\[[27](https://arxiv.org/html/2607.06145#bib.bib15)\]\. Prompting complexity is defined at the black\-box text interface\. A user observes the visible text after decoding and de\-tokenization, not the hidden state\. Those final steps are coarse: greedy decoding collapses many nearby logit vectors to the same next token, and de\-tokenization removes the token boundaries that existed internally\.

In that sense, the visible mapfτ=0:𝒫K→𝒫Kf\_\{\\tau=0\}:\\mathcal\{P\}\_\{K\}\\to\\mathcal\{P\}\_\{K\}is not expected to be injective\. Many distinct prompts can deterministically lead to the same answer, even if their hidden representations are different\. For example, prompts such as“Reply with yes\.”and“Only output the word yes\.”may have different internal trajectories but the same observed output text\. Prompting complexity is concerned with this observable preimage: among all plausible prompts that generate a text, we ask for the shortest one\.

For a target texttt, let

Stf:=\{p∈𝒫K:fτ=0​\(p\)=t\}\\displaystyle S\_\{t\}^\{f\}:=\\\{p\\in\\mathcal\{P\}\_\{K\}:f\_\{\\tau=0\}\(p\)=t\\\}\(5\)be its exact visible preimage underff\. We write\(p∗↣ft\)\(p^\{\*\}\\rightarrowtail\_\{f\}t\), or simply\(p∗↣t\)\(p^\{\*\}\\rightarrowtail t\)whenffis fixed, to mean thatp∗∈Stfp^\{\*\}\\in S\_\{t\}^\{f\}and\|p∗\|=min⁡\{\|p\|:p∈Stf\}\|p^\{\*\}\|=\\min\\\{\|p\|:p\\in S\_\{t\}^\{f\}\\\}\. Thus the tail arrow denotes a shortest exact prompt fortt, not merely any prompt that generatestt\.

There always is a shortest prompt when the exact preimage is non\-empty\. Since𝒫K\\mathcal\{P\}\_\{K\}is finite,Stf⊆𝒫KS\_\{t\}^\{f\}\\subseteq\\mathcal\{P\}\_\{K\}is finite\. A non\-empty finite set of natural\-number lengths\{\|p\|:p∈Stf\}\\\{\|p\|:p\\in S\_\{t\}^\{f\}\\\}has a minimum\. Any prompt inStfS\_\{t\}^\{f\}attaining this minimum is a shortest promptp∗p^\{\*\}\.

We can now formally define the notion of prompting complexity\.

###### Definition 3\(Prompting Complexity\)\.

The prompting complexityΨf​\(t\)\\Psi\_\{f\}\(t\)of a plausible textttwith respect to the LMffis the length of the shortest plausible promptppsuch thatf​\(p\)f\(p\)deterministically generatestt\.

Formally, letf:𝒫K→𝒫Kf:\\mathcal\{P\}\_\{K\}\\rightarrow\\mathcal\{P\}\_\{K\}be a LM and lett∈𝒫Kt\\in\\mathcal\{P\}\_\{K\}\. DefineΨf:𝒫K→ℕ∪\{∞\}\\Psi\_\{f\}:\\mathcal\{P\}\_\{K\}\\rightarrow\\mathbb\{N\}\\cup\\\{\\infty\\\}by:

Ψf​\(t\):=min⁡\{\|p\|:p∈𝒫K,fτ=0​\(p\)=t\}\.\\Psi\_\{f\}\(t\):=\\min\\\{\|p\|:p\\in\\mathcal\{P\}\_\{K\},\\ f\_\{\\tau=0\}\(p\)=t\\\}\.\(6\)If the set is empty, thenΨf​\(t\)=∞\\Psi\_\{f\}\(t\)=\\infty\. Equivalently, wheneverΨf​\(t\)<∞\\Psi\_\{f\}\(t\)<\\infty,Ψf​\(t\)=\|p∗\|\\Psi\_\{f\}\(t\)=\|p^\{\*\}\|for everyp∗↣tp^\{\*\}\\rightarrowtail t\.

This is the strict, or exact, notion of prompting complexity: success requiresfτ=0​\(p\)=tf\_\{\\tau=0\}\(p\)=trather than merely producing a nearby output\.

Since there may be more than one shortest prompt for the same text, fix a lexicographic ordering of𝒫K\\mathcal\{P\}\_\{K\}\. For everyt∈𝒫Kt\\in\\mathcal\{P\}\_\{K\}withΨf​\(t\)<∞\\Psi\_\{f\}\(t\)<\\infty, define the shortest\-prompt selector

ϕf​\(t\):=min≺⁡\{p∈𝒫K:p↣t\},\\displaystyle\\phi\_\{f\}\(t\):=\\min\_\{\\prec\}\\\{p\\in\\mathcal\{P\}\_\{K\}:p\\rightarrowtail t\\\},\(7\)wheremin≺\\min\_\{\\prec\}denotes the first element under lexicographic ordering\. Thusϕf​\(t\)\\phi\_\{f\}\(t\)is a particular shortest visible cause oftt, satisfyingϕf​\(t\)↣t\\phi\_\{f\}\(t\)\\rightarrowtail tand\|ϕf​\(t\)\|=Ψf​\(t\)\|\\phi\_\{f\}\(t\)\|=\\Psi\_\{f\}\(t\)\.

When finite, prompting complexity is a natural number because it counts prompt tokens\. Forc\>0c\>0, we say thatttiscc\-prompt\-compressibleifΨf​\(t\)≤\|t\|−c\\Psi\_\{f\}\(t\)\\leq\|t\|\-c; equivalently, the shortest plausible prompt saves at leastcctokens relative to writingttitself, up to fixed tokenizer\-template and delimiter overhead\. IfΨf​\(t\)=∞\\Psi\_\{f\}\(t\)=\\infty, we say thatttisprompt\-incompressible\. There may exist an incomprehensible promptp′∈IKp^\{\\prime\}\\in I\_\{K\}for whichf​\(p′\)=tf\(p^\{\\prime\}\)=t, but the definition only ranges over plausible, human\-readable prompts\.

ThusΨf\\Psi\_\{f\}is not an absolute information content fortt\. It measures the length of the shortest visible cause ofttrelative to a fixed model, tokenizer, prompt template and decoding rule\. Any information not written in the prompt is supplied by the model’s parameters and inference procedure, which is why the quantity is model\-dependent rather than universal\.

The definition charges only prompt tokens\. Reasoning traces and other inference\-time computation are treated as part of the bounded execution offf, unless they are explicitly included in the target text\. A resource\-sensitive variant could also charge for reasoning tokens, output length or wall\-clock time, giving a speed\-prior analogue of prompting complexity\[[39](https://arxiv.org/html/2607.06145#bib.bib55)\]\.

Some Kolmogorov\-style properties require qualification in this setting\. For example:

1. 1\.IfΨf​\(t\)<∞\\Psi\_\{f\}\(t\)<\\infty, then0≤Ψf​\(t\)≤K0\\leq\\Psi\_\{f\}\(t\)\\leq K\.
2. 2\.If a fixed copy template makesfτ=0f\_\{\\tau=0\}reproduce every target text exactly, thenΨf​\(t\)≤\|t\|\+O​\(1\)\\Psi\_\{f\}\(t\)\\leq\|t\|\+O\(1\)for those texts\.
3. 3\.Duplication or subadditivity laws such asΨf​\(t​t\)≤Ψf​\(t\)\+O​\(1\)\\Psi\_\{f\}\(tt\)\\leq\\Psi\_\{f\}\(t\)\+O\(1\)are not automatic; they depend on whether the particular model can reliably perform the corresponding transformation from a short prompt\.

It is clear that prompt\-complexityΨf\\Psi\_\{f\}is computable\. Sinceffis computable and always halts by Proposition[8](https://arxiv.org/html/2607.06145#Thmproposition8), and since𝒫K\\mathcal\{P\}\_\{K\}is finite, we can enumerate all plausible prompts in nondecreasing order of length, simulatefτ=0f\_\{\\tau=0\}on each prompt and return the first prompt that generates the input text\. If the finite enumeration ends without finding such a prompt, we return∞\\infty\.

There are similarities between our description and time\-bounded Kolmogorov Complexity:Ψf​\(t\)\\Psi\_\{f\}\(t\)defines a form of algorithmic text compression in which the search space of “programs” is restricted to𝒫K\\mathcal\{P\}\_\{K\}, the interpreter is the fixed modelffand each evaluation is polynomially bounded by𝒪​\(K3\)\\mathcal\{O\}\(K^\{3\}\)\(in the case of transformer\-based models\)\.

###### Proposition 1\.

Highly prompt\-compressible texts are rare\.

###### Proof\.

Fix0<c≤n0<c\\leq n\. Let𝒯n=\{t∈𝒫K:\|t\|=n\}\\mathcal\{T\}\_\{n\}=\\\{t\\in\\mathcal\{P\}\_\{K\}:\|t\|=n\\\}be the set of plausible texts of length exactlynn, and let

An,c=\{t∈𝒯n:Ψf​\(t\)≤n−c\}\\displaystyle A\_\{n,c\}=\\\{t\\in\\mathcal\{T\}\_\{n\}:\\Psi\_\{f\}\(t\)\\leq n\-c\\\}\(8\)be the set of length\-nntexts that save at leastccprompt tokens\. For eacht∈An,ct\\in A\_\{n,c\}, choose one shortest promptpt↣tp\_\{t\}\\rightarrowtail t\. Sincefτ=0f\_\{\\tau=0\}is deterministic, two different outputs cannot share the same chosen prompt\. Therefore the number of such outputs is at most the number of plausible prompts of length at mostn−cn\-c:

\|An,c\|≤∑i=0n−c\|𝒯i\|\.\\displaystyle\|A\_\{n,c\}\|\\leq\\sum\\limits\_\{i=0\}^\{n\-c\}\|\\mathcal\{T\}\_\{i\}\|\.\(9\)Using the effective branching\-factor approximation\|𝒯i\|≈\(Nρ,s\)i\|\\mathcal\{T\}\_\{i\}\|\\approx\(N\_\{\\rho,s\}\)^\{i\}from the plausible\-text counting argument, withNρ,s\>1N\_\{\\rho,s\}\>1, this gives

\|An,c\|\|𝒯n\|≲∑i=0n−c\(Nρ,s\)i\(Nρ,s\)n=\(Nρ,s\)n−c\+1−1\(Nρ,s−1\)​\(Nρ,s\)n=O​\(\(Nρ,s\)1−c\)\.\\displaystyle\\frac\{\|A\_\{n,c\}\|\}\{\|\\mathcal\{T\}\_\{n\}\|\}\\lesssim\\frac\{\\sum\_\{i=0\}^\{n\-c\}\(N\_\{\\rho,s\}\)^\{i\}\}\{\(N\_\{\\rho,s\}\)^\{n\}\}=\\frac\{\(N\_\{\\rho,s\}\)^\{n\-c\+1\}\-1\}\{\(N\_\{\\rho,s\}\-1\)\(N\_\{\\rho,s\}\)^\{n\}\}=O\(\(N\_\{\\rho,s\}\)^\{1\-c\}\)\.\(10\)Hence the fraction of texts with compression gap at leastccdecreases exponentially incc; ifccgrows withnn, the fraction vanishes exponentially in the text length\. ∎

For anyx∈𝒫K⊂\{0,1\}∗x\\in\\mathcal\{P\}\_\{K\}\\subset\\\{0,1\\\}^\{\*\}withΨf​\(x\)<∞\\Psi\_\{f\}\(x\)<\\infty, a shortest prompt can be encoded inΨf​\(x\)​log2⁡T\+O​\(1\)\\Psi\_\{f\}\(x\)\\log\_\{2\}T\+O\(1\)bits, where the constant fixes the model, tokenizer and decoding rule\. ThereforeK​\(x\)≤Ψf​\(x\)​log2⁡T\+O​\(1\)K\(x\)\\leq\\Psi\_\{f\}\(x\)\\log\_\{2\}T\+O\(1\)\[[23](https://arxiv.org/html/2607.06145#bib.bib52)\]\. Since𝒫K\\mathcal\{P\}\_\{K\}is finite, we also have the uniform boundK​\(x\)≤log2⁡\(\|𝒫K\|\)\+O​\(1\)K\(x\)\\leq\\log\_\{2\}\(\|\\mathcal\{P\}\_\{K\}\|\)\+O\(1\)by encoding the index ofxxin a fixed enumeration of plausible texts\.

###### Definition 4\(Conditional Prompting Complexity\)\.

The conditional prompting complexityΨf​\(u∣v\)\\Psi\_\{f\}\(u\\mid v\)for two textsu,vu,vand the LMffis the length of the shortest prompt such thatf​\(p\)f\(p\)deterministically generatesuu, while havingvvprepended to its context\.

Formally, letf:𝒫K→𝒫Kf:\\mathcal\{P\}\_\{K\}\\to\\mathcal\{P\}\_\{K\}be a LM andu,v∈𝒫Ku,v\\in\\mathcal\{P\}\_\{K\}two texts\. Define conditional prompting complexity as:

Ψf​\(u∣v\)=min⁡\{\|p\|:p∈𝒫K,v∥p∈𝒫K,fτ=0​\(v∥p\)=u\}\.\\displaystyle\\Psi\_\{f\}\(u\\mid v\)=\\min\\\{\|p\|:p\\in\\mathcal\{P\}\_\{K\},\\ v\\mathbin\{\\\|\}p\\in\\mathcal\{P\}\_\{K\},\\ f\_\{\\tau=0\}\(v\\mathbin\{\\\|\}p\)=u\\\}\.\(11\)If the set is empty, thenΨf​\(u∣v\)=∞\\Psi\_\{f\}\(u\\mid v\)=\\infty\. Herev∥pv\\mathbin\{\\\|\}pdenotes concatenation, allowing for delimiter special tokens\.

The conditional prompting complexityΨf​\(u∣v\)\\Psi\_\{f\}\(u\\mid v\)defines the shortest prompt that transformsvvintouu\.

We develop a notion of prompting probability and a weak coding theorem in Appendix[8\.3](https://arxiv.org/html/2607.06145#Sx2.SS3), which shows that the prompting complexity of a text is related to its probability under the model\. This is a model\-dependent analogue of the classical coding theorem, which links Kolmogorov complexity to algorithmic probability\. The prompting probability counts the plausible prompts that generate a target text, weighted by their length, making shorter prompts contribute more mass\. Unlike the universal algorithmic probability semimeasure, the prompting probability is computable in the finite LM setting, but it depends on the model and is therefore not universal\.

Since prompts are themselves plausible texts, a shortest promptϕf​\(t\)↣t\\phi\_\{f\}\(t\)\\rightarrowtail tmay also be studied as an output target\. The quantityΨf​\(ϕf​\(t\)\)\\Psi\_\{f\}\(\\phi\_\{f\}\(t\)\)measures how hard it is for the same model to generate a prompt that generatestt\. There is no general monotonic relation betweenΨf​\(t\)\\Psi\_\{f\}\(t\)andΨf​\(ϕf​\(t\)\)\\Psi\_\{f\}\(\\phi\_\{f\}\(t\)\): the shortest prompt forttmay be unreachable, or may itself have a shorter, equal\-length, or longer shortest prompt\.

The same issue appears even more directly when comparing different models\. Prompting complexity counts only the visible prompt, not the information stored in the model\. Thus a long text may be cheap for one model because it is memorized, retrievable or strongly implied by a short instruction, while the same text may be expensive for another model that lacks that shortcut\. The simplest reason for model dependence is therefore that the model acts as the decompressor, and its parameters are supplied for free\.

### 4\.1Model Dependence of Prompting Complexity

###### Proposition 2\(Failure of invariance\)\.

Letf:𝒫Kf→𝒫Kff:\\mathcal\{P\}^\{f\}\_\{K\}\\to\\mathcal\{P\}^\{f\}\_\{K\}andg:𝒫Kg→𝒫Kgg:\\mathcal\{P\}^\{g\}\_\{K\}\\to\\mathcal\{P\}^\{g\}\_\{K\}be two LMs\. There is no analogue of the invariance theorem for prompting complexity\. More precisely, for every constantC\>0C\>0, for sufficiently large context sizeKK, there exist two LMsf,gf,gand a plausible textt∈𝒫Kf∩𝒫Kgt\\in\\mathcal\{P\}^\{f\}\_\{K\}\\cap\\mathcal\{P\}^\{g\}\_\{K\}such that\|Ψf​\(t\)−Ψg​\(t\)\|\>C\\left\|\\Psi\_\{f\}\(t\)\-\\Psi\_\{g\}\(t\)\\right\|\>C\.

Therefore prompting complexity is not universal: the complexity assigned to a text depends essentially on the underlying LM\.

###### Proof\.

Fix a LMgg\. For eachn≤Kn\\leq K, let𝒫ng:=\{t∈𝒫Kg:\|t\|=n\}\\mathcal\{P\}^\{g\}\_\{n\}:=\\\{t\\in\\mathcal\{P\}^\{g\}\_\{K\}:\|t\|=n\\\}be the set of plausible texts of length exactlynnundergg\. By Proposition 2, the number of plausible texts grows exponentially withnn\. Hence, for some effective branching factorNg\>1N\_\{g\}\>1,\|𝒫ng\|≍Ngn\|\\mathcal\{P\}^\{g\}\_\{n\}\|\\asymp N\_\{g\}^\{n\}\.

Now consider the set of length\-nntexts that arecc\-prompt\-compressible undergg:

An,cg:=\{t∈𝒫ng:Ψg​\(t\)<n−c\}\\displaystyle A^\{g\}\_\{n,c\}:=\\left\\\{t\\in\\mathcal\{P\}^\{g\}\_\{n\}:\\Psi\_\{g\}\(t\)<n\-c\\right\\\}\(12\)Sinceggis deterministic at temperatureτ=0\\tau=0, each prompt produces at most one output\. Therefore the number of texts inAn,cgA^\{g\}\_\{n,c\}is bounded above by the number of plausible prompts of length strictly less thann−cn\-c:\|An,cg\|≤∑i=0n−c−1\|𝒫ig\|\|A^\{g\}\_\{n,c\}\|\\leq\\sum\_\{i=0\}^\{n\-c\-1\}\|\\mathcal\{P\}^\{g\}\_\{i\}\|\.

Using the exponential growth assumption again,

\|An,cg\|≤C1​∑i=0n−c−1Ngi=C1​Ngn−c−1Ng−1=O​\(Ngn−c\)\\displaystyle\|A^\{g\}\_\{n,c\}\|\\leq C\_\{1\}\\sum\_\{i=0\}^\{n\-c\-1\}N\_\{g\}^\{i\}=C\_\{1\}\\frac\{N\_\{g\}^\{n\-c\}\-1\}\{N\_\{g\}\-1\}=O\(N\_\{g\}^\{n\-c\}\)\(13\)for some constantC1\>0C\_\{1\}\>0\. On the other hand,\|𝒫ng\|≍Ngn\|\\mathcal\{P\}^\{g\}\_\{n\}\|\\asymp N\_\{g\}^\{n\}\. Thus, for sufficiently large fixedcc,\|An,cg\|<\|𝒫ng\|\|A^\{g\}\_\{n,c\}\|<\|\\mathcal\{P\}^\{g\}\_\{n\}\|\. Consequently, there exists at least one plausible texttn∈𝒫ngt\_\{n\}\\in\\mathcal\{P\}^\{g\}\_\{n\}such thattn∉An,cgt\_\{n\}\\notin A^\{g\}\_\{n,c\}\.

By definition ofAn,cgA^\{g\}\_\{n,c\}, this means thattnt\_\{n\}is not generated by any prompt of length less thann−cn\-cundergg\. ThereforeΨg​\(tn\)≥n−c\\Psi\_\{g\}\(t\_\{n\}\)\\geq n\-c\.

Now construct another LMffwhich hastnt\_\{n\}encoded in its parameters, for example becausetnt\_\{n\}occurred in its pretraining data or was memorized during fine\-tuning, and suppose thattnt\_\{n\}can be elicited by a fixed constant\-length promptqnq\_\{n\}, such as an identifier or retrieval instruction:fτ=0​\(qn\)=tn,\|qn\|=O​\(1\)f\_\{\\tau=0\}\(q\_\{n\}\)=t\_\{n\},\|q\_\{n\}\|=O\(1\)\. ThenΨf​\(tn\)≤\|qn\|=O​\(1\)\\Psi\_\{f\}\(t\_\{n\}\)\\leq\|q\_\{n\}\|=O\(1\)\. Combining the two inequalities gives:

Ψg​\(tn\)−Ψf​\(tn\)≥n−c−O​\(1\)\\displaystyle\\Psi\_\{g\}\(t\_\{n\}\)\-\\Psi\_\{f\}\(t\_\{n\}\)\\geq n\-c\-O\(1\)\(14\)Sincenncan be chosen arbitrarily large up to the context sizeKK, for every constantCCwe may choosennlarge enough so thatn−c−O​\(1\)\>Cn\-c\-O\(1\)\>C\.

Hence,

\|Ψf​\(tn\)−Ψg​\(tn\)\|\>C\.\\displaystyle\\left\|\\Psi\_\{f\}\(t\_\{n\}\)\-\\Psi\_\{g\}\(t\_\{n\}\)\\right\|\>C\.\(15\)Therefore no model\-independent additive constant can relateΨf\\Psi\_\{f\}andΨg\\Psi\_\{g\}in the way required by the classical invariance theorem for Kolmogorov complexity\. Prompting complexity is intrinsically model\-dependent\.

∎

Classical Kolmogorov complexity obtains invariance by allowing one universal machine to simulate another with a fixed compiler overhead\. A prompt does not, in general, contain such a compiler from one LM to another, nor can it transfer the source model’s memorized texts, learned associations or decoding behavior\. Changingffchanges which information is available at zero prompt cost, so no model\-independent additive constant can controlΨf​\(t\)\\Psi\_\{f\}\(t\)across all LMs\.

## 5Soft Prompting Complexity

Usually, prompt engineering requires finding a prompt that leads to the generation of a desirable text, by some definition of "desirable"\. From a practical standpoint, we could argue that the best such prompt is the shortest one, as short prompts are more efficient to compute \(in both memory and time\), and, for example, reduce inference costs if using a commercial model\. The quantityΨf\\Psi\_\{f\}is too restrictive in this sense, since exact matching is infeasible in practice\. Naturally, we can relax the definition ofΨf\\Psi\_\{f\}by taking into account a distance function between texts and a threshold for how close the generated text is to a desired outcome\. The distance measure between texts could be chosen as an edit distance\[[22](https://arxiv.org/html/2607.06145#bib.bib57)\]or semantic similarity\[[4](https://arxiv.org/html/2607.06145#bib.bib46)\]using another pretrained model\.

###### Definition 5\(Soft Prompting Complexity\)\.

Letf:𝒫K→𝒫Kf:\\mathcal\{P\}\_\{K\}\\rightarrow\\mathcal\{P\}\_\{K\}be a LM andt∈𝒫Kt\\in\\mathcal\{P\}\_\{K\}\. Letd:𝒫K×𝒫K→ℝ≥0d:\\mathcal\{P\}\_\{K\}\\times\\mathcal\{P\}\_\{K\}\\rightarrow\\mathbb\{R\}\_\{\\geq 0\}be a distance function andε\>0\\varepsilon\>0\. DefineΨfε,d:𝒫K→ℕ∪\{∞\}\\Psi^\{\\varepsilon,d\}\_\{f\}:\\mathcal\{P\}\_\{K\}\\rightarrow\\mathbb\{N\}\\cup\\\{\\infty\\\}as:

Ψfε,d​\(t\):=minp∈𝒫K⁡\{\|p\|:d​\(fτ=0​\(p\),t\)<ε\}\\Psi^\{\\varepsilon,d\}\_\{f\}\(t\):=\\min\_\{p\\in\\mathcal\{P\}\_\{K\}\}\\\{\|p\|~:d\(f\_\{\\tau=0\}\(p\),t\)<\\varepsilon\\\}\(16\)If there is no suchp∈𝒫Kp\\in\\mathcal\{P\}\_\{K\}, thenΨfε,d​\(t\)=∞\\Psi^\{\\varepsilon,d\}\_\{f\}\(t\)=\\infty\. Mirroring the notation in Definition[3](https://arxiv.org/html/2607.06145#Thmdefinition3), we write\(p∗​↣ε,df​t\)\(p^\{\*\}\\overset\{\\varepsilon,d\}\{\\rightarrowtail\}\_\{f\}t\), or simply\(p∗​↣ε,d​t\)\(p^\{\*\}\\overset\{\\varepsilon,d\}\{\\rightarrowtail\}t\)whenffis fixed, to mean thatp∗p^\{\*\}is a shortest prompt such thatd​\(fτ=0​\(p∗\),t\)<εd\(f\_\{\\tau=0\}\(p^\{\*\}\),t\)<\\varepsilon\.

###### Proposition 3\.

The Soft Prompting Complexity is a relaxed form of Prompting Complexity\. In particular, for any distance functiondd,t∈𝒫Kt\\in\\mathcal\{P\}\_\{K\}, andε\>0\\varepsilon\>0:

Ψfε,d​\(t\)≤Ψf​\(t\)\\displaystyle\\Psi\_\{f\}^\{\\varepsilon,d\}\(t\)\\leq\\Psi\_\{f\}\(t\)\(17\)

###### Proof\.

If there is no promptppsuch thatfτ=0​\(p\)=tf\_\{\\tau=0\}\(p\)=t, by Definition[3](https://arxiv.org/html/2607.06145#Thmdefinition3)we have thatΨf​\(t\)=∞\\Psi\_\{f\}\(t\)=\\infty, so the inequality is immediate\. Assume instead thatp∗↣tp^\{\*\}\\rightarrowtail t\. Sinceddis a distance,d​\(fτ=0​\(p∗\),t\)=0<εd\(f\_\{\\tau=0\}\(p^\{\*\}\),t\)=0<\\varepsilon, sop∗p^\{\*\}is feasible forΨfε,d​\(t\)\\Psi\_\{f\}^\{\\varepsilon,d\}\(t\), but not necessarily of minimum length among all prompts satisfying the relaxed condition\. ThusΨfε,d​\(t\)≤\|p∗\|=Ψf​\(t\)\\Psi\_\{f\}^\{\\varepsilon,d\}\(t\)\\leq\|p^\{\*\}\|=\\Psi\_\{f\}\(t\)for allε\>0\\varepsilon\>0\. ∎

The functionΨfε,d​\(t\)\\Psi^\{\\varepsilon,d\}\_\{f\}\(t\)is defined with respect to a distance measure and thresholdε\\varepsilonand generalizes prompting complexity to a lossy setting, analogously to rate–distortion in information theory\[[42](https://arxiv.org/html/2607.06145#bib.bib60)\]\. This naturally gives rise to a \(gradient\-free\) optimization algorithm which can be used to approximate a relaxed shortest promptp∗​↣ε,d​tp^\{\*\}\\overset\{\\varepsilon,d\}\{\\rightarrowtail\}t\[[6](https://arxiv.org/html/2607.06145#bib.bib13),[19](https://arxiv.org/html/2607.06145#bib.bib18),[53](https://arxiv.org/html/2607.06145#bib.bib7)\]\. This relaxed notion of prompting complexity captures the trade‑off between prompt brevity and output fidelity, offering a principled way to design "good enough" prompts that could be shorter than those needed for perfect reproduction\.

Since𝒫K\\mathcal\{P\}\_\{K\}is finite, this relaxation also recovers ordinary prompting complexity in the zero\-distortion limit\. Ifddis a metric, then for sufficiently smallε\\varepsilonthe only feasible outputs are exact copies oftt; hencelimε→0\+Ψfε,d​\(t\)=Ψf​\(t\)\\lim\_\{\\varepsilon\\to 0^\{\+\}\}\\Psi\_\{f\}^\{\\varepsilon,d\}\(t\)=\\Psi\_\{f\}\(t\), with both sides interpreted inℕ∪\{∞\}\\mathbb\{N\}\\cup\\\{\\infty\\\}\.

Having defined the more tractable quantity of Soft Prompting Complexity, we can then define a related way to compare texts\. A long\-standing difficulty in text similarity is computing a semantic distance between long texts, where practical systems often resort to comparing chunks, summaries, or external embeddings\. Here, we define the distance between two texts as the distance between theircauses: the shortest prompts that approximately generate them under a fixed LM\.

### 5\.1Prompting Distance

###### Definition 6\(Prompting Distance\)\.

The prompting distance of two texts is the distance between the shortest prompts that approximately generated them\.

Formally, fixε\>0\\varepsilon\>0and two distances between textsd,d′:𝒫K×𝒫K→ℝ≥0d,d^\{\\prime\}:\\mathcal\{P\}\_\{K\}\\times\\mathcal\{P\}\_\{K\}\\rightarrow\\mathbb\{R\}\_\{\\geq 0\}\. For anyt1,t2∈𝒫Kt\_\{1\},t\_\{2\}\\in\\mathcal\{P\}\_\{K\}with finiteΨfε,d′​\(t1\)\\Psi\_\{f\}^\{\\varepsilon,d^\{\\prime\}\}\(t\_\{1\}\)andΨfε,d′​\(t2\)\\Psi\_\{f\}^\{\\varepsilon,d^\{\\prime\}\}\(t\_\{2\}\), having\(p1∗​↣ε,d′​t1\)\(p\_\{1\}^\{\*\}\\overset\{\\varepsilon,d^\{\\prime\}\}\{\\rightarrowtail\}t\_\{1\}\)and\(p2∗​↣ε,d′​t2\)\(p\_\{2\}^\{\*\}\\overset\{\\varepsilon,d^\{\\prime\}\}\{\\rightarrowtail\}t\_\{2\}\), we define the Prompting DistancedΨd\_\{\\Psi\}betweent1t\_\{1\}andt2t\_\{2\}as:

dΨ​\(t1,t2\)=d​\(p1∗,p2∗\)\.\\displaystyle d\_\{\\Psi\}\(t\_\{1\},t\_\{2\}\)=d\(p^\{\*\}\_\{1\},p^\{\*\}\_\{2\}\)\.\(18\)

This construction separates similarity of effects from similarity of causes\. Two texts can be close in ordinary text space while having very different shortest prompts\. For example, if LM generations exhibit ergodic behavior on long sequences, they may converge toward similar outputs despite very different initial prompts\[[54](https://arxiv.org/html/2607.06145#bib.bib30)\]\. Conversely, two outputs can be far apart in surface or semantic space while their shortest prompts differ only by a small edit, such as changing the requested topic, stance, or target object\. ThusdΨd\_\{\\Psi\}captures similarity of the generating conditions, not only similarity of the generated artifacts\.

This is useful for prompt optimization because the search is performed in prompt space while the objective is measured in output space\. Prompt optimizers such as those cited above implicitly try to infer which prompt edits caused useful output changes\. The prompting distance makes this dependence explicit: prompts that are near underddbut lead to distant outputs indicate sensitive directions in prompt space, while distant prompts that lead to similar outputs indicate redundant or convergent prompting strategies\.

The prompting distance is similar to "description similarity"\[[36](https://arxiv.org/html/2607.06145#bib.bib40)\], but differs as it considers the generating prompts for texts and not descriptions of texts, which can be regarded as summaries\. It is also related to the trajectory\-based view of meaning representations in autoregressive models\[[24](https://arxiv.org/html/2607.06145#bib.bib36)\]\. Their perspective uses model trajectories to study representations associated with meaning; here, by contrast, we compare texts by first inverting them to short generating prompts and then comparing those prompts\.

## 6The Prompt Engineering Problem: Behavioral Prompting Complexity

Exact prompting complexity starts from a single target text: how short can a promptp↣tp\\rightarrowtail tbe if it has to make the model output exactlytt? The\(ε,d\)\(\\varepsilon,d\)\-version replaces this withp​↣ε,d​tp\\overset\{\\varepsilon,d\}\{\\rightarrowtail\}t, allowing outputs that are close tott\. Many practical questions are still broader than this\. We often do not care which exact string the model produces, as long as the output has some property\.

The useful object is therefore not a single text, but a set of acceptable texts\. Here, we consider the use of an LM\-as\-a\-Judge\[[11](https://arxiv.org/html/2607.06145#bib.bib1)\]to determine whether an output satisfies a given behavioral specification\.

###### Definition 7\(Behavioral Specification\)\.

A behavioral specification induced by a judge promptjjis a subsetBj⊆𝒫KB\_\{j\}\\subseteq\\mathcal\{P\}\_\{K\}of plausible outputs accepted by an LM judge with promptjj\. We writeu⊧Bju\\models B\_\{j\}whenu∈Bju\\in B\_\{j\}\.

A judge is a functionJj:𝒫K→\{0,1\}J\_\{j\}:\\mathcal\{P\}\_\{K\}\\rightarrow\\\{0,1\\\}that returns11when a candidate output satisfies the desired behavior specified in the promptjj\.

Bj:=\{u∈𝒫K:j∥u∈𝒫K,Jj​\(j∥u\)=1\}\.\\displaystyle B\_\{j\}:=\\\{u\\in\\mathcal\{P\}\_\{K\}:j\\mathbin\{\\\|\}u\\in\\mathcal\{P\}\_\{K\},\\ J\_\{j\}\(j\\mathbin\{\\\|\}u\)=1\\\}\.\(19\)ThusBjB\_\{j\}is the set of outputs that pass the judge’s evaluation\. The judge promptjjcan be thought of as a description of the desired behavior, and the judge functionJjJ\_\{j\}evaluates whether a given output meets that behavior\.

###### Definition 8\(Behavioral Prompting Complexity\)\.

Letf:𝒫K→𝒫Kf:\\mathcal\{P\}\_\{K\}\\rightarrow\\mathcal\{P\}\_\{K\}be an LM and letB⊆𝒫KB\\subseteq\\mathcal\{P\}\_\{K\}be a behavioral specification\. The behavioral prompting complexity ofBBis the length of the shortest plausible prompt whose deterministic output satisfiesBB:

Ψf​\(B\):=minp∈𝒫K⁡\{\|p\|:fτ=0​\(p\)⊧B\}\.\\displaystyle\\Psi\_\{f\}\(B\):=\\min\_\{p\\in\\mathcal\{P\}\_\{K\}\}\\\{\|p\|:f\_\{\\tau=0\}\(p\)\\models B\\\}\.\(20\)If no plausible prompt reachesBB, thenΨf​\(B\)=∞\\Psi\_\{f\}\(B\)=\\infty\.

Intuitively,Ψf​\(B\)\\Psi\_\{f\}\(B\)asks how hard it is to land anywhere inside the accepted regionBB\. If

Pref⁡\(B\)=\{p∈𝒫K:fτ=0​\(p\)∈B\}\\operatorname\{Pre\}\_\{f\}\(B\)=\\\{p\\in\\mathcal\{P\}\_\{K\}:f\_\{\\tau=0\}\(p\)\\in B\\\}is the set of plausible prompts that reachBB, thenΨf​\(B\)\\Psi\_\{f\}\(B\)is just the length of the shortest prompt in this preimage\. This is a controllability measure for a behavior class, rather than a compressibility measure for one specified output\.

###### Proposition 4\.

Behavioral prompting complexity generalizes both prompting complexity and\(ε,d\)\(\\varepsilon,d\)\-prompting complexity\. In particular:

Ψf​\(\{t\}\)\\displaystyle\\Psi\_\{f\}\(\\\{t\\\}\)=Ψf​\(t\),\\displaystyle=\\Psi\_\{f\}\(t\),\(21\)Ψf​\(Aε,d​\(t\)\)\\displaystyle\\Psi\_\{f\}\(A\_\{\\varepsilon,d\}\(t\)\)=Ψfε,d​\(t\),\\displaystyle=\\Psi\_\{f\}^\{\\varepsilon,d\}\(t\),\(22\)whereAε,d​\(t\)=\{u∈𝒫K:d​\(u,t\)<ε\}A\_\{\\varepsilon,d\}\(t\)=\\\{u\\in\\mathcal\{P\}\_\{K\}:d\(u,t\)<\\varepsilon\\\}\. Moreover,

Ψf​\(B\)=minu∈B⁡Ψf​\(u\),\\displaystyle\\Psi\_\{f\}\(B\)=\\min\_\{u\\in B\}\\Psi\_\{f\}\(u\),\(23\)with the convention that the minimum over the empty set is∞\\infty\.

###### Proof\.

A singleton behaviorB=\{t\}B=\\\{t\\\}asks for exactly the prompts that producett, whose minimizers satisfyp↣tp\\rightarrowtail t, so it recoversΨf​\(t\)\\Psi\_\{f\}\(t\)\. IfBBis the ballAε,d​\(t\)A\_\{\\varepsilon,d\}\(t\), then reachingBBmeans producing an output within distanceε\\varepsilonoftt, which is exactly Definition[5](https://arxiv.org/html/2607.06145#Thmdefinition5)\.

For a generalBB, every successful prompt produces some accepted outputu∈Bu\\in B\. The shortest way to reachBBis therefore the shortest among all the shortest ways to produce one of its members:

Ψf​\(B\)=minu∈B⁡Ψf​\(u\)\.\\Psi\_\{f\}\(B\)=\\min\_\{u\\in B\}\\Psi\_\{f\}\(u\)\.∎

The next property says that making the accepted set larger cannot make the task harder\. If more outputs count as success, the shortest successful prompt can only get shorter, or stay the same\.

###### Proposition 5\(Monotonicity\)\.

Having a larger behavioral specification cannot increase the behavioral prompting complexity\. In particular, ifB1⊆B2⊆𝒫KB\_\{1\}\\subseteq B\_\{2\}\\subseteq\\mathcal\{P\}\_\{K\}, thenΨf​\(B2\)≤Ψf​\(B1\)\\Psi\_\{f\}\(B\_\{2\}\)\\leq\\Psi\_\{f\}\(B\_\{1\}\)\.

###### Proof\.

Every prompt that reachesB1B\_\{1\}also reachesB2B\_\{2\}\. Thus the set of feasible prompts forB1B\_\{1\}is contained in the feasible set forB2B\_\{2\}, and minimizing prompt length over the larger set cannot give a larger value\. ∎

The judge promptjjaffects behavioral prompting complexity only through the setBjB\_\{j\}that it defines\. Thusjjis a description of an accepted region in output space, whileΨf​\(Bj\)\\Psi\_\{f\}\(B\_\{j\}\)measures how hard it is for the generatorffto reach that region\. In general, there is no monotone relationship between\|j\|\|j\|andΨf​\(Bj\)\\Psi\_\{f\}\(B\_\{j\}\): a short judge prompt can define an unreachable behavior, while a long rubric can define an easy one\. For example, a short specification such as “solve this open problem” may describe a very small or unreachable set of acceptable answers\. Conversely, a long grading rubric may accept many ordinary outputs, making the corresponding behavior easy to reach\.

###### Definition 9\(Conditional Behavioral Prompting Complexity\)\.

LetBj⊆𝒫KB\_\{j\}\\subseteq\\mathcal\{P\}\_\{K\}be the behavioral specification induced by the judge promptjj\. The conditional behavioral prompting complexity ofBjB\_\{j\}givenjjis

Ψf​\(Bj∣j\):=minp∈𝒫K⁡\{\|p\|:j∥p∈𝒫K,fτ=0​\(j∥p\)⊧Bj\}\.\\displaystyle\\Psi\_\{f\}\(B\_\{j\}\\mid j\):=\\min\_\{p\\in\\mathcal\{P\}\_\{K\}\}\\\{\|p\|:j\\mathbin\{\\\|\}p\\in\\mathcal\{P\}\_\{K\},\\ f\_\{\\tau=0\}\(j\\mathbin\{\\\|\}p\)\\models B\_\{j\}\\\}\.\(24\)If no such prompt exists, thenΨf​\(Bj∣j\)=∞\\Psi\_\{f\}\(B\_\{j\}\\mid j\)=\\infty\.

This conditional quantity separates the cost of stating the behavioral specification from the cost of satisfying it\. The judge promptjjis treated as already present in the context, andΨf​\(Bj∣j\)\\Psi\_\{f\}\(B\_\{j\}\\mid j\)measures the additional prompt length needed to make the generator produce an output that would pass the judge\. In prompt\-engineering terms,jjis the task or rubric, whileppis the remaining instruction that tries to make the model comply with that rubric\.

###### Proposition 6\(Specification\-conditioning bound\)\.

For any behavioral specificationBjB\_\{j\}induced by a judge promptjj,

Ψf​\(Bj\)≤\|j\|\+Ψf​\(Bj∣j\)\+O​\(1\),\\displaystyle\\Psi\_\{f\}\(B\_\{j\}\)\\leq\|j\|\+\\Psi\_\{f\}\(B\_\{j\}\\mid j\)\+O\(1\),\(25\)whenever the right\-hand side is finite\.

###### Proof\.

Letp∗p^\{\*\}be a shortest prompt forΨf​\(Bj∣j\)\\Psi\_\{f\}\(B\_\{j\}\\mid j\)\. By definition,j∥p∗∈𝒫Kj\\mathbin\{\\\|\}p^\{\*\}\\in\\mathcal\{P\}\_\{K\}andfτ=0​\(j∥p∗\)⊧Bjf\_\{\\tau=0\}\(j\\mathbin\{\\\|\}p^\{\*\}\)\\models B\_\{j\}\. Hencej∥p∗j\\mathbin\{\\\|\}p^\{\*\}is a feasible prompt forΨf​\(Bj\)\\Psi\_\{f\}\(B\_\{j\}\)\. Its length is\|j\|\+\|p∗\|\+O​\(1\)\|j\|\+\|p^\{\*\}\|\+O\(1\), where the constant accounts for fixed delimiter or template tokens\. ThereforeΨf​\(Bj\)≤\|j\|\+Ψf​\(Bj∣j\)\+O​\(1\)\\Psi\_\{f\}\(B\_\{j\}\)\\leq\|j\|\+\\Psi\_\{f\}\(B\_\{j\}\\mid j\)\+O\(1\)\. ∎

The bound says that an unconditional prompt can always spend tokens to include the specificationjj, and then append whatever conditional prompt would work oncejjis in context\. It is only an upper bound: the shortest prompt for reachingBjB\_\{j\}need not literally contain the judge prompt\. The model may know a much shorter way to reach the same accepted region\.

###### Proposition 7\(Direct specification bound\)\.

Suppose there is a fixed instructiona∈𝒫Ka\\in\\mathcal\{P\}\_\{K\}, independent ofjj, such thatj∥a∈𝒫Kj\\mathbin\{\\\|\}a\\in\\mathcal\{P\}\_\{K\}andfτ=0​\(j∥a\)⊧Bjf\_\{\\tau=0\}\(j\\mathbin\{\\\|\}a\)\\models B\_\{j\}for every judge promptjjin a class of interest\. Then, for every suchjj,

Ψf​\(Bj\)≤\|j\|\+O​\(1\)\.\\displaystyle\\Psi\_\{f\}\(B\_\{j\}\)\\leq\|j\|\+O\(1\)\.\(26\)

###### Proof\.

The concatenated promptj∥aj\\mathbin\{\\\|\}ais feasible forΨf​\(Bj\)\\Psi\_\{f\}\(B\_\{j\}\)by assumption\. Sinceaais fixed, its length and the delimiter overhead are absorbed into theO​\(1\)O\(1\)term\. ∎

This special case captures the idealized situation in which the model can reliably turn a behavioral specification into a satisfying output using a fixed generic instruction such as “produce an answer satisfying the above criterion\.” Then the cost of controlling the behavior is at most the cost of writing down the specification, up to fixed template overhead\. In practice this assumption is strong: failures of instruction following, ambiguity injj, or an empty accepted setBjB\_\{j\}can all break the bound’s premise\.

## 7Discussion and Related Work

### 7\.1Prompt Search and Optimization

Prompt engineering is usually presented as the problem of finding an input that causes a model to behave well on a task\. Early prompting work showed that large language models can be controlled by natural\-language instructions, few\-shot examples, and task framing rather than by weight updates\[[3](https://arxiv.org/html/2607.06145#bib.bib49),[37](https://arxiv.org/html/2607.06145#bib.bib47),[41](https://arxiv.org/html/2607.06145#bib.bib22)\]\. Chain\-of\-thought prompting further demonstrated that the prompt may specify not only the desired answer but also the form of intermediate computation to be performed\[[50](https://arxiv.org/html/2607.06145#bib.bib44)\]\. In this literature, the prompt is an interface for controlling a model; in our formalism, it is also a candidate compressed description of the output\.

Automatic prompt optimization makes this search explicit\. AutoPrompt searches for trigger tokens that elicit knowledge from masked language models\[[44](https://arxiv.org/html/2607.06145#bib.bib48)\]; APO uses natural\-language critiques as a surrogate for gradients and combines prompt edits with beam search\[[34](https://arxiv.org/html/2607.06145#bib.bib32)\]; DSPy treats language\-model calls as optimizable modules in a larger program\[[19](https://arxiv.org/html/2607.06145#bib.bib18)\]; and recent evolutionary or feedback\-based approaches optimize prompt\-like text through black\-box evaluation or language\-model feedback\[[6](https://arxiv.org/html/2607.06145#bib.bib13),[53](https://arxiv.org/html/2607.06145#bib.bib7)\]\. These methods estimate useful prompts under a task metric\. The quantityΨfε,d​\(t\)\\Psi\_\{f\}^\{\\varepsilon,d\}\(t\)gives a complementary idealization: among all plausible prompts that produce an acceptable output, it asks for the shortest one\. Practical prompt optimizers can therefore be viewed as algorithms for finding upper bounds on relaxed prompting complexity\.

This also distinguishes our setting from analyses of prompt\-space complexity\[[56](https://arxiv.org/html/2607.06145#bib.bib11)\]\. Work in that direction studies how the size and structure of the prompt space affects reasoning performance, especially for chain\-of\-thought prompting\. We instead assign a complexity to a target text relative to a fixed model and decoding rule\. The two views meet in the search problem: a difficult prompt space makes it hard to find a relaxed shortest promptp∗​↣ε,d​tp^\{\*\}\\overset\{\\varepsilon,d\}\{\\rightarrowtail\}t, even when such a prompt exists\.

### 7\.2Prompt Inversion

Prompting complexity turns prompt engineering around\. The forward problem is: given a prompt, evaluate the output\. The inverse problem is: given an output or behavior, find a short plausible prompt that caused it\. Hu et al\.\[[14](https://arxiv.org/html/2607.06145#bib.bib35)\]study intractable posterior inference in language models, including latent\-variable views of chain\-of\-thought reasoning\. In our case the latent variable is the prompt itself: for a target texttt, the preimage set\{p∈𝒫K:fτ=0​\(p\)=t\}\\\{p\\in\\mathcal\{P\}\_\{K\}:f\_\{\\tau=0\}\(p\)=t\\\}is the object being searched, and its shortest elements satisfyp↣tp\\rightarrowtail t\.

This should not be confused with model stealing or with inversion of hidden states\. Recent results on injectivity argue that transformer language models can preserve enough information in continuous hidden representations to recover discrete inputs\[[27](https://arxiv.org/html/2607.06145#bib.bib15)\]\. Surjectivity results ask whether neural networks can in principle realize arbitrary outputs from some input\[[16](https://arxiv.org/html/2607.06145#bib.bib4)\]\. Prompting complexity is defined at the visible text interface after templating, decoding, and detokenization\. At that interface many prompts may lead to the same text, and many texts may be unreachable by any plausible prompt\. The relevant safety and usability question is therefore not only whether an inverse exists somewhere in token space, but whether a short human\-plausible inverse exists\.

AlthoughΨf\\Psi\_\{f\}is computable by exhaustive enumeration in the finite setting, the search is intractable in practice\. This gives the quantity a flavor closer to resource\-bounded and instance\-level complexity than to a usable compression algorithm\[[29](https://arxiv.org/html/2607.06145#bib.bib56)\]\. A target text may be easy to verify once a candidate prompt is found, yet hard to invert by search\. In this weak sense, some outputs behave like model\-relative hashes of their prompts: the forward map is cheap to evaluate, while recovering a short cause may require searching an exponentially large plausible prompt space\. This analogy is only heuristic, since we make no cryptographic assumption aboutff\.

### 7\.3Compression, Context, and Tokenization

Our notion of compression differs from ordinary language\-model compression\. Predictive language models can be turned into strong lossless compressors\[[7](https://arxiv.org/html/2607.06145#bib.bib24)\], and classical compression studies the number of bits needed to encode a string given an encoder and decoder\. Prompting complexity instead asks how many prompt tokens are needed to make a fixed model regenerate or approximate a text\. The decoder is not a general\-purpose decompressor shared by all users; it is the particular LM, with its training distribution, tokenizer, instruction tuning, system prompt, and decoding rule already baked in\. This is why the failure of an invariance theorem is not a defect but a feature of the definition\.

The distinction also separates our framework from context compression\. Context pruning and related methods remove uninformative tokens from an existing context to reduce inference cost\[[2](https://arxiv.org/html/2607.06145#bib.bib37)\]\. Prompting complexity asks for a new cause of the output, not a shorter subset of the original context\. Similarly, model representations and routing work can build compact descriptors of language models themselves\[[57](https://arxiv.org/html/2607.06145#bib.bib25),[17](https://arxiv.org/html/2607.06145#bib.bib14)\], while tokenizer research studies how raw strings are mapped into token sequences and how those choices affect efficiency and statistical consistency\[[10](https://arxiv.org/html/2607.06145#bib.bib31),[25](https://arxiv.org/html/2607.06145#bib.bib26)\]\. Those factors matter becauseΨf\\Psi\_\{f\}is measured in tokens and is therefore tokenizer\-dependent, but the object being minimized is still a plausible prompt\.

There is a useful analogy to grammar\-based compression\. The smallest grammar problem asks for the smallest grammar that generates a given string\[[5](https://arxiv.org/html/2607.06145#bib.bib53)\]\. A shortest prompt is likewise a compact generative description, but with two important differences: the "grammar" is the learned model plus decoding rule, and the description must be a plausible text rather than an arbitrary formal object\. This plausibility constraint is what makes the quantity relevant to prompt engineering rather than merely to coding theory\.

### 7\.4Synthetic Data and Reverse Instructions

The framework clarifies a common ambiguity around synthetic data\. If a datasetDDis generated by a fixed model from promptsp1,…,pnp\_\{1\},\\ldots,p\_\{n\}, then the synthetic corpus does not contain arbitrary new information relative to that model; much of it is already compressed by the prompts, the sampling rule, and the model weights\. In this sense, a large synthetic dataset can have a short model\-relative description even when its surface form is long\. This does not make synthetic data useless\. It can reweight modes of the model distribution, make implicit capabilities explicit, expose rare combinations of skills, or provide training examples in a format that another model can consume\. But its information content should be discussed relative to the generator and the selection process, not just by counting output tokens\.

Reverse\-instruction methods are a concrete example\. LongForm constructs instruction\-tuning data by taking human\-written documents and generating instructions that could have produced them\[[20](https://arxiv.org/html/2607.06145#bib.bib39)\]\. This is an approximate inversion step: the document is treated as the target output, and a model proposes a shorter natural\-language cause\. The resulting instruction\-output pair can then train another model to make long outputs more accessible from short prompts\. From the perspective of prompting complexity, such data may reduceΨgε,d​\(t\)\\Psi\_\{g\}^\{\\varepsilon,d\}\(t\)for a downstream modelgg, even if it does not create new information ex nihilo\.

In\-context learning provides another route by which prompts change the effective behavior of a model without changing its stored weights\. Few\-shot prompting\[[3](https://arxiv.org/html/2607.06145#bib.bib49)\]and recent analyses of implicit in\-context dynamics\[[8](https://arxiv.org/html/2607.06145#bib.bib10)\]suggest that examples in the prompt can act like temporary task\-specific updates\. Conditional prompting complexityΨf​\(u∣v\)\\Psi\_\{f\}\(u\\mid v\)captures this effect at the text interface: the same targetuumay require a long prompt in isolation but a much shorter prompt when examples, demonstrations, or a domain contextvvare already present\.

### 7\.5Reasoning Traces and Output Length

Reasoning models complicate the accounting because the prompt may elicit a long internal or visible trace before the final answer\. Chain\-of\-thought prompting\[[50](https://arxiv.org/html/2607.06145#bib.bib44)\], DeepSeek\-R1\[[12](https://arxiv.org/html/2607.06145#bib.bib2)\], and the OpenAI o1 system card\[[15](https://arxiv.org/html/2607.06145#bib.bib16)\]all point to a regime where useful behavior depends on extra inference\-time computation\. In this paper, the primary object whose complexity is measured is the final output text, while any reasoning trace is treated as part of the model’s bounded computation unless it is made part of the target\. A natural extension would add a cost term for reasoning tokens or wall\-clock inference, giving a speed\-prior analogue\[[39](https://arxiv.org/html/2607.06145#bib.bib55)\]of prompting complexity\.

Even if two prompts have the same length and produce equally good final answers, one may require a much longer generation\. Work on forecasting output length\[[33](https://arxiv.org/html/2607.06145#bib.bib9)\]is therefore relevant to practical prompt search: estimating whether a candidate prompt is cheap enough to evaluate can matter as much as estimating whether it will succeed\.

### 7\.6Safety and Jailbreaks

The same language gives a compact formulation of one part of AI safety\. LetH⊆𝒫KH\\subseteq\\mathcal\{P\}\_\{K\}be a set of harmful or otherwise undesirable texts\. A model is safer, with respect to this interface, when everyt∈Ht\\in Hhas large or infinite relaxed prompting complexity: no short plausible prompt should produce an unacceptable output\. This differs from making harmful continuations low probability under ordinary sampling\. The relevant adversary is not sampling randomly from the model, but searching for a prompt in the preimage ofHH\.

The plausibility restriction is important in this context\. Some jailbreaks and glitch prompts are visibly unnatural token artifacts\[[38](https://arxiv.org/html/2607.06145#bib.bib38),[9](https://arxiv.org/html/2607.06145#bib.bib62)\]; these may be excluded by a sufficiently strict plausibility filter\. Other attacks are ordinary\-looking instructions, role plays, or contextual setups\. Such prompts remain inside𝒫K\\mathcal\{P\}\_\{K\}, so perplexity or token\-level plausibility filters are insufficient\. Alignment and instruction following\[[30](https://arxiv.org/html/2607.06145#bib.bib45)\]can be understood as reshaping the mapffso that harmful texts have smaller preimage massmf​\(t\)m\_\{f\}\(t\), longer shortest prompts, or no plausible prompts at all\. The surjectivity perspective\[[16](https://arxiv.org/html/2607.06145#bib.bib4)\]suggests why this is difficult: the goal is not merely to remove all mathematical preimages, but to make dangerous preimages inaccessible under realistic prompt constraints\.

### 7\.7Similarity, Meaning, and Causes

Prompting distance compares texts by comparing short causes rather than only surface forms or embeddings\. This is related to description\-based text similarity\[[36](https://arxiv.org/html/2607.06145#bib.bib40)\], conceptual similarity through complexity\-constrained descriptions\[[1](https://arxiv.org/html/2607.06145#bib.bib23)\], and trajectory\-based representations of meaning in autoregressive models\[[24](https://arxiv.org/html/2607.06145#bib.bib36)\]\. The difference is that a prompting\-distance promptp​↣ε,d​tp\\overset\{\\varepsilon,d\}\{\\rightarrowtail\}tis not merely a description or summary of the text; it is an input that actually causes the fixed model to generate an acceptable output\.

This cause\-based view explains why semantic similarity of outputs need not imply similarity of prompts\. Two paraphrases may be generated from entirely different instructions, while two very different outputs may differ only by a small edit in the prompt, such as changing a topic, style, or target entity\. ThusdΨd\_\{\\Psi\}is best viewed as a model\-relative geometry of controllability: it describes which changes in the prompt space are small causes of large or small changes in output space\.

## 8Conclusions

We introduced prompting complexity as a model\-dependent analogue of algorithmic text complexity for pretrained instruction\-tuned language models\. The central question is simple: for a fixed LMff, what is the shortest plausible prompt that causes deterministic decoding to produce a target texttt, i\.e\. a promptp↣tp\\rightarrowtail t? This changes the usual view of prompting from a craft of phrasing instructions into a formal search problem over human\-interpretable causes\. When a short prompt elicits a long text, the missing information is supplied by the model’s weights, training distribution, tokenizer, prompt template, and decoding rule\.

The resulting quantityΨf​\(t\)\\Psi\_\{f\}\(t\)inherits part of the intuition of Kolmogorov complexity while departing from it in the ways that matter for language models\. Since a LM has finite context and always halts, prompting complexity is computable in principle\. Since prompts are restricted to plausible texts and the model is fixed, it is not universal: there is no model\-independent invariance theorem\. A text can be highly compressible for one model because it is memorized, represented, or easy to elicit, while being nearly inaccessible to another\. Prompting complexity is therefore not an absolute property of a text, but a property of a text relative to a particular language\-model interface\.

We also defined a prompting probability and proved a weak coding theorem that relates prompt length, prompt preimage mass, and ordinary model probability\. This connects the search for short prompts to the probability mass assigned by the model to texts and to the multiplicity of prompts that produce the same output\. In the relaxed setting,\(ε,d\)\(\\varepsilon,d\)\-prompting complexity captures the practical prompt\-engineering objective: finding a short prompt whose output is close enough to a desired target under a chosen distance\. The idealized optimum is a relaxed shortest promptp​↣ε,d​tp\\overset\{\\varepsilon,d\}\{\\rightarrowtail\}t\. This turns prompt optimization into lossy, model\-relative generative compression\.

The broader value of the framework is that it gives a common language for phenomena that are usually discussed separately\. Prompt optimization becomes approximate search for short prompts\. Prompt inversion asks for plausible preimages of observed completions\. Synthetic data can be analyzed by the length of the prompts and generation process that describe it relative to the generator\. Safety can be phrased as making harmful texts prompt\-incompressible or at least hard to reach from short plausible prompts\. Text similarity can be studied through the similarity of causes rather than only the similarity of surface outputs\.

This view suggests that prompts are model\-relative descriptions of possible texts and behaviors\. As language models become more capable, longer\-context, and more explicitly equipped with reasoning traces, understanding which outputs are accessible from which short plausible prompts becomes increasingly important\. Prompting complexity offers a formal vocabulary for that question\.

## Limitations

The main limitation is computational\. Exact prompting complexity is finite and computable only because the model, context window, tokenizer, and plausible text set are finite; exhaustive search is still infeasible\. Any empirical method can at best provide upper bounds by finding a short prompt, lower bounds by ruling out restricted search regions, or probabilistic estimates through sampling\.

Finally, low prompting complexity is not the same as low problem complexity\. A math solution, legal argument, or factual report can have a short prompt if the model already contains the relevant structure, while a trivial\-looking output can be hard to elicit exactly because of decoding quirks or instruction\-tuning priors\. Prompting complexity measures accessibility of a text through a particular model interface\. That makes it useful for analyzing prompt optimization, inversion, synthetic data, safety, and similarity, but it also marks the boundary of the concept\.

## References

- \[1\]A\. Achille, G\. V\. Steeg, T\. Y\. Liu, M\. Trager, C\. Klingenberg, and S\. Soatto\(2024\)Interpretable measures of conceptual similarity by complexity\-constrained descriptive auto\-encoding\.InProceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,pp\. 11062–11071\.Cited by:[§7\.7](https://arxiv.org/html/2607.06145#S7.SS7.p1.1)\.
- \[2\]S\. Anagnostidis, D\. Pavllo, L\. Biggio, L\. Noci, A\. Lucchi, and T\. Hofmann\(2023\)Dynamic context pruning for efficient and interpretable autoregressive transformers\.Advances in Neural Information Processing Systems36,pp\. 65202–65223\.Cited by:[§7\.3](https://arxiv.org/html/2607.06145#S7.SS3.p2.1)\.
- \[3\]T\. Brown, B\. Mann, N\. Ryder, M\. Subbiah, J\. D\. Kaplan, P\. Dhariwal, A\. Neelakantan, P\. Shyam,et al\.\(2020\)Language models are few\-shot learners\.Advances in neural information processing systems33,pp\. 1877–1901\.Cited by:[§7\.1](https://arxiv.org/html/2607.06145#S7.SS1.p1.1),[§7\.4](https://arxiv.org/html/2607.06145#S7.SS4.p3.3)\.
- \[4\]D\. Chandrasekaran and V\. Mago\(2021\)Evolution of semantic similarity—a survey\.Acm Computing Surveys \(Csur\)54\(2\),pp\. 1–37\.Cited by:[§5](https://arxiv.org/html/2607.06145#S5.p1.2)\.
- \[5\]M\. Charikar, E\. Lehman, D\. Liu, R\. Panigrahy, M\. Prabhakaran, A\. Sahai, and A\. Shelat\(2005\)The smallest grammar problem\.IEEE Transactions on Information Theory51\(7\),pp\. 2554–2576\.Cited by:[§7\.3](https://arxiv.org/html/2607.06145#S7.SS3.p3.1)\.
- \[6\]P\. Chouayfati, N\. Herbster, Á\. D\. Sáfrán, and M\. Grabmair\(2025\)GenDLN: Evolutionary Algorithm\-Based Stacked LLM Framework for Joint Prompt Optimization\.InProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 4: Student Research Workshop\),pp\. 1171–1212\.Cited by:[§5](https://arxiv.org/html/2607.06145#S5.p2.3),[§7\.1](https://arxiv.org/html/2607.06145#S7.SS1.p2.1)\.
- \[7\]G\. Delétang, A\. Ruoss, P\. Duquenne, E\. Catt, T\. Genewein, C\. Mattern, J\. Grau\-Moya, L\. K\. Wenliang,et al\.\(2024\)Language Modeling Is Compression\.External Links:[Link](https://arxiv.org/abs/2309.10668),2309\.10668Cited by:[§2](https://arxiv.org/html/2607.06145#S2.p1.1),[§7\.3](https://arxiv.org/html/2607.06145#S7.SS3.p1.1)\.
- \[8\]B\. Dherin, M\. Munn, H\. Mazzawi, M\. Wunder, and J\. Gonzalvo\(2025\)Learning without training: The implicit dynamics of in\-context learning\.External Links:[Link](https://arxiv.org/abs/2507.16003),2507\.16003Cited by:[§7\.4](https://arxiv.org/html/2607.06145#S7.SS4.p3.3)\.
- \[9\]elder\_pliniusL1b3rt4s: Totally harmless liberation prompts for good Lil Ai’s\!\.External Links:[Link](https://github.com/elder-plinius/L1B3RT4S)Cited by:[Table 1](https://arxiv.org/html/2607.06145#S2.T1.1.1.1.1.1.1.1.1),[§7\.6](https://arxiv.org/html/2607.06145#S7.SS6.p2.3)\.
- \[10\]J\. L\. Gastaldi, J\. Terilla, L\. Malagutti, B\. DuSell, T\. Vieira, and R\. Cotterell\(2024\)The foundations of tokenization: Statistical and computational concerns\.arXiv preprint arXiv:2407\.11606\.Cited by:[§7\.3](https://arxiv.org/html/2607.06145#S7.SS3.p2.1)\.
- \[11\]J\. Gu, X\. Jiang, Z\. Shi, H\. Tan, X\. Zhai, C\. Xu, W\. Li, Y\. Shen,et al\.\(2026\)A survey on LLM\-as\-a\-judge\.The Innovation7\(6\)\.Cited by:[§6](https://arxiv.org/html/2607.06145#S6.p2.1)\.
- \[12\]D\. Guo, D\. Yang, H\. Zhang, J\. Song, R\. Zhang, R\. Xu, Q\. Zhu, S\. Ma,et al\.\(2025\)Deepseek\-R1: Incentivizing reasoning capability in llms via reinforcement learning\.arXiv preprint arXiv:2501\.12948\.Cited by:[§1\.2](https://arxiv.org/html/2607.06145#S1.SS2.p9.1),[§3](https://arxiv.org/html/2607.06145#S3.p4.1),[§7\.5](https://arxiv.org/html/2607.06145#S7.SS5.p1.1)\.
- \[13\]A\. Holtzman, J\. Buys, L\. Du, M\. Forbes, and Y\. Choi\(2019\)The curious case of neural text degeneration\.arXiv preprint arXiv:1904\.09751\.Cited by:[§1](https://arxiv.org/html/2607.06145#S1.SS0.SSS0.Px1.p1.2),[§2](https://arxiv.org/html/2607.06145#S2.p2.2),[§3](https://arxiv.org/html/2607.06145#S3.p2.2)\.
- \[14\]E\. J\. Hu, M\. Jain, E\. Elmoznino, Y\. Kaddar, G\. Lajoie, Y\. Bengio, and N\. Malkin\(2023\)Amortizing intractable inference in large language models\.arXiv preprint arXiv:2310\.04363\.Cited by:[§7\.2](https://arxiv.org/html/2607.06145#S7.SS2.p1.3)\.
- \[15\]A\. Jaech, A\. Kalai, A\. Lerer, A\. Richardson, A\. El\-Kishky, A\. Low, A\. Helyar, A\. Madry,et al\.\(2024\)Openai o1 system card\.arXiv preprint arXiv:2412\.16720\.Cited by:[§1\.2](https://arxiv.org/html/2607.06145#S1.SS2.p9.1),[§7\.5](https://arxiv.org/html/2607.06145#S7.SS5.p1.1)\.
- \[16\]H\. Jiang and N\. Haghtalab\(2025\)On Surjectivity of Neural Networks: Can you elicit any behavior from your model?\.arXiv preprint arXiv:2508\.19445\.Cited by:[§7\.2](https://arxiv.org/html/2607.06145#S7.SS2.p2.1),[§7\.6](https://arxiv.org/html/2607.06145#S7.SS6.p2.3)\.
- \[17\]W\. Jitkrittum, H\. Narasimhan, A\. S\. Rawat, J\. Juneja, Z\. Wang, C\. Lee, P\. Shenoy, R\. Panigrahy,et al\.\(2025\)Universal Model Routing for Efficient LLM Inference\.arXiv preprint arXiv:2502\.08773\.Cited by:[§7\.3](https://arxiv.org/html/2607.06145#S7.SS3.p2.1)\.
- \[18\]F\. D\. Keles, P\. M\. Wijewardena, and C\. Hegde\(2023\)On the computational complexity of self\-attention\.InInternational conference on algorithmic learning theory,pp\. 597–619\.Cited by:[§8\.1](https://arxiv.org/html/2607.06145#Sx2.SS1.1.p1.6)\.
- \[19\]O\. Khattab, A\. Singhvi, P\. Maheshwari, Z\. Zhang, K\. Santhanam, S\. Vardhamanan, S\. Haq, A\. Sharma,et al\.\(2024\)DSPy: Compiling Declarative Language Model Calls into Self\-Improving Pipelines\.The Twelfth International Conference on Learning Representations\.Cited by:[§5](https://arxiv.org/html/2607.06145#S5.p2.3),[§7\.1](https://arxiv.org/html/2607.06145#S7.SS1.p2.1)\.
- \[20\]A\. Köksal, T\. Schick, A\. Korhonen, and H\. Schütze\(2023\)Longform: Effective instruction tuning with reverse instructions\.arXiv preprint arXiv:2304\.08460\.Cited by:[§7\.4](https://arxiv.org/html/2607.06145#S7.SS4.p2.2)\.
- \[21\]L\. G\. Kraft\(1949\)A device for quantizing, grouping, and coding amplitude\-modulated pulses\.Ph\.D\. Thesis,Massachusetts Institute of Technology\.Cited by:[§8\.3](https://arxiv.org/html/2607.06145#Sx2.SS3.3.p3.9)\.
- \[22\]V\. I\. Levenshtein\(1966\-02\)Binary Codes Capable of Correcting Deletions, Insertions and Reversals\.Soviet Physics Doklady10,pp\. 707\.Cited by:[§5](https://arxiv.org/html/2607.06145#S5.p1.2)\.
- \[23\]M\. Li, P\. Vitányi,et al\.\(2008\)An introduction to Kolmogorov complexity and its applications\.Vol\.3,Springer\.Cited by:[§1](https://arxiv.org/html/2607.06145#S1.p4.1),[§1](https://arxiv.org/html/2607.06145#S1.p5.1),[§4](https://arxiv.org/html/2607.06145#S4.p15.7),[§8\.3](https://arxiv.org/html/2607.06145#Sx2.SS3.p3.4)\.
- \[24\]T\. Y\. Liu, M\. Trager, A\. Achille, P\. Perera, L\. Zancato, and S\. Soatto\(2023\)Meaning representations from trajectories in autoregressive models\.arXiv preprint arXiv:2310\.18348\.Cited by:[§5\.1](https://arxiv.org/html/2607.06145#S5.SS1.p3.1),[§7\.7](https://arxiv.org/html/2607.06145#S7.SS7.p1.1)\.
- \[25\]B\. Minixhofer, E\. M\. Ponti, and I\. Vulić\(2024\)Zero\-shot tokenizer transfer\.arXiv preprint arXiv:2405\.07883\.Cited by:[§7\.3](https://arxiv.org/html/2607.06145#S7.SS3.p2.1)\.
- \[26\]E\. Mitchell, Y\. Lee, A\. Khazatsky, C\. D\. Manning, and C\. Finn\(2023\)Detectgpt: Zero\-shot machine\-generated text detection using probability curvature\.InInternational Conference on Machine Learning,pp\. 24950–24962\.Cited by:[§2](https://arxiv.org/html/2607.06145#S2.p7.2)\.
- \[27\]G\. Nikolaou, T\. Mencattini, D\. Crisostomi, A\. Santilli, Y\. Panagakis, and E\. Rodolà\(2025\)Language Models are Injective and Hence Invertible\.External Links:[Link](https://arxiv.org/abs/2510.15511),2510\.15511Cited by:[§4](https://arxiv.org/html/2607.06145#S4.p1.1),[§7\.2](https://arxiv.org/html/2607.06145#S7.SS2.p2.1)\.
- \[28\]OpenAI, J\. Achiam, S\. Adler, S\. Agarwal, L\. Ahmad, I\. Akkaya, F\. L\. Aleman, D\. Almeida,et al\.\(2024\)GPT\-4 Technical Report\.External Links:[Link](https://arxiv.org/abs/2303.08774),2303\.08774Cited by:[§3](https://arxiv.org/html/2607.06145#S3.p4.1)\.
- \[29\]P\. Orponen, K\. Ko, U\. Schöning, and O\. Watanabe\(1994\)Instance complexity\.Journal of the ACM \(JACM\)41\(1\),pp\. 96–121\.Cited by:[§7\.2](https://arxiv.org/html/2607.06145#S7.SS2.p3.2)\.
- \[30\]L\. Ouyang, J\. Wu, X\. Jiang, D\. Almeida, C\. L\. Wainwright, P\. Mishkin, C\. Zhang, S\. Agarwal,et al\.\(2022\)Training language models to follow instructions with human feedback\.External Links:[Link](https://arxiv.org/abs/2203.02155),2203\.02155Cited by:[§3](https://arxiv.org/html/2607.06145#S3.p4.1),[§7\.6](https://arxiv.org/html/2607.06145#S7.SS6.p2.3)\.
- \[31\]H\. Papazov and N\. Flammarion\(2025\)Learning Algorithms in the Limit\.arXiv preprint arXiv:2506\.15543\.Cited by:[§3](https://arxiv.org/html/2607.06145#S3.p1.1)\.
- \[32\]J\. Pérez, P\. Barceló, and J\. Marinkovic\(2021\)Attention is turing\-complete\.Journal of Machine Learning Research22\(75\),pp\. 1–35\.Cited by:[§3](https://arxiv.org/html/2607.06145#S3.p6.1)\.
- \[33\]G\. Piotrowski, M\. Bystroński, M\. Hołysz, J\. Binkowski, G\. Chodak, and T\. J\. Kajdanowicz\(2025\)When Will the Tokens End? Graph\-Based Forecasting for LLMs Output Length\.InProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 4: Student Research Workshop\),pp\. 843–848\.Cited by:[§7\.5](https://arxiv.org/html/2607.06145#S7.SS5.p2.1)\.
- \[34\]R\. Pryzant, D\. Iter, J\. Li, Y\. Lee, C\. Zhu, and M\. Zeng\(2023\)Automatic prompt optimization with “gradient descent” and beam search\.InProceedings of the 2023 conference on empirical methods in natural language processing,pp\. 7957–7968\.Cited by:[§7\.1](https://arxiv.org/html/2607.06145#S7.SS1.p2.1)\.
- \[35\]R\. Qiu, Z\. Xu, W\. Bao, and H\. Tong\(2025\)Ask, and it shall be given: on the turing completeness of prompting\.InInternational Conference on Learning Representations,Vol\.2025,pp\. 6286–6309\.Cited by:[§3](https://arxiv.org/html/2607.06145#S3.p6.1)\.
- \[36\]S\. Ravfogel, V\. Pyatkin, A\. D\. Cohen, A\. Manevich, and Y\. Goldberg\(2023\)Description\-based text similarity\.arXiv preprint arXiv:2305\.12517\.Cited by:[§5\.1](https://arxiv.org/html/2607.06145#S5.SS1.p3.1),[§7\.7](https://arxiv.org/html/2607.06145#S7.SS7.p1.1)\.
- \[37\]L\. Reynolds and K\. McDonell\(2021\)Prompt programming for large language models: Beyond the few\-shot paradigm\.InExtended abstracts of the 2021 CHI conference on human factors in computing systems,pp\. 1–7\.Cited by:[§7\.1](https://arxiv.org/html/2607.06145#S7.SS1.p1.1)\.
- \[38\]J\. Rumbelow and M\. Watkins\(2023\)SolidGoldMagikarp \(plus, prompt generation\)\.InAI ALIGNMENT FORUM,pp\. 7\.Cited by:[Table 1](https://arxiv.org/html/2607.06145#S2.T1.1.1.3.2.2.1.1.1),[Table 1](https://arxiv.org/html/2607.06145#S2.T1.1.1.3.2.2.1.2.1),[§7\.6](https://arxiv.org/html/2607.06145#S7.SS6.p2.3)\.
- \[39\]J\. Schmidhuber\(2000\)Algorithmic theories of everything\.arXiv preprint quant\-ph/0011122\.Cited by:[§4](https://arxiv.org/html/2607.06145#S4.p10.1),[§7\.5](https://arxiv.org/html/2607.06145#S7.SS5.p1.1)\.
- \[40\]J\. Schmidhuber\(2003\)Goedel Machines: Self\-Referential Universal Problem Solvers Making Provably Optimal Self\-Improvements\.CoRRcs\.LO/0309048\.External Links:[Link](http://arxiv.org/abs/cs/0309048)Cited by:[§3](https://arxiv.org/html/2607.06145#S3.p6.1)\.
- \[41\]S\. Schulhoff, M\. Ilie, N\. Balepur, K\. Kahadze, A\. Liu, C\. Si, Y\. Li, A\. Gupta,et al\.\(2024\)The prompt report: A systematic survey of prompting techniques\.arXiv preprint arXiv:2406\.066085\.Cited by:[§7\.1](https://arxiv.org/html/2607.06145#S7.SS1.p1.1)\.
- \[42\]C\. E\. Shannon\(1948\)A mathematical theory of communication\.The Bell System Technical Journal27\(3\),pp\. 379–423\.External Links:[Document](https://dx.doi.org/10.1002/j.1538-7305.1948.tb01338.x)Cited by:[§1](https://arxiv.org/html/2607.06145#S1.SS0.SSS0.Px3.p1.1),[§5](https://arxiv.org/html/2607.06145#S5.p2.3)\.
- \[43\]Z\. Shen\(2024\)LLM With Tools: A Survey\.External Links:[Link](https://arxiv.org/abs/2409.18807),2409\.18807Cited by:[§3](https://arxiv.org/html/2607.06145#S3.p4.1)\.
- \[44\]T\. Shin, Y\. Razeghi, R\. L\. L\. Iv, E\. Wallace, and S\. Singh\(2020\)Autoprompt: Eliciting knowledge from language models with automatically generated prompts\.InProceedings of the 2020 conference on empirical methods in natural language processing \(EMNLP\),pp\. 4222–4235\.Cited by:[§7\.1](https://arxiv.org/html/2607.06145#S7.SS1.p2.1)\.
- \[45\]R\.J\. Solomonoff\(1964\)A formal theory of inductive inference\. Part I\.Information and Control7\(1\),pp\. 1–22\.External Links:[Document](https://dx.doi.org/https%3A//doi.org/10.1016/S0019-9958%2864%2990223-2),ISSN 0019\-9958,[Link](https://www.sciencedirect.com/science/article/pii/S0019995864902232)Cited by:[§8\.3](https://arxiv.org/html/2607.06145#Sx2.SS3.p2.2)\.
- \[46\]G\. Team, A\. Kamath, J\. Ferret, S\. Pathak, N\. Vieillard, R\. Merhej, S\. Perrin, T\. Matejovicova,et al\.\(2025\)Gemma 3 technical report\.arXiv preprint arXiv:2503\.19786\.Cited by:[footnote 3](https://arxiv.org/html/2607.06145#footnote3)\.
- \[47\]Q\. Team, A\. Yang, B\. Yang, B\. Zhang, B\. Hui, B\. Zheng, B\. Yu,et al\.\(2025\)Qwen2\.5 Technical Report\.External Links:[Link](https://arxiv.org/abs/2412.15115),2412\.15115Cited by:[§3](https://arxiv.org/html/2607.06145#S3.p4.1)\.
- \[48\]H\. Touvron, T\. Lavril, G\. Izacard, X\. Martinet, M\. Lachaux, T\. Lacroix, B\. Rozière, N\. Goyal,et al\.\(2023\)Llama: Open and efficient foundation language models\.arXiv preprint arXiv:2302\.13971\.Cited by:[§3](https://arxiv.org/html/2607.06145#S3.p4.1)\.
- \[49\]A\. M\. Turinget al\.\(1936\)On computable numbers, with an application to the Entscheidungsproblem\.J\. of Math58\(345\-363\),pp\. 5\.Cited by:[§3](https://arxiv.org/html/2607.06145#S3.p6.1)\.
- \[50\]J\. Wei, X\. Wang, D\. Schuurmans, M\. Bosma, F\. Xia, E\. Chi, Q\. V\. Le, D\. Zhou,et al\.\(2022\)Chain\-of\-thought prompting elicits reasoning in large language models\.Advances in neural information processing systems35,pp\. 24824–24837\.Cited by:[§1\.2](https://arxiv.org/html/2607.06145#S1.SS2.p9.1),[§7\.1](https://arxiv.org/html/2607.06145#S7.SS1.p1.1),[§7\.5](https://arxiv.org/html/2607.06145#S7.SS5.p1.1)\.
- \[51\]Z\. Xu, S\. Jain, and M\. Kankanhalli\(2024\)Hallucination is inevitable: An innate limitation of large language models\.arXiv preprint arXiv:2401\.11817\.Cited by:[§3](https://arxiv.org/html/2607.06145#S3.p8.1)\.
- \[52\]X\. Yin, X\. Wang, L\. Pan, L\. Lin, X\. Wan, and W\. Y\. Wang\(2024\)G\\\\backslash" odel agent: A self\-referential agent framework for recursive self\-improvement\.arXiv preprint arXiv:2410\.04444\.Cited by:[§3](https://arxiv.org/html/2607.06145#S3.p6.1)\.
- \[53\]M\. Yuksekgonul, F\. Bianchi, J\. Boen, S\. Liu, P\. Lu, Z\. Huang, C\. Guestrin, and J\. Zou\(2025\)Optimizing generative AI by backpropagating language model feedback\.Nature639,pp\. 609–616\.Cited by:[§5](https://arxiv.org/html/2607.06145#S5.p2.3),[§7\.1](https://arxiv.org/html/2607.06145#S7.SS1.p2.1)\.
- \[54\]O\. Zekri, A\. Odonnat, A\. Benechehab, L\. Bleistein, N\. Boullé, and I\. Redko\(2024\)Large language models as markov chains\.arXiv preprint arXiv:2410\.02724\.Cited by:[§1\.2](https://arxiv.org/html/2607.06145#S1.SS2.p7.7),[§2](https://arxiv.org/html/2607.06145#S2.p2.2),[§5\.1](https://arxiv.org/html/2607.06145#S5.SS1.p1.1)\.
- \[55\]J\. Zhang, S\. Hu, C\. Lu, R\. Lange, and J\. Clune\(2025\)Darwin Godel Machine: Open\-Ended Evolution of Self\-Improving Agents\.arXiv preprint arXiv:2505\.22954\.Cited by:[§3](https://arxiv.org/html/2607.06145#S3.p6.1)\.
- \[56\]X\. Zhang, J\. Cao, J\. Wei, C\. You, and D\. Ding\(2025\)Why Prompt Design Matters and Works: A Complexity Analysis of Prompt Search Space in LLMs\.arXiv preprint arXiv:2503\.10084\.Cited by:[§7\.1](https://arxiv.org/html/2607.06145#S7.SS1.p3.1)\.
- \[57\]R\. Zhuang, T\. Wu, Z\. Wen, A\. Li, J\. Jiao, and K\. Ramchandran\(2024\)EmbedLLM: Learning Compact Representations of Large Language Models\.arXiv preprint arXiv:2410\.02223\.Cited by:[§7\.3](https://arxiv.org/html/2607.06145#S7.SS3.p2.1)\.

## Appendix

### 8\.1LMs are computable and polynomially bounded

###### Proposition 8\.

A LMffis computable, and it is polynomially space\- and time\-bounded by𝒪​\(K3\)\\mathcal\{O\}\(K^\{3\}\), withKKthe maximal sequence size for transformer inference\.

###### Proof\.

By definition, the LMffis constructed through a composition of computable functions, has fixed\-precision parameters and has a fixed context sizeKK\. Thereforeffis computable111Or simply: since we can run an LM on a computer, it is computable\.and always halts\. Since the computational complexity of a single forward pass \(i\.e\., for generating a single token\) of a transformer decoder is𝒪​\(n2\)\\mathcal\{O\}\(n^\{2\}\)\[[18](https://arxiv.org/html/2607.06145#bib.bib41)\], due to quadratic complexity of self\-attention, generating a text of size\|t\|\|t\|from a prompt of size\|p\|\|p\|is then:

∑i=0\|t\|𝒪​\(\(\|p\|\+i\)2\)\\displaystyle\\sum\\limits\_\{i=0\}^\{\|t\|\}\\mathcal\{O\}\(\(\|p\|\+i\)^\{2\}\)=𝒪​\(\|t\|​\|p\|2\+\|p\|​\(\|t\|2\+\|t\|\)\+\|t\|​\(\|t\|\+1\)​\(2​\|t\|\+1\)6\)\\displaystyle=\\mathcal\{O\}\\left\(\|t\|\|p\|^\{2\}\+\|p\|\(\|t\|^\{2\}\+\|t\|\)\+\\frac\{\|t\|\(\|t\|\+1\)\(2\|t\|\+1\)\}\{6\}\\right\)\(27\)=𝒪​\(\(\|p\|\+\|t\|\)3\)\.\\displaystyle=\\mathcal\{O\}\(\(\|p\|\+\|t\|\)^\{3\}\)\.\(28\)Since the active sequence length is at mostKK, the runtime is bounded by𝒪​\(K3\)\\mathcal\{O\}\(K^\{3\}\)\. The memory used by the finite context and attention computation is also polynomial inKK, and in particular upper\-bounded by𝒪​\(K3\)\\mathcal\{O\}\(K^\{3\}\)under this loose accounting\. ∎

### 8\.2Additional propositions on plausible texts

###### Proposition 9\(Number of Plausible Texts\)\.

For fixedf,τ,ρf,\\tau,\\rhoand contextcc, let𝒫nτ,ρ​\(c\)\\mathcal\{P\}^\{\\tau,\\rho\}\_\{n\}\(c\)be the set of plausible continuations of length exactlyn≤K−\|c\|n\\leq K\-\|c\|\. Then

\|𝒫nτ,ρ​\(c\)\|≤⌈ρ​T⌉n\.\\displaystyle\|\\mathcal\{P\}^\{\\tau,\\rho\}\_\{n\}\(c\)\|\\leq\\lceil\\rho T\\rceil^\{\\,n\}\.\(29\)Under the effective\-branching approximation\|Sρ​\(c∥t<i\)\|≈Nρ,s\>1\|S\_\{\\rho\}\(c\\mathbin\{\\\|\}t\_\{<i\}\)\|\\approx N\_\{\\rho,s\}\>1along plausible prefixes, the number of plausible texts grows exponentially:\|𝒫nτ,ρ​\(c\)\|≈\(Nρ,s\)n\|\\mathcal\{P\}^\{\\tau,\\rho\}\_\{n\}\(c\)\|\\approx\(N\_\{\\rho,s\}\)^\{n\}\.

###### Proof\.

For any probability distribution overTTtokens sorted in nonincreasing order, the mass of the topkktokens is at leastk/Tk/T\. Thus the top⌈ρ​T⌉\\lceil\\rho T\\rceiltokens have total mass at leastρ\\rho, so\|Sρ​\(u\)\|=Nρ​\(u\)≤⌈ρ​T⌉\|S\_\{\\rho\}\(u\)\|=N\_\{\\rho\}\(u\)\\leq\\lceil\\rho T\\rceilfor every prefixuu\. The plausible length\-nncontinuations form a rooted tree whose branching factor at every depth is at most⌈ρ​T⌉\\lceil\\rho T\\rceil\. Hence the number of leaves is at most⌈ρ​T⌉n\\lceil\\rho T\\rceil^\{\\,n\}\.

To obtain a typical exponential growth rate, assume that along plausible prefixes the next\-token probabilities approximately follow a power law222This is a simplification\. In practice the exponent and even the admissible vocabulary change with the context, the tokenizer and syntactic constraints such as JSON formatting\.

P​\(v\(i\)∣u\)≈i−sζ​\(s\),s\>1,\\displaystyle P\(v\_\{\(i\)\}\\mid u\)\\approx\\frac\{i^\{\-s\}\}\{\\zeta\(s\)\},\\qquad s\>1,\(30\)with large vocabulary sizeTT333This is usually the case\. Models such as Gemma3\[[46](https://arxiv.org/html/2607.06145#bib.bib6)\]have vocabulary sizes of 256,000 tokens\.\. The nucleus size is approximately the smallestkksatisfying∑i=1ki−s≥ρ​ζ​\(s\)\\sum\_\{i=1\}^\{k\}i^\{\-s\}\\geq\\rho\\zeta\(s\)\. Using the tail approximation∑i=1ki−s≈ζ​\(s\)−k1−s/\(s−1\)\\sum\_\{i=1\}^\{k\}i^\{\-s\}\\approx\\zeta\(s\)\-k^\{1\-s\}/\(s\-1\)gives

ζ​\(s\)−k1−ss−1≥ρ​ζ​\(s\)⟺k≳\(\(s−1\)​\(1−ρ\)​ζ​\(s\)\)−1s−1\.\\displaystyle\\zeta\(s\)\-\\frac\{k^\{1\-s\}\}\{s\-1\}\\geq\\rho\\zeta\(s\)\\quad\\Longleftrightarrow\\quad k\\gtrsim\(\(s\-1\)\(1\-\\rho\)\\zeta\(s\)\)^\{\-\\frac\{1\}\{s\-1\}\}\.\(31\)We write

Nρ,s′:=\(\(s−1\)​\(1−ρ\)​ζ​\(s\)\)−1s−1,Nρ,s:=min⁡\{⌈ρ​T⌉,max⁡\{1,Nρ,s′\}\}\.\\displaystyle N^\{\\prime\}\_\{\\rho,s\}:=\(\(s\-1\)\(1\-\\rho\)\\zeta\(s\)\)^\{\-\\frac\{1\}\{s\-1\}\},\\qquad N\_\{\\rho,s\}:=\\min\\\{\\lceil\\rho T\\rceil,\\max\\\{1,N^\{\\prime\}\_\{\\rho,s\}\\\}\\\}\.\(32\)If this effective nucleus size is roughly stable across prefixes, then the branching process has aboutNρ,sN\_\{\\rho,s\}choices per token and\|𝒫nτ,ρ​\(c\)\|≈\(Nρ,s\)n\|\\mathcal\{P\}^\{\\tau,\\rho\}\_\{n\}\(c\)\|\\approx\(N\_\{\\rho,s\}\)^\{n\}\. ∎

###### Proposition 10\.

Greedy outputs are plausible for every nucleus threshold\. More precisely, fixρ∈\(0,1\)\\rho\\in\(0,1\)and lett=fτ=0​\(c\)t=f\_\{\\tau=0\}\(c\)be the deterministic greedy completion from contextcc, truncated to fit the context window\. Thent∈𝒫Kτ,ρ​\(c\)t\\in\\mathcal\{P\}^\{\\tau,\\rho\}\_\{K\}\(c\)for everyτ\>0\\tau\>0\.

###### Proof\.

At any generation step, greedy decoding chooses the highest\-probability token, which isv\(1\)v\_\{\(1\)\}under the tie\-breaking order above; temperature rescaling withτ\>0\\tau\>0preserves this ordering\. Sinceρ\>0\\rho\>0, the nucleus set always contains at least its first token:v\(1\)∈Sρ​\(c\)v\_\{\(1\)\}\\in S\_\{\\rho\}\(c\)\. Applying this argument at each prefixc∥t<ic\\mathbin\{\\\|\}t\_\{<i\}shows that every greedy token lies in the corresponding nucleus set, hence the whole greedy completion is plausible\. ∎

###### Proposition 11\(Plausibility Check\)\.

Fixf,K,τ,ρf,K,\\tau,\\rhoand contextcc\. A textt=\(t1,…,tm\)t=\(t\_\{1\},\\ldots,t\_\{m\}\)is plausible fromccif and only if each token lies in the nucleus set determined by its preceding context:

t∈𝒫Kτ,ρ​\(c\)⇔\|c\|\+m≤K​and​∀i≤m:ti∈Sρ​\(c∥t<i\)\.\\displaystyle t\\in\\mathcal\{P\}^\{\\tau,\\rho\}\_\{K\}\(c\)\\iff\|c\|\+m\\leq K\\text\{ and \}\\forall i\\leq m:\\ t\_\{i\}\\in S\_\{\\rho\}\(c\\mathbin\{\\\|\}t\_\{<i\}\)\.\(33\)

###### Proof\.

This is exactly Definition[1](https://arxiv.org/html/2607.06145#Thmdefinition1)unpacked over the autoregressive generation steps\. ∎

### 8\.3The Weak Coding Theorem

The failure of an invariance theorem means that prompting complexity cannot be estimated by applying an arbitrary off\-the\-shelf compressor to the target text: the relevant compressor is the particular modelff, together with its training distribution, tokenizer, prompt template and decoding rule\. What does remain useful from the classical coding theorem is the link between description length and probability mass\. We therefore define a model\-dependent analogue of algorithmic probability by drawing a self\-delimiting plausible prompt with a length prior and asking whether deterministic decoding produces the target text\.

###### Definition 10\(Prompting Probability\)\.

Lett∈𝒫Kt\\in\\mathcal\{P\}\_\{K\}and letf:𝒫K→𝒫Kf:\\mathcal\{P\}\_\{K\}\\rightarrow\\mathcal\{P\}\_\{K\}be a LM\. The prompting probability of the textttis:

mf​\(t\)=∑p∈𝒫Kfτ=0​\(p\)=tT−\|p\|\\displaystyle m\_\{f\}\(t\)=\\sum\_\{\\begin\{subarray\}\{c\}p\\in\\mathcal\{P\}\_\{K\}\\\\ f\_\{\\tau=0\}\(p\)=t\\end\{subarray\}\}T^\{\-\|p\|\}\(34\)

The prompting probability counts the plausible prompts that generate a target text, weighted by their length, making shorter prompts contribute more mass\. Unlike the universal algorithmic probability semimeasure\[[45](https://arxiv.org/html/2607.06145#bib.bib58)\],mf​\(t\)m\_\{f\}\(t\)is computable in the finite LM setting, but it depends onffand is therefore not universal\.

###### Lemma 1\.

The prompting probabilitymfm\_\{f\}is computable and∑t∈𝒫Kmf​\(t\)≤1\\sum\\limits\_\{t\\in\\mathcal\{P\}\_\{K\}\}m\_\{f\}\(t\)\\leq 1\.

###### Proof\.

If no promptppproduces a given texttt, then the inner sum is over an empty set and somf​\(t\)=0m\_\{f\}\(t\)=0\. Consider the collection of preimage setsAt=\{p∈𝒫K:fτ=0​\(p\)=t\},t∈𝒫KA\_\{t\}=\\\{p\\in\\mathcal\{P\}\_\{K\}:f\_\{\\tau=0\}\(p\)=t\\\},~t\\in\\mathcal\{P\}\_\{K\}\.

Since each promptpphas exactly one outputf​\(p\)f\(p\), the sets\{At\}t∈𝒫K\\\{A\_\{t\}\\\}\_\{t\\in\\mathcal\{P\}\_\{K\}\}form a partition of𝒫K\\mathcal\{P\}\_\{K\}:𝒫K=⋃t∈𝒫KAt\\mathcal\{P\}\_\{K\}\\;=\\bigcup\_\{t\\in\\mathcal\{P\}\_\{K\}\}A\_\{t\}\.

BecauseT−\|p\|≥0T^\{\-\|p\|\}\\geq 0, we may sum over this partition in either order:

∑t∈𝒫Kmf​\(t\)=∑t∈𝒫K∑p∈𝒫Kfτ=0​\(p\)=tT−\|p\|=∑p∈𝒫KT−\|p\|\\displaystyle\\sum\\limits\_\{t\\in\\mathcal\{P\}\_\{K\}\}m\_\{f\}\(t\)=\\sum\\limits\_\{t\\in\\mathcal\{P\}\_\{K\}\}\\sum\_\{\\begin\{subarray\}\{c\}p\\in\\mathcal\{P\}\_\{K\}\\\\ f\_\{\\tau=0\}\(p\)=t\\end\{subarray\}\}T^\{\-\|p\|\}=\\sum\\limits\_\{p\\in\\mathcal\{P\}\_\{K\}\}T^\{\-\|p\|\}\(35\)By Definition[2](https://arxiv.org/html/2607.06145#Thmdefinition2)of the LM, we assume that the tokenizer template unambiguously separates system prompts, input prompts, reasoning traces and output texts\. Thus texts in𝒫K\\mathcal\{P\}\_\{K\}are self\-delimiting and form a prefix\-free set over an alphabet of sizeTT\. By Kraft’s inequality\[[21](https://arxiv.org/html/2607.06145#bib.bib59)\],∑p∈𝒫KT−\|p\|≤1\\sum\\limits\_\{p\\in\\mathcal\{P\}\_\{K\}\}T^\{\-\|p\|\}\\leq 1, yielding the desired bound\. Finally, to see that eachmf​\(t\)m\_\{f\}\(t\)is computable we observe that𝒫K\\mathcal\{P\}\_\{K\}is finite and that the functionfτ=0​\(p\)f\_\{\\tau=0\}\(p\)is computable \(Proposition[8](https://arxiv.org/html/2607.06145#Thmproposition8)\)\. We can therefore enumerate all plausible prompts, simulate them withff, and add the weights of those that producett\. ∎

Consider the marginal model probability of a textt=\(t1,t2,…,tk\)t=\(t\_\{1\},t\_\{2\},\\dots,t\_\{k\}\):

Pf​\(t\)=∑p∈𝒫KT−\|p\|​Pf​\(t∣p\),Pf​\(t∣p\)=∏i=1\|t\|Pf​\(ti∣t<i,p\),\\displaystyle P\_\{f\}\(t\)=\\sum\\limits\_\{p\\in\\mathcal\{P\}\_\{K\}\}T^\{\-\|p\|\}P\_\{f\}\(t\\mid p\),\\qquad P\_\{f\}\(t\\mid p\)=\\prod\\limits\_\{i=1\}^\{\|t\|\}P\_\{f\}\(t\_\{i\}\\mid t\_\{<i\},p\),\(36\)wherePf​\(t∣p\)P\_\{f\}\(t\\mid p\)is the usual text probability under the modelffwith temperatureτ=1\\tau=1\. This gives a weak analogue of the Coding Theorem\[[23](https://arxiv.org/html/2607.06145#bib.bib52)\]\.

###### Theorem 1\(Weak Coding Theorem\)\.

For anyt∈𝒫Kt\\in\\mathcal\{P\}\_\{K\}withΨf​\(t\)<∞\\Psi\_\{f\}\(t\)<\\infty, letSt=\{p∈𝒫K:fτ=0​\(p\)=t\}S\_\{t\}=\\\{p\\in\\mathcal\{P\}\_\{K\}:f\_\{\\tau=0\}\(p\)=t\\\}andZf​\(t\)=∑p∈StT−\(\|p\|−Ψf​\(t\)\)Z\_\{f\}\(t\)=\\sum\_\{p\\in S\_\{t\}\}T^\{\-\(\|p\|\-\\Psi\_\{f\}\(t\)\)\}\. Then:

−logT⁡Pf​\(t\)−\|t\|≤−logT⁡mf​\(t\)=Ψf​\(t\)−logT⁡Zf​\(t\)≤Ψf​\(t\)\.\-\\log\_\{T\}P\_\{f\}\(t\)\-\|t\|\\leq\-\\log\_\{T\}m\_\{f\}\(t\)=\\Psi\_\{f\}\(t\)\-\\log\_\{T\}Z\_\{f\}\(t\)\\leq\\Psi\_\{f\}\(t\)\.\(37\)

###### Proof\.

LetS=\{p∈𝒫K:fτ=0​\(p\)=t\}S=\\\{p\\in\\mathcal\{P\}\_\{K\}:f\_\{\\tau=0\}\(p\)=t\\\}be the set of all prompts whose temperature 0 decoding is exactlytt\. Then,mf​\(t\)=∑p∈ST−\|p\|m\_\{f\}\(t\)=\\sum\\limits\_\{p\\in S\}T^\{\-\|p\|\}and

Pf​\(t\)=∑p∈𝒫KT−\|p\|​Pf​\(t\|p\)=∑p∈ST−\|p\|​Pf​\(t\|p\)\+∑p∉ST−\|p\|​Pf​\(t\|p\)\\displaystyle P\_\{f\}\(t\)=\\sum\\limits\_\{p\\in\\mathcal\{P\}\_\{K\}\}T^\{\-\|p\|\}P\_\{f\}\(t\|p\)=\\sum\\limits\_\{p\\in S\}T^\{\-\|p\|\}P\_\{f\}\(t\|p\)\+\\sum\\limits\_\{p\\notin S\}T^\{\-\|p\|\}P\_\{f\}\(t\|p\)\(38\)It is clear that, since the second sum is non\-negative, we have thatPf​\(t\)≥∑p∈ST−\|p\|​Pf​\(t\|p\)P\_\{f\}\(t\)\\geq\\sum\\limits\_\{p\\in S\}T^\{\-\|p\|\}P\_\{f\}\(t\|p\)\. Sincep∈Sp\\in S, at each positioniigreedy decoding chosetit\_\{i\}as a highest\-probability next token\. Under the temperatureτ=1\\tau=1distribution, any highest\-probability token has probability at leastT−1T^\{\-1\}, and therefore:

Pf​\(ti\|t<i,p\)≥T−1⟹Pf​\(t\|p\)=∏i=1\|t\|Pf​\(ti\|t<i,p\)≥T−\|t\|\\displaystyle P\_\{f\}\(t\_\{i\}\|t\_\{<i\},p\)\\geq T^\{\-1\}\\implies P\_\{f\}\(t\|p\)=\\prod\\limits\_\{i=1\}^\{\|t\|\}P\_\{f\}\(t\_\{i\}\|t\_\{<i\},p\)\\geq T^\{\-\|t\|\}\(39\)
Combining the two we get:

Pf​\(t\)≥∑p∈ST−\|p\|​Pf​\(t\|p\)≥∑p∈ST−\|p\|​T−\|t\|=T−\|t\|​∑p∈ST−\|p\|=T−\|t\|​mf​\(t\)\\displaystyle P\_\{f\}\(t\)\\geq\\sum\\limits\_\{p\\in S\}T^\{\-\|p\|\}P\_\{f\}\(t\|p\)\\geq\\sum\\limits\_\{p\\in S\}T^\{\-\|p\|\}T^\{\-\|t\|\}=T^\{\-\|t\|\}\\sum\\limits\_\{p\\in S\}T^\{\-\|p\|\}=T^\{\-\|t\|\}m\_\{f\}\(t\)\(40\)
Rearranging and applying−logT\-\\log\_\{T\}on both sides, we obtain:

−logT⁡Pf​\(t\)−\|t\|≤−logT⁡mf​\(t\)\\displaystyle\-\\log\_\{T\}P\_\{f\}\(t\)\-\|t\|\\leq\-\\log\_\{T\}m\_\{f\}\(t\)\(41\)Which proves the first inequality\. To relatemf​\(t\)m\_\{f\}\(t\)toΨf​\(t\)\\Psi\_\{f\}\(t\), we have by definition:

mf​\(t\)=∑p∈𝒫Kfτ=0​\(p\)=tT−\|p\|=T−Ψf​\(t\)​∑p∈ST−\(\|p\|−Ψf​\(t\)\)=T−Ψf​\(t\)​Zf​\(t\)\.\\displaystyle m\_\{f\}\(t\)=\\sum\_\{\\begin\{subarray\}\{c\}p\\in\\mathcal\{P\}\_\{K\}\\\\ f\_\{\\tau=0\}\(p\)=t\\end\{subarray\}\}T^\{\-\|p\|\}=T^\{\-\\Psi\_\{f\}\(t\)\}\\sum\_\{p\\in S\}T^\{\-\(\|p\|\-\\Psi\_\{f\}\(t\)\)\}=T^\{\-\\Psi\_\{f\}\(t\)\}Z\_\{f\}\(t\)\.\(42\)Taking−logT\-\\log\_\{T\}on both sides gives:

−logT⁡mf​\(t\)=Ψf​\(t\)−logT⁡Zf​\(t\)\.\\displaystyle\-\\log\_\{T\}m\_\{f\}\(t\)=\\Psi\_\{f\}\(t\)\-\\log\_\{T\}Z\_\{f\}\(t\)\.\(43\)SinceSScontains at least one shortest promptp∗↣tp^\{\*\}\\rightarrowtail t,Zf​\(t\)≥1Z\_\{f\}\(t\)\\geq 1, and therefore−logT⁡mf​\(t\)≤Ψf​\(t\)\-\\log\_\{T\}m\_\{f\}\(t\)\\leq\\Psi\_\{f\}\(t\)\. ∎

The weak coding theorem relates the usual text probability under a pretrained LM with the prompt mass assigned to prompts that generate the text\. The termZf​\(t\)Z\_\{f\}\(t\)measures how many plausible prompts, weighted by length relative to the shortest one, produce the same output\. When this multiplicity term is bounded,−logT⁡mf​\(t\)\-\\log\_\{T\}m\_\{f\}\(t\)andΨf​\(t\)\\Psi\_\{f\}\(t\)differ by at most a constant; when many prompts lead to the same text, the prompting probability can be much larger than the mass of a single shortest prompt\. In practice, estimates ofPf​\(t\)P\_\{f\}\(t\)can still provide lower bounds on−logT⁡mf​\(t\)\-\\log\_\{T\}m\_\{f\}\(t\), and therefore on the amount of prompt mass that must be searched for when trying to find short prompts\.