Prompting Complexity: Shortest Prompts for Texts and Behaviors in LLMs
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 i
Lineage graph
Paper → model → repo connections mined from source citations (Tier-1 exact match).
Why these links exist
Every edge carries a method, confidence, and the source snippet that justified it — so bad links are debuggable.
- PossiblePossibly related (embedding) · 55%KennispuntTwente/tidyprompt →
- PossiblePossibly related (embedding) · 51%linshenkx/prompt-optimizer →
- PossiblePossibly related (embedding) · 50%Would having a dedicated programming language specifically for LLMs be a viable solution? [D] →
- PossiblePossibly related (embedding) · 50%minimal-diffusion-lm →
- PossiblePossibly related (embedding) · 50%Can We Understand How Large Language Models Reason? - Communications of the ACM →
- PossiblePossibly related (embedding) · 47%vicentereig/dspy.rb →
- FuzzySimilar title/name (fuzzy) · 87%f/prompts.chat →
“Fuzzy title match (0.94): “Prompting Complexity: Shortest Prompts for Texts and Behavio” ≈ “f/prompts.chat””
- LinkedLinked via arxiv author · 85%Adrian Cosma →
“Prompting Complexity: Shortest Prompts for Texts and Behaviors in LLMs”