Source-linked AI summary
AdaT$^2$: Adaptive Test Transformations for Black-Box Boundary Testing of Conversational Agents
Liting Lin, Boxi Yu, Qinghua Xu, Yuzhong Zhang, Lionel Briand, Emir Muñoz
TL;DR
Conversational agents can fail to follow policies across multi-turn conversations, and actions taken through tools may be costly when they cannot be reversed. AdaT2 extracts policy statements from agent replies and adaptively generates plain and transformed boundary tests. Across four τ3-bench domains, it produces a higher proportion of explicitly valid tests than AgentEval, and transformed tests cover additional explicit boundaries.
Problem
Conversational agents often fail to comply with policies across multi-turn conversations, and tool actions such as refunds or cancellations may not be reversible.
Source: §1 · pp. 1–2Method
AdaT2 extracts statements describing policy conditions and expected behavior from agent replies, then adaptively selects plain or instruction-transformed boundary tests.
Source: §1 · pp. 3–4Results
Across four τ3-bench domains, 62.7% to 83.3% of AdaT2’s tests are explicitly valid, a higher proportion than AgentEval in every domain.
Source: §1 · p. 4Takeaways & Limitations
Transformed tests cover explicit boundaries missed by plain tests, and AdaT2’s suites detect more seeded policy faults than AgentEval’s in the airline and retail domains.
Source: §1 · p. 4, §7 · p. 19In each domain, both methods cover both sides of less than a quarter of their explicit boundaries.
Source: §5 · p. 17
Abstract
from arXiv · showhide
Conversational agents based on large language models (LLMs) must comply with policies. Each condition in a policy draws a boundary between user requests, and the agent must behave differently on its two sides. We present AdaT$^2$, which extracts statements from the agent's replies in exploratory conversations with an LLM acting as the user, and uses the statements to guide boundary test generation. Each statement describes one condition and the behavior expected when the condition holds. Besides plain tests guided by single statements, AdaT$^2$ writes transformed tests guided by pairs of a statement and a test transformation instruction, such as "omit one required input". The instruction of a pair can move a test to the other side of the statement's boundary or to another boundary. The statements and instructions form far more pairs than a run can try, and many pairs are not applicable. Adaptive pair selection therefore chooses the statement of each pair by novelty and the instruction with the bandit algorithm Bayes-UCB, which learns from whether earlier pairs yielded a test and whether the agent passed it according to an LLM judge. Our benchmark counts the two sides of each boundary separately and distinguishes boundaries explicitly defined by the agent's prompt, tool code, or knowledge base from boundaries that the agent's LLM infers from domain knowledge. On four domains of $\tau^3$-bench, 62.7% to 83.3% of AdaT$^2$'s tests are valid boundary tests whose expected behavior is explicitly defined, higher in every domain than AgentEval's (47.7% to 68.1%). Transformed tests add 13 to 46 explicitly defined boundaries that plain tests miss. As regression tests, AdaT$^2$'s test suites detect all eight seeded policy faults in the airline domain and four of eight in the retail domain, and AgentEval's test suites, with fewer than a third as many tests, detect five and two, respectively.
1 Introduction
AdaT2 guides black-box boundary tests with statements extracted from agent replies and transformed tests selected adaptively. Across four τ3-bench domains, it yields a higher proportion of explicitly valid tests than AgentEval, while transformed tests cover additional explicit boundaries.
Motivation
- Policy failures can be costly because tool actions such as refunds or cancellations may not be reversible, while agents often fail to comply with policies across multi-turn conversations.Policies may specify eligibility limits, required confirmations, and identity checks in prompts, knowledge bases, or tool code.Source: §1 · pp. 1–2
Approach
- A boundary divides requests the agent must handle differently, and a boundary test checks whether the agent behaves as expected for a request on one side.Policy conditions define such divisions between requests that satisfy a condition and those that violate it.Source: §1 · p. 2
Prior work
- AgentEval targets workflow-graph nodes and edges, but these can merge multiple boundaries and leave expected behavior to the generator; 22.0% to 36.0% of its tests expect domain-knowledge-only behavior.Its targets are selected before tests run, so earlier outcomes cannot guide later target choices.Source: §1 · pp. 2–3
Approach
- AdaT2 extracts statements describing one policy condition and its expected behavior, then uses them alone for plain tests or with instructions that can shift tests across boundaries.Instructions can change a request value or wording, or the conversation state.Source: §1 · p. 3
- Because statement–instruction combinations can vastly outnumber attempts and many are inapplicable, AdaT2 selects statements by novelty and instructions with Bayes-UCB using applicability and judge verdicts as feedback.One experiment had 11,466 pairs but only 400 attempts per run.Source: §1 · p. 3
Benchmark
- The benchmark distinguishes artifact-defined explicit boundaries from boundaries inferred from domain knowledge and counts each boundary’s two sides separately.An auditor checks test validity against the agent’s artifacts and necessary domain implications; explicitly valid tests expect only artifact-supported behavior.Source: §1 · pp. 3–4
Results
- Across four τ3-bench domains, 62.7% to 83.3% of AdaT2’s tests are explicitly valid, higher than AgentEval in every domain; transformed tests add 13 to 46 explicit boundaries missed by plain tests.As regression tests, AdaT2 detects all eight seeded airline faults and four of eight retail faults; AgentEval detects five and two, respectively.Source: §1 · p. 4
2 Preliminaries
The preliminaries establish the testing workflow and define boundary tests, state the method’s assumptions, and illustrate a policy boundary in the airline agent.
2.1 Discovery, Generation, and Execution
- The framework discovers agent behavior through conversations, generates tests from discovery traces, then executes and judges those tests.Discovery sessions use objectives and strategies to explore tasks, required inputs, and responses; tests specify goals, step hints, criteria, and a turn limit.Source: §2.1 · pp. 4–5
2.2 Boundary Tests
- A boundary divides user requests into sides that require different behavior, and a boundary test checks the agent’s behavior on one side.Policy conditions define boundaries; an agent’s artifacts explicitly define a boundary when they specify its condition and expected behavior on at least one side.Source: §2.2 · p. 6
2.3 Assumptions
- The method assumes resettable sessions with the same initial state, a limited testing budget, and policy compliance in most conversations.The latter assumption means faults are rare and discovery replies mostly show expected behavior.Source: §2.3 · pp. 6–7
2.4 Running Example
- In the airline example, changing only one of two unflown business-class flights violates the same-cabin-class condition, so the agent must not make the change.Changing both flights to economy lies on the side where the agent can change the cabin class.Source: §2.4 · p. 7
3 Method
AdaT2 extracts behavior statements from discovery replies to guide plain and transformed tests. Adaptive selection chooses statement–instruction pairs using novelty and feedback on applicability and judged test outcomes.
3.1 Overview
- AdaT2 extracts statements from discovery traces, generates plain tests and adaptively selected transformed tests, and executes and judges the generated tests.A grounding check removes statements unsupported by their replies and ranks the remainder by confidence.Source: §3.1 · p. 7
3.2 Statements
- Each statement describes one condition and the agent behavior expected when that condition holds, generalized beyond the specific entity in its supporting reply.Statements are extracted from replies and stored with those supporting replies as evidence for test generation.Source: §3.2 · pp. 8–9
3.3 Test Transformation Instructions and Statement–Instruction Pairs
- A transformed test pairs a statement with an instruction that changes a test factor and may move the request to another side or boundary.The instruction applies only when its condition is met and the discovery replies justify the transformation; the generator reports inapplicable pairs.Source: §3.3 · p. 9
3.4 Pair Selection
- Adaptive selection prioritizes novel statements and uses Bayes-UCB feedback on pair applicability and judged verdicts to choose instructions.The verdict reward is only a proxy for validity: it favors passing tests and can penalize instructions whose tests expose agent faults.Source: §3.4 · pp. 10–11
4 Evaluation
The evaluation tests AdaT2’s effectiveness, adaptive selection, comparison with baselines, and regression performance across four τ³-bench domains. It also assesses the auditor and defines measures for test validity, boundary coverage, execution verdicts, and seeded-fault detection.
4.2 Experimental Setup
- The study uses four text-based domains, shared discovery statements, GPT-6 Luna for generation and judging, and a fixed catalog of 91 instructions.AdaT2 and AgentEval share discovery traces and a generator model; the direct baseline receives traces without statement or instruction guidance.Source: §4 · p. 11, §4.2 · p. 12
4.3 Auditor and Measures
- The auditor labels tests as explicitly valid, valid but not explicit, or neither, and measures validity rates, distinct explicit boundaries and sides, and transformation attempts.Execution labels compare the judge’s verdict with the auditor’s compliance judgment; false alarm rate and accuracy are calculated from those labels.Source: §4.3 · pp. 12–13
- Regression testing uses eight policy-flip faulty agents per airline and retail domain; a suite detects a fault only when specified original-agent and faulty-agent verdict and auditor conditions hold.The mutation score is the proportion of the eight faults detected by a suite.Source: §4.3 · p. 13
4.4 Reliability of the Auditor
- On the airline samples, the three auditor models disagree with the expert on only two of 37 sampled executions, both with fail verdicts.The models label both TP, while the expert labels one FP and the other INC; pass-verdict executions are weighted to represent all 310 in the execution-label agreement measure.Source: §4.4 · p. 13, Table 1 · p. 14
4.5 Results
- Across four domains, 74.3% to 88.3% of AdaT2’s tests are valid boundary tests and 62.7% to 83.3% are explicitly valid boundary tests.Transformed tests contribute additional explicit boundaries and sides in every domain; the suites cover 71 to 147 explicit boundaries and 84 to 158 sides.Source: §4.5 · p. 14, Table 2 · p. 14
- Among selectors, AdaT2 needs the fewest or about as few attempts as the best alternatives, with only 3% of airline attempts and 2% of retail attempts ending as not applicable.Six other selectors that learn from prior attempts perform about as well in validity and additional explicit boundaries and sides, with two domain-specific exceptions.Source: §4.5 · pp. 14–15, Table 3 · p. 15
- Across all four domains, AdaT2’s suites have higher explicit validity rates than AgentEval’s, while AgentEval has higher validity rates in banking, retail, and telecom.With more than three times as many tests, AdaT2’s suites cover more sides in every domain; they cover more explicit boundaries in banking and telecom and about as many in airline and retail. AdaT2’s suites also have lower false alarm rates in every domain.Source: §4.5 · pp. 15–16, Table 4 · p. 16
- AdaT2 detects all eight seeded airline faults and four of eight retail faults; the airline direct baseline detects six and AgentEval detects five.In retail, AgentEval detects two of the four faults AdaT2 detects, and the direct baseline detects one; all three suites miss the other four faults.Source: §4.5 · pp. 16–17, Table 5 · p. 16
5 Discussion and Threats to Validity
Both methods cover less than a quarter of explicit boundaries on both sides in every domain, and the evaluation is constrained by limited runs, auditor judgments, and scope.
5 Discussion and Threats to Validity
- In every domain, both methods cover less than a quarter of their explicit boundaries on both sides, leaving two-sided discrimination limited.The authors identify this as a limitation for tests that cover only one side of a boundary.Source: §5 · p. 17
- Because LLM-call costs limited runs, several configurations use one test suite per method and domain, and the study cannot conduct significance tests.RQ2 uses three runs per configuration; the authors report low variation for AdaT2 in those runs.Source: §5 · p. 17
- An LLM auditor supplies validity labels, boundary and side counts, and most execution labels, so absolute validity rates depend on the auditor model.Compared suites within each domain share the same auditor, and the auditor alone attributes fail verdicts to seeded faults.Source: §5 · p. 17
- External validity is limited to four τ3-bench domains, one agent model, one generator model, one discovery campaign per domain, and 91 instructions.RQ2 and RQ4 use only airline and retail; seeded faults rewrite only prompt policy text.Source: §5 · p. 17
6 Related Work
Related work spans black-box agent testing, specification and boundary testing, and adaptive test selection. AdaT2 shares some of these aims while using statement-guided tests and adaptive transformations.
Testing LLM-based agents
- Like AgentEval, AdaT2 tests agents from discovery conversations, but replaces workflow-graph nodes and edges with statements that directly provide expected behavior.AgentEval targets graph nodes and edges with perturbed user messages.Source: §6 · pp. 17–18
Expected behaviors
- AdaT2’s statements resemble likely invariants more than state machines, describing one condition and the expected behavior when it holds.The paper contrasts this with work that infers invariants or state machines from executions and with agents that extract specifications from prompts.Source: §6 · p. 18
Boundary testing
- Unlike program boundary methods based on input distances, AdaT2 can test identical requests on different sides when conversation context changes.The paper notes that the side can depend on what the conversation has established.Source: §6 · p. 18
Test purposes, patterns, and partitions
- AdaT2 pairs statements with instructions instead of relying on human-listed category constraints; the generator determines whether an instruction applies.An instruction’s applicability condition corresponds to the context of a test-selection pattern.Source: §6 · p. 18
Metamorphic testing
- Although some AdaT2 instructions alter request wording, each transformed test is judged against its own criteria in one execution, not as a relation across executions.This distinguishes the approach from metamorphic testing.Source: §6 · p. 18
Adaptive selection
- Because the black-box selector cannot observe test validity or explicit-boundary coverage, it learns from test generation and judge verdicts using a bandit over instructions.Unlike COLEMAN’s failure-oriented reward, AdaT2 favors pass verdicts because failures can reflect defective tests or judge errors.Source: §6 · p. 18
Adaptive random testing
- AdaT2’s novelty order analogously disperses transformed tests across textually dissimilar statements, while adaptive random testing aims to spread inputs across a domain.The passage presents this as an analogy to adaptive random testing.Source: §6 · p. 18
7 Conclusion
AdaT2 extracts statements from discovery replies to guide boundary-test generation, including transformed tests from statement–instruction pairs. Across four τ3-bench domains, its suites outperform baselines on explicitly valid tests and seeded-fault detection, while leaving scope for broader two-sided coverage and fewer inconclusive judge verdicts.
7 Conclusion
- AdaT2 extracts statements from agent replies in discovery traces and uses them to guide boundary-test generation.The statements serve as the targets for test generation.Source: §7 · p. 19
- Across four τ3-bench domains, AdaT2’s suites contain a higher proportion of explicitly valid boundary tests than AgentEval and a direct baseline.The conclusion reports this cross-domain comparison without giving percentages here.Source: §7 · p. 19
- Transformed tests cover explicit boundaries that plain tests miss and account for most original-agent executions in which an expert confirms a fault.Source: §7 · p. 19
- As regression tests, AdaT2’s suites detect all seeded policy faults in airline and half in retail, outperforming both baselines.Source: §7 · p. 19
- Future work includes covering both sides of more explicit boundaries and reducing judge inconclusive verdicts, which currently lower test-suite accuracy.Source: §7 · p. 19