# Survival of the Most Influential Prompts: Efficient Black-Box Prompt Search via Clustering and Pruning

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 47 references that are in the map.
- First posted on arXiv 19 Oct 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Parameter-Efficient Transfer Learning for NLP](https://mlsanity.com/paper/1902.00751/) (2019)
- [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)
- [Scaling Instruction-Finetuned Language Models](https://mlsanity.com/paper/2210.11416/) (2022)
- [Character-level Convolutional Networks for Text Classification](https://mlsanity.com/paper/1509.01626/) (2015)
- [A large annotated corpus for learning natural language inference](https://mlsanity.com/paper/1508.05326/) (2015)
- [What Makes Good In-Context Examples for GPT-3?](https://mlsanity.com/paper/2101.06804/) (2021)
- [XNLI: Evaluating Cross-lingual Sentence Representations](https://mlsanity.com/paper/1809.05053/) (2018)
- [Towards a Unified View of Parameter-Efficient Transfer Learning](https://mlsanity.com/paper/2110.04366/) (2021)
- [Learning To Retrieve Prompts for In-Context Learning](https://mlsanity.com/paper/2112.08633/) (2021)
- [RLPrompt: Optimizing Discrete Text Prompts with Reinforcement Learning](https://mlsanity.com/paper/2205.12548/) (2022)
- [True Few-Shot Learning with Language Models](https://mlsanity.com/paper/2105.11447/) (2021)
- [Parameter-efficient Multi-task Fine-tuning for Transformers via Shared Hypernetworks](https://mlsanity.com/paper/2106.04489/) (2021)
- [Black-Box Tuning for Language-Model-as-a-Service](https://mlsanity.com/paper/2201.03514/) (2022)
- [Batch Calibration: Rethinking Calibration for In-Context Learning and Prompt Engineering](https://mlsanity.com/paper/2309.17249/) (2023)
- [Z-ICL: Zero-Shot In-Context Learning with Pseudo-Demonstrations](https://mlsanity.com/paper/2212.09865/) (2022)
- [Bayesian Optimization of Combinatorial Structures](https://mlsanity.com/paper/1806.08838/) (2018)
- [Think Global and Act Local: Bayesian Optimisation over High-Dimensional Categorical and Mixed Search Spaces](https://mlsanity.com/paper/2102.07188/) (2021)
- [Better Zero-Shot Reasoning with Self-Adaptive Prompting](https://mlsanity.com/paper/2305.14106/) (2023)
- [AutoPEFT: Automatic Configuration Search for Parameter-Efficient Fine-Tuning](https://mlsanity.com/paper/2301.12132/) (2023)
- [Self-ICL: Zero-Shot In-Context Learning with Self-Generated Demonstrations](https://mlsanity.com/paper/2305.15035/) (2023)
- [Bayesian Optimization over Discrete and Mixed Spaces via Probabilistic Reparameterization](https://mlsanity.com/paper/2210.10199/) (2022)
- [Neural Architecture Generator Optimization](https://mlsanity.com/paper/2004.01395/) (2020)
- [One Network, Many Masks: Towards More Parameter-Efficient Transfer Learning](https://mlsanity.com/paper/2305.17682/) (2023)

## Built on by (most cited first, 17 of 17)

- [Aligning with Human Judgement: The Role of Pairwise Preference in Large Language Model Evaluators](https://mlsanity.com/paper/2403.16950/) (2024)
- [Multi-Agent Design: Optimizing Agents with Better Prompts and Topologies](https://mlsanity.com/paper/2502.02533/) (2025)
- [A Systematic Survey of Automatic Prompt Optimization Techniques](https://mlsanity.com/paper/2502.16923/) (2025)
- [Fairer Preferences Elicit Improved Human-Aligned Large Language Model Judgments](https://mlsanity.com/paper/2406.11370/) (2024)
- [On Calibration of LLM-based Guard Models for Reliable Content Moderation](https://mlsanity.com/paper/2410.10414/) (2024)
- [When Large Language Models Meet Evolutionary Algorithms: Potential Enhancements and Challenges](https://mlsanity.com/paper/2401.10510/) (2024)
- [An Empirical Analysis of Uncertainty in Large Language Model Evaluations](https://mlsanity.com/paper/2502.10709/) (2025)
- [Large Language Models are Miscalibrated In-Context Learners](https://mlsanity.com/paper/2312.13772/) (2023)
- [Position Engineering: Boosting Large Language Models through Positional Information Manipulation](https://mlsanity.com/paper/2404.11216/) (2024)
- [Judge as A Judge: Improving the Evaluation of Retrieval-Augmented Generation through the Judge-Consistency of Large Language Models](https://mlsanity.com/paper/2502.18817/) (2025)
- [HPSS: Heuristic Prompting Strategy Search for LLM Evaluators](https://mlsanity.com/paper/2502.13031/) (2025)
- [Comparing Uncertainty Measurement and Mitigation Methods for Large Language Models: A Systematic Review](https://mlsanity.com/paper/2504.18346/) (2025)
- [Bounds of Chain-of-Thought Robustness: Reasoning Steps, Embed Norms, and Beyond](https://mlsanity.com/paper/2509.21284/) (2025)
- [Large Language Models are Demonstration Pre-Selectors for Themselves](https://mlsanity.com/paper/2506.06033/) (2025)
- [Are the LLMs Capable of Maintaining at Least the Language Genus?](https://mlsanity.com/paper/2510.21561/) (2025)
- [Towards Spec Learning: Inference-Time Alignment from Preference Pairs](https://mlsanity.com/paper/2606.24004/) (2026)
- [STEVE: Stabilizing Textual Gradient-Based Prompt Optimization via Error-Driven Refinement and Regularized Verification](https://mlsanity.com/paper/2609.23716/) (2026)

## Abstract (arXiv)

Prompt-based learning has been an effective paradigm for large pretrained language models (LLM), enabling few-shot or even zero-shot learning. Black-box prompt search has received growing interest recently for its distinctive properties of gradient-free optimization, proven particularly useful and powerful for model-as-a-service usage. However, the discrete nature and the complexity of combinatorial optimization hinder the efficiency of modern black-box approaches. Despite extensive research on search algorithms, the crucial aspect of search space design and optimization has been largely overlooked. In this paper, we first conduct a sensitivity analysis by prompting LLM, revealing that only a small number of tokens exert a disproportionate amount of influence on LLM predictions. Leveraging this insight, we propose the Clustering and Pruning for Efficient Black-box Prompt Search (ClaPS), a simple black-box search method that first clusters and prunes the search space to focus exclusively on influential prompt tokens. By employing even simple search methods within the pruned search space, ClaPS achieves state-of-the-art performance across various tasks and LLMs, surpassing the performance of complex approaches while significantly reducing search costs. Our findings underscore the critical role of search space design and optimization in enhancing both the usefulness and the efficiency of black-box prompt-based learning.