# EVOREFUSE: Evolutionary Prompt Optimization for Evaluation and Mitigation of LLM Over-Refusal to Pseudo-Malicious Instructions

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in Safety alignment and jailbreak attacks, one of 10 directions in LLM alignment / RLHF / preference optimisation.
- Builds on 37 of its 51 references that are in the map.
- First posted on arXiv 29 May 2025.

## Placed in

- LLM alignment / RLHF / preference optimisation / [Safety alignment and jailbreak attacks](https://mlsanity.com/alignment/safety-alignment-and-jailbreak-attacks/)
- LLM safety and security / [Safety alignment, refusal and guardrails](https://mlsanity.com/safety/safety-alignment-refusal-and-guardrails/)

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

- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [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)
- [Universal and Transferable Adversarial Attacks on Aligned Language Models](https://mlsanity.com/paper/2307.15043/) (2023)
- [HarmBench: A Standardized Evaluation Framework for Automated Red Teaming and Robust Refusal](https://mlsanity.com/paper/2402.04249/) (2024)
- [Jailbreaking Black Box Large Language Models in Twenty Queries](https://mlsanity.com/paper/2310.08419/) (2023)
- [AutoDAN: Generating Stealthy Jailbreak Prompts on Aligned Large Language Models](https://mlsanity.com/paper/2310.04451/) (2023)
- [Red Teaming Language Models to Reduce Harms: Methods, Scaling Behaviors, and Lessons Learned](https://mlsanity.com/paper/2209.07858/) (2022)
- [GPTFUZZER: Red Teaming Large Language Models with Auto-Generated Jailbreak Prompts](https://mlsanity.com/paper/2309.10253/) (2023)
- [XSTest: A Test Suite for Identifying Exaggerated Safety Behaviours in Large Language Models](https://mlsanity.com/paper/2308.01263/) (2023)
- [Safety-Tuned LLaMAs: Lessons From Improving the Safety of Large Language Models that Follow Instructions](https://mlsanity.com/paper/2309.07875/) (2023)
- [Hard Prompts Made Easy: Gradient-Based Discrete Optimization for Prompt Tuning and Discovery](https://mlsanity.com/paper/2302.03668/) (2023)
- [PKU-SafeRLHF: Towards Multi-Level Safety Alignment for LLMs with Human Preference](https://mlsanity.com/paper/2406.15513/) (2024)
- [OR-Bench: An Over-Refusal Benchmark for Large Language Models](https://mlsanity.com/paper/2405.20947/) (2024)
- [PromptAgent: Strategic Planning with Language Models Enables Expert-level Prompt Optimization](https://mlsanity.com/paper/2310.16427/) (2023)
- [JailBreakV: A Benchmark for Assessing the Robustness of MultiModal Large Language Models against Jailbreak Attacks](https://mlsanity.com/paper/2404.03027/) (2024)
- [PromptRobust: Towards Evaluating the Robustness of Large Language Models on Adversarial Prompts](https://mlsanity.com/paper/2306.04528/) (2023)
- [Rainbow Teaming: Open-Ended Generation of Diverse Adversarial Prompts](https://mlsanity.com/paper/2402.16822/) (2024)
- [Evolution through Large Models](https://mlsanity.com/paper/2206.08896/) (2022)
- [GrIPS: Gradient-free, Edit-based Instruction Search for Prompting Large Language Models](https://mlsanity.com/paper/2203.07281/) (2022)
- [Language Model Crossover: Variation through Few-Shot Prompting](https://mlsanity.com/paper/2302.12170/) (2023)
- [On Prompt-Driven Safeguarding for Large Language Models](https://mlsanity.com/paper/2401.18018/) (2024)
- [Multitask Prompt Tuning Enables Parameter-Efficient Transfer Learning](https://mlsanity.com/paper/2303.02861/) (2023)
- [Improved Techniques for Optimization-Based Jailbreaking on Large Language Models](https://mlsanity.com/paper/2405.21018/) (2024)
- [Why Should Adversarial Perturbations be Imperceptible? Rethink the Research Paradigm in Adversarial NLP](https://mlsanity.com/paper/2210.10683/) (2022)
- [Improved Few-Shot Jailbreaking Can Circumvent Aligned Language Models and Their Defenses](https://mlsanity.com/paper/2406.01288/) (2024)
- [What is Wrong with Perplexity for Long-context Language Modeling?](https://mlsanity.com/paper/2410.23771/) (2024)
- [FuzzLLM: A Novel and Universal Fuzzing Framework for Proactively Discovering Jailbreak Vulnerabilities in Large Language Models](https://mlsanity.com/paper/2309.05274/) (2023)
- [Offline Regularised Reinforcement Learning for Large Language Models Alignment](https://mlsanity.com/paper/2405.19107/) (2024)

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

- [SineProject: Machine Unlearning for Stable Vision Language Alignment](https://mlsanity.com/paper/2511.18444/) (2025)
- [MCCE: A Framework for Multi-LLM Collaborative Search in Discrete Spaces with Similarity-Filtered Preference Learning](https://mlsanity.com/paper/2510.06270/) (2025)
- [Understanding and Mitigating Over-refusal for Large Language Models via Representation Intervention](https://mlsanity.com/paper/2511.19009/) (2025)
- [Rendering Data Unlearnable by Exploiting LLM Alignment Mechanisms](https://mlsanity.com/paper/2601.03401/) (2026)
- [AOR-Bench: Do Large Audio Language Models Over-Refuse Pseudo-Harmful Queries?](https://mlsanity.com/paper/2606.21147/) (2026)
- [Door-in-the-Face Requests and Refusal Behaviour in Large Language Models](https://mlsanity.com/paper/2609.02707/) (2026)

## Abstract (arXiv)

Large language models (LLMs) frequently refuse to respond to pseudo-malicious instructions: semantically harmless input queries triggering unnecessary LLM refusals due to conservative safety alignment, significantly impairing user experience. Collecting such instructions is crucial for evaluating and mitigating over-refusals, but existing instruction curation methods, like manual creation or instruction rewriting, either lack scalability or fail to produce sufficiently diverse and effective refusal-inducing prompts. To address these limitations, we introduce EVOREFUSE, a prompt optimization approach that generates diverse pseudo-malicious instructions consistently eliciting confident refusals across LLMs. EVOREFUSE employs an evolutionary algorithm exploring the instruction space in more diverse directions than existing methods via mutation strategies and recombination, and iteratively evolves seed instructions to maximize evidence lower bound on LLM refusal probability. Using EVOREFUSE, we create two novel datasets: EVOREFUSE-TEST, a benchmark of 582 pseudo-malicious instructions that outperforms the next-best benchmark with 85.34% higher average refusal triggering rate across 9 LLMs without a safety-prior system prompt, 34.86% greater lexical diversity, and 40.03% improved LLM response confidence scores; and EVOREFUSE-ALIGN, which provides 3,000 pseudo-malicious instructions with responses for supervised and preference-based alignment training. With supervised fine-tuning on EVOREFUSE-ALIGN, LLAMA3.1-8B-INSTRUCT achieves up to 29.85% fewer over-refusals than models trained on the second-best alignment dataset, without compromising safety. Our analysis with EVOREFUSE-TEST reveals models trigger over-refusals by overly focusing on sensitive keywords while ignoring broader context. Our code and datasets are available at https://github.com/FishT0ucher/EVOREFUSE.