# Why Prompt Design Matters and Works: A Complexity Analysis of Prompt Search Space in LLMs

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 48 references that are in the map.
- First posted on arXiv 13 Mar 2025.

## Builds on (most cited first, 29 of 29)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [RLPrompt: Optimizing Discrete Text Prompts with Reinforcement Learning](https://mlsanity.com/paper/2205.12548/) (2022)
- [A Systematic Evaluation of Large Language Models of Code](https://mlsanity.com/paper/2202.13169/) (2022)
- [ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Search](https://mlsanity.com/paper/2406.03816/) (2024)
- [On the Expressive Power of Deep Neural Networks](https://mlsanity.com/paper/1606.05336/) (2016)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Physics of Language Models: Part 3.1, Knowledge Storage and Extraction](https://mlsanity.com/paper/2309.14316/) (2023)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [Depth-Adaptive Transformer](https://mlsanity.com/paper/1910.10073/) (2019)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Tokenization counts: the impact of tokenization on arithmetic in frontier LLMs](https://mlsanity.com/paper/2402.14903/) (2024)
- [Physics of Language Models: Part 2.1, Grade-School Math and the Hidden Reasoning Process](https://mlsanity.com/paper/2407.20311/) (2024)
- [Don't Trust ChatGPT when Your Question is not in English: A Study of Multilingual Abilities and Types of LLMs](https://mlsanity.com/paper/2305.16339/) (2023)
- [Transformers, parallel computation, and logarithmic depth](https://mlsanity.com/paper/2402.09268/) (2024)
- [NUWA-Infinity: Autoregressive over Autoregressive Generation for Infinite Visual Synthesis](https://mlsanity.com/paper/2207.09814/) (2022)
- [Towards Data Distillation for End-to-end Spoken Conversational Question Answering](https://mlsanity.com/paper/2010.08923/) (2020)
- [Knowledge Distillation for Improved Accuracy in Spoken Question Answering](https://mlsanity.com/paper/2010.11067/) (2020)
- [Calibrating Multi-modal Representations: A Pursuit of Group Robustness without Annotations](https://mlsanity.com/paper/2403.07241/) (2024)
- [Contextualized Attention-based Knowledge Transfer for Spoken Conversational Question Answering](https://mlsanity.com/paper/2010.11066/) (2020)
- [Beyond Matryoshka: Revisiting Sparse Coding for Adaptive Representation](https://mlsanity.com/paper/2503.01776/) (2025)
- [Language Models Need Inductive Biases to Count Inductively](https://mlsanity.com/paper/2405.20131/) (2024)
- [Aligning Source Visual and Target Language Domains for Unpaired Video Captioning](https://mlsanity.com/paper/2211.12148/) (2022)
- [A Character-Level Length-Control Algorithm for Non-Autoregressive Sentence Summarization](https://mlsanity.com/paper/2205.14522/) (2022)
- [Multi2: Multi-Agent Test-Time Scalable Framework for Multi-Document Processing](https://mlsanity.com/paper/2502.20592/) (2025)
- [Weakly-guided Self-supervised Pretraining for Temporal Activity Detection](https://mlsanity.com/paper/2111.13675/) (2021)
- [Black-Box Diagnosis and Calibration on GAN Intra-Mode Collapse: A Pilot Study](https://mlsanity.com/paper/2107.12202/) (2021)

## Built on by (most cited first, 30 of 31)

- [From AI for Science to Agentic Science: A Survey on Autonomous Scientific Discovery](https://mlsanity.com/paper/2508.14111/) (2025)
- [Semantic-Aware Logical Reasoning via a Semiotic Framework](https://mlsanity.com/paper/2509.24765/) (2025)
- [The Curse of CoT: On the Limitations of Chain-of-Thought in In-Context Learning](https://mlsanity.com/paper/2504.05081/) (2025)
- [TimeSeriesScientist: A General-Purpose AI Agent for Time Series Analysis](https://mlsanity.com/paper/2510.01538/) (2025)
- [PosterGen: Aesthetic-Aware Multi-Modal Paper-to-Poster Generation via Multi-Agent LLMs](https://mlsanity.com/paper/2508.17188/) (2025)
- [Tokenization Constraints in LLMs: A Study of Symbolic and Arithmetic Reasoning Limits](https://mlsanity.com/paper/2505.14178/) (2025)
- [Retrieval is Not Enough: Enhancing RAG Reasoning through Test-Time Critique and Optimization](https://mlsanity.com/paper/2504.14858/) (2025)
- [Universal Biological Sequence Reranking for Improved De Novo Peptide Sequencing](https://mlsanity.com/paper/2505.17552/) (2025)
- [FORESTLLM: Large Language Models Make Random Forest Great on Few-shot Tabular Learning](https://mlsanity.com/paper/2601.11311/) (2026)
- [Seeing Sarcasm Through Different Eyes: Analyzing Multimodal Sarcasm Perception in Large Vision-Language Models](https://mlsanity.com/paper/2503.12149/) (2025)
- [Thinking with Nothinking Calibration: A New In-Context Learning Paradigm in Reasoning Large Language Models](https://mlsanity.com/paper/2508.03363/) (2025)
- [The End of Reward Engineering: How LLMs Are Redefining Multi-Agent Coordination](https://mlsanity.com/paper/2601.08237/) (2026)
- [Confusion-Aware Rubric Optimization for LLM-based Automated Grading](https://mlsanity.com/paper/2603.00451/) (2026)
- [Bidirectional Representations Augmented Autoregressive Biological Sequence Generation](https://mlsanity.com/paper/2510.08169/) (2025)
- [When Retrieval Succeeds and Fails: Rethinking Retrieval-Augmented Generation for LLMs](https://mlsanity.com/paper/2510.09106/) (2025)
- [Towards Accurate UAV Image Perception: Guiding Vision-Language Models with Stronger Task Prompts](https://mlsanity.com/paper/2512.07302/) (2025)
- [Characterizing Readability Issue Patterns and the Role of Prompt Design in LLM-Generated Code](https://mlsanity.com/paper/2605.13280/) (2026)
- [Prompting Complexity: Shortest Prompts for Texts and Behaviors in LLMs](https://mlsanity.com/paper/2607.06145/) (2026)
- [Semiotic logical hexagon theory for LLM logical reasoning](https://mlsanity.com/paper/2607.21933/) (2026)
- [TORSO: Template-Oriented Reasoning Towards General Tasks](https://mlsanity.com/paper/2509.09448/) (2025)
- [Reasoning with Preference Constraints: A Benchmark for Language Models in Many-to-One Matching Markets](https://mlsanity.com/paper/2509.13131/) (2025)
- [Reasoning About Reasoning: Towards Informed and Reflective Use of LLM Reasoning in HCI](https://mlsanity.com/paper/2510.22978/) (2025)
- [SGG-Rrm 3: From Next-Token Prediction to End-to-End Unbiased Scene Graph Generation](https://mlsanity.com/paper/2603.07961/) (2026)
- [Magic Words or Methodical Work? Challenging Conventional Wisdom in LLM-Based Political Text Annotation](https://mlsanity.com/paper/2603.26898/) (2026)
- [Combating Data Laundering in LLM Training](https://mlsanity.com/paper/2604.01904/) (2026)
- [When LLMs Develop Languages: Symbolic Communication for Efficient Multi-Agent Reasoning](https://mlsanity.com/paper/2606.29354/) (2026)
- [Cognivia: A Cognitive Behavioral Therapy Copilot for Evidence-Based Mental Healthcare](https://mlsanity.com/paper/2607.25681/) (2026)
- [When LLM Meets Tree Search: A Systematic View of Inference as Search in Large Language Models](https://mlsanity.com/paper/2608.30395/) (2026)
- [SurveyAgent-HKA: A multi-agent framework for scientific survey generation with LLMs and human knowledge augmentation](https://mlsanity.com/paper/2609.05938/) (2026)
- [LLJ Cards: Best practices for the Use of LLMs as Judges](https://mlsanity.com/paper/2609.24516/) (2026)

## Abstract (arXiv)

Despite the remarkable successes of large language models (LLMs), the underlying Transformer architecture has inherent limitations in handling complex reasoning tasks. Chain-of-thought (CoT) prompting has emerged as a practical workaround, but most CoT-based methods rely on a single, generic prompt such as "think step by step", with no task-specific adaptation. These approaches expect the model to discover an effective reasoning path on its own, forcing it to search through a vast prompt space. In contrast, several studies have explored task-specific prompt designs to boost performance. However, these designs are typically developed through trial and error, lacking theoretical grounding. As a result, prompt engineering remains largely ad hoc and unguided. In this paper, we provide a theoretical framework that explains why some prompts succeed while others fail. We show that prompts function as selectors, extracting task-relevant information from the model's full hidden state during CoT reasoning. Each prompt defines a unique trajectory through the answer space, and the choice of trajectory is crucial for task performance and future navigation within the space. We analyze the complexity of finding optimal prompts and characterize the size of the prompt space for a given task. Our theory reveals principles behind effective prompt design and shows that naive CoT-using self-guided prompts like "think step by step"-can severely hinder performance. Through experiments, we show that optimal prompt search can lead to more than a 50% improvement on reasoning tasks, providing a theoretical foundation for prompt engineering.