Source-linked AI summary
EDGE: Engine for Deterministic Graph Evaluation through Conversation Simulation from Graph Structured DSL Configuration
Ram Kulathumani, Regunathan Radhakrishnan, Anupam Tripathi, Xiangbo Mao, Roshanak Omrani, Keshav Somani, Shwet Kamal Mishra, Shayna Lurya
TL;DR
Agentic systems need systematic evaluation of behavioral consistency as their multi-agent workflows grow more complex. EDGE uses a graph DSL as ground truth, exhaustively enumerates and replays conversational paths, and finds that structured, constrained transitions yield more deterministic behavior while response consistency can remain limited.
Problem
Growing multi-agent orchestration complexity creates a need for systematic evaluation of determinism, reproducibility, and behavioral consistency.
Method
EDGE uses a DSL-defined agent graph to enumerate conversational paths, replay them, and compare outputs and state transitions with the intended specification.
Results
Structured transitions improve determinism, while high trajectory consistency does not necessarily ensure consistent responses.
Takeaways & Limitations
Constrained graph topology provides a more deliberate basis for reproducible agent execution and determinism evaluation.
Abstract
from arXiv · showhide
As agentic systems evolve into complex multi agent orchestration workflows, there is a growing and critical need for systematic frameworks that measures an agent's behavioral consistency and determinism. In this paper, we introduce a formal evaluation methodology that is grounded in AgentGraph, a planner powered by a domain specific language that represents agent reasoning through a dynamically adjustable directed graph. We leverage this structural formalism and utilize graph traversal algorithms that exhaustively enumerate conversational paths, forming a comprehensive evaluation set that captures the agent's complete behavioral space. We then systematically replay these reproducible trajectories to compare observed outputs and state transitions against the intended DSL specification. To quantify reliability, we define novel metrics that measure response and trajectory determinism, structural adherence and semantic consistency across both exact replays and their linguistic variants. Our system's results demonstrate that agents configured using frameworks like AgentGraph and LangGraph with explicitly structured node transitions show superior determinism over agents that are not configured with controlled transitions.
1. Introduction
EDGE introduces a graph-based methodology for evaluating determinism, reproducibility, and behavioral consistency in multi-agent systems. It exhaustively enumerates conversational paths and compares replayed behavior with the intended graph specification.
- Depth-first traversal of AgentGraph enumerates conversational paths to form a comprehensive evaluation dataset.
- The framework replays reproducible paths and compares observed outputs and state transitions with the DSL specification.
- EDGE formalizes determinism evaluation for agentic systems configured with graph-based DSLs.
- EDGE defines metrics for lexical, structural, and trajectory consistency across exact replays and varied user inputs.
- Carefully designed node transitions produced better determinism than configurations without deliberate transition design.
2. Related Work
EDGE addresses limitations of reactive and stochastic agent evaluation by using exhaustive graph traversal and the graph DSL as a verification schema. This extends structured orchestration from execution toward formal behavioral verification.
- Existing trace-analysis systems evaluate paths triggered by production traffic or fixed datasets, leaving much of an agent’s logic space unprobed.
- Closed-loop challenger-agent simulations provide dynamic testing but may miss branches that the simulator does not trigger.
- EDGE replaces stochastic play-acting with exhaustive depth-first traversal of the configured graph.
- Unlike prior graph-based orchestration work focused primarily on execution, EDGE uses the Graph DSL as ground truth for structural adherence.
3. Proposed EDGE Framework
The EDGE framework evaluates DSL-configured agents through conversation simulation, behavior capture, and determinism metrics. It traverses intended graph paths, replays exact and variant tasks, and analyzes node, edge, response, and action consistency.
- EDGE represents an agent as a DSL-defined directed acyclic graph whose nodes are subagents managing memory, tools, and state transitions.
- The framework comprises conversation simulation, agent-behavior capture, and determinism-metric computation.
- Conversation Simulation: Conversation variants modify user persona, user-model temperature, and intent wording while preserving the underlying task.
- Conversation Simulation: Depth-first search maps DSL paths to multi-turn conversations covering different intents and their variations.
- Behavior Capture: Captured behavior includes user and assistant turns, internal states, and invoked actions with parameters.
- Determinism Metrics: Exact replays measure response, node-trajectory, and action-trajectory consistency, while variant replays compare similar tasks with different action inputs.
- Graph Traversal Metrics: Conversation Convergence Rate measures intended-path completion without backtracking, whereas Path Completion Rate measures completion of all state transitions.
- Graph Traversal Metrics: Node and edge utility quantify visitation and transition frequency, while transition and failure metrics expose execution patterns and missing coverage.
4. Other Use-Cases
EDGE’s metrics can be applied to production conversations and used to inspect how agents traverse their graphs. Utility measures also support next-turn intent recommendations based on observed states.
- Production conversations can be replayed using their original user turns to measure agent reliability after deployment.
- The same determinism metrics used in simulation can assess response and trajectory reliability in production.
- Node and edge utility reveal likely transitions from a current state and can support recommendations for what users should say next.
5. Experimental Setup
The evaluation covers three graph-based agents, using sampled or exhaustive conversational paths and repeated replays to assess behavior across tasks and transitions.
- Agents: The framework evaluates a LangGraph Honda Dealer agent, a complex AgentGraph recruitment agent, and a baseline recruitment agent with all possible transitions enabled.The Honda and both recruitment agents contain four, six, and six nodes respectively.
- Honda Dealer Agent: The Honda Dealer agent handles test-drive scheduling, warranty lookups, and general car-feature questions using the Honda Car Manual for ZDX.It is a simple four-node agent.
- Honda Dealer Agent: Thirty Honda conversation scenarios sampled graph paths, including adversarial inputs, and each scenario was replayed four times.The scenarios test cases where the user does not provide information needed at a particular turn.
- Recruitment Agents: The recruitment graph contains six task-specific nodes, including routing, inquiry handling, screening, killer questions, and interview finalization.The complex variant reaches Killer Questions only after all screening questions are passed.
- Recruitment Agents: The recruitment evaluation simulated 136 conversations across all DFS paths, with each scenario replayed three times.The study compared two recruitment-agent variations.
6. Results
Results summarize per-agent determinism, node utilization, and graph connectivity for the Honda Dealer and recruitment agents.
- Metrics: Tables 3 and 4 report per-agent determinism and node-utilization metrics averaged over all simulations.The metrics provide an aggregate view of behavior across the evaluated agents.
- Graph Visualizations: Figures 4 and 5 depict node connectivity, with node sizes and edge widths proportional to average utilization.The figures show connectivity patterns for the Honda Dealer and baseline Recruitment agents.
7. Discussion
The results distinguish trajectory and response consistency, showing that deliberate, constrained graph transitions improve determinism but do not ensure semantic response consistency.
- Cross-Agent Comparison: The Honda Dealer agent has lower node-order, node-overlap, and action determinism than both Recruitment-agent variants.The comparison is based on the determinism metrics in Table 3.
- Routing and Trajectory: A dedicated topic selector consistently routes the Recruitment process after each conversation turn, supporting its superior trajectory performance.The routing node is identified as the explanation for the Recruitment agent’s stronger performance relative to Honda Dealer.
- Response Consistency: High trajectory consistency and consistent action selection do not necessarily produce semantically consistent responses.The Recruitment agent maintains expected paths while showing relatively low response consistency in both variants.
- Topology Effects: The complex Recruitment variant outperforms its baseline, likely because its less-dense topology constrains the decision space and balances reactiveness with proactiveness.Removing selected edges produces more deliberate transitions and improves determinism.
8. Conclusion
EDGE evaluates graph-based agents through conversation simulation and replay, and the experiments highlight more stable execution from deliberately constrained transitions.
- Framework: EDGE uses an agent’s graph configuration as ground truth for reproducible testing across intended conversational paths.Its metrics analyze response, node, and action trajectory consistency.
- Findings: The complex Recruitment agent shows higher determinism and more stable execution than the baseline version.The reported difference is associated with deliberate and constrained transitions rather than a broadly permissive graph.
- Scope: The LangGraph Honda Dealer agent serves as an illustrative example that EDGE is not limited to one authoring framework.The paper presents this as evidence of the approach’s generality.
Impact Statement
The paper aims to advance agentic-system evaluation through improved determinism assessment and systematic conversation simulation in graph-based workflows. It reports no broader societal impacts requiring specific discussion.
- The proposed framework supports improved assessment of determinism in agentic systems.
- It enables systematic simulation of conversations in graph-based agent workflows.
- The paper identifies no broader societal impacts requiring specific discussion.