# Prompting Complexity: Shortest Prompts for Texts and Behaviors in LLMs

arXiv: https://arxiv.org/abs/2607.06145 · HTML: https://mlsanity.com/paper/2607.06145/

## Key facts

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

## Builds on (most cited first, 30 of 32)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Gemma 3 Technical Report](https://mlsanity.com/paper/2503.19786/) (2025)
- [A Survey on LLM-as-a-Judge](https://mlsanity.com/paper/2411.15594/) (2024)
- [DSPy: Compiling Declarative Language Model Calls into Self-Improving Pipelines](https://mlsanity.com/paper/2310.03714/) (2023)
- [DetectGPT: Zero-Shot Machine-Generated Text Detection using Probability Curvature](https://mlsanity.com/paper/2301.11305/) (2023)
- [Automatic Prompt Optimization with "Gradient Descent" and Beam Search](https://mlsanity.com/paper/2305.03495/) (2023)
- [Prompt Programming for Large Language Models: Beyond the Few-Shot Paradigm](https://mlsanity.com/paper/2102.07350/) (2021)
- [Darwin Godel Machine: Open-Ended Evolution of Self-Improving Agents](https://mlsanity.com/paper/2505.22954/) (2025)
- [Hallucination is Inevitable: An Innate Limitation of Large Language Models](https://mlsanity.com/paper/2401.11817/) (2024)
- [On The Computational Complexity of Self-Attention](https://mlsanity.com/paper/2209.04881/) (2022)
- [Amortizing intractable inference in large language models](https://mlsanity.com/paper/2310.04363/) (2023)
- [Universal Model Routing for Efficient LLM Inference](https://mlsanity.com/paper/2502.08773/) (2025)
- [Evolution of Semantic Similarity -- A Survey](https://mlsanity.com/paper/2004.13820/) (2020)
- [Dynamic Context Pruning for Efficient and Interpretable Autoregressive Transformers](https://mlsanity.com/paper/2305.15805/) (2023)
- [EmbedLLM: Learning Compact Representations of Large Language Models](https://mlsanity.com/paper/2410.02223/) (2024)
- [LongForm: Effective Instruction Tuning with Reverse Instructions](https://mlsanity.com/paper/2304.08460/) (2023)
- [Learning without training: The implicit dynamics of in-context learning](https://mlsanity.com/paper/2507.16003/) (2025)
- [Large Language Models as Markov Chains](https://mlsanity.com/paper/2410.02724/) (2024)
- [Language Models are Injective and Hence Invertible](https://mlsanity.com/paper/2510.15511/) (2025)
- [Zero-Shot Tokenizer Transfer](https://mlsanity.com/paper/2405.07883/) (2024)
- [Why Prompt Design Matters and Works: A Complexity Analysis of Prompt Search Space in LLMs](https://mlsanity.com/paper/2503.10084/) (2025)
- [G"odel Agent: A Self-Referential Agent Framework for Recursive Self-Improvement](https://mlsanity.com/paper/2410.04444/) (2024)
- [The Foundations of Tokenization: Statistical and Computational Concerns](https://mlsanity.com/paper/2407.11606/) (2024)
- [Meaning Representations from Trajectories in Autoregressive Models](https://mlsanity.com/paper/2310.18348/) (2023)
- [Learning Algorithms in the Limit](https://mlsanity.com/paper/2506.15543/) (2025)
- [Description-Based Text Similarity](https://mlsanity.com/paper/2305.12517/) (2023)

## Built on by (most cited first, 1 of 1)

- [The Value of a Prompt: An LLM-Relative Kolmogorov-Complexity Approach](https://mlsanity.com/paper/2608.16438/) (2026)

## 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.