Kolmogorov complexity

Prompting Complexity: A Kolmogorov-Inspired Formal Framework for Shortest LLM Prompts

A new arXiv preprint introduces 'prompting complexity,' a model-relative analogue of resource-bounded Kolmogorov complexity that measures the shortest plausible human-readable prompt needed to make a deterministic LLM produce a target text. The framework extends to soft prompting complexity for approximate outputs, prompting distance, and behavioral prompting complexity for specification-satisfying outputs. Unlike classical Kolmogorov complexity, the measure is intentionally non-universal and model-specific, with no invariance theorem across models. The paper lays out a research agenda for empirically studying which texts and behaviors are accessible from short prompts under a fixed model interface.