EVOREFUSE: Evolutionary Prompt Optimization for Evaluation and
  Mitigation of LLM Over-Refusal to Pseudo-Malicious Instructions
Authors: name: Xiaorui Wu; name: Xiaofeng Mao; name: Xin Zhang; name: Fei Li; name: Chong Teng; name: Yuxiang Peng; name: Li Zheng; name: Donghong Ji; name: Zhuang Li
Published: 2025-05-29 14:26:46

Abstract: 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
140.41% higher average refusal triggering rate across 9 LLMs, 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.
LLAMA3.1-8B-INSTRUCT supervisedly fine-tuned on EVOREFUSE-ALIGN achieves up to
14.31% 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.