Symbolic Prompt Program Search: A Structure-Aware Approach to Efficient Compile-Time Prompt Optimization (2024)

Abstract: 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 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://anonymous.4open.science/r/sammo-4003/.

## introduction with the recent development of large language models (llms) such as mixtral 8x7b @xcite or gpt-4, it is now possible to provide llms with longer inputs including richer context and more detailed instructions. as a result, the complexity of prompts has increased, including longer strings of instructions, demonstrations or examples, and specification of more structured output. these lengthy instructions are often reused as part of larger prompts, where static information (e.g., instructions) is combined with input-dependent information (e.g., user queries, retrieved documents in rag systems) at runtime. this has led to prompts being regarded as programs themselves, where each part is the result of other subprograms @xcite . as llm performance depends on a variety of factors such as paraphrasing, formatting and ordering @xcite , a key challenge to solve in practice is automatically finding the best prompt program for a given task and model. in this paper, we focus on compile-time optimization of prompt programs under black-box llm access. compile-time optimization is carried out only once before deployment and has two large advantages: (i) we can amortize the optimization cost over multiple uses of the prompt program and (ii) keep the existing run-time architecture unchanged. this is different from run-time optimization approaches, e.g., token pruning @xcite which are called every time before inference and thus have non-amortizable costs. a lot of work on prompt optimization has focused on simple prompt programs where the program consists of a single string (which is subsumed by our representation in section 2), mostly using structure-unaware operations such as paraphrasing @xcite @xcite . another line of work has focused on optimizing prompts with more complex programmatic structure, but still considers only static prompt structures, e.g., dspy @xcite . initial work in this direction focused on applying textual mutators to different prompt components @xcite @xcite figure 1 : left: symbolic prompt program (spp) for a binary classification task, where each node is a function with attributes and dependencies (children). the example also shows how the spp allows for structural changes (e.g., deletenode) and attribute-based changes (e.g., changeformat) which, after applying, result in the mutated prompt (right). these enable sammo to explore a large set of possible prompt candidates automatically. @xcite . subsequent work considered both textual mutation and hyperparameter selection @xcite . however, with increasing complexity of prompt structure, many prompt optimization techniques are no longer applicable and a new approach is needed that is able to optimize complex prompt programs with their hyperparameters. to address this, we introduce sammo, a general purpose framework for compile-time optimizations of prompt programs. different from existing approaches sammo represents prompt programs as symbolic prompt programs (spp) which are abstract program graphs that can be changed arbitrarily. this allows sammo to efficiently search through the space of valid prompt programs by automatically generating new promising candidates through mutations. moreover, sammo allows to both represent the internal structure of prompts (e.g., sections) as well as program structure (e.g., calling a retriever) in a unified fashion. by writing custom mutation operators, practitioners can encode their domain knowledge and guide the search process. sammo naturally extends previous prompt programming approaches such as dspy @xcite and encompasses several specialized prompt tuning methods as special cases. through spps, sammo (i) allows dynamic changes to prompt programs, (ii) generalizes compile-time optimizations to all prompt components (e,g., textual content, hyperparameters). ## symbolic prompt programs a prompt program π is a function that takes input data x and maps it to another string ŷ = π[x]. sammo's biggest innovation is the use of symbolic prompt programs to represent valid prompt structures, enabling flexible transformations and efficient search. that is in contrast to frameworks such as dspy @xcite , that use static prompt programs in their optimization process. to illustrate the advantages of symbolic prompt programs, consider the example prompt program in figure 1 for a binary classification task. each node is a function with attributes whose dependencies are indicated through child nodes. the program combines a number of text spans with the input data, sends it to the llm and parses the output response. static programs (e.g., dspy programs) have a fixed structure which limits the operations to mostly changes in a node's attributes, e.g., by paraphrasing text. symbolic prompt programs (spps) that sammo uses allow us to make much larger changes, all while ensuring that the prompt program remains semantically valid. two useful operators are highlighted in figure 1 , where we change the data format to xml and also remove the instructions prefix. these program modification would be challenging, if not infeasible, with static programs. section 2 will introduce many more possible operators for spps. ## compile-time prompt optimization our goal in this paper is the compile-time optimization of prompt programs. compile-time indicates that the optimization is done only once before using the prompt program, typically many times over with different inputs. we assume a black-box model for llm access where the only information returned is the response text and no probabilities. given an objective s ϕ (y, ŷ ) ∈ r and set of samples d s drawn i.i.d from a data distribution p (x, y ), the compile-time optimizer's goal is to return a more performant prompt program: note that s ϕ can also specify trade-offs between potentially multiple individual quality objectives s i (y, ŷ ). equation 1 is different but complementary to run-time optimization which is run every time when input x arrives (i.e., @xmath0. we implement ρ compile as a search procedure over a search space π of (symbolic) prompt programs. our goal is to find a prompt program π that performs best across the entire data distribution: here, p (x, y ) is the distribution that the labeled samples d s are drawn from. since the data distribution p (x, y ) is unknown and the evaluation cost of equation 2 is prohibitive, we resort to using the following sampled score in the spirit of empirical risk minimization (erm): π = arg min π∈π s ϕ (π, d train ). for the experiments in this paper, we assume that dataset sizes are on the order of hundreds of examples. this represents a reasonable amount of data that can be hand-labeled; increasing the amount would limit the applicability in practice substantially. ## sammo: structure-aware multi-objective metaprompt optimization we outline sammo, which is a general framework for optimizing the performance of symbolic prompt programs. specific details can be found in the opensource implementation of sammo. sammo uses two classes of search algorithms with a rich set of mutation operators to explore the space of prompts. the main novelty of sammo is that prompt programs are represented with all their structural dependencies on a symbolic level. without it, one is bound to a rigid prompt structure and also limited πactive ← samplecandidates(πc, dtrain, s ϕ ) 4: πnextgen ← ∅ 5: for each π ∈ πactive do 6: @xmath1: @xmath2: ∀@xmath3: add mutate(m, πactive) to πnextgen 9: end for 10: πc ←prune(πc ∪ πnextgen, dtrain, s ϕ ) 11: end while 12: return best candidate from πc to a much smaller set of possible mutation operators. moreover, it is also challenging to describe the search space efficiently. sammo supports both explicit and implicit descriptions of the search space through symbolic operators. figure 2 presents an overview of sammo's main components. starting from the top, sammo employs two types of search algorithms for different scenarios. below that sits of layer of prompt mutation operators that define the search space and actions. at the bottom is a base layer of function operators from which prompt programs are being composed, corresponding to the nodes in figure 1 . ## experiments we demonstrate the flexibility and effectiveness of sammo's spp search approach across three different scenarios, comparing to the most appropriate baselines in each scenario. in line with our assumption of limited data availability (section 3), we sample @xmath4. for the backend llms, we consider two open-source models, mixtral 7x8b @xcite and llama-2 70b @xcite ; as well as two closedsource models, gpt-3.5 and gpt-4 @xcite . see appendix b.1 for model details. un- ## related work related work can be categorized into two areas: prompt optimization and prompt compression. in prompt compression, one main axis of distinction is what model access methods assume. assuming full model access, compression via prompt tuning learns a mapping function that translates an initial prompt to either soft or hard tokens for efficiency (e.g., @xcite ). for example, @xcite uses a distillation objective to steer text generation with compressed instructions and @xcite use meta-learning to compresses prompts into "gist" tokens. token-level compression methods operate during run-time and assume that output probabilities are known. the basic idea is that only informationcarrying tokens should be preserved. for example, @xcite uses self-information to select and merge less probable tokens to compress in-context examples. jiang et al. (2023) extend this approach by doing it segment-wise and adding a prefiltering step. @xcite use a reinforcement learning approach to learn which tokens can be excluded from a prompt without degradation in accuracy. however, this requires extensive finetuning with external datasets. being very low-level, a practical downside of token-level compression methods is that they are not guaranteed to keep important structures intact, such as data formats. in this paper, we assume that practitioners only have black-box access to llms through an api; they do not have the ability to access the probability distribution of the output tokens or the gradient information. focusing on compressing task definitions, @xcite propose stdc, a method that uses breadth-first search to prune the syntax-tree after parsing the instructions. comple- b a s e li n e s t d c a p e s to p w o rd s g p t -4 r e w ri te s a m m o -5k 0 5k 10k 15k -0.1 0 0.1 0.2 b a s e li n e s t d c a p e s to p w o rd s g p t -4 r e w ri te s a m m o -10k 0 10k 20k -0.1 0 0.1 0.2 b a s e li n e s t d c a p e s to p w o rd s g p t -4 r e w ri te s a m m o -10k 0 10k 20k -0.1 0 0.1 0.2 b a s e li n e s t d c a p e s to p w o rd s g p t -4 r e w ri te s a m m o -50k 0 50k 100k -0.1 0 0.1 0.2 weighted costs δ baseline accuracy weighted costs δ baseline accuracy weighted costs δ baseline accuracy weighted costs δ baseline accuracy weighted costs δ baseline accuracy gpt-4 gpt-3.5 mixtral-7b llama-2 70b figure 6: sammo is able the achieve high compression rates while still maintaining high accuracy. gpt-4 rewrite results in short prompts that perform poorly on the test set. 0 0.2 0.4 changedataformat decreaseincontextexamples dropexamples dropintro induceinstructions removestopwordsfromsegment segmenttobulletpoints shortensegment llm gpt-3.5 gpt-4 llama-2 70b mixtral 8x7b improvement rate chosen mutation action mentary to that are efforts to improve call efficiency by batching instances together that share the same overall task instructions @xcite . as shown by @xcite , batching only minimally impacts performance as long as batch sizes do not exceed a certain modelspecific threshold. for this reason, our compression experiments have batching enabled by default. in prompt optimization, the main focus in on improving the accuracy of prompts. past work has typically focused on simpler (e.g. single task, non-batched) prompts with less structure. again, there are a variety of methods that assume full model access @xcite ) which we will not discuss further. working with continuous prompt representations using a smaller surrogate model, instructzero @xcite optimizes prompts locally via bayesian optimization and uses calls to the llm api as feedback. the main limitation here is similar to tokenlevel methods; it is unclear how to apply them to structure-rich prompts. on the discrete optimization side, automatic prompt engineer (ape) @xcite generates instruction candidates from a few input-output pairs, and then uses beam search over paraphrased candidates. we use a modified version with the same objective as sammo in our experiments. targeting mainly accuracy and not compression, grips @xcite uses beam search with edit, add and delete operations on the syntax tree after parsing the instructions. similarily, automatic prompt optimization (apo) @xcite re-writes instructions by generating explanations for errors, changing the prompt to reflect explanations, and then generating more prompt candidates by paraphrasing. ## conclusion in this paper, we introduced sammo, a framework for efficient compile-time optimization of prompt programs. the key innovation of sammo is to represent prompts as symbolic prompt programs. symbolic prompt programs enable sammo to search through the space of possible programs in an efficient manner. this approach notably outperforms and generalizes existing methods of prompt optimization and compression, as demonstrated through several use cases tasks in our experimental evaluation. sammo is made available publicly as an opensource project. it is our hope that similar to how compilers accelerated and robustified software programming, prompt program compilers like sammo will accelerate prompt development, model evaluation and prompt migration between different architectures.