Mining Workflow Graphs for Black-Box Boundary Testing of Conversational LLM Agents

• URL: http://arxiv.org/abs/2607.06873v1
• Date: Wed, 08 Jul 2026 00:11:41 GMT
• Title: Mining Workflow Graphs for Black-Box Boundary Testing of Conversational LLM Agents
• Abstract summary: We present AgentEval, a black-box testing framework that discovers and stresses stateful boundaries.<n>Instead of prompting blindly, AgentEval uses this graph's structure to enumerate specific guards and prerequisites as test targets.<n>We benchmark AgentEval against a privileged, white-box auditor with access to the agent's underlying source code, which AgentEval never sees.
• Score: 2.9512821350868754
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Conversational LLM agents can cause real-world harm when their internal workflows fail, such as completing a transaction without confirmation. Testing these state-dependent failures is difficult because critical boundaries, such as identity checks and confirmation gates, are hidden behind multi-turn conversational prerequisites, rendering them inaccessible to standard tests. We present AgentEval, a black-box testing framework that discovers and stresses these stateful boundaries. AgentEval interacts with an agent to mine a \emph{conversational workflow graph}, a model of its behavior. Instead of prompting blindly, AgentEval uses this graph's structure to enumerate specific guards and prerequisites as test targets, replaying the conversational path to a boundary before applying a perturbation. AgentEval then executes each test, determining whether it passes or fails using only the conversation turns. We benchmark AgentEval against a privileged, white-box auditor with access to the agent's underlying source code, which AgentEval never sees. On four $τ^3$-bench agents, AgentEval successfully generates tests covering $23$--$38$ distinct boundaries per agent; ablation studies attribute the gain to the graph's structure: $23$ distinct boundaries versus $12$ with a prompt-only baseline, at lower duplicate and false-alarm rates.

Related papers

• Codebook Agent: Amortized Topology Design for LLM Multi-Agent Systems [67.04448659688579]
  We develop a query-independent 16-entry codebook that ranks the top decoded candidates in a single batched forward pass.<n>With no iterative search and no message passing at test time, Codebook Agent is the most accurate method on all six benchmarks.
  arXiv  Detail & Related papers  (2026-09-02T08:10:22Z)
• Facts Without Rules: Boundary Metadata Collapse in Multi-Agent LLM Handoffs [13.92589238677081]
  We show that summaries preferentially preserve operational facts while weakening the boundary metadata that governs how those facts may be used.<n> Boundary-marker and operational-fact survival are nearly uncorrelated at the handoff level on both GPT-5-mini and DeepSeek-R1-32B.
  arXiv  Detail & Related papers  (2026-08-29T03:38:35Z)
• An Interactive Agent for Requirement-Driven Candidate Sourcing [75.63902836826038]
  We present sys, the first requirements-driven candidate-sourcing agent.<n>It elicits, validates, retrieves, and verifies a vague people-request into a justified slate.<n>It dominates breadth ($100%$ coverage at $2.5times$ the yield) and is emphnear-orthogonal to the field.
  arXiv  Detail & Related papers  (2026-08-24T17:04:16Z)
• Do Context Files Help Coding Agents? A Two-Agent Ablation Study on Real Repositories [0.0]
  Persistent context files (AGENTS.md, CLAUDE.md) are standard practice for guiding AI coding agents, yet evidence for their effectiveness is contradictory.<n>We present a controlled ablation of context-injection strategy across two frontier agents (Claude Code and Codex)
  arXiv  Detail & Related papers  (2026-07-28T11:07:53Z)
• TensorBench: Benchmarking Coding Agents on a Compiler-Based Tensor Framework [0.9012337166501982]
  CohenBench is a benchmark for tasks on an open-source compiler-based framework.<n>It grades each run by applying the agent's patch and running the framework's test suite.<n>We evaluate seven coding agents spanning three frontier model families and one open-weight model.
  arXiv  Detail & Related papers  (2026-06-04T01:42:40Z)
• HLL: Can Agents Cross Humanity's Last Line of Verification? [27.923163104768758]
  We introduce textbfHumanity's Last Line of Verification (HLL) to evaluate whether agents can cross this boundary through grounded, human-like interaction.<n>HLL covers diverse CAPTCHA interactions and exposes agents to controlled realism stressors.<n>Results show that current agents remain brittle at this human-substitution boundary.
  arXiv  Detail & Related papers  (2026-06-01T16:20:45Z)
• LACUNA: Safe Agents as Recursive Program Holes [3.2613419151327343]
  LLM agents increasingly act by writing code, yet a split persists between the runtime that drives the agent and the code the model writes.<n>We present LACUNA, a programming model for agents that closes this split while preserving safety.<n>Our primitive expresses ReAct loops, sub-agents, skills, parallel decomposition, and multi-model planning as ordinary control flow.
  arXiv  Detail & Related papers  (2026-05-27T15:27:25Z)
• DoVer: Intervention-Driven Auto Debugging for LLM Multi-Agent Systems [48.971606069204825]
  DoVer is an intervention-driven debug framework for large language model (LLM)-based multi-agent systems.<n>It augments hypothesis generation with active verification through targeted interventions.<n>DoVer flips 18-28% of failed trials into successes, achieves up to 16% milestone progress, and validates or refutes 30-60% of failure hypotheses.
  arXiv  Detail & Related papers  (2025-12-07T09:23:48Z)
• Holistic Agent Leaderboard: The Missing Infrastructure for AI Agent Evaluation [87.47155146067962]
  We provide a standardized evaluation harness that orchestrates parallel evaluations across hundreds of tasks.<n>We conduct three-dimensional analysis spanning models, scaffolds, and benchmarks.<n>Our analysis reveals surprising insights, such as higher reasoning effort reducing accuracy in the majority of runs.
  arXiv  Detail & Related papers  (2025-10-13T22:22:28Z)
• Agent-Testing Agent: A Meta-Agent for Automated Testing and Evaluation of Conversational AI Agents [2.3429263075112288]
  We present the Agent-Testing Agent (ATA), a meta-agent that combines static code analysis, designer interrogation, literature mining, and persona-driven adversarial test generation.<n>Each dialogue is scored with an LLM-as-a-Judge (LAAJ) rubric and used to steer subsequent tests toward the agent's weakest capabilities.
  arXiv  Detail & Related papers  (2025-08-24T15:02:13Z)
• Runaway is Ashamed, But Helpful: On the Early-Exit Behavior of Large Language Model-based Agents in Embodied Environments [54.67512489842682]
  Large language models (LLMs) have demonstrated strong planning and decision-making capabilities in complex embodied environments.<n>We take a first step toward exploring the early-exit behavior for LLM-based agents.
  arXiv  Detail & Related papers  (2025-05-23T08:23:36Z)
• Preventing Rogue Agents Improves Multi-Agent Collaboration [21.955058255432974]
  We propose to monitor agents during action prediction and intervene when a future error is likely to occur.<n>Experiments on WhoDunitEnv, code generation tasks and the GovSim environment for resource sustainability show that our approach leads to substantial performance gains.
  arXiv  Detail & Related papers  (2025-02-09T18:35:08Z)
• On the Resilience of LLM-Based Multi-Agent Collaboration with Faulty Agents [58.79302663733703]
  Large language model-based multi-agent systems have shown great abilities across various tasks due to the collaboration of expert agents.<n>The impact of clumsy or even malicious agents--those who frequently make errors in their tasks--on the overall performance of the system remains underexplored.<n>This paper investigates what is the resilience of various system structures under faulty agents on different downstream tasks.
  arXiv  Detail & Related papers  (2024-08-02T03:25:20Z)
• A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits [77.09836892653176]
  We study federated contextual linear bandits, where $M$ agents cooperate with each other to solve a global contextual linear bandit problem with the help of a central server. We consider the asynchronous setting, where all agents work independently and the communication between one agent and the server will not trigger other agents' communication. We prove that the regret of textttFedLinUCB is bounded by $tildeO(dsqrtsum_m=1M T_m)$ and the communication complexity is $tildeO(dM
  arXiv  Detail & Related papers  (2022-07-07T06:16:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.