Prompting Complexity: Shortest Prompts for Texts and Behaviors in LLMs

• URL: http://arxiv.org/abs/2607.06145v1
• Date: Tue, 07 Jul 2026 11:12:44 GMT
• Title: Prompting Complexity: Shortest Prompts for Texts and Behaviors in LLMs
• Abstract summary: We define the quantity of prompting complexity for a fixed instruction-tuned language model.<n>We restrict programs to plausible human-readable texts rather than arbitrary token strings.<n>We also define prompting distance by comparing shortest generating prompts, and behavioral prompting complexity for reaching any output satisfying a specification.
• Score: 1.9875440739965626
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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.

Related papers

• Weave of Formal Thought [51.56484100374058]
  We introduce Weave of Formal Thought (WoFT), a paradigm uniting rigorous syntactic validation with learned structural representations.<n>We present a latent-variable fine-tuning method training the language model to interleave non-terminal grammar symbols directly into generation.<n>For Python, fine-tuning StarCoder2-3B with our RWS objective reduces per-token cross-entropy by 14.3% relative to a text-only SFT baseline.
  arXiv  Detail & Related papers  (2026-06-24T15:58:11Z)
• Understanding LLM Failures: A Multi-Tape Turing Machine Analysis of Systematic Errors in Language Model Reasoning [0.033842793760651545]
  Large language models (LLMs) exhibit failure modes on seemingly trivial tasks.<n>We propose a formalisation of interaction using a deterministic multi-tape Turing machine.<n>The model enables precise localisation of failure modes to specific pipeline stages.
  arXiv  Detail & Related papers  (2026-01-27T16:12:01Z)
• Self-Steering Language Models [113.96916935955842]
  DisCIPL is a method for "self-steering" language models (LMs)<n>DisCIPL generates a task-specific inference program that is executed by a population of Follower models.<n>Our work opens up a design space of highly-parallelized Monte Carlo inference strategies.
  arXiv  Detail & Related papers  (2025-04-09T17:54:22Z)
• Critical Thinking: Which Kinds of Complexity Govern Optimal Reasoning Length? [72.70486097967124]
  We formalize a framework using deterministic finite automata (DFAs)<n>We show that there exists an optimal amount of reasoning tokens such that the probability of producing a correct solution is maximized.<n>We then demonstrate an implication of these findings: being able to predict the optimal number of reasoning tokens for new problems and filtering out non-optimal length answers results in consistent accuracy improvements.
  arXiv  Detail & Related papers  (2025-04-02T17:45:58Z)
• Graph-DPEP: Decomposed Plug and Ensemble Play for Few-Shot Document Relation Extraction with Graph-of-Thoughts Reasoning [34.85741925091139]
  Graph-DPEP framework is grounded in the reasoning behind triplet explanation thoughts presented in natural language. We develop "ensemble-play", reapplying generation on the entire type list by leveraging the reasoning thoughts embedded in a sub-graph.
  arXiv  Detail & Related papers  (2024-11-05T07:12:36Z)
• FLARE: Faithful Logic-Aided Reasoning and Exploration [47.46564769245296]
  We introduce a novel approach for traversing the problem space using task decompositions.<n>We use the Large Language Models to plan a solution, soft-formalise the query into facts and predicates using a logic programming code.<n>Our method allows us to compute the faithfulness of the reasoning process w.r.t. the generated code and analyse the steps of the multi-hop search without relying on external solvers.
  arXiv  Detail & Related papers  (2024-10-14T19:39:11Z)
• JoPA:Explaining Large Language Model's Generation via Joint Prompt Attribution [41.89180735617241]
  Large Language Models (LLMs) have demonstrated impressive performances in complex text generation tasks.<n>The contribution of the input prompt to the generated content still remains obscure to humans.<n>We introduce a counterfactual explanation framework based on Joint Prompt Attribution, JoPA.
  arXiv  Detail & Related papers  (2024-05-30T18:16:41Z)
• Monotonic Paraphrasing Improves Generalization of Language Model Prompting [42.74429247000797]
  MonoPara is an end-to-end decoding strategy that paraphrases given prompts or instructions into their lower perplexity counterparts. It does not require any training and can monotonically lower the perplexity of the paraphrased prompt or instruction. It is also shown to effectively improve LMs' generalization on perturbed and unseen task instructions.
  arXiv  Detail & Related papers  (2024-03-24T06:49:07Z)
• Can Large Language Models Understand Real-World Complex Instructions? [54.86632921036983]
  Large language models (LLMs) can understand human instructions, but struggle with complex instructions. Existing benchmarks are insufficient to assess LLMs' ability to understand complex instructions. We propose CELLO, a benchmark for evaluating LLMs' ability to follow complex instructions systematically.
  arXiv  Detail & Related papers  (2023-09-17T04:18:39Z)
• Adapting Language Models to Compress Contexts [71.98287002918941]
  Transformer-based language models (LMs) are powerful and widely-applicable tools, but their usefulness is constrained by a finite context window. We propose to adapt pre-trained LMs into AutoCompressors, which are capable of compressing long contexts into compact summary vectors. We fine-tune OPT and Llama-2 models on sequences of up to 30,720 tokens and show that AutoCompressors can utilize long contexts to improve perplexity.
  arXiv  Detail & Related papers  (2023-05-24T06:42:44Z)
• RelationPrompt: Leveraging Prompts to Generate Synthetic Data for Zero-Shot Relation Triplet Extraction [65.4337085607711]
  We introduce the task setting of Zero-Shot Relation Triplet Extraction (ZeroRTE) Given an input sentence, each extracted triplet consists of the head entity, relation label, and tail entity where the relation label is not seen at the training stage. We propose to synthesize relation examples by prompting language models to generate structured texts.
  arXiv  Detail & Related papers  (2022-03-17T05:55:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.