[Paper] STELLAR: A Search-Based Testing Framework for Large Language Model Applications

Source: arXiv - 2601.00497v1

Overview

The paper introduces STELLAR, an automated, search‑based testing framework designed to stress‑test applications that rely on large language models (LLMs). By treating test‑case generation as an optimization problem, STELLAR systematically discovers prompts that provoke unsafe, inaccurate, or otherwise undesirable responses—something that traditional manual or coverage‑based testing struggles to achieve at scale.

Key Contributions

• Search‑based test generation: Formulates prompt creation as an evolutionary optimization task, dynamically exploring a rich feature space (style, content, perturbations).
• Feature‑level discretization: Breaks down the massive input space into interpretable dimensions, enabling targeted exploration of risky prompt combinations.
• Empirical evaluation on three real‑world systems:
  • Safety‑focused benchmark across public and proprietary LLMs.
  • Two navigation‑oriented conversational agents (open‑source and industrial retrieval‑augmented).
• Significant failure discovery boost: Finds up to 4.3× (average 2.5×) more problematic responses than prior baseline methods.
• Open‑source prototype: Provides a reusable code base that can be plugged into existing LLM pipelines for continuous testing.

Methodology

1. Feature Modeling – The input prompt is represented by three orthogonal groups:
   • Stylistic: tone, formality, length, punctuation.
   • Content‑related: domain keywords, intent signals, question type.
   • Perturbations: misspellings, paraphrases, token swaps, adversarial noise.
2. Optimization Loop – An evolutionary algorithm (EA) iteratively mutates and recombines prompt candidates:
   • Initialization: Randomly sample prompts from a seed corpus.
   • Evaluation: Each prompt is sent to the target LLM; the response is scored by a failure detector (e.g., toxicity classifier, factuality checker, domain‑specific rule set).
   • Selection & Variation: High‑scoring (i.e., more failure‑prone) prompts survive; crossover and mutation operators tweak feature values.
   • Termination: After a fixed budget of queries or when improvement plateaus, the best‑performing prompts are reported.
3. Failure Detection – The framework can plug in any metric: safety (toxicity, hate speech), factual correctness, or business‑logic violations, making it adaptable to different application domains.

The overall pipeline is lightweight enough to run against commercial APIs (e.g., OpenAI, Anthropic) while respecting rate limits, and it can be integrated into CI/CD pipelines for continuous regression testing.

Results & Findings

Key Takeaways

• Evolutionary search uncovers edge‑case prompts that simple fuzzing or prompt‑engineering heuristics miss.
• The feature‑level abstraction enables the algorithm to “learn” which stylistic or perturbation patterns are most likely to trigger failures for a given system.
• Even with a modest query budget (≈10 k calls), STELLAR surfaces a substantial number of high‑impact bugs, suggesting that many production LLM services are under‑tested.

Practical Implications

• Continuous Safety Assurance – Teams can embed STELLAR into their CI pipelines to automatically flag regressions in toxicity or misinformation after model updates or prompt‑template changes.
• Domain‑Specific Guardrails – By swapping in custom failure detectors (e.g., compliance rules for finance, medical fact‑checkers), developers can generate targeted adversarial prompts without hand‑crafting them.
• Cost‑Effective QA – Compared to exhaustive manual prompt engineering, the evolutionary approach yields more failures per API call, reducing testing spend on expensive LLM endpoints.
• Model‑agnostic Deployment – Because STELLAR interacts with LLMs only through their standard text‑in/text‑out interface, it works with any vendor or self‑hosted model, making it a versatile addition to heterogeneous stacks.
• Insight for Prompt Designers – The discovered prompt patterns can inform better prompt‑templating practices, helping product teams write safer, more robust user‑facing prompts from the start.

Limitations & Future Work

• Failure Detector Dependency – The quality of discovered bugs hinges on the reliability of the downstream classifiers (toxicity, factuality). Mis‑calibrated detectors could produce false positives/negatives.
• Query Budget Constraints – While effective with ~10 k queries, very large commercial models with strict rate limits may need further budget‑aware strategies (e.g., surrogate models to pre‑filter candidates).
• Limited to Textual Inputs – STELLAR focuses on pure‑text prompts; extending the approach to multimodal LLMs (image‑text, audio‑text) remains an open challenge.
• Evolutionary Hyper‑parameters – The current EA settings (population size, mutation rates) were tuned for the evaluated tasks; a more automated hyper‑parameter search could improve portability across domains.

Future research directions include integrating learned surrogate models to predict failure likelihood before making costly API calls, expanding the feature taxonomy for multimodal inputs, and exploring hybrid search strategies that combine gradient‑based prompt optimization with evolutionary methods.

Authors

• Lev Sorokin
• Ivan Vasilev
• Ken E. Friedl
• Andrea Stocco

Paper Information

• arXiv ID: 2601.00497v1
• Categories: cs.SE
• Published: January 1, 2026
• PDF: Download PDF