This paper defines prompting complexity as the length of the shortest plausible prompt required to make a deterministic decoding process produce a target text using a fixed instruction-tuned language model. It presents this measure as an LM-relative analogue of resource-bounded Kolmogorov complexity, where the model interface acts as the interpreter.
- The framework restricts programs to human-readable texts to align with prompt engineering practices.
- The authors extend the definition to soft prompting complexity for approximate outputs and define prompting distance by comparing shortest generating prompts.
- A research agenda is proposed for empirically studying which texts and behaviors are accessible from short plausible prompts under a fixed LM interface.