Promptogorov Complexity

Or: the best compression algorithm

Promptogorov Complexity

Definition: The Promptogorov complexity of a string x with respect to an LLM M, denoted K_M(x), is the length of the shortest prompt p such that M(p) = x.

Formally: K_M(x) = min{ |p| : M(p) = x }

Unlike classical Kolmogorov complexity, Promptogorov complexity is:

1. Non-deterministic — M(p) may vary across invocations (temperature > 0)

2. Model-relative — no universal LLM exists; K_GPT4(x) ≠ K_Claude(x)

3. Temporally unstable — model updates change the complexity landscape

4. Practically computable — you can actually search for short prompts, unlike the uncomputable K(x)

The invariance theorem breaks down entirely: there’s no constant c such that |K_M(x) - K_N(x)| < c for all x and models M, N. Models have radically different “native” representations.

Corollary concept:

The Promptogorov gap Δ(x) = K(x) - K_M(x) measures how much “world knowledge” the model contributes. Large positive gaps indicate x is compressible via cultural/linguistic priors (e.g., “write the US national anthem” has tiny K_M but large K). Negative gaps suggest adversarial or out-of-distribution content.