# Localized Zeroth-Order Prompt Optimization

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 46 references that are in the map.
- First posted on arXiv 5 Mar 2024.

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

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [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)
- [Prefix-Tuning: Optimizing Continuous Prompts for Generation](https://mlsanity.com/paper/2101.00190/) (2021)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Pre-train, Prompt, and Predict: A Systematic Survey of Prompting Methods in Natural Language Processing](https://mlsanity.com/paper/2107.13586/) (2021)
- [WizardLM: Empowering large pre-trained language models to follow complex instructions](https://mlsanity.com/paper/2304.12244/) (2023)
- [Large Language Models Are Human-Level Prompt Engineers](https://mlsanity.com/paper/2211.01910/) (2022)
- [Are NLP Models really able to Solve Simple Math Word Problems?](https://mlsanity.com/paper/2103.07191/) (2021)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Automatic Prompt Optimization with "Gradient Descent" and Beam Search](https://mlsanity.com/paper/2305.03495/) (2023)
- [Program Induction by Rationale Generation : Learning to Solve and Explain Algebraic Word Problems](https://mlsanity.com/paper/1705.04146/) (2017)
- [Prompt Programming for Large Language Models: Beyond the Few-Shot Paradigm](https://mlsanity.com/paper/2102.07350/) (2021)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Promptbreeder: Self-Referential Self-Improvement Via Prompt Evolution](https://mlsanity.com/paper/2309.16797/) (2023)
- [RLPrompt: Optimizing Discrete Text Prompts with Reinforcement Learning](https://mlsanity.com/paper/2205.12548/) (2022)
- [Black-Box Tuning for Language-Model-as-a-Service](https://mlsanity.com/paper/2201.03514/) (2022)
- [Reframing Instructional Prompts to GPTk's Language](https://mlsanity.com/paper/2109.07830/) (2021)
- [Instruction Induction: From Few Examples to Natural Language Task Descriptions](https://mlsanity.com/paper/2205.10782/) (2022)
- [Optimal Approximation Rate of ReLU Networks in terms of Width and Depth](https://mlsanity.com/paper/2103.00502/) (2021)
- [Black-box Prompt Learning for Pre-trained Language Models](https://mlsanity.com/paper/2201.08531/) (2022)
- [InstructZero: Efficient Instruction Optimization for Black-Box Large Language Models](https://mlsanity.com/paper/2306.03082/) (2023)
- [Universal Approximation Theorems for Differentiable Geometric Deep Learning](https://mlsanity.com/paper/2101.05390/) (2021)
- [NASI: Label- and Data-agnostic Neural Architecture Search at Initialization](https://mlsanity.com/paper/2109.00817/) (2021)
- [Unifying and Boosting Gradient-Based Training-Free Neural Architecture Search](https://mlsanity.com/paper/2201.09785/) (2022)

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

- [Prompt Optimization with EASE? Efficient Ordering-aware Automated Selection of Exemplars](https://mlsanity.com/paper/2405.16122/) (2024)
- [Prompt Optimization with Human Feedback](https://mlsanity.com/paper/2405.17346/) (2024)
- [AutoPDL: Automatic Prompt Optimization for LLM Agents](https://mlsanity.com/paper/2504.04365/) (2025)
- [Aviary: training language agents on challenging scientific tasks](https://mlsanity.com/paper/2412.21154/) (2024)
- [GReaTer: Gradients over Reasoning Makes Smaller Language Models Strong Prompt Optimizers](https://mlsanity.com/paper/2412.09722/) (2024)
- [Powering Up Zeroth-Order Training via Subspace Gradient Orthogonalization](https://mlsanity.com/paper/2602.17155/) (2026)
- [Hyperband-based Bayesian Optimization for Black-box Prompt Selection](https://mlsanity.com/paper/2412.07820/) (2024)
- [Language Model Embeddings Can Be Sufficient for Bayesian Optimization](https://mlsanity.com/paper/2410.10190/) (2024)
- [Zeroth-Order Optimization is Secretly Single-Step Policy Optimization](https://mlsanity.com/paper/2506.14460/) (2025)
- [Ferret: Federated Full-Parameter Tuning at Scale for Large Language Models](https://mlsanity.com/paper/2409.06277/) (2024)
- [DETAIL: Task DEmonsTration Attribution for Interpretable In-context Learning](https://mlsanity.com/paper/2405.14899/) (2024)
- [Code-enabled language models can outperform reasoning models on diverse tasks](https://mlsanity.com/paper/2510.20909/) (2025)
- [PRESTO: Preimage-Informed Instruction Optimization for Prompting Black-Box LLMs](https://mlsanity.com/paper/2510.25808/) (2025)
- [Test-Time Policy Adaptation for Enhanced Multi-Turn Interactions with LLMs](https://mlsanity.com/paper/2509.23166/) (2025)
- [FedPOB: Sample-Efficient Federated Prompt Optimization via Bandits](https://mlsanity.com/paper/2509.24701/) (2025)
- [Bounds of Chain-of-Thought Robustness: Reasoning Steps, Embed Norms, and Beyond](https://mlsanity.com/paper/2509.21284/) (2025)
- [Test-Time Detoxification without Training or Learning Anything](https://mlsanity.com/paper/2602.02498/) (2026)
- [Efficient Multi-objective Prompt Optimization via Pure-exploration Bandits](https://mlsanity.com/paper/2605.14553/) (2026)
- [Learning Dynamics of Zeroth-Order Optimization: A Kernel Perspective](https://mlsanity.com/paper/2605.03373/) (2026)
- [BoLT: A Benchmark to Democratize Black-box Optimization Research for Expensive LLM Tasks](https://mlsanity.com/paper/2605.17000/) (2026)
- [UniScale: Adaptive Unified Inference Scaling via Online Joint Optimization of Model Routing and Test-Time Scaling](https://mlsanity.com/paper/2605.30898/) (2026)
- [Position: Vector Prompt Interfaces Should Be Exposed to Enable Customization of Large Language Models](https://mlsanity.com/paper/2603.04292/) (2026)
- [Personalization as Inverse Planning: Learning Latent Design Intents for Agentic Slide Generation via Structural Denoising](https://mlsanity.com/paper/2607.00407/) (2026)

## Abstract (arXiv)

The efficacy of large language models (LLMs) in understanding and generating natural language has aroused a wide interest in developing prompt-based methods to harness the power of black-box LLMs. Existing methodologies usually prioritize a global optimization for finding the global optimum, which however will perform poorly in certain tasks. This thus motivates us to re-think the necessity of finding a global optimum in prompt optimization. To answer this, we conduct a thorough empirical study on prompt optimization and draw two major insights. Contrasting with the rarity of global optimum, local optima are usually prevalent and well-performed, which can be more worthwhile for efficient prompt optimization (Insight I). The choice of the input domain, covering both the generation and the representation of prompts, affects the identification of well-performing local optima (Insight II). Inspired by these insights, we propose a novel algorithm, namely localized zeroth-order prompt optimization (ZOPO), which incorporates a Neural Tangent Kernel-based derived Gaussian process into standard zeroth-order optimization for an efficient search of well-performing local optima in prompt optimization. Remarkably, ZOPO outperforms existing baselines in terms of both the optimization performance and the query efficiency, which we demonstrate through extensive experiments.