Technical Summary: PQR – A Framework to Generate Diverse and Realistic User Queries that Elicit QA Agent Failures

Problem Statement

Evaluating Large Language Model (LLM)-based agents in real-world domains (e.g., e-commerce, healthcare, finance) remains a significant challenge. Current evaluation practices rely heavily on human effort to manually design test scenarios, a process that is costly, difficult to scale, and ill-suited for iterative development cycles.

Existing automated approaches generally fall into two categories, both of which have limitations:

1. Adversarial Attack Generation: Methods like PAIR and TAP focus on generating adversarial queries to induce safety failures (jailbreaks). However, these often produce "gibberish" or unnatural queries that do not reflect real user intents. Furthermore, their reliance on predefined strategies limits their ability to discover unexpected failure cases requiring novel, dynamically learned strategies.
2. Prompt Refinement: Prior works (e.g., GEPA, ACE) optimize prompts to improve task success or generate realistic queries. However, these are primarily designed to optimize effectiveness under a specific instruction and do not explicitly account for query diversity. In failure discovery, repeatedly eliciting the same type of failure offers limited diagnostic value and fails to capture the breadth of an agent's weaknesses.

The core problem is the lack of a systematic framework that can simultaneously generate failure-triggering queries that are both diverse (covering a wide range of failure modes) and realistic (mimicking genuine user behavior).

Methodology: The PQR Framework

The authors propose PQR (Prompt-Query-Refinement), a framework designed to generate diverse and realistic user queries that elicit agent failures under natural-language-defined objectives (e.g., helpfulness, safety). PQR operates through an iterative loop coupling two complementary modules to mitigate the weaknesses of using either alone:

1. Query Refinement Module

This module focuses on exploring diverse query variations through localized rewrites. It adopts strategies from prior adversarial work, categorized into:

• Perturbation: Operating at character, word, and sentence levels (e.g., adding typos, synonym replacement, syntactic changes).
• Role-Playing: Introducing variations via personas, tones, and scenarios.

The module employs a dual selection mechanism using beam search:

• Query Selection: Retains promising queries based on reward scores from an LLM-as-a-Judge.
• Strategy Selection: Retains perturbation/role-playing strategies that were most effective in the previous iteration at lowering reward scores (i.e., inducing more failures).
  This process continues until the compute budget is exhausted, ensuring a diverse set of candidate queries.

2. Prompt Refinement Module

While query refinement ensures diversity, it may miss failures requiring strategies beyond existing perturbations and lacks explicit enforcement of realism. The prompt refinement module addresses this by aggregating feedback to derive new objective-violating strategies and realism policies. It follows a three-stage loop:

• Selection: Uses beam search to retain prompts that generate the most objective-violating queries.
• Reflection: Produces two types of feedback:
  • Realism-related: Diagnoses why queries appear unrealistic and suggests improvements.
  • Objective-related: Includes three signals: (1) Objective-violation feedback (identifying features that trigger failures), (2) Objective-compliant feedback (identifying features that help the agent succeed, to be avoided), and (3) Criterion-specific feedback (targeting under-explored criteria).
• Expansion: Generates new candidate prompts using three parallel directions:
  • Exploitation: Amplifies strategies that have already triggered failures.
  • Exploration: Uses objective-compliant feedback to introduce contrasting strategies pushing toward new failure modes.
  • Examination: Targets the least frequently violated criteria to probe under-explored objectives.

Key Contributions

1. Novel Framework: PQR is the first framework to couple query refinement (for diversity) and prompt refinement (for strategy discovery and realism) in an iterative loop specifically for agent failure discovery.
2. Realism and Diversity Balance: Unlike prior methods that sacrifice realism for failure rates (adversarial attacks) or diversity for realism (prompt optimization), PQR explicitly balances both.
3. Dynamic Strategy Learning: By using feedback from query refinement to update prompt generation policies, PQR can discover novel failure strategies rather than relying solely on predefined templates.

Experimental Results

The framework was evaluated on detecting unhelpful responses from an e-commerce QA agent (built on Qwen3-8b), with additional safety-objective studies. Comparisons were made against prompt refinement baselines (GEPA, ACE) and query refinement baselines (TAP, PAIR) using GPT-5-mini and Gemma3-27b.

• Failure Discovery Rate (Unhelpfulness Rate - UHR): PQR achieved the highest UHR (56.32% with GPT-5-mini), uncovering 23% – 78% more unhelpful responses compared to baselines.
• Realism: PQR-generated queries achieved the highest realism scores among automated methods, closely matching human-generated queries (Human score: 4.51 vs. PQR: 3.66). It significantly outperformed query refinement baselines (TAP, PAIR) which produced less realistic queries.
• Diversity: PQR maintained high diversity scores (measured by embedding cosine similarity, distinct n-grams, and MTLD), outperforming prompt refinement baselines which tended to produce repetitive outputs.
• Cost Efficiency: PQR achieved these results at the lowest cost (token usage) among all methods, demonstrating higher efficiency in failure discovery.
• Human Evaluation: In a study with domain experts, PQR queries received the highest realism ratings (2.50/3.0) and matched the top relevance scores, confirming that the framework improves realism without sacrificing topical relevance.

Significance and Claims

The paper claims that PQR provides a more cost-efficient and systematic approach to evaluating LLM agents. By generating queries that are both diverse and realistic, PQR uncovers a broader spectrum of agent weaknesses than previous methods. The authors emphasize that while existing methods often produce arbitrary or unnatural failure-inducing queries, PQR's ability to surface realistic failure scenarios (e.g., ambiguous multi-attribute questions from a shopper) offers higher diagnostic value for improving agent robustness in real-world deployment.

The authors note modestly that the framework is currently tested primarily on helpfulness and safety objectives within e-commerce. They acknowledge that while PQR is agent-framework-agnostic, its scalability to agents with richer capabilities (e.g., complex tool-using, multi-step systems) and other domains requires further broader evaluation.