Efficient Agent Evaluation via Diversity-Guided User Simulation

Itay Nakash, George Kour, Ateret Anaby-Tavor · 2026

Read Efficient Agent Evaluation via Diversity-Guided User Simulation by Itay Nakash, George Kour, Ateret Anaby-Tavor (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-21480.txt.

Introduction

Itay Nakash, George Kour, and Ateret Anaby-Tavor make agent testing cheaper and more thorough with DIVERT, a snapshot-based, coverage-guided user simulation system. Standard linear rollouts redo identical early prefixes and miss deep failures from rare user behaviors. DIVERT captures full agent-environment state at key decision points and resumes from snapshots, reusing shared prefixes. From each junction it branches with targeted, diversity-inducing user responses, exploring other paths. The method finds more failures per token than linear rollouts and widens the set of tasks where failures surface.

Catalog record

CREATORItay Nakash, George Kour, Ateret Anaby-Tavor
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62977
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.21480

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Efficient Agent Evaluation via Diversity-Guided User Simulation Itay Nakash, George Kour, Ateret Anaby-Tavor Abstract 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, requiring re-processing identical conversation prefixes, and often fails to expose deep failure modes hidden behind rare user behaviors. In this work, we introduce DIVERT ( D iversity- I nduced EV aluation via b r anching of T rajectories), an efficient, snapshot-based, coverage-guided user simulation framework for systematic exploration of diverse agent–user interactions. DIVERT snapshots the full agent–environment state at critical junctions and resumes execution from these points. By reusing shared conversation prefixes, it avoids regenerating identical early turns, reducing token cost. From each junction, it branches with targeted, diversity-inducing user responses, enabling directed exploration of alternative user responses. As a result, the evaluation is steered toward unexplored semantic paths and rare interaction states efficiently. Empirical experiments show that our framework both improves failure discovery efficiency compared to standard linear rollout protocols. Figure 1: Standard Rollout Evaluation vs. DIVERT. Left: Conventional evaluation repeatedly rolls out full conversations from the beginning, often producing low-impact interactions and failing to explore deeper failure modes. Right: Our snapshot-based evaluation framework stores intermediate conversation states and branches at critical junctions with directed, diverse user responses, enabling more efficient exploration and improved discovery of failures (a full example is provided in Appendix A ). 1 Introduction Large language models (LLMs) are increasingly deployed as customer-facing agents that interact with users over multiple turns while invoking external tools and APIs 12 . Evaluating such agents is fundamentally different from single-turn LLM evaluation: behavior emerges from long interaction histories, stochastic decisions, compounding errors, and high evaluation cost 23 ; 2 . As a result, agent behavior is probabilistic: both the agent’s decisions and the user’s responses may vary across runs, even under identical initial conditions 13 . Consequently, meaningful evaluation requires multiple executions of the conversation between the agent under test and a user simulator. Repeated runs serve two distinct purposes. First, they expose user-side diversity : different user behaviors or responses can lead the agent down qualitatively different conversation paths, revealing how robustly the agent handles variation in interaction. Second, they test agent-side consistency : an agent that succeeds only intermittently on the same task is fundamentally unreliable in deployment. To capture these effects, recent benchmarks such as \tau -bench 21 adopt interactive evaluation protocols that execute full conversations and report aggregate success metrics over multiple trials. However, the dominant evaluation paradigm remains linear Monte Carlo rollout from the initial state, i.e., repeatedly sampling independent stochastic trajectories from identical initial conditions to estimate success 11 ; 25 . This approach is not always optimal in practice. First, repeated rollouts are wasteful: they regenerate nearly identical early prefixes, such as routine logins or basic diagnostic questions, incurring unnecessary token cost 8 . Second, because these prefixes are only semantically similar rather than token-identical, they limit KV-cache reuse 10 . Appendix E.1 quantifies exact shared-prefix overlap as a proxy for this structural opportunity. Third, it provides limited coverage: standard user simulators favor high-probability, cooperative behaviors, making it unlikely to expose failures that arise only after rare user responses ( 15 ) . As agents scale to longer horizons and more realistic service domains, these inefficiencies become a bottleneck. A key observation motivates our work: while current evaluations are linear, agent trajectories are inherently tree-structured . Many conversations share long prefixes and diverge only at a small number of critical interaction points. Restarting evaluation from the root discards this structure, preventing systematic exploration once a fragile or promising state is reached. We propose a snapshot-based, coverage-directed user simulation framework that explicitly exploits this tree structure. Instead of repeatedly restarting from the initial state, we snapshot the full agent–environment state at critical junctions and branch evaluation from these points. A targeted divergence mechanism generates semantically distinct but intent-consistent user responses, steering the agent toward unexplored continuations and deep failure modes. Our results demonstrate that coverage-guided, snapshot-based evaluation is a more cost-effective and informative alternative to conventional linear rollouts for evaluating customer-facing LLM agents. 2 Related Work Agent Evaluation Benchmarks. General agent benchmarks such as AgentBench 11 , GAIA2 14 , and WebArena 25 assess agents’ reasoning, tool use, and web interaction across diverse tasks and environments. For customer-facing settings with explicit policy-adherence requirements, \tau -bench 21 and \tau^{2} -bench 3 model realistic service domains (e.g., airline, retail, telecom), incorporating tools, policies, and LLM-based user simulators. User Simulation. The robustness of agent evaluation relies heavily on the User Simulator. While early simulators relied on rigid agenda-based rules 17 , recent advancements utilize LLMs to generate diverse interactions. A key limitation of standard LLM-based simulators is "benevolence bias", i.e., their tendency to be overly cooperative and thus unrepresentative of realistic user behavior. Recent work 9 ; 18 ; 15 addresses this by introducing "Non-Collaborative User Simulators" that model adversarial behaviors such as malicious intent, emotional manipulation, and insistence. Complementary work studies adversarial perturbations at the agent or tool level, such as prompt injection 4 ; 16 , but does not explicitly target systematic, coverage-oriented variation during evaluation. DIVERT is orthogonal to this choice of user strategy: rather than proposing a specific cooperative or adversarial simulator, it provides a branching evaluation structure that can incorporate benign, adversarial, or red-teaming user policies. Evaluation Efficiency. A current limitation of these benchmarks is that they rely almost exclusively on restart-from-root Monte Carlo rollouts to estimate capability and reliability 3 ; 7 . This leads to substantial redundancy in early conversation prefixes, poor coverage of deep interaction failures, and significant computational and economic inefficiency. Recent “Cost-of-Pass” analyses 5 ; 14 ; 20 show that achieving reliable statistics often requires prohibitive token budgets due to repeated regeneration of identical prefixes. While tree-based methods such as Monte Carlo Tree Search (MCTS) are emerging in agent training, planning, and reasoning 24 ; 22 ; 19 , current evaluation frameworks lack a corresponding branching mechanism and rely on linear restart sampling. 3 Method Algorithm 1 DIVERT Pipeline 1: Task set \mathcal{T} , agent model M_{\text{agent}} , user model M_{\text{user}} , #rollouts per task R , #branches per task B , #candidate generations K 2: \mathcal{D}\mathrel{{\color[rgb]{0.5,0,0.5}=}}\emptyset 3: for T\mathrel{{\color[rgb]{0.5,0,0.5}\in}}\mathcal{T} : 4: \mathcal{D}\mathrel{{\color[rgb]{0.5,0,0.5}\cup=}}{\color[rgb]{0,0.3984,0.8008}\text{Rollout}}(T,M_{\text{user}},M_{\text{agent}},R) 5: for s\mathrel{{\color[rgb]{0.5,0,0.5}=}}1\dots B : 6: \tau\sim\mathcal{D} 7: j\mathrel{{\color[rgb]{0.5,0,0.5}=}}{\color[rgb]{0,0.3984,0.8008}\text{JunctionChooser}}(\tau) 8: \triangleright Directed generation of alternative user responses 9: for k\mathrel{{\color[rgb]{0.5,0,0.5}=}}1\dots K : 10: u_{k}\mathrel{{\color[rgb]{0.5,0,0.5}=}}{\color[rgb]{0,0.3984,0.8008}\text{DirectedUserGen}}(\tau,j) 11: d_{k}\mathrel{{\color[rgb]{0.5,0,0.5}=}}1-{\color[rgb]{0,0.3984,0.8008}\text{Sim}}(u_{k},u_{j}) 12: k^{\star}\mathrel{{\color[rgb]{0.5,0,0.5}=}}{\color[rgb]{0,0.3984,0.8008}\text{argmax}}_{k}\;d_{k} 13: u^{\star}\mathrel{{\color[rgb]{0.5,0,0.5}=}}u_{k^{\star}} 14: \triangleright Resume simulation from junction j 15: \tau^{\prime}\mathrel{{\color[rgb]{0.5,0,0.5}=}}{\color[rgb]{0,0.3984,0.8008}\text{Resume}}(\tau,j,u^{\star}) 16: \mathcal{D}\mathrel{{\color[rgb]{0.5,0,0.5}\cup=}}\{\tau^{\prime}\} We present an efficient, coverage-guided evaluation pipeline for interactive agents. Our method replaces repeated rollouts from the root with branching from critical mid-trajectory states, enabling efficient and diverse exploration of agent behavior. 3.1 Overview of the DIVERT Pipeline DIVERT evaluates interactive agents by resuming execution from intermediate states rather than repeatedly restarting from the initial state. We select an existing trajectory, then we identify critical "junction points" - interaction states where alternative behaviors are likely to emerge. At each junction, we use a pre-saved snapshot of the complete execution state, including the agent context,

Read the complete text