M utant P rompt: Prompt Optimization via Mutation Under a Budget on Modest-sized LM s (2025)

Abstract: Prompts serve as a critical instruction interface to unlock the diverse capabilities of Large Language Models (LLMs), thus directly influencing the quality of their outputs. While prompt engineering has shown great promise, identifying optimal prompts remains a significant challenge, particularly for low-resource languages, which often face higher computational costs due to increased token generation and limited gold standard task data. In response, we propose MutantPrompt, a framework that leverages multi-armed bandit algorithms to efficiently identify optimal prompts tailored to low-resource languages. By framing prompt selection as an exploration-exploitation problem under a fixed computational budget, the framework dynamically balances exploring new prompts with exploiting known high-performing ones. We demonstrate the framework’s effectiveness across multiple low-resource Indic language tasks, including classification, question-answering and causal reasoning using three small parameter-size LLMs. The results highlight the cost efficiency of the search method in finding optimal prompts and resulting performance improvements.

## introduction large language models (llms) (openai et al., @xcite have revolutionized natural language processing (nlp), enabling stateof-the-art performance across various tasks, from text generation to complex reasoning. however, llms' effectiveness heavily depends on the quality of the prompts used to interact with them. prompt engineering-the practice of crafting effective input instructions to elicit high-quality outputs-has gained considerable attention as a means to optimize llm performance. despite its potential, identifying the most effective prompts remains a challenging problem, particularly in lowresource language (lrl) settings, perhaps widening the performance gap between lrls and hrls (high-resource languages) @xcite . low-resource languages face unique obstacles when interacting with llms. these languages often have limited annotated datasets, making it difficult to fine-tune models effectively. in addition, due to differences in tokenization @xcite and linguistic structures, they frequently incur higher computational costs @xcite as llms generate more tokens to process input and produce output with slow inference @xcite . a naïve approach of finding optimal prompts using a trialand-error method can be costly in such settings, as the higher number of token generations results in a significantly increased budget requirement. furthermore, compared to hrl tasks, lrl tasks have less available gold standard data @xcite , necessitating prompt optimization methods that rely less on such data to be effective. this paper introduces mutantprompt, a novel framework that addresses these challenges by leveraging multi-armed bandit (mab) algorithms to optimize prompt selection for lrls. by framing prompt selection as an exploration-exploitation problem, the framework strategically balances the discovery of new prompts with the utilization of previously identified high-performing ones under a fixed computational budget. this approach enables efficient search and selection of effective prompts without exhaustive manual tuning or expensive computational resources. we evaluate mutantprompt across multiple nlp tasks in 11 low-resource indic languages, including classification, question-answering, and causal reasoning using three recent small-size (2b-7b parameters) llms, namely llama-3.2 @xcite , mistral-3 @xcite and gemma-2 (gemma @xcite . our experimental results demonstrate the cost efficiency of the search methodology in identifying optimal prompts while improving task performance. the findings underscore the importance of intelligent prompt selection mechanisms in promoting equitable and efficient llm applications, ensuring that lrl users benefit from the advancement of nlp. ## related work continuous prompt-based methods (li and liang, @xcite , which tune the parameters of specific input tokens, have demonstrated effectiveness but is costly and less interpretable @xcite , while discrete prompt optimization, using task-specific instructions or keywords, is more interpretable and user-friendly (schick and schütze, @xcite . various methods for automatic discrete prompt search and generation have been explored @xcite . however, many rely on model gradients or token probabilities, which may not suit all models. others select the best prompts through enumeration, re-sampling, or iterative edits @xcite . while effective, these methods can be computationally expensive or converge to suboptimal solutions. recently, evoprompt @xcite demonstrates the effectiveness of genetic and evolutionary algorithms to give optimal prompts without the need for model parameter tuning and is doing better than recent pseudo-gradient @xcite and model token probability-based methods @xcite . while their method provides valuable insights, it relies on extensive inference budgets due to longer instructions and full development data for scoring prompts, which can be costly. in contrast, mutantprompt uses a budgetconstrained mab approach, exploiting and mutating the best-performing prompt using simple instructions and a dynamic mutation rate while using a small subset of data for scoring. we compare mutantprompt with evoprompt to demonstrate performance and cost improvements. algorithm 1 mutantprompt. inputs: • seed prompt p seed , instruction pinstr, budget b • max mutation rate rmax, min mutation rate rmin • decay rate r decay , decay step dstep • dev dataset d dev , batch size b 1: p ← {p seed } /* prompt pool */ 2: i ← b b /* total iterations */ 3: countsucc ← {} /* success counts, empty dictionary */ 4: count f ail ← {} /* failure counts, empty dictionary */ 5: for @xmath0, i) do 6: for @xmath1: θ[i] ← βi(countsucc[i] + 1, count f ail [i] + 1) /* sample prompt's success probability from beta distribution */ 8: pcurr ← arg @xmath2: batchsucc, batch f @xmath3, d dev , b) /* evaluate the prompt on a batch of dev set and return the success and failure count */ 10: countsucc[pcurr] + = batch_succ 11: count f ail [pcurr] + = batch_f ail 12: @xmath4, rmax • r ⌊ i d step ⌋ decay )/* update mutation rate */ 13: p robmut ∼ u (0, 1) /* generate random probability of mutation from uniform distribution */ 14: if p @xmath5: p @xmath6: @xmath7, p best )/* generate new prompt from p best */ 17: p ← p ∪ pnew 18: countsucc[pnew] = 0 19: count f ail [pnew] = 0 20: p f inal ← arg @xmath8: return p f inal /* best performing prompt */ 3 proposed method: mutantprompt in this work, given a task and a budget, we frame the search for an optimal prompt as a multi-armed bandit (mab) problem where each arm represents a prompt (we use thompson sampling to implement mab). in addition, we want to extend the prompt pool by mutating the best-performing prompt after each iteration. we describe mutant-prompt in algorithm 1. at the start of each iteration, we sample the probability of success of each prompt p i denoted by θ i , from a beta distribution with the parameter α i and β i as the number of successes and a number of failures correspondingly till now for the prompt (line 7). initially, they are set to zero, making it a uniform distribution. next, we take the prompt with the highest success probability (line 8) and explore it by evaluating it on a small test set, and update the success and failure count of the prompt (lines 9-11). subsequently, we probabilistically mutate the prompt with the best performance and add it to the prompt pool (line 14-19) (appendix a figure 1 shows the instruction p instr used for this). by mutating the best prompt, we expect another reasonably effective prompt to be added to the pool, making the prompt pool rich. we also exponentially reduce the mutation rate (line 12) as we move forward before it saturates to the minimum mutation rate. there are two motivations for doing this -first, as we start with a single prompt, it is essential to mutate more frequently in the beginning to increase the prompt pool. second, if we keep mutating at a higher rate throughout iterations, the prompt pool will explode, not converging the beta distributions as exploration outweighs exploitation. after the entire budget is consumed, we select the prompt with the best success ratio as the optimal prompt (line 20). in summary, starting with a single seed prompt, the algorithm iteratively evaluates its performance and refines the prompt pool. at each iteration, thompson sampling is used to estimate the success probabilities of all prompts in the pool, selecting the most promising one for evaluation. the success and failure counts of the selected prompt are updated based on its performance. to expand the pool, the algorithm probabilistically mutates the best-performing prompt into a new one using a dynamic mutation rate that decreases over time, ensuring a balance between exploration (discovering new prompts) and exploitation (exploring existing prompts to build confidence). this iterative process continues until the computational budget is exhausted, after which the prompt with the highest success rate is selected as the optimal solution. details of algorithm parameters are in appendix b ( ## experiment and results to check the effectiveness of mutantprompt, we experiment with five datasets, of which four are from indicxtreme @xcite -indicsentiment (sentiment classification), indicxnli (natural language inference), indic-copa (commonsense causal reasoning), indicx-paraphrase (paraphrase detection) and one from indicglue @xcite ) -csqa (multiple-choice qa) covering 11 indian languages. we use three recent small parameter size llms (2b-7b parameters) to show the technique's effectiveness in resource-constrained setup. the llms are mistral-3(7b), llama-3.2(3b) and gemma-2(2b). for performance metrics, we use exact match accuracy for all the tasks. details ## conclusion this paper presents a framework leveraging multiarmed bandit algorithms to generate and search for optimal prompts for low-resource language tasks. by framing the prompt selection process as an exploration-exploitation problem under a fixed computational budget, the proposed approach efficiently balances the discovery of new prompts with the exploitation of known high-performing ones. this method addresses the unique challenges faced by low-resource language tasks, including limited gold standard data, high computational costs due to increased token generation, and the need to optimize prompts without overwhelming smaller llms with overly complex instructions. our experimental evaluations on various nlp tasks in low-resource indic languages demonstrate the effectiveness and cost-efficiency of this approach. moving forward, we want to explore the proposed framework for more complex tasks and other lrls, fostering more inclusive and efficient llm querying.