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

arXiv: https://arxiv.org/abs/2607.06873 · HTML: https://mlsanity.com/paper/2607.06873/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 36 of its 61 references that are in the map.
- First posted on arXiv 8 Jul 2026.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 30 of 36)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [WebArena: A Realistic Web Environment for Building Autonomous Agents](https://mlsanity.com/paper/2307.13854/) (2023)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [Not what you've signed up for: Compromising Real-World LLM-Integrated Applications with Indirect Prompt Injection](https://mlsanity.com/paper/2302.12173/) (2023)
- [τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains](https://mlsanity.com/paper/2406.12045/) (2024)
- [GAIA: a benchmark for General AI Assistants](https://mlsanity.com/paper/2311.12983/) (2023)
- [Large Language Models Cannot Self-Correct Reasoning Yet](https://mlsanity.com/paper/2310.01798/) (2023)
- [Ignore Previous Prompt: Attack Techniques For Language Models](https://mlsanity.com/paper/2211.09527/) (2022)
- [CRITIC: Large Language Models Can Self-Correct with Tool-Interactive Critiquing](https://mlsanity.com/paper/2305.11738/) (2023)
- [τ2-Bench: Evaluating Conversational Agents in a Dual-Control Environment](https://mlsanity.com/paper/2506.07982/) (2025)
- [AppWorld: A Controllable World of Apps and People for Benchmarking Interactive Coding Agents](https://mlsanity.com/paper/2407.18901/) (2024)
- [An Empirical Evaluation of Using Large Language Models for Automated Unit Test Generation](https://mlsanity.com/paper/2302.06527/) (2023)
- [On the Self-Verification Limitations of Large Language Models on Reasoning and Planning Tasks](https://mlsanity.com/paper/2402.08115/) (2024)
- [Preventing Repeated Real World AI Failures by Cataloging Incidents: The AI Incident Database](https://mlsanity.com/paper/2011.08512/) (2020)
- [ConvLab-2: An Open-Source Toolkit for Building, Evaluating, and Diagnosing Dialogue Systems](https://mlsanity.com/paper/2002.04793/) (2020)
- [τ-Knowledge: Evaluating Conversational Agents over Unstructured Knowledge](https://mlsanity.com/paper/2603.04370/) (2026)
- [CoverUp: Effective High Coverage Test Generation for Python](https://mlsanity.com/paper/2403.16218/) (2024)
- [TestART: Improving LLM-based Unit Testing via Co-evolution of Automated Generation and Repair Iteration](https://mlsanity.com/paper/2408.03095/) (2024)
- [Unsupervised Dialog Structure Learning](https://mlsanity.com/paper/1904.03736/) (2019)
- [Are Large Language Models Reliable AI Scientists? Assessing Reverse-Engineering of Black-Box Systems](https://mlsanity.com/paper/2505.17968/) (2025)
- [Morest: Model-based RESTful API Testing with Execution Feedback](https://mlsanity.com/paper/2204.12148/) (2022)
- [Testing RESTful APIs: A Survey](https://mlsanity.com/paper/2212.14604/) (2022)
- [Event Abstraction for Process Mining using Supervised Learning Techniques](https://mlsanity.com/paper/1606.07283/) (2016)
- [Dialog2Flow: Pre-training Soft-Contrastive Action-Driven Sentence Embeddings for Automatic Dialog Flow Extraction](https://mlsanity.com/paper/2410.18481/) (2024)
- [RealHarm: A Collection of Real-World Language Model Application Failures](https://mlsanity.com/paper/2504.10277/) (2025)
- [Graph2Eval: Automatic Multimodal Task Generation for Agents via Knowledge Graphs](https://mlsanity.com/paper/2510.00507/) (2025)

## Abstract (arXiv)

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 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.