Constructing Coherent Spatial Memory in LLM Agents through Graph Rectification

Current LLM approaches to spatial reasoning face significant limitations:

• Lack of interpretability: LLMs using context windows for text reading and spatial reasoning operate as black boxes
• Context limitations: Small context windows cannot handle long texts effectively
• Need for external memory: These limitations necessitate incremental graph construction to build spatial memory externally

However, incremental graph construction introduces new challenges:

• Construction errors: The graph building process may introduce errors
• Delayed conflict manifestation: Detectable structural conflicts in graphs may not indicate the root cause of errors
• Error masking: Errors can mask each other, causing conflicts to trigger with delays

We propose a framework that enables LLMs to resolve conflicts and potential errors more efficiently through:

1. Version Control System: Tracks the evolution of the navigation graph, enabling backtracking to previous states when conflicts are detected
2. Edge Dependency Detection: Evaluates the structural importance and impact of edges, helping LLMs prioritize which edges to examine when resolving conflicts

This dual approach allows for both temporal analysis (when errors were introduced) and structural analysis (which edges are most critical to graph coherence).

https://nitpicker55555.github.io/text_maze.github.io/

https://huggingface.co/datasets/boboIloveyou/spatial_refined_mango/tree/main

The root-level files are a minimal reference implementation, organized as the same five modules as in the paper:

• map_slam_system.py — End-to-end pipeline. For each walkthrough step it runs (1) NavigationGraph.process_step, (2) VersionControl.commit, (3) ConflictDetector.detect_all_conflicts, and on detected conflicts (4) ConflictLocalizer.localize_conflicts followed by (5) EdgeImpactScorer.score_edges.

• navigation_graph.py — LLM-driven incremental graph construction. Tracks unit-distance positions for every node so the topological exclusivity check has the coordinates it needs, and auto-inserts reverse edges for cardinal directions.

• conflict_detector.py — Implements the three structural conflict types from paper Section 2.2:

  1. Topological conflict — two distinct nodes inferred to occupy the same unit-distance position (physical exclusivity violation).
  2. Directional conflict — a single source node has multiple outgoing edges with the same direction label.
  3. Naming conflict — the same canonical name is attached to two structurally distinct nodes.

• conflict_localizer.py — Implements the four-stage error localization pipeline from paper Section 2.3. Crucially, the LCA is computed on the Reasoning History Tree T (a DAG indexed by construction timestamps tau(v)), not on the spatial graph, so it remains well-defined when the spatial graph contains cycles. Uses paper Equation 2:

  LCA(pi_1, pi_2) = argmax_{v in pi_1 ∩ pi_2} tau(v)
  

• edge_impact_scorer.py — Implements the Edge Impact Score from paper Equation 1:

  score(e) = R_hat(e) + C_hat(e) + U_hat(e)
  

  where each factor is min-max normalized to [0, 1] across the candidate edges. The three factors are:

  • Reachability R(e): number of nodes downstream-reachable from e
  • Conflict count C(e): distinct conflicts involving e
  • Usage U(e): walkthrough traversals containing e

• version_control.py — Versioned reasoning history (paper Section 2.4). Each commit G_i records {Step_id, Commit, Trigger_event, Observation_id, Analysis}. Exposes the three operations from the paper: rollback_to(version), recall_step(version), and diff(G_i, G_j). Also exports the Reasoning History Tree T and timestamps tau for the localizer.

• mango_dataset.py — Loader for the refined MANGO walkthrough format.
• llm_agent.py — Thin OpenAI wrapper (chat_single).
• batch_run.py — CLI that runs the full pipeline on one or many games and writes per-game JSON reports plus an aggregate summary. Supports --all and --workers N.
• test_pipeline.py — End-to-end smoke test that replays the paper's Case Study B (long-range conflict, 9-node toy environment) without invoking any LLM and verifies the EIS ranking matches the paper.

Every quantitative claim in the paper is produced by a script under experiments/ and saved as a raw JSON under results/. This repo is self-contained for all paper data except (i) the Dream of the Red Chamber deployment (Table 4) and (ii) the hand-crafted TC1–TC6 scenarios (Section 4.4 / Appendix B); both live in the companion repo https://github.com/nitpicker55555/spatial_memory.

Setup once:

pip install -e .        # or: pip install -r requirements.txt
cp .env.example .env    # add OPENAI_API_KEY / proxy keys
export PYTHONPATH=src

gpt-4.1 as repair LLM. Random graphs of size 60 with directly injected topology or direction errors at densities 4 and 8. Each cell aggregates n=20 independent seeds; 95% Wilson confidence intervals. Base. = unscaffolded LLM, EI = Edge-Impact Ranking, VC = Version Control, VC+EI = combined.

python -m experiments.exp29_complementary_roles --seeds 20

Seven LLMs from OpenAI, Anthropic, and Google. (i) Synthetic graphs with direction-conflict noise (1–3 conflicts per graph, n=20 seeds per cell). (ii) TextWorld procedurally-generated text-adventure games with mango-like noise mixture (room-name collapses, duplicate-direction edges, hallucinated rooms; n=30 seeds per cell). Bold entries denote cells where VC+EI outperforms the baseline LLM.

python -m experiments.exp25_frontier_2026
python -m experiments.exp26_frontier_textworld

Repair on all 42 cleaned-MANGO games whose gpt-4.1-built input graphs contain ≥1 residual conflict (534 conflicts in aggregate). Three vendors × three modes plus two non-LLM references. Counts above 534 indicate that the repair mode introduced additional conflicts; lower is better.

Headline cells (residual conflicts after repair):

• GPT-5.5 EI: 609 → 396 (Δ = −213, 35% relative improvement)
• Claude-Haiku 4.5 VC+EI: 874 → 625 (Δ = −249, 28% relative improvement)
• Gemini 3.5-Flash EI: 841 → 572 (Δ = −269, 32% relative improvement)
• heuristic_remove: 98 (strongest absolute reducer)
• heuristic_modify: 438

The Table 3 data pipeline (each stage's output feeds the next):

data_fixed/<game>/<game>.walkthrough         ← MANGO raw walkthrough
        ↓ experiments/exp11c_gt_aligned_clean.py
results/exp11c/clean_walkthroughs/           ← 53 GT-aligned clean walkthroughs
        ↓ experiments/exp14_remap_v3_fixed.py  (gpt-4.1 LLM mapping)
results/exp14/gpt-4.1/<game>_edges.json      ← 53 LLM-built input graphs (42 of them have ≥1 conflict, aggregating to 534)
        ↓ experiments/exp30c_full_mango_sweep.py  (EI / VC+EI / heuristic repair)
results/exp30c/raw.json                      ← 362 per-(game, mode, model) repair runs that produce Table 3

python -m experiments.exp11c_gt_aligned_clean
python -m experiments.exp14_remap_v3_fixed
python -m experiments.exp30c_full_mango_sweep

Aggregate change in ground-truth-direction-correct edges across the same 42 cleaned-MANGO games. All values are non-positive; values closer to zero (less negative) indicate better preservation.

Non-LLM references (model-independent):

(Table A3 shares its raw source with Table 3; the two tables are different aggregations of the same 362-run experiment.)

5 representative cleaned-MANGO games × GPT-5.5 + Edge-Impact × max_iter ∈ {5, 10, 20, 40}.

Aggregate net resolution rate (repaired minus newly-introduced, normalized by input conflicts; positive = net repair):

python -m experiments.exp31_iter_sensitivity

End-to-end LLM-MapRepair on natural text. Chapters 16–17 against a human-authored ground-truth map (35 unique locations, 34 spatial relation pairs evaluated as undirected pairs). Both methods use gpt-4.1.

The DRC pipeline data files live in the companion repository https://github.com/nitpicker55555/spatial_memory:

TC1–TC6 hand-crafted scenarios:

These numbers reproduce bit-exactly from the companion repository https://github.com/nitpicker55555/spatial_memory, under lca_algorithm_validation/:

1,160-graph programmatically-generated scale-up:

python -m experiments.exp01_localization

53 environments, 1,673 → 1,513 edges (160 removed) via the 6-step refinement pipeline.

# Single game
python batch_run.py --games zork1 --data-dir /path/to/data_fixed

# All 53 games in parallel
python batch_run.py --all --workers 4 --data-dir /path/to/data_fixed

# Different LLM backbone, capped at 50 steps each
python batch_run.py --all --model gpt-4o-mini --max-steps 50

python test_pipeline.py

test_pipeline.py replays the paper's Case Study B in plain Python: it introduces a directional error at step 5, watches the topological conflict fire 15 steps later when Lab and Meeting Room land on the same coordinate, runs LCA on the Reasoning History Tree, and prints the EIS ranking that puts the true error at the top.

@misc{zhang2025constructingcoherentspatialmemory,
      title={Constructing coherent spatial memory in LLM agents through graph rectification}, 
      author={Puzhen Zhang and Xuyang Chen and Yu Feng and Yuhan Jiang and Liqiu Meng},
      year={2025},
      eprint={2510.04195},
      archivePrefix={arXiv},
      primaryClass={cs.AI},
      url={https://arxiv.org/abs/2510.04195}, 
}