On the Capability and Limitation of Hard Prompt

Lijia Yu; Shuaitong Liu; Gaojie Jin; Xinyu Li; Xiao-Shan Gao

cs.LGSep 26, 2026

On the Capability and Limitation of Hard Prompt

Authors: Lijia Yu, Shuaitong Liu, Gaojie Jin, Xinyu Li, Xiao-Shan Gao

Organizations: Institute of AI for Industries, Chinese Academy of Sciences · Southwest University · Department of Artificial Intelligence&Institute of Artificial Intelligence and Brain Sciences, University of Macau · Department of Computer Science, University of Exeter ·

Abstract

Prompt engineering has become an indispensable tool for using large language models (LLMs), turning LLMs into task-specific experts without changing their weights. Despite notable theoretical advances in prompt engineering, the theory for the more practical hard or discrete prompts is largely open. In this paper, we try to fill this gap either by providing a complete solution or by making substantial progress on the three core theoretical questions regarding hard prompts. First, we show that determining the existence of a hard prompt for a transformer to solve a downstream task is NP-complete and that finding an optimal hard prompt is NP-hard, which is the first computational complexity result for hard prompting, as far as we know. Second, we show that, unlike soft or continuous prompts, hard prompts have essential limitations: hard prompts are not complete; short hard prompts do not significantly enhance the ability of transformers; and long hard prompts exhibit the "prompt dominating answer phenomenon," meaning that, with high probability, the same answer is given for all queries of the same length. On the other hand, linear hard prompts do not have the limitations of short or long prompts. Third, we provide a tight bound on the size of the task in terms of the prompt length for the performance of prompts on the finite task to generalize to the entire data distribution, leading to a necessary and sufficient condition for generalizability. This is the first result on generalization for prompting, as far as we know. Our findings not only offer the first theoretical insights into hard prompts but also provide provably reliable practical guidance for real-world LLM usage.

Figures & tables

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Methods	Qwen-7B	Qwen-14B	LLaMA	GPT
No prompt	12/90	19/90	30/90	59/90
Prompt $\mathcal{P}_{<1}$	12/90	19/90	30/90	59/90
Prompt $\mathcal{P}_{=1}$	42/90	72/90	75/90	84/90
Prompt $\mathcal{P}_{>1}$	30/90	61/90	59/90	77/90

Appendix

Table 1: The numbers of questions that can be solved in pass@

1

using various prompts in the 90 questions. We use four models: Qwen-7B, Qwen-14B, LLaMA-70B, and GPT-OSS-120B.

Methods	Qwen-7B	Qwen-14B	LLaMA	GPT
No prompt	13/90	21/90	45/90	76/90
Prompt $\mathcal{P}_{<1}$	13/90	21/90	45/90	76/90
Prompt $\mathcal{P}_{=1}$	49/90	73/90	80/90	88/90
Prompt $\mathcal{P}_{>1}$	34/90	63/90	62/90	80/90

Appendix

Table 2: The numbers of questions that can be solved in

pass@10

using various prompts in the 90 questions. We use four models: Qwen-7B, Qwen-14B, LLaMA-70B, and GPT-OSS-120B.

Panel of Figure 1 — Figure 1: On the left, most of the points lie above the blue baseline, showing that in most cases, using $\mathcal{P}_{<1}$ shifts the incorrect positions back. On the right, $\mathcal{P}_{<1}$ is far more effective at correcting errors occurring at the beginning than those appearing later of the answer.

Figure 2: The answer without prompt. The red part is the error position.

Figure 3: The answer with prompt $\mathcal{P}_{<1}$ . The red part is the error position.

Figure 4: The correct answer with prompt $\mathcal{P}_{=1}$ .

Figure 5: The incorrect answer with prompt $\mathcal{P}_{>1}$ .

Figure 6: The prompt $\mathcal{P}_{>1}$ .

LLM Prompting

Large language model prompting studies how instructions, examples, context, and formats steer model behavior at inference time.

See all 429 papers

Prompting Complexity: Shortest Prompts for Texts and Behaviors in LLMs
Jul 7, 2026Adrian CosmaLLM Prompting Prompt Optimization
Dalle Molle Institute for Artificial Intelligence (IDSIA)
On the Limits of Prompt-Conditioned Language Models as General-Purpose Learners
Jun 22, 2026David Mguni, Julian Ma, Jun WangLLM Alignment LLM Prompting
Queen Mary University London · University College London
RLPE: Teaching LLMs to Prompt with Reinforcement Learning
Oct 13, 2026Rahul Singhal, Karime Maamari, Pradyumna TambwekarLLM Prompting Automatic Prompt Optimization

Jul 7, 2026J/K move · Enter open · S save

Prompting Complexity: Shortest Prompts for Texts and Behaviors in LLMs

Adrian Cosma

Dalle Molle Institute for Artificial Intelligence (IDSIA)

LLM Prompting Prompt Optimization Kolmogorov Complexity

Open paper AskPDF arXiv

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.

Abstract

LLM Prompting

Explore similar work

Prompting Complexity: Shortest Prompts for Texts and Behaviors in LLMs

On the Limits of Prompt-Conditioned Language Models as General-Purpose Learners

RLPE: Teaching LLMs to Prompt with Reinforcement Learning