mlsanityData to 7 Oct 2026

Prompting Complexity: Shortest Prompts for Texts and Behaviors in LLMs

arXiv 2607.06145 ↗First posted 7 Jul 2026cs.CLcited by 1

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 32 of its 57 references that are in the map. First posted on arXiv 7 Jul 2026.

Builds on

32 of 57 references.

References · 32

  1. 2020Language Models are Few-Shot Learnerscited by 32,199
  2. 2022Training language models to follow instructions with human feedbackcited by 15,712
  3. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 13,958
  4. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  5. 2019The Curious Case of Neural Text Degenerationcited by 2,881
  6. 2025Gemma 3 Technical Reportcited by 1,686
  7. 2024A Survey on LLM-as-a-Judgecited by 1,384
  8. 2023DSPy: Compiling Declarative Language Model Calls into Self-Improving Pipelinescited by 803
  9. 2023DetectGPT: Zero-Shot Machine-Generated Text Detection using Probability Curvaturecited by 705
  10. 2023Automatic Prompt Optimization with "Gradient Descent" and Beam Searchcited by 628
  11. 2021Prompt Programming for Large Language Models: Beyond the Few-Shot Paradigmcited by 599
  12. 2024Hallucination is Inevitable: An Innate Limitation of Large Language Modelscited by 329
20 more
  1. 2025Darwin Godel Machine: Open-Ended Evolution of Self-Improving Agentscited by 294
  2. 2022On The Computational Complexity of Self-Attentioncited by 137
  3. 2023Amortizing intractable inference in large language modelscited by 94
  4. 2020Evolution of Semantic Similarity -- A Surveycited by 83
  5. 2025Universal Model Routing for Efficient LLM Inferencecited by 80
  6. 2023Dynamic Context Pruning for Efficient and Interpretable Autoregressive Transformerscited by 67
  7. 2023LongForm: Effective Instruction Tuning with Reverse Instructionscited by 47
  8. 2024EmbedLLM: Learning Compact Representations of Large Language Modelscited by 46
  9. 2025Learning without training: The implicit dynamics of in-context learningcited by 41
  10. 2024Large Language Models as Markov Chainscited by 33
  11. 2025Language Models are Injective and Hence Invertiblecited by 31
  12. 2024Zero-Shot Tokenizer Transfercited by 30
  13. 2025Why Prompt Design Matters and Works: A Complexity Analysis of Prompt Search Space in LLMscited by 29
  14. 2024G"odel Agent: A Self-Referential Agent Framework for Recursive Self-Improvementcited by 27
  15. 2024The Foundations of Tokenization: Statistical and Computational Concernscited by 20
  16. 2023Meaning Representations from Trajectories in Autoregressive Modelscited by 18
  17. 2025Learning Algorithms in the Limitcited by 9
  18. 2023Description-Based Text Similaritycited by 7
  19. 2024Interpretable Measures of Conceptual Similarity by Complexity-Constrained Descriptive Auto-Encodingcited by 4
  20. 2025On Surjectivity of Neural Networks: Can you elicit any behavior from your model?cited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026The Value of a Prompt: An LLM-Relative Kolmogorov-Complexity Approachcited by 0