# Prompts Generalize with Low Data: Non-vacuous Generalization Bounds for Optimizing Prompts with More Informative Priors

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 36 references that are in the map.
- First posted on arXiv 9 Oct 2025.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [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)
- [Pre-train, Prompt, and Predict: A Systematic Survey of Prompting Methods in Natural Language Processing](https://mlsanity.com/paper/2107.13586/) (2021)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Making Pre-trained Language Models Better Few-shot Learners](https://mlsanity.com/paper/2012.15723/) (2020)
- [Large Language Models Are Human-Level Prompt Engineers](https://mlsanity.com/paper/2211.01910/) (2022)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [Automatic Prompt Optimization with "Gradient Descent" and Beam Search](https://mlsanity.com/paper/2305.03495/) (2023)
- [Prompt Programming for Large Language Models: Beyond the Few-Shot Paradigm](https://mlsanity.com/paper/2102.07350/) (2021)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Fantastic Generalization Measures and Where to Find Them](https://mlsanity.com/paper/1912.02178/) (2019)
- [Detecting Language Model Attacks with Perplexity](https://mlsanity.com/paper/2308.14132/) (2023)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [PromptAgent: Strategic Planning with Language Models Enables Expert-level Prompt Optimization](https://mlsanity.com/paper/2310.16427/) (2023)
- [Demystifying Prompts in Language Models via Perplexity Estimation](https://mlsanity.com/paper/2212.04037/) (2022)
- [Does Prompt Formatting Have Any Impact on LLM Performance?](https://mlsanity.com/paper/2411.10541/) (2024)
- [Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates](https://mlsanity.com/paper/1911.02151/) (2019)
- [Multi-Agent Design: Optimizing Agents with Better Prompts and Topologies](https://mlsanity.com/paper/2502.02533/) (2025)
- [Perplexed by Perplexity: Perplexity-Based Data Pruning With Small Reference Models](https://mlsanity.com/paper/2405.20541/) (2024)
- [Language Model Evaluation Beyond Perplexity](https://mlsanity.com/paper/2106.00085/) (2021)
- [ETHOS: an Online Hate Speech Detection Dataset](https://mlsanity.com/paper/2006.08328/) (2020)
- [PLOT: Prompt Learning with Optimal Transport for Vision-Language Models](https://mlsanity.com/paper/2210.01253/) (2022)
- [Non-Vacuous Generalization Bounds for Large Language Models](https://mlsanity.com/paper/2312.17173/) (2023)
- [Prompt Risk Control: A Rigorous Framework for Responsible Deployment of Large Language Models](https://mlsanity.com/paper/2311.13628/) (2023)
- [Understanding prompt engineering may not require rethinking generalization](https://mlsanity.com/paper/2310.03957/) (2023)
- [Perplexed: Understanding When Large Language Models are Confused](https://mlsanity.com/paper/2404.06634/) (2024)
- [PLPP: Prompt Learning with Perplexity Is Self-Distillation for Vision-Language Models](https://mlsanity.com/paper/2412.15277/) (2024)

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

- [Aligning Probabilistic Beliefs under Informative Missingness: LLM Steerability in Clinical Reasoning](https://mlsanity.com/paper/2512.00479/) (2025)
- [ESPO: Error-Structured Prompt Optimization via Diagnose, Diversify, and Stabilize](https://mlsanity.com/paper/2609.04197/) (2026)
- [Certification Frontiers for Gaussian LoRA: Independent Priors, Posterior Risk, and Prediction-Preserving Balancing](https://mlsanity.com/paper/2609.32271/) (2026)

## Abstract (arXiv)

Many prompt engineering techniques have been successful in practice, even when optimizing over a large prompt space with with a small amount of task-specific data. Recent work has partially explained this success by showing generalization bounds which apply PAC-Bayes theory to the discrete prompt space, but they are non-vacuous only in data-rich scenarios. We argue that such widespread success can be more fully explained through more carefully considering data- or distribution-dependent perplexity, which acts as an effective prior and steers the optimization towards prompts that are more ``natural'' for the task at hand. We derive novel generalization bounds that are non-vacuous for data-scarce prompt optimization via more useful priors, formally analyzing how perplexity regularization tightens these bounds by limiting exploration. Empirically, we explore both the bounds' effectiveness and the practical benefits of perplexity regularization in improving prompt generalization.