{"id":"d7b67452-0d2f-4bf7-8b26-4013ba038a0c","arxiv_id":"2607.06145","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":3,"one_line_summary":"The paper defines prompting complexity as the length of the shortest plausible prompt that deterministically generates a target text with a fixed language model.","lead":"This paper defines 'prompting complexity': the length of the shortest human-readable prompt that causes a fixed language model to deterministically produce a target text. It provides a formal, model-relative analogue to Kolmogorov complexity, framing prompt engineering as a search for compressed descriptions relative to a specific model's weights and training data.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"The Weak Coding Theorem (Theorem 1) relies on P_K being prefix-free, but Definition 1 does not ensure this; every prefix of a plausible text is itself plausible, so Kraft's inequality does not apply as stated.","rationale":"The reader correctly identifies P_K as the weakest point, but focuses on the practical relevance of the ρ threshold — whether P_K faithfully captures human-readable prompts. That is a valid concern about applicability, but the paper is upfront about being a formal framework and research agenda, so the absence of empirical validation of ρ is expected rather than a defect. The more technically load-bearing issue is that the proof of Lemma 1 (and hence Theorem 1) incorrectly assumes P_K is prefix-free. Definition 1 makes P_K closed under prefixes, so Kraft's inequality does not apply. This is a concrete proof gap in one of the paper's main formal results. However, the gap is fixable (restrict to EOS-terminated texts or adjust the normalization), and the paper's other results — the central definition, Proposition 1 (rarity of compressible texts), and Proposition 2 (failure of invariance) — do not depend on the coding theorem. Since the reader's verdict is CONDITIONAL (appropriately, given the paper's status as a formal framework without empirical validation), and since the coding theorem gap is fixable without changing the paper's core contributions, I recommend UNCHANGED. The reader's verdict already captures the right level of caution. The prefix-free issue should be noted as an additional correction needed before the coding theorem result can be relied upon, but it does not move the paper from CONDITIONAL to REJECT because the central definitions and propositions stand independently.","tokens_in":22543,"tokens_out":4484,"duration_ms":177862,"concrete_test":"Construct a minimal concrete example: fix a toy vocabulary V={a,b,eos} with T=3, a simple model where both 'a' and 'b' are always in the nucleus set, and ρ close to 1. Then P_K includes all strings over {a,b} of length ≤ K, plus their extensions with eos. Compute Σ_{p∈P_K} T^{-|p|} for K=3. If this sum exceeds 1 (which it will, since e.g. Σ_{i=0}^{3} 2^i · 3^{-i} = 1 + 2/3 + 4/9 + 8/27 ≈ 2.63 > 1), the Kraft bound in Lemma 1 is violated. Then check whether restricting P_K to EOS-terminated texts restores the bound and whether Theorem 1's inequality still holds under this restriction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's most technically substantive result is the Weak Coding Theorem (Theorem 1, §8.3), which relates prompting probability m_f(t) to model probability P_f(t). The proof of Lemma 1 applies Kraft's inequality to conclude Σ_{p∈P_K} T^{-|p|} ≤ 1, which requires P_K to be a prefix-free set. The paper justifies this by claiming that 'the tokenizer template unambiguously separates system prompts, input prompts, reasoning traces and output texts. Thus texts in P_K are self-delimiting and form a prefix-free set.' However, Definition 1 defines P_K purely via nucleus sampling: a text t=(t_1,...,t_m) is plausible if each t_i ∈ S_ρ(c∥t_{<i}). There is no requirement that texts terminate with a special delimiter token. Under this definition, if t is plausible, then every prefix (t_1,...,t_j) for j<m is also plausible, since the nucleus condition is checked independently at each position. Therefore P_K is closed under taking prefixes and is emphatically not prefix-free. Consequently, Σ_{p∈P_K} T^{-|p|} can exceed 1, the bound in Lemma 1 fails, and the inequality chain in Theorem 1 (specifically the step using Kraft's inequality) is not valid as written. This affects the paper's claim that prompting complexity relates to model probability via a coding-theorem-style bound. The fix is straightforward — restrict P_K to texts ending with an EOS token, or use a different normalization — but as stated, the proof has a genuine gap. The central definition (Definition 3) and Propositions 1–2 do not depend on this result and remain sound.","agreement_with_reader":"partial"},"referee_report":{"model":"glm-5.2","summary":"The paper introduces 'prompting complexity' Ψ_f(t), defined as the length of the shortest plausible prompt that causes a fixed language model f to deterministically generate a target text t. The framework draws an analogy to resource-bounded Kolmogorov complexity, replacing the universal machine with a specific LM and arbitrary programs with plausible, human-readable texts (constrained by nucleus sampling). The paper extends this to soft prompting complexity (allowing approximate outputs), prompting distance (comparing texts via their shortest prompts), and behavioral prompting complexity (reaching any output satisfying a specification judged by an LM). Propositions establish that highly compressible texts are rare, that no model-independent invariance theorem holds, and that behavioral complexity generalizes the exact and soft variants. A weak coding theorem relates prompting probability to model probability.","tokens_in":22862,"tokens_out":951,"duration_ms":238614,"significance":"The paper provides a clean, self-contained formal framework that is well-motivated by practical prompt engineering. The definitions are carefully constructed from standard concepts (Kolmogorov complexity, nucleus sampling, rate-distortion), and the propositions are correctly proven given the definitions. Propositions 1 (rarity of compressible texts) and 2 (failure of invariance) are straightforward but useful counting arguments. The framework offers a principled vocabulary for unifying several phenomena—prompt optimization, synthetic data analysis, safety, and text similarity—and defines a clear, falsifiable research agenda. The extension to behavioral specifications via LM-as-a-judge is a natural and practically relevant generalization.","major_comments":[{"comment":"§8.3, Lemma 1: The proof applies Kraft's inequality to conclude Σ_{p∈P_K} T^{-|p|} ≤ 1, which requires P_K to be a prefix-free set. The paper justifies this by claiming that 'the tokenizer template unambiguously separates system prompts, input prompts, reasoning traces and output texts. Thus texts in P_K are self-delimiting and form a prefix-free set.' However, Definition 1 defines P_K purely via nucleus sampling: a text t=(t_1,...,t_m) is plausible if each t_i ∈ S_ρ(c∥t_{<i}). Under this definition, if t is plausible, then every prefix (t_1,...,t_j) for j<m is also plausible, since the nucleus condition is checked independently at each position. Therefore P_K is closed under taking prefixes and is not prefix-free. Consequently, Σ_{p∈P_K} T^{-|p|} can exceed 1, the bound in Lemma 1 fails, and the inequality chain in Theorem 1 (specifically the step using Kraft's inequality) is not valid.","section":null}],"minor_comments":[{"comment":"§4, Definition 3: The notation f_{τ=0}(p) = t is used in Eq. (6), but the subscript τ=0 is not introduced before this point in the main text. Clarify that this refers to deterministic (greedy) decoding.","section":null},{"comment":"Table 1: The column header reads 'Plausible, Self-Delimiting texts' but the self-delimiting property is not formally established in Definition 1 (it is only informally claimed in §8.3). This header should be revised to avoid asserting a property that is not proven.","section":null},{"comment":"§5.1, Definition 6: The prompting distance d_Ψ depends on the choice of two distances d and d', but the notation d_Ψ does not reflect this dependence. Consider writing d_{Ψ,d,d'} or clarifying in the text.","section":null},{"comment":"§7.5: 'DeepSeek-R1 [12]' — the reference is listed as 'Deepseek [12]' in §3. Standardize the name.","section":null},{"comment":"§1.1, R4: 'performace' should be 'performance.'","section":null},{"comment":"§6, Eq. (19): The judge function J_j is introduced but its relationship to the LM f (is the judge the same model? a different model?) is not specified. A brief clarification would help.","section":null}],"recommendation":"major_revision","confidential_remarks":"The prefix-free issue identified in the stress-test is a genuine gap in the proof of Lemma 1 and Theorem 1. The fix is straightforward (restrict P_K to texts ending with EOS, or use a different normalization), but it is load-bearing for the coding theorem result. The central definitions (Definition 3) and Propositions 1-2 do not depend on this and remain valid. I recommend major revision to give the author the opportunity to fix this cleanly."},"author_rebuttal":{"model":"glm-5.2","summary":"The referee identifies a genuine technical error in Lemma 1: the set P_K of plausible texts is closed under prefixes (not prefix-free) under Definition 1, so Kraft's inequality cannot be applied as stated. We agree this is correct and will revise the proof. The core definitions, propositions, and framework are unaffected; only the proof of Lemma 1 and the derivation in Theorem 1 require modification.","responses":[{"response":"The referee is entirely correct on the mathematical point. Under Definition 1, if a text t = (t_1, ..., t_m) is plausible, then every prefix (t_1, ..., t_j) for j < m is also plausible, because the nucleus membership condition is checked independently at each position. Therefore P_K is closed under taking prefixes and is not prefix-free. Kraft's inequality cannot be applied to P_K as currently stated, and the bound Σ_{p∈P_K} T^{-|p|} ≤ 1 does not follow from the argument given in Lemma 1. We acknowledge this error without qualification. We will revise the proof in the next version. The fix is straightforward and does not affect the definitions, other propositions, or the overall framework. Specifically, we will restrict the sum in Lemma 1 to a prefix-free subset of P_K. The natural choice is the set of plausible texts that are maximal (i.e., terminated by an end-of-sequence token or the context bound), which is prefix-free by construction: if a text is maximal, no proper prefix is maximal. Alternatively, one can define a prefix-free encoding by appending a fixed end-of-sequence marker to each prompt and summing only over such completed prompts. Under either approach, Kraft's inequality applies to the restricted set, yielding Σ_{p∈P_K*} T^{-|p|} ≤ 1 for the prefix-free subset P_K* ⊆ P_K. The prompting probability m_f(t) is then defined as a sum over this prefix-free subset (or equivalently, the definition is adjusted to sum over completed prompts). The key identity m_f(t) = T^{-Ψ_f(t)} · Z_f(t) and the inequality chain in Theorem 1 remain valid under this restriction, since the shortest prompt p* ↣ t is itself a completed prompt and thus belongs to P_K*. The only change is that m_f becomes a semimeasure over a prefix-free subset rather than over all of P_K, which is in类比","revision_made":"no","referee_comment":"§8.3, Lemma 1: The proof applies Kraft's inequality to conclude Σ_{p∈P_K} T^{-|p|} ≤ 1, which requires P_K to be a prefix-free set. The paper justifies this by claiming that 'the tokenizer template unambiguously separates system prompts, input prompts, reasoning traces and output texts. Thus texts in P_K are self-delimiting and form a prefix-free set.' However, Definition 1 defines P_K purely via nucleus sampling: a text t=(t_1,...,t_m) is plausible if each t_i ∈ S_ρ(c∥t_{<i}). Under this definition, if t is plausible, then every prefix (t_1,...,t_j) for j<m is also plausible, since the nucleus condition is checked independently at each position. Therefore P_K is closed under taking prefixes and is not prefix-free. Consequently, Σ_{p∈P_K} T^{-|p|} can exceed 1, the bound in Lemma 1 fails, and the inequality chain in Theorem 1 (specifically the step using Kraft's inequality) is not valid."}],"tokens_in":22275,"tokens_out":771,"duration_ms":152933,"standing_objections":[]},"desk_editor":{"model":"glm-5.2","letter":"This paper defines prompting complexity — the length of the shortest plausible prompt that makes a fixed LM deterministically generate a target text — and extends it to soft (approximate) and behavioral (specification-based) variants. The core idea is clean and well-motivated: treat the prompt as a program, the LM as a non-universal interpreter, and measure model-relative compressibility. The central definition (Definition 3) is sound, and the two main propositions are correct: Proposition 1 (compressible texts are rare) is a straightforward counting argument, and Proposition 2 (failure of invariance across models) is the right observation — prompting complexity is intrinsically model-dependent, and the paper is honest about this being a feature, not a bug. The extensions to soft prompting complexity, prompting distance, and behavioral complexity are natural and give a useful shared vocabulary for things that are usually discussed separately (memorization, jailbreaks, synthetic data, prompt optimization). The paper is upfront that it is a research agenda, not an empirical study, and the research questions it poses are reasonable. Credit is due for writing definitions that are actually precise enough to check, which is not always the case in this kind of work. The stress-test concern about Theorem 1 (the Weak Coding Theorem) lands. Lemma 1 applies Kraft's inequality to conclude that the sum of T^{-|p|} over plausible prompts is at most 1, which requires P_K to be prefix-free. But Definition 1 defines plausibility via nucleus sampling at each position independently, so if a text is plausible, every prefix of it is also plausible. P_K is prefix-closed, not prefix-free. The paper's justification — that tokenizer templates make texts self-delimiting — doesn't fix this: the template adds role markers, but the set P_K as defined doesn't require texts to terminate with a delimiter. So Kraft's inequality doesn't apply as stated, and the bound in Lemma 1 can fail. The fix is simple: restrict P_K to texts ending with EOS, or use a different normalization. This gap affects Theorem 1 and the prompting probability definition, but not Definition 3 or Propositions 1–2, which are the load-bearing parts of the paper. The reader's concern about the arbitrary choice of ρ is valid but minor — it's a design parameter, and the paper is transparent about it. This is a solid formal framework paper with one fixable proof gap in a secondary result. The main definitions and propositions are correct and useful. It deserves a serious referee who can verify the fix and push on whether the framework generates non-trivial empirical predictions.","headline":"Clean formal framework for model-relative prompt complexity; one proof gap in the coding theorem, fixable; main definitions and propositions hold.","tokens_in":23315,"tokens_out":1388,"would_cite":true,"duration_ms":111564,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"glm-5.2","headline":"Shortest prompt that generates a text is a model-relative Kolmogorov complexity","keywords":[],"falsifier":"If empirical studies found that the choice of nucleus threshold ρ does not meaningfully change which prompts are considered plausible — or that the boundary between plausible and implausible prompts is so sharp that the entire framework reduces to either all-prompts or almost-no-prompts — then the restriction to P_K would not formalize human-readable prompt engineering as intended.","tokens_in":22618,"feed_emoji":"📏","tokens_out":1025,"duration_ms":58776,"temperature":0.7,"pith_summary":"This paper defines prompting complexity, a formal measure of the length of the shortest human-readable prompt that causes a fixed language model to deterministically produce a target text. The central object is Ψ_f(t), defined as the minimum length of a plausible prompt p such that model f, under deterministic decoding, outputs text t. The author frames this as a model-relative analogue of Kolmogorov complexity: the prompt is the program, the model is the interpreter, and information not in the prompt is supplied by the model's weights, training data, tokenizer, and decoding rule. Unlike classical Kolmogorov complexity, which enjoys an invariance theorem (the complexity of a string is roughly the same regardless of which universal machine you pick), prompting complexity has no such invariance: the same text can be cheap for one model (because it was memorized) and inaccessible to another. The paper proves this failure of invariance (Proposition 2), shows that highly compressible texts are rare (Proposition 1), and establishes a weak coding theorem linking prompting probability to ordinary model probability. The author extends the exact definition to soft prompting complexity (allowing approximate outputs within a distance threshold), prompting distance (comparing texts by comparing their shortest generating prompts), and behavioral prompting complexity (shortest prompt to reach any output satisfying a judge-defined specification). The paper is primarily definitional and agenda-setting: it provides the formal vocabulary and poses empirical questions rather than answering them.","feed_headline":"Shortest prompt to generate a text defines model-relative complexity","feed_subtitle":"Formal measure Ψ_f(t) mirrors Kolmogorov complexity but provably lacks a model-independent invariance theorem, making compression a property","key_machinery":"prompting complexity Ψ_f(t)","core_discovery":"The central claim is that prompting complexity Ψ_f(t) := min{|p| : p ∈ P_K, f_{τ=0}(p) = t} is a well-defined, computable-in-principle, model-relative analogue of Kolmogorov complexity for language models, and that it provably lacks a model-independent invariance theorem. The author proves that for any constant C, two language models f and g can be found that assign prompting complexities differing by more than C to the same text — because one model may have memorized the text and can elicit it with a short identifier-like prompt, while the other cannot. This means prompting complexity is not a property of a text but of a text-model pair. The paper also shows that the fraction of texts that,","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Prompting complexity: shortest prompt that yields a target text","Shortest generating prompt is model-relative, no invariance theorem","Prompt length as Kolmogorov analogue lacks model-independent bound","Same text can be cheap for one LM and costly for another","Prompting complexity is a text-model pair property, not text alone"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The definition of plausible texts P_K restricts the prompt search space to high-probability token sequences under a nucleus sampling threshold ρ, but the choice of ρ is arbitrary and model-dependent, with no empirical validation that a specific value captures the boundary between human-readable prompts and adversarial artifacts.","fun_headline_variants_meta":{"raw":{"variants":["Prompting complexity: shortest prompt that yields a target text","Shortest generating prompt is model-relative, no invariance theorem","Prompt length as Kolmogorov analogue lacks model-independent bound","Same text can be cheap for one LM and costly for another","Prompting complexity is a text-model pair property, not text alone"]},"model":"glm-5.2","effort":"high","cost_usd":0.0,"raw_usage":{"total_tokens":693,"prompt_tokens":622,"completion_tokens":71,"prompt_tokens_details":null},"tokens_in":622,"tokens_out":71,"duration_ms":22477,"temperature":1.0,"reasoning_tokens":null,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-08T15:10:31.101841+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"If empirical studies found that the choice of nucleus threshold ρ does not meaningfully change which prompts are considered plausible — or that the boundary between plausible and implausible prompts is so sharp that the entire framework reduces to either all-prompts or almost-no-prompts — then the restriction to P_K would not formalize human-readable prompt engineering as intended.","supporting_citations":[],"review_version":1}