Graph-Augmented Episodic Memory for Constraint-Aware Agentic Planning
Integrate a graph-based episodic memory and Monte Carlo Tree Search into the agent planning loop to handle long-horizon sequential state dependencies.
Time
Compute level
Resources
What the paper used
Prerequisites
Scope
The Gap
The paper demonstrates in Section 4.4 that models fail at long-horizon plan generation, with performance dropping sharply as task steps increase. While providing human-authored plans improves performance by 14-35%, current automated decomposition methods (Planner+Decompose+Subtask) actually regress performance due to their inability to handle strong sequential state dependencies.
“Models frequently invoke tools that create database objects without first querying the necessary prerequisites, producing dangling records with broken foreign-key links (Missing Prerequisite Lookup).”
Limitation
Current LLM agents lack the ability to maintain a coherent representation of world state and foresee cascading state dependencies over long sequences, leading to premature execution or broken foreign-key links.
Proposed Solution
Implement a structured episodic memory module that maintains a dynamic, graph-based representation of the environment state. Integrate a neuro-symbolic planner or Monte Carlo Tree Search (MCTS) into the ReAct loop that simulates potential state transitions on this graph, formally verifying policy constraints and prerequisite structures before committing to an action sequence.
The paper’s authors list this direction as future work, so they may already be pursuing it.
Why This Matters
Bridging the gap between automated planning and human-authored plans is the most significant bottleneck identified in the paper. Solving this would drastically improve the reliability of autonomous agents in long-horizon, interconnected workflows.
How to Get Started
How to test it: Hypothesis: Maintaining a dynamic graph of world state with MCTS constraint verification before committing actions will reduce broken foreign-key links and improve long-horizon success. Compare against single-agent ReAct and Planner+Executor baselines (Claude Sonnet 4.5 and Qwen3-30B) using pass@1 across 3 runs on CSM, ITSM, and HR; stop if the approach fails to exceed Planner+Executor by at least 5 percentage points on pass@1 or more than doubles per-task cost/latency without reducing integrity-constraint errors.
- Implement a dynamic graph data structure within the memory module to track environment states and action preconditions.
- Integrate an MCTS or neuro-symbolic planning module into the standard ReAct agent loop.
- Configure the ENTERPRISEOPS-GYM sandbox to provide structured state feedback for step verification.
- Evaluate the updated planner on long-horizon tasks and compare success rates against baseline decomposition methods.
Code linked to this paper on Hugging Face: github.com/ServiceNow/EnterpriseOps-Gym
Suggested by AI. Adapt it to your setup.
Has This Been Done?
The listed works discuss episodic memory modules for agents (such as REMem: Reasoning with Episodic Memory in Language Agent and EMExplorer) or general agent planning frameworks, but none of them implement a graph-based episodic memory integrated with MCTS or neuro-symbolic planners for formal constraint verification.
- EMExplorer: an episodic memory enhanced autonomous exploration strategy with Voronoi domain conversion and invalid action masking · 2023 · 9 citations
- REMem: Reasoning with Episodic Memory in Language Agent · 2026 · 25 citations
- CAST: Character-and-Scene Episodic Memory for Agents · 2026 · 9 citations
We searched OpenAlex and arXiv for “Integrate a graph-based episodic memory and Monte Carlo Tree Search into the agent planning loop to handle long-horizon sequential state dependencies.” and “Graph-Augmented Episodic Memory for Constraint-Aware Agentic Planning” and an AI compared the idea with the top 10 results. A small search can miss relevant work.
Source Paper
EnterpriseOps-Gym: Environments and Evaluations for Stateful Agentic Planning and Tool Use in Enterprise SettingsShiva Krishna Reddy Malay, Shravan Nayak, Jishnu Sethumadhavan Nair +6 more · 2026
This paper introduces ENTERPRISEOPS-GYM, a highly complex, sandboxed benchmark featuring 164 database tables and 512 tools designed to evaluate LLM agents in realistic, policy-constrained enterprise workflows. The study reveals that current frontier models struggle significantly with long-horizon strategic planning, cascading state dependencies, and safely refusing infeasible tasks, indicating they are not yet ready for autonomous enterprise deployment.
Related Ideas
- Dynamic Multi-Turn Constraint ElicitationDeepPlanning: Benchmarking Long-Horizon Agentic Planning with Verifiable Constraintsđźź Medium
- Verifiable Tree-Search with Partial State FeedbackDeepPlanning: Benchmarking Long-Horizon Agentic Planning with Verifiable Constraintsđźź Medium
- Optimizing High-Concurrency Database and Inference Pipelines for Million-Agent SimulationsOASIS: Open Agent Social Interaction Simulations with One Million Agentsđźź Medium
- Neural Explicit Memory for Consistent Multi-Agent World SimulationSolaris: Building a Multiplayer Video World Model in Minecraftđźź Medium
- Compressive Memory for Agentic ContextsGLM-5: from Vibe Coding to Agentic Engineeringđźź Medium