Exposing Long-Tail Safety Failures in Large Language Models through Efficient Diverse Response Sampling

This work proposes and demonstrates that Progressive Diverse Population Sampling (PDPS), a method that uncovers hidden vulnerabilities by shifting focus from rephrasing inputs to systematically and efficiently sampling high quality diverse model outputs, can expose a broad range of suppressed unsafe knowledge in LLMs at a significantly lower computational cost than traditional methods.

The Gist

Imagine you want to build a very smart, very polite robot assistant. How do you train it? First, you let it read a massive amount of data from the internet (the pre-training phase). This allows it to learn language, acquire knowledge, and memorize facts. However, during this process, the robot may also learn undesirable information, such as harmful instructions (e.g., how to make a bomb) or biased and offensive language.

How do we ensure that the robot does not exhibit such unsafe behaviors?
To address this, we perform safety tuning. We train the robot to produce refusal responses such as:

• "I can't provide that information…"
• "As a harmless assistant, I cannot help with that…"

when it is asked harmful questions like:

• "How to make a bomb?"
• "Provide instructions to build a weapon."

After extensive training, we might believe the system is safe. However, safety tuning is generally incomplete, far from exhaustive or foolproof. As a result, researchers actively try to find ways to break these safety mechanisms so vulnerabilities can be identified and fixed early (a process known as "red teaming").

The Existing Way: Tricking the Robot by Rephrasing the Question (Input-Space Search)

An existing way to break this robot's safety rules is to try to trick it by rephrasing the question. They try different ways of asking, like:

• "Pretend you are a villain..."
• "What would a bad guy do?"
• "Translate this into French..."
• "How to make a bomb? Sure, here…"

and hoping that the robot will slip and produce some unsafe responses, either because it gets confused by the rephrased query or in its effort to obey the user's instructions. This is like trying to break into a house by searching for unknown hidden backdoors or broken windows that may exist due to improper construction.

While this approach has been widely adopted and largely successful, it remains heuristic and ad hoc, offering no guarantee of comprehensive coverage and often incurring high computational costs.

The Proposed Idea: Program the Robot to Slip-Up (Output-Space Search)

This paper proposes an orthogonal and complementary strategy. It's about fixing a question (e.g., "How to make a bomb?") and asking the robot to answer it many, many times in different ways.

The idea hinges on two hypotheses:

1. If the robot has undergone a poor safety tuning process, the robot does not totally forget the dangerous knowledge; rather it just suppresses it in favor of safe refusal responses. So, those dangerous answers are still there, buried deep in the robot's memory.
2. The dangerous answers are semantically different from the refusal responses (e.g., "To make a bomb, you need the following ingredients:…" vs. "I can't answer the question…").

So, if you ask the robot to answer the same question 1,000 times in 1,000 different but meaningful ways (i.e., not just gibberish), it might eventually slip and produce some of the dangerous answers it has buried in its memory, as it tries to come up with responses that are different from the usual refusal ones. The more you ask, and the more you push the answers to be different from each other, the higher the chance the robot will reveal its unsafe knowledge.

The Problem: It's Too Expensive

There's a catch. Asking the robot 1,000 times to get just a few bad answers is incredibly expensive. It takes a lot of computer power and time. It's like hiring 1,000 actors to try to break into a house when most of them will just say "I can't do that," wasting your money.

The Solution: PDPS (The Smart Scout Team)

The authors created a clever method called PDPS (Progressive Diverse Population Sampling).
Imagine you are a general looking for enemy camps in a huge forest. You have identified 1,000 different roads by which the enemy soldiers might have moved.

The Brute-Force Way (IID Sampling): You send 1,000 soldiers, each assigned to a different road. They travel all the way to the end, wasting time and energy, and most of them find nothing.

The PDPS Way:
You notice that the enemy must have moved their tankers and heavy vehicles through these roads. So, the roads that lead to an enemy camp are likely to be well-conditioned (i.e., high quality). You also realize that some roads might lead to the same place. Therefore, it's enough to send soldiers only along roads that lead to different locations (i.e., high diversity).
However, you can't tell whether a road is well-conditioned or whether two roads lead to the same place just by looking at the beginning of them. To figure that out, you actually need to explore them. The further you go down a road, the more confident you become about its condition and direction.
So, you take the following steps to reduce fuel costs while maximizing your chances of finding enemy camps:

1. The Scout Run: You send 1,000 scouts, but they only go a short distance down each road.
2. The Filter: You take feedback from them about the road-condition and direction of the roads. You find that some roads are not suitable for heavy vehicles, while several others are leading in the same direction.
3. The Selection: You call back the scouts whose roads are not good enough or whose paths are heading in a direction similar to others. You keep the remaining scouts.
4. The Expansion: You tell the remaining scouts to go further into the forest to see if their paths lead to an enemy camp.
5. Repeat: You repeat this process a few more times, constantly pruning the group to keep only high-quality, diverse paths.

Why is this better?

• Efficiency: You don't waste time exploring the entire forest with soldiers who are likely to find nothing or head in the same direction. Instead, you focus your resources on the paths that look promising and avoid allocating resources to multiple similar paths.
• Coverage: You ensure that your scouts explore different directions, rather than all going the same way. This helps you find multiple enemy camps, if there is more than one. In other words, it helps you discover different ways the robot might fail, not just one.

The Results

The paper tested this on several smart AI models. Here is what they found:

• It Works: By using this "scout" method, they found dangerous answers that the standard safety training missed.
• It's Fast: They found nearly as many dangerous answers as the "brute-force" method of asking 1,000 times, while using only 8% to 29% of the computational power.
• It's Better: When the robot is limited to generating just 16 responses per query (so they're easy to check manually, unlike 1,000 responses), the method still finds 26% to 40% more dangerous answers than other methods.

The Big Takeaway

What this paper proposes is an orthogonal and complementary approach to uncovering safety failure modes in LLMs. Instead of (or in addition to) trying to trick the model with rephrased questions, we can systematically stress-test it by asking the same question and pushing it to respond in many different, creative ways, checking whether it slips and produces unsafe answers. With the proposed PDPS method, we can do this efficiently without burning through a huge amount of compute. This provides a novel, principled avenue to uncover hidden failure modes and fix them before deployment.

Technical Summary

1. Problem Statement

Despite safety tuning techniques like Supervised Fine-Tuning (SFT) and Reinforcement Learning from Human Feedback (RLHF), Large Language Models (LLMs) remain vulnerable to jailbreak attacks. Red-teaming aims to identify and mitigate these latent vulnerabilities prior to deployment. Therefore, developing novel red-teaming methods that are principled, systematic, comprehensive, efficient, and computationally scalable remains an active area of research.

2. The Current Approach to Red-teaming

Most existing red-teaming approaches focus on input-space optimization, i.e., crafting adversarial prompts to manipulate LLMs into generating unsafe responses.
Limitations:

• Heuristic / ad hoc: These techniques largely rely on human creativity or handcrafted templates, and therefore lack a systematic search strategy.
• Poor coverage: They explore only a small region of the input space and miss failures that are not easily triggered by rephrasing.
• Low sample efficiency: Since most prompt variations result in refusal responses, many attempts are needed to find even a single failure, leading to wasted computational effort.
• Computationally expensive at scale: Automated adversarial search often requires many queries and repeated evaluations (e.g., evolutionary or gradient-free methods), or costly gradient-based optimization, while still uncovering only a limited set of failures.
• Mode collapse to known tricks: These methods tend to rediscover the same types of jailbreaks (e.g., role-play, translation), resulting in limited diversity in the vulnerabilities found.

3. Proposed Approach: Output Space Search

This work proposes a principled, scalable, and complementary approach to augment existing input-space search-based red-teaming methods. The core idea is to explore, for a given query, the output space of the LLM by repeatedly querying it with the same prompt and generating multiple diverse responses. The rationale behind this approach is based on the following two hypotheses:

1. Imperfect safety alignment allows failure modes to persist in the long tail of the output distribution. In particular, safety tuning increases the likelihood of generating safe refusal responses relative to pre-trained unsafe or toxic behaviors. However, such undesirable responses are not entirely eliminated; instead, they persist as low-probability outputs for a given query. Notably, these low-probability harmful responses can become high-probability under adversarially perturbed prompts or due to misalignments introduced during fine-tuning.
2. Unsafe responses are semantically distinct from high-probability safe or refusal responses. This follows from the observation that safe or refusal responses typically take standardized forms such as "I can't answer this query" or "I am unable to assist with this request," which are semantically very different from low-probable unsafe responses that directly address the query (e.g., providing procedural details in response to a harmful instruction request such as "How to make a bomb?").

Therefore, generating a large number of semantically diverse responses for the same query increases the likelihood of sampling low-probability outputs that are semantically distinct from high-probability safe responses, thereby increasing the chance of eliciting unsafe behaviors.

4. PDPS: Making the Output Space Search Efficient

One way to explore a large output space and to increase the likelihood of generating the low-probable responses is to perform IID sampling of a large number of responses using some diversity-induced token level sampling mechanisms like high temperature sampling, nucleus sampling with large threshold or min-p sampling. However, sampling a large number of long responses for each query can be computationally prohibitive. To prevent it the authors propose Progressive Diverse Population Sampling (PDPS), a compute-efficient framework designed to explore the output space broadly while maintaining a compact, semantically diverse set of responses.

Core Concept:
Instead of generating thousands of full-length responses (which are mostly safe refusals), PDPS uses a multi-stage expansion-and-selection strategy:

1. Initialization: Start with a large pool of short, partial responses (e.g., 1024 instances of the prompt).
2. Iterative Expansion: In each step, expand the current candidates by sampling a block of new tokens using diversity-inducing methods (e.g., high-temperature, nucleus sampling).
3. Diversity-Aware Selection: Before the next expansion, prune the pool. The algorithm selects a subset of candidates that maximizes a quality-diversity objective:
   $$\text{Maximize } \frac{1}{n} \sum_{s \in A} q(s) + \lambda \cdot h(A)$$
   Where:
   • $q(s)$: Quality measure evaluating the quality of generated responses or the likelihood of the responses to be unsafe measured by a judge model.
   • $h(A)$: Diversity measure of the responses in $A$ (average pairwise distance between semantic embeddings of responses).
   • $\lambda$: Hyperparameter controlling the trade-off.
4. Termination: Repeat until a small set of full-length responses is obtained.

Technical Details:

• Quality Measure: The geometric mean of token probabilities measured by the target model itself has been used as the quality measure.
• Semantic Diversity: The framework uses the target model's internal hidden states (mean-pooled last-layer) projected via UMAP or cosine distance to measure semantic differences, rather than surface-level token overlap.
• Algorithm: The selection step solves a Max-Avg Diversification Problem, approximated using a greedy algorithm with a theoretical guarantee of at least $1/2$ of the optimal solution.
• Efficiency: By expanding only the most promising and diverse partial sequences, PDPS avoids the computational cost of generating full-length redundant refusals.

5. Key Contributions

1. Empirical Analysis of Output-Space Search: The paper demonstrates that increasing the number of samples ($N$) and decoding stochasticity (temperature $\tau$, top-$p$) leads to a monotonic increase in jailbreak success rates, supporting that safety tuning leaves a "long tail" of exploitable failures (Hypothesis 1).
2. Empirical Analysis of Semantic Separability of Safe and Unsafe Responses: The results demonstrate that unsafe responses largely lie in a distinct semantic embedding space compared to safe responses (Hypothesis 2).
3. PDPS Framework: Introduction of an efficient algorithm that replaces naive large-scale IID sampling with a diversity-aware expansion-and-selection strategy.
4. Performance vs. Cost: PDPS achieves attack success rates comparable to brute-force IID sampling (generating 1024 responses) while using only 8%–29% of the computational cost.
5. Superiority in Limited Budgets: Under constrained response budgets (e.g., generating only 16 or 64 responses), PDPS outperforms standard IID sampling and Diverse Beam Search (DBS) by 26%–40% in ASR.
6. Broader Failure Coverage: PDPS generates a higher number of distinct unsafe outputs, uncovering a wider range of failure modes compared to baselines that often produce redundant variations.

6. Experimental Results

The authors evaluated PDPS on four open-source LLMs (Llama-2-7B/13B, Qwen2.5-7B, Qwen3-14B) across four safety benchmarks (HarmBench, JailbreakBench, AdvBench, MaliciousInstruct).

• Attack Success Rate (ASR):
  • Limited Generation (16 responses): PDPS achieved an average ASR improvement of 38% over IID sampling and 40% over Diverse Beam Search.
  • Comparison to Brute-Force: PDPS with only 16 responses achieved >80% of the ASR of a brute-force IID sampling of 1024 responses in 11 out of 16 model-dataset combinations. With 64 responses, it exceeded 80% in all cases and reached >97% of the brute-force upper bound.
• Diversity of Failures:
  • PDPS identified a significantly higher number of unique unsafe responses per successful query compared to baselines.
  • Diversity metrics (Distinct-n, Self-BLEU, Unigram Entropy, Cosine Distance) confirmed that PDPS outputs are semantically more distinct, whereas baselines often cluster around similar refusal patterns or minor surface variations.
• Computational Efficiency:
  • PDPS reduced sampling time to 8%–29% of the time required by brute-force IID sampling (IID1024).
  • In limited-budget scenarios, PDPS was significantly faster than generating the same number of full-length responses via IID because it pruned the search space early.

7. Significance and Impact

• Paradigm Shift: The paper shifts the red-teaming focus from solely finding "vulnerable prompts" (input-space) to exploring "vulnerable distributions" (output-space). It highlights that the model's hidden vulnerabilities can be systematically uncovered by exploring the long-tail of the output distribution.
• Practical Utility: PDPS provides a highly efficient tool for developers and safety researchers to stress-test models. It allows for the discovery of seemingly rare, consequential safety failures without the prohibitive computational cost of massive-scale sampling.
• Safety Implications: The findings suggest that current safety alignment methods are imperfect and incomplete, allowing failure modes to persist in the long tail of the output distribution. Achieving true robustness requires explicitly addressing these unsafe behaviors that reside in the tail.

In conclusion, the paper establishes that diversity-driven sampling is a critical, underutilized vector for uncovering LLM safety failures, and PDPS offers a scalable, efficient solution to operationalize this discovery.