PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Agent Evaluation via Diversity-Guided User Simulation

Itay Nakash, George Kour, Ateret Anaby-Tavor

arXiv:2604.21480v1cs.AI

TL;DR

Evaluating stochastic, multi-turn customer-facing agents requires repeated conversation executions, making efficient exploration important. DIVERT snapshots intermediate states and branches with diverse user responses, discovering failures more efficiently while expanding task-level coverage.

  • Problem

    Evaluating stochastic, multi-turn agents requires repeated full-conversation executions to capture user diversity and agent consistency at high cost.

  • Method

    DIVERT snapshots complete agent-environment states at critical junctions and branches with intent-consistent, semantically diverse user responses.

  • Results

    Across three domains and two models, DIVERT consistently improves failure discovery per token and exposes failures in more tasks than standard rollouts.

  • Takeaways & Limitations

    Reusing shared prefixes and branching at salient decision points enables broader behavioral coverage without increasing overall evaluation cost.

  • Takeaways & Limitations

    Current branching is limited to user turns, while junction selection and diversity rely on LLM-based and cosine-similarity signals.

Abstract

from arXiv · show

Large language models (LLMs) are increasingly deployed as customer-facing agents, yet evaluating their reliability remains challenging due to stochastic, multi-turn interactions. Current evaluation protocols rely on linear Monte Carlo rollouts of complete agent-user conversations to estimate success. However, this approach is computationally inefficient, repeatedly regenerating identical early prefixes, and often fails to uncover deep failure modes that arise from rare user behaviors. We introduce DIVERT (Diversity-Induced Evaluation via Branching of Trajectories), an efficient, snapshot-based, coverage-guided user simulation framework for systematic exploration of agent-user interactions. DIVERT captures the full agent-environment state at critical decision points and resumes execution from these snapshots, enabling reuse of shared conversation prefixes and reducing redundant computation. From each junction, the framework branches using targeted, diversity-inducing user responses, allowing directed exploration of alternative interaction paths. By focusing evaluation on semantically diverse and underexplored trajectories, DIVERT improves both efficiency and coverage. Empirical results show that it discovers more failures per token compared to standard linear rollout protocols, while expanding the set of tasks on which failures are identified.

1 Introduction

DIVERT addresses the inefficiency and limited exploration of linear Monte Carlo evaluation for stochastic, multi-turn agents by reusing shared prefixes and branching from critical states with diverse user responses. This snapshot-based, coverage-directed framework targets unexplored continuations and deep failure modes.

  • Motivation: Multi-turn agent behavior is probabilistic because both agent decisions and user responses can vary across runs, even under identical initial conditions.Behavior also depends on long interaction histories, stochastic decisions, and compounding errors.
  • Motivation: Multiple conversation executions expose diverse user behaviors and test whether agents consistently succeed on the same task.Different user responses can produce qualitatively different paths, while intermittent success reveals inconsistency.
  • Limitations of Existing Evaluation: Linear Monte Carlo rollouts repeatedly regenerate nearly identical early prefixes from the initial state, incurring unnecessary token cost.Examples include routine logins and basic diagnostic questions.
  • Motivation: Agent trajectories are tree-structured: conversations share long prefixes and diverge at a small number of critical interaction points.Restarting from the root discards this structure and prevents systematic exploration after reaching fragile or promising states.
  • DIVERT: DIVERT snapshots the full agent–environment state at critical junctions and branches from those points using semantically distinct, intent-consistent user responses.The coverage-directed mechanism steers evaluation toward unexplored continuations and deep failure modes.

2 Related Work

Related work spans general and customer-facing agent benchmarks, LLM-based user simulation, and rollout-based evaluation. DIVERT addresses limitations in simulator behavior and evaluation structure by providing branching exploration that is compatible with different user strategies.

  • Agent Evaluation Benchmarks: General benchmarks assess agent reasoning, tool use, and web interaction across diverse tasks and environments.Examples include AgentBench, GAIA2, and WebArena.
  • Agent Evaluation Benchmarks: Customer-facing benchmarks model realistic airline, retail, and telecom service domains with tools, policies, and LLM-based user simulators.τ-bench and τ 2-bench target settings with explicit policy-adherence requirements.
  • User Simulation: LLM-based user simulators generate diverse interactions but can exhibit benevolence bias by being overly cooperative and unrepresentative of realistic user behavior.Earlier simulators relied on rigid agenda-based rules, while recent work addresses this limitation.
  • Evaluation Efficiency: DIVERT provides a branching evaluation structure that is orthogonal to user-strategy choice and can incorporate benign, adversarial, or red-teaming user policies.Its contribution is an evaluation structure rather than a specific cooperative or adversarial simulator.
  • Evaluation Efficiency: Existing evaluation benchmarks rely mainly on restart-from-root Monte Carlo rollouts, causing redundant early prefixes, poor coverage of deep failures, and computational and economic inefficiency.Tree-based methods such as MCTS are emerging elsewhere, but current evaluation frameworks lack a corresponding branching mechanism and rely on linear restart sampling.

3 Method

DIVERT replaces root-restarted rollouts with coverage-guided branching from critical mid-trajectory states. It restores complete execution snapshots, generates semantically varied user responses, and resumes interactions to explore alternative futures efficiently.

  • Junction selection: DIVERT identifies critical junction points where alternative user behavior may change downstream agent behavior, then resumes execution from saved intermediate states.The junction chooser analyzes the full serialized trajectory and selects the user turn to modify with a brief justification.
  • Diverse user branching: At each junction, DIVERT generates k = 3 candidate user responses conditioned on conversation context, task purpose, and user backstory.Generation preserves original task intent while inducing meaningful semantic variation relative to the original response.
  • State snapshots and replay: Snapshots taken before each user turn preserve conversation history, agent state, tool environment, simulator context, and the original random seed for exact replay.After selecting a junction and response, DIVERT reloads the state immediately preceding that user turn and resumes under identical conditions.
  • Efficient branching: Reusing cached prefixes avoids regenerating identical early turns, reduces token consumption, and enables multiple alternative futures to be explored from one trajectory prefix.Exact prefixes may also support KV-cache reuse under compatible serving systems.
  • Branching trade-offs: Increasing the branch-number parameter expands coverage and trajectory count while increasing token cost; junction selection and directed generation consume 0.2%– 0.08% of total evaluation cost.The reported overhead applies when assessing a SOTA frontier agent using GPT-OSS-120B as the evaluator.

4 Experimental Setup

DIVERT is evaluated against linear rollouts under matched agent, environment, decoding, and token-budget conditions across three τ-bench domains. The setup uses two LLMs and metrics for failure-discovery efficiency and task-level coverage, with proprietary-model budgets bounded due to reproduction cost.

  • Comparison Protocol: DIVERT is compared with standard linear rollouts under identical agent, environment, decoding, and token-budget conditions.Full generation and decoding parameters are reported in Appendix G.
  • Benchmarks: Evaluation covers Airline, Retail, and Telecom τ-bench domains, each containing fixed tasks defined by an initial user intent, available tools, and executable success predicate.These task specifications seed the multi-turn interaction between the user simulator and agent.
  • Models: The main models are GPT-OSS-120B and Gemini-2.5-Flash, with GPT-OSS-120B serving as the user simulator except in heterogeneous experiments.The simulator is selected for its cost–performance tradeoff, while heterogeneous experiments vary agent and simulator models.
  • Evaluation Metrics: The primary metrics are Errors per 100K Tokens for efficiency and task-level failure coverage for identifying previously unseen failures.Errors per 100K Tokens normalizes failed trajectories by total agent-generated tokens, while coverage captures expansion to new task-level failures.
  • Evaluation Constraints: Proprietary-model evaluation budgets are bounded because large-scale repeated τ-bench runs across all three domains are expensive to reproduce.This constraint applies to repeated evaluations across the benchmark domains.

5 Results

DIVERT improves evaluation efficiency and task-level failure coverage by reusing shared prefixes and directing branches toward diverse, underexplored interaction paths. Its diversity selection produces divergent candidates and downstream trajectories, while ablations assess the contribution of its components.

  • Efficiency: Across all domains and both agents, branch-based evaluation is more token-efficient than full rollouts, with even one branch (8+1) improving failure discovery per token.Shared-prefix reuse and selective mid-trajectory branching redirect computation toward higher-leverage paths instead of regenerating prefixes.
  • Efficiency: Efficiency gains grow monotonically with additional branches, and snapshot-based branching improves failure discovery efficiency under a fixed trajectory budget.The results characterize snapshot-based, coverage-guided simulation as a more efficient evaluation regime than restarting from the root.
  • Coverage: Increasing branches substantially improves task-level failure coverage across domains, exposing failures in more tasks than standard rollouts at a fixed trajectory count.This indicates broader exploration of agent-user interactions.
  • Coverage: Additional rollout iterations show diminishing coverage gains, whereas larger branch budgets unlock new failing tasks that repeated restarts do not address.Directed branching from original conversations therefore expands the set of failure modes found.
  • Diversity validation: Across 4,500 candidates, the most dissimilar response has lower similarity to the original utterance than the second and third candidates in every domain.Across 1,200 continuations, lower-similarity candidates also yield more divergent downstream conversation suffixes, validating diversity at both levels.
  • Ablation: Ablation evaluations incrementally add DIVERT components to standard linear rollouts, with the junction chooser starting conversations from critical points without directed user generation.This reduces evaluation cost while isolating the contribution of individual components.

6 Conclusions · A Example: Full Rollout vs. DIVERT Branching

DIVERT improves evaluation efficiency by reusing shared prefixes and branching at behaviorally salient decision points, enabling broader coverage without increasing overall cost. The paper illustrates this with a targeted insurance-proof alternative and identifies extensions to tool outputs, environment dynamics, and selection signals.

  • 6 Conclusions: Early dialogue turns often have little downstream influence, so repeatedly regenerating greetings, authentication, or static context wastes tokens.The conclusion motivates avoiding redundant computation on low-impact prefixes.
  • 6 Conclusions: DIVERT reuses shared rollout prefixes and reallocates computation to behaviorally salient decision points where agent actions diverge.This snapshot-based branching strategy targets pivotal mid-trajectory states rather than regenerating identical early turns.
  • 6 Conclusions: By resuming from pivotal mid-trajectory states, DIVERT achieves broader behavioral coverage without increasing overall cost.The conclusion presents coverage expansion and cost preservation as the central evaluation benefit.
  • 6 Conclusions: Future work will extend branching beyond user turns to tool outputs and environment dynamics for dynamic task variation and richer counterfactual evaluation.These extensions would broaden the sources of alternative interaction trajectories.
  • 6 Conclusions: Another planned direction is replacing the LLM-based junction chooser and cosine-similarity selection with alternative junction signals and diversity metrics.Examples include similarity- or perplexity-based junction selection and metrics beyond cosine similarity.
  • A Example: Full Rollout vs. DIVERT Branching: In the example, the conversation prefix remains identical until the selected junction where the agent lacks verifiable insurance proof.The junction chooser identifies this turn as the branching point.
  • A Example: Full Rollout vs. DIVERT Branching: DIVERT replaces the original user message with an insurance confirmation number, producing a divergent continuation from the shared prefix.The example contrasts a linear rollout with a directed branched alternative.

B Implementation Details … D.1 Extended Rollout and Branch Results

DIVERT implements snapshot-based branching by serializing complete agent–environment states, selecting high-impact user-turn pivots, and generating semantically divergent continuations. Across domains, branching improves failure coverage and discovery efficiency under fixed token or rollout budgets.

  • B.1 Snapshot Contents and Serialization: Snapshots serialize dialogue, agent, user-simulator, environment, and task state, preserving tool effects and intermediate context for exact counterfactual continuation.The serialized state includes the full trajectory, internal states, environment mutations, and task constraints.
  • B.1 Snapshot Contents and Serialization: Snapshots are saved before user-response generation and restored by loading state, synchronizing tools and memory, and optionally injecting a new user response.This avoids recomputing earlier turns while enabling branching from identical dialogue states.
  • B.2 Junction Selection: LLM-based junction selection identifies the user turn expected to cause maximal downstream behavioral change while preserving the original task intent.The method serializes and analyzes the full trajectory rather than relying only on local heuristics.
  • B.3 Divergent User Generation: At each junction, DIVERT samples multiple user responses at temperature 0.7 and selects the candidate with the lowest embedding-based similarity to the original response.Experiments use K = 3 candidates, with all-MiniLM-L6-v2 embeddings for lightweight similarity scoring.
  • C Failure Discovery Dynamics: Branch-based configurations achieve higher failure coverage earlier for the same token budget across Airline, Retail, and Telecom.Larger branch budgets produce steeper early gains and delayed saturation, exposing additional failure modes rather than repeatedly revisiting known ones.
  • D.1 Extended Rollout and Branch Results: Increasing the number of branches consistently improves failure discovery efficiency (Err/100K) and task-level coverage (Fail) across domains and rollout budgets.The reported results show no observed degradation relative to linear rollouts.
  • D.1 Extended Rollout and Branch Results: For a fixed number of rollouts, reallocating budget toward mid-trajectory branches yields near-monotonic gains in task-level failure coverage.This supports branching as a more effective allocation of evaluation effort than repeatedly extending linear rollouts.

D.2 Heterogeneous Agent–User Experiments · D.3 Diversity Selection Validation · E Cost Breakdown and Token Accounting

DIVERT retains its efficiency and coverage advantages in heterogeneous agent–user configurations, while diversity selection produces increasingly divergent downstream trajectories. Token accounting shows reduced agent and evaluation-side consumption through shared-prefix reuse and avoided repeated simulation.

  • D.2 Heterogeneous Agent–User Experiments: The heterogeneous experiments evaluate both model-direction configurations, including Gemini-2.5-Flash as agent and GPT-OSS-120B as user simulator, and the reverse.Appendix tables report results across domains and the airline domain for these configurations.
  • D.2 Heterogeneous Agent–User Experiments: DIVERT consistently improves failure-discovery efficiency and task-level coverage when GPT-OSS-120B and Gemini-2.5-Flash serve as agent and user simulator in either direction.These results suggest the benefits extend to cross-model agent–simulator interactions.
  • D.3 Diversity Selection Validation: Lower similarity denotes greater divergence from the original user utterance or trajectory in both diversity-selection analyses.The analyses report full per-domain results for candidate-level and trajectory-level selection.
  • D.3 Diversity Selection Validation: The most dissimilar generated candidate is consistently separated from the second and third candidates across all domains.Candidate-level diversity compares each response with the original user utterance at the selected junction.
  • D.3 Diversity Selection Validation: Candidates more dissimilar to the original utterance also produce more divergent interaction trajectories when continued from the same junction.The candidate-level ordering is preserved in downstream conversation suffixes.
  • E Cost Breakdown and Token Accounting: 5,763.52 total tokens are consumed by an average standard full-rollout trajectory on Airline, including 4,068.86 agent tokens (70.6%) and 1,694.66 user-simulator tokens (29.4%).The per-trajectory profile separates agent-generated tokens from user-simulator-generated tokens.
  • E Cost Breakdown and Token Accounting: 3,272.96 average agent tokens per trajectory under DIVERT represent a reduction of 795.90 tokens (19.6%) compared to full rollouts.Evaluation-side user and framework tokens also decrease by 563.56 per trajectory through shared-prefix reuse and avoided repeated simulation steps.
  • E Cost Breakdown and Token Accounting: 795.90 agent tokens and 563.56 evaluation tokens are reduced per trajectory before accounting for DIVERT overhead.This summarizes the total average reductions reported for agent and evaluation-side consumption.

E.1 Shared Prefix Analysis and KV-Cache Implications · E.2 DIVERT Overhead

DIVERT increases exact shared-prefix overlap, creating structural potential for KV-cache reuse without directly measuring serving-system speedups or memory behavior. Its branching overhead is quantified at 429.52 tokens per branch, while evaluation-side savings and overall usage reductions remain substantial after accounting for that cost.

  • E.1 Shared Prefix Analysis and KV-Cache Implications: System-level KV-cache reuse, latency, and memory behavior are not directly benchmarked because they depend on serving stack, batching, cache management, and hardware.The analysis therefore reports exact shared-prefix overlap rather than measured cache speedups.
  • E.1 Shared Prefix Analysis and KV-Cache Implications: DIVERT branches resume from identical cached prefixes before diverging, whereas independent regular rollouts do not systematically reuse exact prefixes.Exact shared-prefix overlap is used as a structural proxy for potential KV-cache reuse.
  • E.1 Shared Prefix Analysis and KV-Cache Implications: 34.80% on Airline, 42.50% on Retail, and 58.35% on Telecom are DIVERT’s exact shared-prefix fractions.Standard independent rollouts share roughly 0.5%–0.6% of exact prefix tokens.
  • E.2 DIVERT Overhead: Each DIVERT branch adds framework overhead from junction selection and divergent user generation.The overhead arises from the additional operations required to select junctions and generate alternative user responses.
  • E.2 DIVERT Overhead: 103.48 tokens are spent on junction selection, while candidate generation costs 108.68 tokens per candidate.DIVERT generates k = 3 candidates per junction, yielding a total candidate-generation cost of 326.04 tokens.
  • E.2 DIVERT Overhead: 429.52 tokens is the total average branching overhead per branch.This equals 103.48 tokens for junction selection plus 326.04 tokens for generating three candidates.
  • E.2 DIVERT Overhead: Branching retains a substantial net reduction in total evaluation-token usage after subtracting its 429.52-token overhead.The reduction in agent tokens remains the dominant and economically most significant cost component.
  • E.2 DIVERT Overhead: 563.56 tokens is the evaluation-side user/framework token reduction enabled by branching beyond agent-token savings.The paper describes this reduction as contributing to a substantial net decrease in total evaluation-token usage after overhead.

E.3 Relative Cost of DIVERT Framework Overhead

DIVERT’s framework overhead contributes well below 1% of total monetary evaluation cost for frontier agents, with agent token generation dominating expense. Consequently, evaluation should primarily optimize agent-token usage, while reporting full framework overhead for transparency.

  • Relative overhead: 0.20%: At a representative frontier price of $10 per 1M output tokens, DIVERT overhead is approximately 0.20% of total evaluation cost.The calculation uses GPT-OSS-120B at $0.19 per 1M output tokens.
  • Relative overhead: DIVERT framework overhead contributes well below 1% of total monetary evaluation cost for SOTA frontier-agent evaluation.Hosting GPT-OSS-120B locally as an open-weight model can further reduce evaluation-side cost.
  • Cost drivers: Agent token generation is the dominant cost driver, while junction selection and divergent user generation contribute only a marginal fraction of total expense.The framework overhead includes junction selection, user simulation, and replay bookkeeping.
  • Concrete cost estimate: The branch-augmented τ-bench setting uses 4,068.86 agent generation tokens per average trajectory and 3,272.96 agent tokens per branch.The setup contains 278 tasks and uses 10 rollouts plus 12 branches per task.
  • Optimization target: The economically meaningful optimization target is the number of agent tokens generated because reductions in redundant prefixes or unnecessary full rollouts yield immediate monetary savings.Errors per 100K Agent Tokens directly reflects the real-world cost of assessing a production-grade agent.

F User Intent Preservation Analysis

DIVERT’s intent-preservation analysis uses the Airline domain as a strict proxy because it uniquely provides explicit task-purpose fields. Under an automatic judge, branched messages preserve task alignment at least as well as original simulator messages while enabling broader behavioral exploration.

  • Airline is used as the strict proxy domain because it is the only τ-bench domain with explicit per-task purpose fields and contains the most complex, constraint-heavy tasks.
  • Original and branched user messages are independently judged against each task purpose using GPT-OSS-120B at temperature 0, focusing on core intent rather than wording, quality, or strategy.
  • The post-hoc check covers all Airline branching points, labels intent preservation separately, and includes manual inspection of sampled judge decisions without affecting branching or evaluation cost.
  • 207 cases (28.12%) of original simulator messages miss task intent, compared with 186 cases (25.27%) for branched messages across 700 Airline instances.The results indicate that intent-directed branching does not degrade alignment and slightly improves it by correcting some simulator-message drift.
  • The findings support that DIVERT maintains task-purpose alignment under the automatic judge while enabling broader behavioral exploration.Sampled human inspection yielded consistent judgments.

G Reproducibility Details … G.3 Execution Limits

The reproducibility setup fixes randomness, model and decoding choices, and execution limits across evaluations. Trajectories stop on success or when configured step or error thresholds are reached.

  • G.1 Randomness and Seeds: Experiments use fixed random seed 42 for agent rollouts, user generation, and branching logic, ensuring determinism across repeated runs.The same seed is applied to all three stochastic components.
  • G.2 Models and Decoding Configuration: Unless otherwise stated, the acting agent and user simulator use the same model backbone with configurations matching the original τ-bench setup.This shared-backbone setup applies to the reported experiments.
  • G.2 Models and Decoding Configuration: Each trajectory allows a maximum of 100 simulation steps.This is the stated maximum simulation length per trajectory.
  • G.2 Models and Decoding Configuration: Each trajectory permits a maximum of 10 errors.The error threshold is a configured per-trajectory limit.
  • G.2 Models and Decoding Configuration: Each LLM call allows up to 3 retries.The retry limit applies to individual inference calls.
  • G.2 Models and Decoding Configuration: No failed inference calls or missing runs were observed due to LLM errors.The reported executions completed without those LLM-error-related omissions.
  • G.3 Execution Limits: Trajectory execution terminates when the task is successfully completed.Successful completion is one explicit termination condition.
  • G.3 Execution Limits: Execution also terminates upon reaching 100 turns or exceeding 10 errors.These stopping conditions correspond to the maximum step and error thresholds.
Loading 2604.21480v1…