Pith. sign in

REVIEW 1 major objections 6 minor 58 references

Reviewed by Pith at T0; open to challenge.

T0 means a machine referee read the full paper against a public rubric. The mark states how deep the mechanical check went, never who wrote it. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · glm-5.2

Shortest prompt that generates a text is a model-relative Kolmogorov complexity

2026-07-08 15:10 UTC pith:464T7KWP

load-bearing objection Clean formal framework for model-relative prompt complexity; one proof gap in the coding theorem, fixable; main definitions and propositions hold. the 1 major comments →

arxiv 2607.06145 v1 pith:464T7KWP submitted 2026-07-07 cs.CL

Prompting Complexity: Shortest Prompts for Texts and Behaviors in LLMs

Adrian Cosma This is my paper
classification cs.CL
keywords complexitypromptpromptingmodeldefineplausiblepromptsshortest
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

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.

Core claim

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,

What carries the argument

prompting complexity Ψ_f(t)

Load-bearing premise

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.

What would settle it

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.

Watch this falsifier — get emailed when new claim-graph text bears on it.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 6 minor

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.

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 (1)
  1. §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.
minor comments (6)
  1. §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.
  2. 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.
  3. §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.
  4. §7.5: 'DeepSeek-R1 [12]' — the reference is listed as 'Deepseek [12]' in §3. Standardize the name.
  5. §1.1, R4: 'performace' should be 'performance.'
  6. §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.

Simulated Author's Rebuttal

1 responses · 0 unresolved

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.

read point-by-point responses

  1. Referee: §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.

    Authors: 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: no

Circularity Check

0 steps flagged

No circularity found: definitions are self-contained and derived results follow from stated assumptions

full rationale

The paper constructs a formal framework for prompting complexity from standard concepts (Kolmogorov complexity, nucleus sampling, Kraft's inequality) without fitting parameters to data and then renaming fits as predictions. Definition 3 (Ψ_f(t)) is a direct minimization over a finite search space, not a quantity defined in terms of itself. Proposition 1 (rarity of compressible texts) follows from a counting argument: deterministic decoding means each prompt maps to at most one output, so the number of c-compressible texts is bounded by the number of short prompts — this is a standard pigeonhole argument, not circular. Proposition 2 (failure of invariance) constructs two models f, g where one memorizes a text and the other does not, deriving the gap from the definitions; the proof is self-contained. The Weak Coding Theorem (Theorem 1) relates m_f(t) to P_f(t) via algebraic manipulation of the definitions and a lower bound on greedy-token probability; the steps are Eq. (34) → Eq. (42) → Eq. (43), which are direct substitutions. The self-citation to [54] (Zekri et al., 'LLMs as Markov chains') is used only for the finite-sequence formalism V^K and the observation that τ>0 allows exploring the full vocabulary — it is a framing reference, not load-bearing for any theorem. No theorem's conclusion appears as its own premise. The prefix-free gap in Lemma 1 (P_K is closed under prefixes by Definition 1, so Kraft's inequality may not apply as stated) is a correctness concern, not a circularity issue: the proof attempts to use an external mathematical tool (Kraft's inequality) on the defined set, and the gap is whether the tool's preconditions are met, not whether the result is true by definition. The paper's central claims (Definition 3, Propositions 1–2, the research agenda) do not reduce to their inputs by construction.

Axiom & Free-Parameter Ledger

3 free parameters · 3 axioms · 0 invented entities

The paper introduces no new physical entities or particles. The 'plausible text' set P_K is a formal construction, not an invented entity. The free parameters (ρ, τ, K) are standard interface choices, not fitted constants. The axioms are standard domain assumptions about LLMs, with the plausibility restriction being the key ad-hoc methodological choice.

free parameters (3)
  • ρ (nucleus threshold)
    The threshold for plausible text (Definition 1) is a free parameter that determines the size of P_K. It is not fitted to data but must be chosen by the practitioner.
  • τ (temperature)
    Used in the definition of plausible text, though deterministic decoding (τ=0) is used for the final complexity measure.
  • K (max context length)
    A fixed parameter of the model interface, bounding the search space.
axioms (3)
  • domain assumption Language models are computable and polynomially bounded (Proposition 8).
    The paper assumes LMs can be treated as computable functions that always halt, which is true for finite-context transformer inference.
  • ad hoc to paper Plausible texts P_K are a meaningful formalization of human-readable prompts.
    The restriction to nucleus-sampled texts is the core methodological choice. The paper argues for it but does not empirically prove it captures 'human-readability'.
  • domain assumption Next-token probabilities approximately follow a power law along plausible prefixes.
    Used in Proposition 9 to estimate the number of plausible texts. The author notes this is a simplification.

pith-pipeline@v1.1.0-glm · 25274 in / 2370 out tokens · 299575 ms · 2026-07-08T15:10:31.101841+00:00 · methodology

0 comments
read the original abstract

In this paper, we define the quantity of prompting 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 to soft prompting complexity for approximate outputs, yielding a lossy notion of model-relative text compression and a formal target for prompt optimization. We also define prompting distance by comparing shortest generating prompts, and behavioral prompting complexity for 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.

Figures

Figures reproduced from arXiv: 2607.06145 by Adrian Cosma.

Figure 1
Figure 1. Figure 1: Illustration of prompting complexity concepts developed in this work. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

58 extracted references · 58 canonical work pages · 26 internal anchors

  1. [1]

    Interpretable measures of conceptual similarity by complexity-constrained descriptive auto-encoding

    Alessandro Achille, Greg Ver Steeg, Tian Yu Liu, Matthew Trager, Carson Klingenberg, and Stefano Soatto. Interpretable measures of conceptual similarity by complexity-constrained descriptive auto-encoding. InProceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11062–11071, 2024

    work page 2024

  2. [2]

    Dynamic context pruning for efficient and interpretable autoregressive transformers

    Sotiris Anagnostidis, Dario Pavllo, Luca Biggio, Lorenzo Noci, Aurelien Lucchi, and Thomas Hofmann. Dynamic context pruning for efficient and interpretable autoregressive transformers. Advances in Neural Information Processing Systems, 36:65202–65223, 2023

    work page 2023

  3. [3]

    Language models are few-shot learners.Advances in neural information processing systems, 33:1877–1901, 2020

    Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, et al. Language models are few-shot learners.Advances in neural information processing systems, 33:1877–1901, 2020

    work page 1901

  4. [4]

    Evolution of semantic similarity—a survey.Acm Computing Surveys (Csur), 54(2):1–37, 2021

    Dhivya Chandrasekaran and Vijay Mago. Evolution of semantic similarity—a survey.Acm Computing Surveys (Csur), 54(2):1–37, 2021

    work page 2021

  5. [5]

    The smallest grammar problem.IEEE Transactions on Information Theory, 51(7): 2554–2576, 2005

    Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, Amit Sahai, and Abhi Shelat. The smallest grammar problem.IEEE Transactions on Information Theory, 51(7): 2554–2576, 2005

    work page 2005

  6. [6]

    GenDLN: Evolutionary Algorithm-Based Stacked LLM Framework for Joint Prompt Optimization

    Pia Chouayfati, Niklas Herbster, Ábel Domonkos Sáfrán, and Matthias Grabmair. GenDLN: Evolutionary Algorithm-Based Stacked LLM Framework for Joint Prompt Optimization. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 4: Student Research Workshop), pages 1171–1212, 2025

    work page 2025

  7. [7]

    Language Modeling Is Compression,

    Grégoire Delétang, Anian Ruoss, Paul-Ambroise Duquenne, Elliot Catt, Tim Genewein, Christo- pher Mattern, Jordi Grau-Moya, Li Kevin Wenliang, et al. Language Modeling Is Compression,

    work page

  8. [8]

    URLhttps://arxiv.org/abs/2309.10668. 17

    work page internal anchor Pith review Pith/arXiv arXiv

  9. [9]

    Learning without training: The implicit dynamics of in-context learning

    Benoit Dherin, Michael Munn, Hanna Mazzawi, Michael Wunder, and Javier Gonzalvo. Learning without training: The implicit dynamics of in-context learning, 2025. URL https://arxiv.org/abs/2507.16003

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  10. [10]

    L1b3rt4s: Totally harmless liberation prompts for good Lil Ai’s!, 2025/8/4

    elder_plinius. L1b3rt4s: Totally harmless liberation prompts for good Lil Ai’s!, 2025/8/4 . URL https://github.com/elder-plinius/L1B3RT4S

    work page 2025

  11. [11]

    The Foundations of Tokenization: Statistical and Computational Concerns

    Juan Luis Gastaldi, John Terilla, Luca Malagutti, Brian DuSell, Tim Vieira, and Ryan Cot- terell. The foundations of tokenization: Statistical and computational concerns.arXiv preprint arXiv:2407.11606, 2024

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  12. [12]

    A survey on LLM-as-a-judge.The Innovation, 7(6), 2026

    Jiawei Gu, Xuhui Jiang, Zhichao Shi, Hexiang Tan, Xuehao Zhai, Chengjin Xu, Wei Li, Yinghan Shen, et al. A survey on LLM-as-a-judge.The Innovation, 7(6), 2026

    work page 2026

  13. [13]

    DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning

    Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, et al. Deepseek-R1: Incentivizing reasoning capability in llms via reinforcement learning.arXiv preprint arXiv:2501.12948, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  14. [14]

    The Curious Case of Neural Text Degeneration

    Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration.arXiv preprint arXiv:1904.09751, 2019

    work page internal anchor Pith review Pith/arXiv arXiv 1904

  15. [15]

    Amortizing intractable inference in large language models

    Edward J Hu, Moksh Jain, Eric Elmoznino, Younesse Kaddar, Guillaume Lajoie, Yoshua Bengio, and Nikolay Malkin. Amortizing intractable inference in large language models.arXiv preprint arXiv:2310.04363, 2023

    work page internal anchor Pith review Pith/arXiv arXiv 2023

  16. [16]

    OpenAI o1 System Card

    Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, et al. Openai o1 system card.arXiv preprint arXiv:2412.16720, 2024

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  17. [17]

    On Surjectivity of Neural Networks: Can you elicit any behavior from your model?

    Haozhe Jiang and Nika Haghtalab. On Surjectivity of Neural Networks: Can you elicit any behavior from your model?arXiv preprint arXiv:2508.19445, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  18. [18]

    Universal Model Routing for Efficient LLM Inference

    Wittawat Jitkrittum, Harikrishna Narasimhan, Ankit Singh Rawat, Jeevesh Juneja, Zifeng Wang, Chen-Yu Lee, Pradeep Shenoy, Rina Panigrahy, et al. Universal Model Routing for Efficient LLM Inference.arXiv preprint arXiv:2502.08773, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  19. [19]

    On the computa- tional complexity of self-attention

    Feyza Duman Keles, Pruthuvi Mahesakya Wijewardena, and Chinmay Hegde. On the computa- tional complexity of self-attention. InInternational conference on algorithmic learning theory, pages 597–619. PMLR, 2023

    work page 2023

  20. [20]

    DSPy: Compiling Declarative Language Model Calls into Self-Improving Pipelines.The Twelfth International Conference on Learning Representations, 2024

    Omar Khattab, Arnav Singhvi, Paridhi Maheshwari, Zhiyuan Zhang, Keshav Santhanam, Sri Vardhamanan, Saiful Haq, Ashutosh Sharma, et al. DSPy: Compiling Declarative Language Model Calls into Self-Improving Pipelines.The Twelfth International Conference on Learning Representations, 2024

    work page 2024

  21. [21]

    LongForm: Effective Instruction Tuning with Reverse Instructions

    Abdullatif Köksal, Timo Schick, Anna Korhonen, and Hinrich Schütze. Longform: Effective instruction tuning with reverse instructions.arXiv preprint arXiv:2304.08460, 2023

    work page internal anchor Pith review Pith/arXiv arXiv 2023

  22. [22]

    PhD thesis, Massachusetts Institute of Technology, 1949

    Leon Gordon Kraft.A device for quantizing, grouping, and coding amplitude-modulated pulses. PhD thesis, Massachusetts Institute of Technology, 1949

    work page 1949

  23. [23]

    Binary Codes Capable of Correcting Deletions, Insertions and Reversals

    Vladimir I Levenshtein. Binary Codes Capable of Correcting Deletions, Insertions and Reversals. Soviet Physics Doklady, 10:707, February 1966

    work page 1966

  24. [24]

    Springer, 2008

    Ming Li, Paul Vitányi, et al.An introduction to Kolmogorov complexity and its applications, volume 3. Springer, 2008

    work page 2008

  25. [25]

    Meaning Representations from Trajectories in Autoregressive Models

    Tian Yu Liu, Matthew Trager, Alessandro Achille, Pramuditha Perera, Luca Zancato, and Stefano Soatto. Meaning representations from trajectories in autoregressive models.arXiv preprint arXiv:2310.18348, 2023

    work page internal anchor Pith review Pith/arXiv arXiv 2023

  26. [26]

    Zero-shot tokenizer transfer.arXiv preprint arXiv:2405.07883, 2024

    Benjamin Minixhofer, Edoardo Maria Ponti, and Ivan Vuli´c. Zero-shot tokenizer transfer.arXiv preprint arXiv:2405.07883, 2024. 18

    work page arXiv 2024

  27. [27]

    Detectgpt: Zero-shot machine-generated text detection using probability curvature

    Eric Mitchell, Yoonho Lee, Alexander Khazatsky, Christopher D Manning, and Chelsea Finn. Detectgpt: Zero-shot machine-generated text detection using probability curvature. InInterna- tional Conference on Machine Learning, pages 24950–24962. PMLR, 2023

    work page 2023

  28. [28]

    Language Models are Injective and Hence Invertible, 2025

    Giorgos Nikolaou, Tommaso Mencattini, Donato Crisostomi, Andrea Santilli, Yannis Panagakis, and Emanuele Rodolà. Language Models are Injective and Hence Invertible, 2025. URL https://arxiv.org/abs/2510.15511

    work page arXiv 2025

  29. [29]

    GPT-4 Technical Report

    OpenAI, Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Flo- rencia Leoni Aleman, Diogo Almeida, et al. GPT-4 Technical Report, 2024. URL https: //arxiv.org/abs/2303.08774

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  30. [30]

    Instance complexity.Journal of the ACM (JACM), 41(1):96–121, 1994

    Pekka Orponen, Ker-I Ko, Uwe Schöning, and Osamu Watanabe. Instance complexity.Journal of the ACM (JACM), 41(1):96–121, 1994

    work page 1994

  31. [31]

    Training language models to follow instructions with human feedback

    Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, et al. Training language models to follow instructions with human feedback, 2022. URLhttps://arxiv.org/abs/2203.02155

    work page internal anchor Pith review Pith/arXiv arXiv 2022

  32. [32]

    Learning Algorithms in the Limit

    Hristo Papazov and Nicolas Flammarion. Learning Algorithms in the Limit.arXiv preprint arXiv:2506.15543, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  33. [33]

    Attention is turing-complete.Journal of Machine Learning Research, 22(75):1–35, 2021

    Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is turing-complete.Journal of Machine Learning Research, 22(75):1–35, 2021

    work page 2021

  34. [34]

    When Will the Tokens End? Graph-Based Forecasting for LLMs Output Length

    Grzegorz Piotrowski, Mateusz Bystro´nski, Mikołaj Hołysz, Jakub Binkowski, Grzegorz Chodak, and Tomasz Jan Kajdanowicz. 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), pages 843–848, 2025

    work page 2025

  35. [35]

    gradient descent

    Reid Pryzant, Dan Iter, Jerry Li, Yin Lee, Chenguang Zhu, and Michael Zeng. Automatic prompt optimization with “gradient descent” and beam search. InProceedings of the 2023 conference on empirical methods in natural language processing, pages 7957–7968, 2023

    work page 2023

  36. [36]

    Ask, and it shall be given: On the turing completeness of prompting

    Ruizhong Qiu, Zhe Xu, Wenxuan Bao, and Hanghang Tong. Ask, and it shall be given: On the turing completeness of prompting. InInternational Conference on Learning Representations, volume 2025, pages 6286–6309, 2025

    work page 2025

  37. [37]

    Description-Based Text Similarity

    Shauli Ravfogel, Valentina Pyatkin, Amir DN Cohen, Avshalom Manevich, and Yoav Goldberg. Description-based text similarity.arXiv preprint arXiv:2305.12517, 2023

    work page internal anchor Pith review Pith/arXiv arXiv 2023

  38. [38]

    Prompt programming for large language models: Beyond the few-shot paradigm

    Laria Reynolds and Kyle McDonell. Prompt programming for large language models: Beyond the few-shot paradigm. InExtended abstracts of the 2021 CHI conference on human factors in computing systems, pages 1–7, 2021

    work page 2021

  39. [39]

    SolidGoldMagikarp (plus, prompt generation)

    Jessica Rumbelow and Matthew Watkins. SolidGoldMagikarp (plus, prompt generation). InAI ALIGNMENT FORUM, page 7, 2023

    work page 2023

  40. [40]

    Algorithmic Theories of Everything

    Jürgen Schmidhuber. Algorithmic theories of everything.arXiv preprint quant-ph/0011122, 2000

    work page internal anchor Pith review Pith/arXiv arXiv 2000

  41. [41]

    Goedel Machines: Self-Referential Universal Problem Solvers Making Provably Optimal Self-Improvements.CoRR, cs.LO/0309048, 2003

    Jürgen Schmidhuber. Goedel Machines: Self-Referential Universal Problem Solvers Making Provably Optimal Self-Improvements.CoRR, cs.LO/0309048, 2003. URL http://arxiv. org/abs/cs/0309048

    work page arXiv 2003

  42. [42]

    The Prompt Report: A Systematic Survey of Prompt Engineering Techniques

    Sander Schulhoff, Michael Ilie, Nishant Balepur, Konstantine Kahadze, Amanda Liu, Chenglei Si, Yinheng Li, Aayush Gupta, et al. The prompt report: A systematic survey of prompting techniques.arXiv preprint arXiv:2406.06608, 5, 2024

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  43. [43]

    C. E. Shannon. A mathematical theory of communication.The Bell System Technical Journal, 27(3):379–423, 1948. doi: 10.1002/j.1538-7305.1948.tb01338.x

    work page doi:10.1002/j.1538-7305.1948.tb01338.x 1948

  44. [44]

    LLM With Tools: A Survey, 2024

    Zhuocheng Shen. LLM With Tools: A Survey, 2024. URL https://arxiv.org/abs/2409. 18807. 19

    work page 2024

  45. [45]

    Auto- prompt: Eliciting knowledge from language models with automatically generated prompts

    Taylor Shin, Yasaman Razeghi, Robert L Logan Iv, Eric Wallace, and Sameer Singh. Auto- prompt: Eliciting knowledge from language models with automatically generated prompts. InProceedings of the 2020 conference on empirical methods in natural language processing (EMNLP), pages 4222–4235, 2020

    work page 2020

  46. [46]

    Solomonoff

    R.J. Solomonoff. A formal theory of inductive inference. Part I.Information and Control, 7 (1):1–22, 1964. ISSN 0019-9958. doi: https://doi.org/10.1016/S0019-9958(64)90223-2. URL https://www.sciencedirect.com/science/article/pii/S0019995864902232

    work page doi:10.1016/s0019-9958(64)90223-2 1964

  47. [47]

    Gemma 3 Technical Report

    Gemma Team, Aishwarya Kamath, Johan Ferret, Shreya Pathak, Nino Vieillard, Ramona Merhej, Sarah Perrin, Tatiana Matejovicova, et al. Gemma 3 technical report.arXiv preprint arXiv:2503.19786, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  48. [48]

    Qwen2.5 Technical Report

    Qwen Team, An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, et al. Qwen2.5 Technical Report, 2025. URLhttps://arxiv.org/abs/2412.15115

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  49. [49]

    LLaMA: Open and Efficient Foundation Language Models

    Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Tim- othée Lacroix, Baptiste Rozière, Naman Goyal, et al. Llama: Open and efficient foundation language models.arXiv preprint arXiv:2302.13971, 2023

    work page internal anchor Pith review Pith/arXiv arXiv 2023

  50. [50]

    On computable numbers, with an application to the Entschei- dungsproblem.J

    Alan Mathison Turing et al. On computable numbers, with an application to the Entschei- dungsproblem.J. of Math, 58(345-363):5, 1936

    work page 1936

  51. [51]

    Chain-of-thought prompting elicits reasoning in large language models

    Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824–24837, 2022

    work page 2022

  52. [52]

    Hallucination is Inevitable: An Innate Limitation of Large Language Models

    Ziwei Xu, Sanjay Jain, and Mohan Kankanhalli. Hallucination is inevitable: An innate limitation of large language models.arXiv preprint arXiv:2401.11817, 2024

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  53. [53]

    G\"odel Agent: A Self-Referential Agent Framework for Recursive Self-Improvement

    Xunjian Yin, Xinyi Wang, Liangming Pan, Li Lin, Xiaojun Wan, and William Yang Wang. G\" odel agent: A self-referential agent framework for recursive self-improvement.arXiv preprint arXiv:2410.04444, 2024

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  54. [54]

    Optimizing generative AI by backpropagating language model feedback.Nature, 639:609–616, 2025

    Mert Yuksekgonul, Federico Bianchi, Joseph Boen, Sheng Liu, Pan Lu, Zhi Huang, Carlos Guestrin, and James Zou. Optimizing generative AI by backpropagating language model feedback.Nature, 639:609–616, 2025

    work page 2025

  55. [55]

    Large Language Models as Markov Chains

    Oussama Zekri, Ambroise Odonnat, Abdelhakim Benechehab, Linus Bleistein, Nicolas Boullé, and Ievgen Redko. Large language models as markov chains.arXiv preprint arXiv:2410.02724, 2024

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  56. [56]

    Darwin Godel Machine: Open-Ended Evolution of Self-Improving Agents

    Jenny Zhang, Shengran Hu, Cong Lu, Robert Lange, and Jeff Clune. Darwin Godel Machine: Open-Ended Evolution of Self-Improving Agents.arXiv preprint arXiv:2505.22954, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  57. [57]

    Why Prompt Design Matters and Works: A Complexity Analysis of Prompt Search Space in LLMs

    Xiang Zhang, Juntai Cao, Jiaqi Wei, Chenyu You, and Dujian Ding. Why Prompt Design Matters and Works: A Complexity Analysis of Prompt Search Space in LLMs.arXiv preprint arXiv:2503.10084, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  58. [58]

    EmbedLLM: Learning Compact Representations of Large Language Models

    Richard Zhuang, Tianhao Wu, Zhaojin Wen, Andrew Li, Jiantao Jiao, and Kannan Ramchandran. EmbedLLM: Learning Compact Representations of Large Language Models.arXiv preprint arXiv:2410.02223, 2024. Appendix 8.1 LMs are computable and polynomially bounded Proposition 8.A LM f is computable, and it is polynomially space- and time-bounded by O(K3), withKthe m...

    work page internal anchor Pith review Pith/arXiv arXiv 2024