# Symbolic Prompt Program Search: A Structure-Aware Approach to Efficient Compile-Time Prompt Optimization

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- Placed in RAG for code, one of 15 directions in Retrieval-augmented generation.
- Builds on 19 of its 33 references that are in the map.
- First posted on arXiv 2 Apr 2024.

## Placed in

- Retrieval-augmented generation / [RAG for code](https://mlsanity.com/rag/rag-for-code/)

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [The Power of Scale for Parameter-Efficient Prompt Tuning](https://mlsanity.com/paper/2104.08691/) (2021)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [Large Language Models Are Human-Level Prompt Engineers](https://mlsanity.com/paper/2211.01910/) (2022)
- [Regularized Evolution for Image Classifier Architecture Search](https://mlsanity.com/paper/1802.01548/) (2018)
- [DSPy: Compiling Declarative Language Model Calls into Self-Improving Pipelines](https://mlsanity.com/paper/2310.03714/) (2023)
- [Quantifying Language Models' Sensitivity to Spurious Features in Prompt Design or: How I learned to start worrying about prompt formatting](https://mlsanity.com/paper/2310.11324/) (2023)
- [Automatic Prompt Optimization with "Gradient Descent" and Beam Search](https://mlsanity.com/paper/2305.03495/) (2023)
- [Promptbreeder: Self-Referential Self-Improvement Via Prompt Evolution](https://mlsanity.com/paper/2309.16797/) (2023)
- [Learning to Compress Prompts with Gist Tokens](https://mlsanity.com/paper/2304.08467/) (2023)
- [Learning How to Ask: Querying LMs with Mixtures of Soft Prompts](https://mlsanity.com/paper/2104.06599/) (2021)
- [Task-Oriented Dialogue as Dataflow Synthesis](https://mlsanity.com/paper/2009.11423/) (2020)
- [Prompt Compression and Contrastive Conditioning for Controllability and Toxicity Reduction in Language Models](https://mlsanity.com/paper/2210.03162/) (2022)
- [Batch Prompting: Efficient Inference with Large Language Model APIs](https://mlsanity.com/paper/2301.08721/) (2023)
- [Discrete Prompt Compression with Reinforcement Learning](https://mlsanity.com/paper/2308.08758/) (2023)
- [Did You Read the Instructions? Rethinking the Effectiveness of Task Definitions in Instruction Learning](https://mlsanity.com/paper/2306.01150/) (2023)
- [PyGlove: Symbolic Programming for Automated Machine Learning](https://mlsanity.com/paper/2101.08809/) (2021)
- [BatchPrompt: Accomplish more with less](https://mlsanity.com/paper/2309.00384/) (2023)
- [Leveraging Code to Improve In-context Learning for Semantic Parsing](https://mlsanity.com/paper/2311.09519/) (2023)

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

- [A Systematic Survey of Automatic Prompt Optimization Techniques](https://mlsanity.com/paper/2502.16923/) (2025)
- [Eureka: Evaluating and Understanding Large Foundation Models](https://mlsanity.com/paper/2409.10566/) (2024)
- [Beyond Prompt Content: Enhancing LLM Performance via Content-Format Integrated Prompt Optimization](https://mlsanity.com/paper/2502.04295/) (2025)
- [LLM Whisperer: An Inconspicuous Attack to Bias LLM Responses](https://mlsanity.com/paper/2406.04755/) (2024)
- [Hyperband-based Bayesian Optimization for Black-box Prompt Selection](https://mlsanity.com/paper/2412.07820/) (2024)
- [PromptPex: Automatic Test Generation for Language Model Prompts](https://mlsanity.com/paper/2503.05070/) (2025)
- [A Course Correction in Steerability Evaluation: Revealing Miscalibration and Side Effects in LLMs](https://mlsanity.com/paper/2505.23816/) (2025)
- [Verification-Guided Context Optimization for Tool Calling via Hierarchical LLMs-as-Editors](https://mlsanity.com/paper/2512.13860/) (2025)
- [PromptPrism: A Linguistically-Inspired Taxonomy for Prompts](https://mlsanity.com/paper/2505.12592/) (2025)
- [Stabilizing Black-Box Prompt Optimization with Textual Regularization and Signal Aggregation](https://mlsanity.com/paper/2507.09839/) (2025)
- [Are My Optimized Prompts Compromised? Exploring Vulnerabilities of LLM-based Optimizers](https://mlsanity.com/paper/2510.14381/) (2025)
- [Sharing State Between Prompts and Programs](https://mlsanity.com/paper/2512.14805/) (2025)
- [Grammar-Guided Evolutionary Search for Discrete Prompt Optimisation](https://mlsanity.com/paper/2507.10326/) (2025)
- [Prompt Orchestration Markup Language](https://mlsanity.com/paper/2508.13948/) (2025)
- [Clotho: Measuring Task-Specific Pre-Generation Test Adequacy for LLM Inputs](https://mlsanity.com/paper/2509.17314/) (2025)
- [BoundRL: Efficient Structured Text Segmentation through Reinforced Boundary Generation](https://mlsanity.com/paper/2510.20151/) (2025)
- [REVERE: Reflective Evolving Research Engineer](https://mlsanity.com/paper/2603.20667/) (2026)
- [TSCG: Deterministic Tool-Schema Compilation for Agentic LLM Deployments](https://mlsanity.com/paper/2605.04107/) (2026)
- [SPEAR: Code-Augmented Agentic Prompt Optimization](https://mlsanity.com/paper/2605.26275/) (2026)
- [Large Language Models Do Not Always Need Readable Language](https://mlsanity.com/paper/2606.19857/) (2026)
- [GenAIOps for GenAI Model-Agility](https://mlsanity.com/paper/2502.17440/) (2024)
- [KACE: Knowledge-Adaptive Context Engineering for Mathematical Reasoning](https://mlsanity.com/paper/2606.00532/) (2026)
- [CRAFT: Cost-aware Refinement And Front-aware Tuning of Prompts](https://mlsanity.com/paper/2606.04661/) (2026)
- [Towards Spec Learning: Inference-Time Alignment from Preference Pairs](https://mlsanity.com/paper/2606.24004/) (2026)
- [Object Aligner: A Configurable JSON Schema Similarity Score for Graphs, Applied to LLM Prompt Optimization](https://mlsanity.com/paper/2607.01972/) (2026)
- [Imprompt: A Language Framework for Prompt Programming](https://mlsanity.com/paper/2607.22683/) (2026)
- [SEPO: Evidence-Grounded Prompt Optimization via Structural Editing](https://mlsanity.com/paper/2608.28067/) (2026)
- [Control-Data Flow Separation: Stable Prompt Optimization in Multi-Agent LLMs](https://mlsanity.com/paper/2609.00621/) (2026)
- [Mapping the RAG Landscape: A Four Axis Taxonomy of Efficiency, Defense, Interactivity, and Reasoning](https://mlsanity.com/paper/2610.01936/) (2026)
- [MoPrO-SD: Modular Prompt Optimization for Stance Detection](https://mlsanity.com/paper/2610.13386/) (2026)

## Abstract (arXiv)

In many modern LLM applications, such as retrieval augmented generation, prompts have become programs themselves. In these settings, prompt programs are repeatedly called with different user queries or data instances. A big practical challenge is optimizing such prompt programs. Recent work has mostly focused on either simple prompt programs or assumed that the general structure of a prompt program is fixed. We introduce SAMMO, a framework to perform symbolic prompt program search for compile-time optimizations of prompt programs. SAMMO represents prompt programs on a symbolic level which allows for a rich set of transformations that can be searched over during optimization. We show that SAMMO generalizes previous methods and improves the performance of complex prompts on (1) instruction tuning, (2) RAG pipeline tuning, and (3) prompt compression, across several different LLMs. We make all code available open-source at https://github.com/microsoft/sammo .