PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2601.00497v2cs.SE

TL;DR

LLM applications are difficult to test because they can produce harmful or faulty responses across a vast input space. STELLAR formulates testing as evolutionary search over discretized style, content, and perturbation features, and evaluates it on safety and navigation systems. The framework consistently uncovers more failures than baseline approaches, while the study’s generalizability remains limited to three systems and selected models.

  • Problem

    LLM applications can generate incorrect, incomplete, or harmful outputs, while their high-dimensional input spaces make exhaustive testing impractical.

  • Method

    STELLAR uses evolutionary search over discretized stylistic, content, and perturbation features to generate failure-revealing text inputs.

  • Results

    STELLAR consistently uncovers more failures than randomization, combinatorial, coverage-based, and state-of-the-art automated testing baselines across two case studies and three systems.

  • Takeaways & Limitations

    STELLAR provides a search-based framework for benchmarking LLM applications across malicious-input handling and task-oriented dialogue settings.

  • Takeaways & Limitations

    The evaluation covers two case studies, three systems, and up to six LLMs, so generalization to other domains, larger systems, or additional LLM families requires caution.

Abstract

from arXiv · show

Large Language Model (LLM)-based applications are increasingly deployed across various domains, including customer service, education, and mobility. However, these systems are prone to inaccurate, fictitious, or harmful responses, and their vast, high-dimensional input space makes systematic testing particularly challenging. To address this, we present STELLAR, an automated search-based testing framework for LLM-based applications that systematically uncovers text inputs leading to inappropriate system responses. Our framework models test generation as an optimization problem and discretizes the input space into stylistic, content-related, and perturbation features. Unlike prior work that focuses on prompt optimization or coverage heuristics, our work employs evolutionary optimization to dynamically explore feature combinations that are more likely to expose failures. We evaluate STELLAR on three LLM-based conversational question-answering systems. The first focuses on safety, benchmarking both public and proprietary LLMs against malicious or unsafe prompts. The second and third target navigation, using an open-source and an industrial retrieval-augmented system for in-vehicle venue recommendations. Overall, STELLAR exposes up to 4.3 times (average 2.5 times) more failures than the existing baseline approaches.

I. INTRODUCTION

LLM applications require systematic testing because they can produce incorrect or harmful outputs while exposing an impractically large input space. STELLAR addresses this challenge with evolutionary search over discretized linguistic features and evaluates the approach across safety and navigation systems.

  • LLM applications can generate incorrect, incomplete, or harmful information, making comprehensive robustness testing essential.
  • Benchmark datasets suffer from contamination and cannot exhaustively cover the diverse, unexpected inputs that LLM applications must handle.
  • Over 390,000 feature combinations would require more than 20 days of continuous execution at five seconds per test.
  • STELLAR frames testing as optimization, discretizes inputs into stylistic, content, and perturbation features, and uses evolutionary search to explore combinations.
  • STELLAR evaluates malicious-prompt safety and in-car navigation assistants, consistently revealing more failures than random, combinatorial, and coverage-based baselines.
  • The testing problem models an application, search domain, vector-valued fitness function, and failure oracle that identifies failure-inducing inputs.

III. APPROACH

STELLAR represents LLM test inputs with discrete style, content, and perturbation features, encodes them numerically, and uses search guided by fitness evaluation and a failure oracle.

  • LLM input spaces are represented through discrete features, including stylistic properties and perturbations such as word removals or misspellings.
  • STELLAR receives feature sets, constraints, the application under test, a generation model and template, a fitness function, and a failure oracle.
  • Each feature takes values from a finite domain, enabling candidate test inputs to be expressed as feature vectors.
  • Ordinal and categorical feature values are mapped to numerical indices so optimization algorithms can control test generation systematically.
  • The algorithm samples feature combinations, executes candidates while the budget remains available, evaluates them, and returns failure-inducing inputs.

B. Test Preparation

Before generating tests, STELLAR applies domain-specific constraints to remove incompatible feature combinations and preserve coherent candidate inputs.

  • Feature constraint rules are applied during evaluation to eliminate incompatible combinations, such as food types paired with a car-repair category.
  • Constraints can also prevent conflicting stylistic settings, such as simultaneously polite and very direct utterances.
  • After constraint handling, the feature vector is used to produce a valid candidate for test generation.

C. Test Generation

STELLAR converts constrained feature vectors into executable text through a domain-specific prompt template, augmented with retrieved examples before LLM generation.

  • The constrained feature vector is converted into an executable test input using the supplied prompt template.
  • Content, style, and perturbation vectors are inserted into a domain-specific template containing linguistic, content-related, and perturbation-related attributes.
  • Figure 1 illustrates a NaviQA generation prompt in which feature types and examples are passed as parameters.
  • RAG adds existing test examples to the template by retrieving samples whose embeddings match the feature vector before an LLM generates executable inputs.

D. Initial Test Execution and Evaluation

STELLAR evaluates generated test inputs by executing them on the application under test and assigning fitness scores that measure semantic alignment between inputs and outputs.

  • Generated test inputs are executed by the application under test, which produces corresponding outputs for evaluation.
  • A fitness function assigns each input-output pair a quantitative score reflecting their degree of semantic alignment.The fitness function may use either single-objective or multi-objective evaluation, depending on the use case.

E. Genetic Optimization

STELLAR iteratively applies evolutionary optimization to encoded test inputs, generating, evaluating, archiving, and selecting candidates through crossover, mutation, and survival operations.

  • The optimization pipeline repeatedly generates candidates, executes the application under test, archives evaluated tests, and selects candidates using fitness values.
  • Crossover exchanges feature labels between parent test vectors, using SBX for ordinal features and uniform crossover for categorical features.Parent selection uses tournament selection, while a probability threshold controls which elements are exchanged.
  • Mutation alters feature-vector variables with uniform mutation for categorical features or polynomial mutation for other feature types, subject to threshold thM.
  • Survival ranks solutions by nondominance and then prioritizes tests using crowding distance before the oracle labels failures after the search budget is exhausted.
  • Inputs whose embedding cosine similarity exceeds 0.8 are removed to reduce duplicate or near-duplicate tests in the population.Embeddings are computed using ALL-MINILM-L6-V24.

G. Implementation

The implementation evaluates STELLAR across safety and navigation case studies, using LLM-based judging and multiple autonomous systems under varied deployment settings.

  • Implementation: The study executes more than 234,000 tests, with 1,000 tests per run and more than 24 days of total execution time.
  • Evaluation: An LLM-based oracle evaluates system responses, and RQ0 measures how accurately LLM judges classify pass/fail outcomes.
  • STELLAR is evaluated across two domains and three application-under-test configurations to assess effectiveness and generalizability.
  • SafeQA: The safety case study tests whether standalone LLMs generate unsafe responses to malicious or safety-critical prompts.Examples include requests for insults or instructions to destroy a neighbor’s car.
  • NaviQA: NaviQA-I uses a static Yelp-based dataset, whereas NaviQA-II retrieves points of interest dynamically through online APIs and supports additional vehicle-related features.The two navigation systems therefore cover open-source data and an industrial-grade setting with different potential failure modes.

C. Baselines

STELLAR is compared with randomized, combinatorial, and coverage-oriented baselines across safety and navigation tasks, using judge evaluation, failure counts, and failure diversity measures.

  • Baselines: For SafeQA, STELLAR is compared with Random Search, ASTRAL, and T-WISE, while navigation experiments compare STELLAR with T-WISE and Random Search.ASTRAL is not directly applicable outside safety-focused LLM testing.
  • Effectiveness: Effectiveness is measured by the number of failing inputs found over a fixed budget, excluding duplicates, invalid inputs, and specified navigation cases without an existing point of interest.
  • Failure Diversity: Failure diversity is measured by clustering aggregated failures, automatically selecting clusters with the Silhouette method, and averaging cluster coverage across 10 repetitions.
  • Judge Evaluation: The safety experiments benchmark LLM-based judges on 1,000 question-answer pairs using continuous and binary safety scores.Continuous scores provide search fitness values, while binary scores support comparison with ASTRAL.
  • Search Space: STELLAR’s feature space includes content categories, stylistic dimensions, and perturbations such as word deletions, filler words, homophones, character noise, and typos.Navigation features are also defined along style, content, and perturbation dimensions.

3) Navigation:

STELLAR constructs navigation tests from discretized style, content, and perturbation features, then evaluates response quality and POI-constraint satisfaction. GPT-4O-MINI was selected as the judge after validation, and failures are flagged when either fitness score falls below 0.75.

  • Feature design: Navigation style features were derived from real user interactions and BMW expert discussions, while content features came from the POI database.
  • Feature design: STELLAR models speech-related variation with homophonic substitutions for ASR errors and filler words for natural speech, discretizing style and perturbation features into three to five categories.
  • Test generation: GPT-4O-MINI generated navigation inputs with a 93.5% averaged validity rate in expert review and was selected for test generation.
  • Fitness functions: Fitness Response evaluates textual appropriateness across request-oriented, detail, and politeness dimensions, while the POI fitness evaluates returned venues against user constraints.
  • Fitness functions: The POI fitness compares requested constraints with returned venues using distance functions, including Euclidean distance for ordinal numerical constraints and exact matching for categorical constraints.
  • Failure oracle: The failure oracle labels a test as failing when either normalized fitness score is below 0.75.
  • Evaluation setup: The SafeQA judge evaluation was averaged over five runs, while the SafeQA testing figures report failures after two hours and average results over six runs.

F. Results

Across SafeQA and NaviQA, STELLAR consistently finds more failures than randomized, combinatorial, coverage-based, and state-of-the-art baselines. Its average failure-rate advantage is 2.2 times in SafeQA and 2.5 times in NaviQA, with statistically significant improvements and large effect sizes.

  • Judge evaluation: GPT-4O-MINI was selected as the judge because it balanced accuracy, latency, and cost across SafeQA and NaviQA.
  • Judge evaluation: The judge evaluation used 30 generated question-answer pairs, 10 BMW participants, and 300 annotations for NaviQA response assessment.
  • SafeQA: STELLAR consistently identified more SafeQA failures than ASTRAL, T-WISE, and randomized search across all evaluated LLMs.
  • SafeQA: 2.2 times higher failure rate was achieved by STELLAR on average than by the best baseline in SafeQA.
  • NaviQA: STELLAR consistently discovered more NaviQA failures than randomized search and T-WISE across all application-under-test systems, clearly outperforming baselines in NaviQA-II.
  • NaviQA: 2.5 times higher failure rate was achieved by STELLAR on average in NaviQA than by the comparison approaches.
  • Overall effectiveness: The improvements over all baselines were statistically significant, with large effect sizes, across both case studies and the three application-under-test systems.

3) Diversity (RQ2):

STELLAR finds diverse failure behaviors across safety and navigation systems, including challenging and previously undetected failure types. Its diversity is attributed to targeted exploration rather than random dispersion, while the evaluation acknowledges methodological and generalization limits.

  • Coverage results: STELLAR achieves up to 98% failure-cluster coverage on GPT-5-CHAT, where failures are harder to expose.In SafeQA, it consistently surpasses ASTRAL across models.
  • Coverage results: STELLAR matches or exceeds randomized and coverage-based baselines across all NaviQA-I and NaviQA-II systems.No NaviQA baseline shows a significant advantage over STELLAR.
  • Threats to validity: Results may vary with clustering thresholds, nondeterministic model outputs, API durations, and generator utterances that do not exactly match intended features.The study mitigated these factors through repeated runs, averaging, generator evaluation, and monitoring.
  • Threats to validity: Generalization is limited because the evaluation covers two case studies, three systems under test, and up to six LLMs.The authors advise caution when extending findings to other domains, larger systems, or additional LLM families.
  • Qualitative findings: The qualitative evaluation identifies failure types spanning endpoint, retrieval, and linguistic-perturbation errors, with domain-expert confirmation that all are realistic.Failures were clustered by embeddings of system answers and manually assigned to failure types.
  • Qualitative findings: Only failure types F3 and F5 had not previously been detected during NaviQA-II testing.Types F1, F2, F6, F7, F8, and F9 had been frequently detected, while F4 had appeared in another context.
  • Severity: Most identified failures were high severity, and STELLAR showed high detection rates for the particularly challenging F3 and F5 categories.The domain expert characterized F6 as low severity because synchronization issues make it difficult to avoid.

VII. RELATED WORK

Prior LLM testing methods include benchmark datasets, randomized or adaptive input transformations, metamorphic testing, and coverage-based generation. STELLAR differs by using feedback-guided optimization to explore failure-inducing inputs without relying on a fixed initial dataset.

  • Benchmark datasets: Existing LLM evaluations use safety, general-capability, and dialogue-oriented benchmark datasets across diverse application domains.Examples include BeaverTails, Do-Not-Answer, ToxiGen, MMLU, BIG-Bench, CoQA, MultiWOZ 2.2, and KVRET.
  • Automated testing approaches: Existing approaches include randomized jailbreak suffix search, metamorphic testing, turn-level dialogue transformations, adaptive randomized selection, and toxicity testing.METAL, MORTAR, Yoon et al., and EvoTox address different testing objectives and input-generation settings.
  • Automated testing approaches: METAL and MORTAR require initial datasets with inputs and expected outputs or comparison relations, limiting their use when such resources are unavailable.METAL also lacks a feedback loop for guiding generation toward likely failing cases.
  • Comparison with ASTRAL: ASTRAL discretizes feature combinations and constructs a coverage matrix but does not scale well to many features or use feedback from evaluated tests.STELLAR addresses these limitations through optimization-guided generation.
  • STELLAR: STELLAR dynamically modifies test inputs using feedback to explore potentially failure-inducing behaviors, rather than relying on static coverage or randomized selection.Its evaluation reports more failures than randomization, combinatorial methods, and a state-of-the-art automated baseline.
  • Reproducibility: The replication package makes the testing pipeline and reported results available.This supports reproduction of the presented evaluation.
Loading 2601.00497v2…