Heuristic-based Search Algorithm in Automatic Instruction-focused Prompt Optimization: A Survey (2025)

Abstract: Recent advances in Large Language Models(LLMs) have led to remarkable achievements across a variety of Natural Language Processing(NLP) tasks, making prompt engineering increasingly central to guiding model outputs. While manual methods (e.g., “chain-of-thought,” “step-by-step” prompts) can be effective, they typically rely on intuition and do not automatically refine prompts over time. In contrast, automatic prompt optimization employing heuristic-based search algorithms can systematically explore and improve prompts with minimal human oversight. This survey proposes a comprehensive taxonomy of these methods, categorizing them by where optimization occurs, what is optimized, what criteria drive the optimization, which operators generate new prompts, and which iterative search algorithms are applied. We further highlight specialized datasets and tools that support and accelerate automated prompt refinement. We conclude by discussing key open challenges, pointing toward future opportunities for more robust and versatile LLM applications.

## introduction the rapid evolution of large language models (llms) has catalyzed significant progress in diverse tasks @xcite . as these models become more capable, the design of the prompt used to interface with them has emerged as a crucial factor in terms of both prompt content and format @xcite . manual approaches such as "chain-of-thought" @xcite prompting or instructing the model to "let's think step by step" @xcite can yield enhanced performance in certain scenarios, but these methods remain fundamentally reliant on human intuition and repeated trial-and-error. in contrast, automatic prompt optimization aims to systematically discover and refine prompts, minimizing human efforts and potentially uncovering highly effective solutions that manual experimentation might overlook @xcite . these techniques treat prompt design as a search problem, wherein a heuristic-based search algorithmic process iteratively evaluates candidate prompts and adapts them based on performance feedback or other criteria @xcite @xcite . other lines of work applies reinforcement learning @xcite @xcite or ensemble methods @xcite to optimize prompts dynamically or adaptively. this survey focuses on heuristic-based search methods due to their ability to unify a broad range of strategies under an interpretable, modular framework that is compatible with both discrete and soft prompt spaces. we further concentrate on instruction-focused approaches, emphasizing the clarity and structure of the instruction while optionally incorporating in-context examples. instruction-based prompting continues to be the dominant paradigm, making it a practical and impactful focus. by narrowing our scope to this intersection, we aim to provide a coherent taxonomy and detailed analysis of methods that are both theoretically grounded and widely applicable. we begin by examining the fundamental dimensions of where optimization happens (optimization space) and what is optimized (optimization target). we then review what criteria to optimize (optimization criteria), recognizing that many practitioners now consider objectives beyond task performance. then, we dive into how optimization happens by categorizing which operators are used to create new prompt candidates and which iterative algorithm guides the refinement loop. with a growing body of literature addressing these topics, we also review benchmarking datasets covering a wide range of domains. moreover, we survey a range of tools that can automate or streamline prompt optimization workflows, enabling rapid iteration with less manual effort. we conclude by identifying open problems. addressing these challenges will unlock reliable, adaptable, and ethical llm applications. ## where does optimization happen? prompt optimization in llms can be broadly categorized into soft prompt space optimization and discrete prompt space optimization. ## what criteria to optimize in heuristic-based automatic prompt optimization, the objectives or criteria for refinement vary widely depending on the application domain. while early research predominantly focused on task performance, growing interest in real-world deployments has led to broader optimization goals: ## which operators are used for iterative optimization, generating new candidate prompts is essential. these generation methods, referred to as operators, are categorized based on the number of parent prompts needed. parent prompts are existing prompts used to derive new candidates. ## which iterative algorithm is used iterative algorithms are crucial in automatic prompt optimization. they guide the selection and application of operators to refine prompts effectively. ## common datasets used considering the broad applicability of prompt optimization, a variety of databases across different domains were used, as shown in ## common tools automatic prompt optimization tools aim to accelerate and streamline the optimization process. below, we provide an overview of notable tools and their key characteristics. promptim promptim is an experimental opensource library. given an initial prompt, a dataset, and evaluators, promptim iteratively refines the prompt using a meta prompt to suggest improvements based on evaluation scores. it integrates with langsmith for data and prompt management and supports optional human feedback. contrary to other tools, promptim prioritizes keeping humans in the loop throughout the optimization process. dspy dspy is a framework developed by stanford researchers that takes a more declarative approach to building complex llm applications. instead of directly writing prompts, users define the desired "program" as a series of declarative steps. dspy implements mipro @xcite and uses llms to generate and optimize the underlying prompts to fulfill the program's goals. this approach allows for more structured and modular development of llm applications and facilitates prompt optimization as part of the program execution. dspy emphasizes the decomposition of complex tasks into simpler sub-tasks and is widely used in research @xcite . openprompt openprompt @xcite is an open-source toolkit specifically designed for prompt-learning. it provides a standardized framework for implementing and experimenting with various templating, verbalizing, and optimization strategies. openprompt offers pre-defined templates for different prompting methods, such as prefix-tuning and p-tuning. its combinability across different pretrained lms, task formats, and optimization methods makes it a valuable tool. vertex ai prompt optimizer google cloud's vertex ai platform offers a prompt optimizer as part of its suite of tools. this service allows users to experiment with and optimize prompts following learning from wan et al. (2024). integrated within the vertex ai ecosystem, the prompt optimizer benefits from google's cloud infrastructure and provides a scalable solution for prompt optimization tasks. promptbench promptbench (zhu et al., 2023) is an open-source benchmark designed to evaluate the robustness of prompts under adversarial perturbations. rather than introducing new task datasets, promptbench applies systematic transformations-such as instruction negation or paraphrasing-to existing prompts across a variety of standard nlp datasets. it helps researchers assess how well prompt optimization methods preserve model performance under distributional shift. aws bedrock aws bedrock includes a prompt engineering playground within its cloud platform, allowing users to prototype and evaluate prompts across multiple foundation models. the interface supports a/b testing, real-time inference, and evaluation metrics. while not open-source, it provides a practical environment for optimizing and comparing prompt variants in production-ready workflows. anthropic claude prompt tools anthropic's claude platform offers interactive tools for prompt optimization directly through its web interface. these tools provide live feedback, suggest rewrites, and support prompt experimentation tailored specifically to claude models. while proprietary, they are useful for developers seeking to iteratively refine instructions with guidance grounded in claude's internal safety and helpfulness principles. 10 open challenges soft to discrete projection soft prompt spaces enable continuous optimization but often lack interoperability provided by discrete prompts. to address this, some methods project soft embeddings back into discrete space. hu et al. (2024), wen et al. (2023) and zhao et al. (2024) adopt a pre-generated finite set of unique candidates, where gradient-updated embeddings are mapped back to the closest entry in this set. however, this approach heavily depends on the quality of the pre-generated set. another approach leverages an open-source llm as a converter to translate soft prompts into discrete instructions @xcite , offering a more flexible and adaptive solution. further research in this area could enhance both optimization effectiveness and interpretability. ## conclusion this survey has explored heuristic-based search algorithms for automatic instruction-focused prompt optimization, organizing methods along five key dimensions: the optimization space, the optimization target, the optimization criteria, the operators, and the iterative algorithms. the goal was to allow mixing and matching components like a toolkit, enabling the design of new prompt optimization pipelines by combining different operators with various search or learning algorithms. to make this more concrete, one might think of our framework like a recipe book: operators are the ingredients (e.g., "add", "replace", "rephrase"), and the iterative algorithms are the cooking methods (e.g., "bake" with genetic algorithms, "slow simmer" with beam search). different combinations yield different flavors-and innovations. we hope this survey could jump-start researchers in understanding the existing landscape and inspire new research on the practical application of llms.