# On the Capability and Limitation of Hard Prompt

arXiv: https://arxiv.org/abs/2609.32302 · HTML: https://mlsanity.com/paper/2609.32302/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 37 of its 48 references that are in the map.
- First posted on arXiv 26 Sep 2026.

## Builds on (most cited first, 30 of 37)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [Prefix-Tuning: Optimizing Continuous Prompts for Generation](https://mlsanity.com/paper/2101.00190/) (2021)
- [The Power of Scale for Parameter-Efficient Prompt Tuning](https://mlsanity.com/paper/2104.08691/) (2021)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Training Compute-Optimal Large Language Models](https://mlsanity.com/paper/2203.15556/) (2022)
- [Making Pre-trained Language Models Better Few-shot Learners](https://mlsanity.com/paper/2012.15723/) (2020)
- [An Explanation of In-context Learning as Implicit Bayesian Inference](https://mlsanity.com/paper/2111.02080/) (2021)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [GPT Understands, Too](https://mlsanity.com/paper/2103.10385/) (2021)
- [It's Not Just Size That Matters: Small Language Models Are Also Few-Shot Learners](https://mlsanity.com/paper/2009.07118/) (2020)
- [Automatic Prompt Optimization with "Gradient Descent" and Beam Search](https://mlsanity.com/paper/2305.03495/) (2023)
- [Llemma: An Open Language Model For Mathematics](https://mlsanity.com/paper/2310.10631/) (2023)
- [Learning How to Ask: Querying LMs with Mixtures of Soft Prompts](https://mlsanity.com/paper/2104.06599/) (2021)
- [Hard Prompts Made Easy: Gradient-Based Discrete Optimization for Prompt Tuning and Discovery](https://mlsanity.com/paper/2302.03668/) (2023)
- [In-Context Learning Creates Task Vectors](https://mlsanity.com/paper/2310.15916/) (2023)
- [Black-Box Tuning for Language-Model-as-a-Service](https://mlsanity.com/paper/2201.03514/) (2022)
- [Controlling Linguistic Style Aspects in Neural Language Generation](https://mlsanity.com/paper/1707.02633/) (2017)
- [Goedel-Prover: A Frontier Model for Open-Source Automated Theorem Proving](https://mlsanity.com/paper/2502.07640/) (2025)
- [GrIPS: Gradient-free, Edit-based Instruction Search for Prompting Large Language Models](https://mlsanity.com/paper/2203.07281/) (2022)
- [Prompt Compression for Large Language Models: A Survey](https://mlsanity.com/paper/2410.12388/) (2024)
- [TEMPERA: Test-Time Prompting via Reinforcement Learning](https://mlsanity.com/paper/2211.11890/) (2022)
- [What's the Magic Word? A Control Theory of LLM Prompting](https://mlsanity.com/paper/2310.04444/) (2023)
- [Memorization Capacity of Multi-Head Attention in Transformers](https://mlsanity.com/paper/2306.02010/) (2023)
- [An Information-Theoretic Analysis of In-Context Learning](https://mlsanity.com/paper/2401.15530/) (2024)
- [In-Context Learning with Representations: Contextual Generalization of Trained Transformers](https://mlsanity.com/paper/2408.10147/) (2024)
- [Universality and Limitations of Prompt Tuning](https://mlsanity.com/paper/2305.18787/) (2023)

## Abstract (arXiv)

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.