Source-linked AI summary
MAP: A Map-then-Act Paradigm for Long-Horizon Interactive Agent Reasoning
Yuxin Liu, Ziang Ye, Yueqing Sun, Mingye Zhu, Jinwei Xiao, Zhuowen Han, Qi GU, Xunliang Cai, Lei Zhang
TL;DR
Interactive LLM agents typically acquire environmental knowledge during execution, leaving a gap between reasoning and environmental understanding. MAP addresses this gap by mapping environments before acting, and it consistently improves benchmark performance, including gains in 22 of 25 ARC-AGI-3 games and stronger results from MAP-2K training than expert execution traces.
Problem
Existing agents infer environmental constraints reactively through actions and observations, creating an epistemic bottleneck because observational data does not identify how environments respond to interventions.
Method
MAP decouples environmental understanding from execution through global exploration, task-specific cognitive mapping, and knowledge-augmented execution, with MAP-2K training on complete map-then-act trajectories.
Results
MAP consistently improves success rates and reduces interaction steps across benchmarks, improves performance in 22 of 25 ARC-AGI-3 games, and MAP-4B outperforms counterparts trained on traditional expert execution traces.
Takeaways & Limitations
The results suggest that explicit cognitive mapping and environmental understanding are more foundational for long-horizon agents than surface-level action imitation.
Takeaways & Limitations
MAP is primarily validated in text-based environments with action spaces and has not yet been extended to embodied or multimodal settings.
Abstract
from arXiv · showhide
Current interactive LLM agents rely on goal-conditioned stepwise planning, where environmental understanding is acquired reactively during execution rather than established beforehand. This temporal inversion leads to Delayed Environmental Perception: agents must infer environmental constraints through trial-and-error, resulting in an Epistemic Bottleneck that traps them in inefficient failure cycles. Inspired by human affordance perception and cognitive map theory, we propose the Map-then-Act Paradigm (MAP), a plug-and-play framework that shifts environment understanding before execution. MAP consists of three stages: (1) Global Exploration, acquiring environment-general priors; (2) Task-Specific Mapping, constructing a structured cognitive map; and (3) Knowledge-Augmented Execution, solving tasks grounded on the map. Experiments show consistent gains across benchmarks and LLMs. On ARC-AGI-3, MAP enables frontier models to surpass near-zero baseline performance in 22 of 25 game environments. We further introduce MAP-2K, a dataset of map-then-act trajectories, and show that training on it outperforms expert execution traces, suggesting that understanding environments is more fundamental than imitation.
1 Introduction
Existing interactive LLM agents learn about environments reactively while acting, creating an epistemic bottleneck. MAP instead establishes environmental understanding before execution through a map-then-act paradigm, improving performance across benchmarks.
- Current agents use goal-conditioned stepwise planning, selecting each action from the current observation and immediately continuing execution.Existing optimization emphasizes reasoning capability and memory systems within this action-conditioned cycle.
- Delayed Environmental Perception forces agents to infer layouts, affordances, and latent constraints through trial-and-error feedback.This reverses the desired order of understanding and action.
- The resulting Epistemic Bottleneck produces Goal Drift and Redundant Trial-and-Error during task execution.Agents may remain in locally plausible but globally suboptimal behaviors or repeatedly violate latent environmental logic.
- MAP decouples environmental understanding from task execution by establishing a global environmental prior before acting.The paradigm is motivated by affordance perception and cognitive map theory, summarized as “Let’s look around first”.
- MAP consistently improves success rates and reduces interaction steps without parameter updates, while MAP-4B trained on MAP-2K outperforms models trained on expert execution traces.The results suggest that teaching agents to understand environments is more fundamental than teaching them to imitate solutions.
2 Related Work
Related work improves agent reasoning and memory, but existing approaches still struggle to model environmental structure. This motivates structured environment representations for reliable environment-aware execution.
- Prompting-based agents often exhibit planning hallucinations and trial-and-error, while later work improves reasoning through expert imitation, reinforcement learning, and replay.These approaches primarily optimize decision-making within existing workflows.
- Environment-aware execution requires an accurate model of environmental structure, including spatial layouts and object affordances.Agents may succeed through trial-and-error or imitation without capturing these underlying properties.
- Long-context windows and key-value memories struggle to organize fragmented interaction histories into consistent spatial or physical representations.Model-based reinforcement learning offers environment dynamics models but is less compatible with language-based agents and open-ended settings.
3 Method
MAP decouples environmental understanding from task execution through a structured mapping workflow, then conditions execution on global and task-specific knowledge. Its method combines cross-task exploration, adaptive task mapping, and knowledge-augmented execution, with MAP-2K enabling internalization of map-then-act behavior.
- 3.1 Task Formulation: MAP separates environmental understanding from execution by actively probing the environment, constructing a cognitive map, and conditioning decisions on that map.This shifts the agent from observational history alone toward causally grounded, knowledge-driven reasoning.
- 3.2 MAP Architecture: Cross-task global exploration distills persistent knowledge Kg containing action syntax, interaction rules, and recurring error patterns shared across tasks.Kg is constructed once per environment and reused for downstream task instances, reducing redundant rule verification.
- 3.2 MAP Architecture: Task-specific cognitive mapping constructs Mt from concrete facts about spatial layouts, environmental physics, object-action affordances, and environment-specific game rules.The map is tailored to the current environment instance and is guided by the global prior Kg.
- 3.2 MAP Architecture: Adaptive exploration uses knowledge increment and state novelty to decide when mapping has sufficiently reduced uncertainty and covered novel regions.Cond_A tracks newly added knowledge entries, while Cond_B tracks revisitation through a decaying novelty reward; both conditions must converge simultaneously.
- 3.2 MAP Architecture: Knowledge-augmented execution samples actions conditioned on the task instruction, global prior Kg, task map Mt, and interaction history.The final execution stage applies the dual-layer representation {Kg, Mt} after mapping has been completed.
- 3.3 Internalization via Cognitive Fine-tuning: MAP-2K is built through teacher-student distillation of full map-then-act trajectories and fine-tunes a student policy on the complete action sequence.The training objective supervises both environment understanding and task execution rather than expert execution actions alone.
4 Experiment
Experiments across long-horizon and fluid-intelligence benchmarks test MAP’s performance, environmental understanding, efficiency, and component necessity. Results consistently favor staged map-then-act reasoning, including broad gains in novel environments and stronger training signals from MAP-2K.
- Main Results: MAP consistently outperforms ReAct and CoMAP across most benchmarks and backbones, showing that both environmental understanding and staged decoupling matter.CoMAP improves over ReAct, while MAP further improves over CoMAP under comparable token budgets.
- Main Results: MAP-2K substantially outperforms expert execution trajectories across all benchmarks under identical training settings.MAP-4B also surpasses several larger models, supporting map-then-act trajectories as a stronger training source than surface-level action imitation.
- Main Results: 22 of 25 ARC-AGI-3 games show consistent MAP improvements over near-zero ReAct performance in fully novel environments.The evaluation uses Claude 4.6 Opus and tests exploration and rule discovery without explicit rules or goals.
- Environmental Understanding Ability: Strong accuracy across four Map QA categories indicates that constructed cognitive maps capture environment structure before execution.The categories are object locations, object-action affordances, negative knowledge, and task reasoning.
- Environmental Understanding Ability: MAP-4B shows a substantially smaller performance drop and more efficient recovery than the untuned base model under mid-episode object relocation.The perturbation experiment tests adaptive replanning rather than reliance on memorized action sequences.
- Ablation Study: Both stage ablations reduce performance across 4B, 8B, and 32B models, with removing task mapping causing the larger degradation.Removing global exploration produces complementary losses, while task mapping is identified as the more critical stage.
5 Conclusion
The paper identifies an epistemic bottleneck in existing agent paradigms and proposes MAP to decouple environmental understanding from task execution. MAP improves performance across benchmarks and model scales, including progress in previously near-zero ARC-AGI-3 settings.
- MAP explicitly decouples environmental understanding from task execution through a structured Map-then-Act paradigm.
- MAP consistently outperforms existing paradigms across benchmarks and model scales, while MAP-4B surpasses models of significantly larger size.
- MAP enables meaningful progress on ARC-AGI-3, where frontier models score near zero, demonstrating the value of structured exploration in fully unknown environments.
- The findings suggest that explicit cognitive mapping provides a robust foundation for adaptive, long-horizon interactive agents.
A Limitations and Future Works
MAP is primarily validated in text-based environments with action spaces. Extending cognitive mapping to embodied and multimodal settings remains future work.
- MAP is currently validated primarily in text-based environments with action spaces.
- The framework has not yet been extended to embodied AI or multimodal perception involving visual inputs and continuous action spaces.
- Future work includes robotic manipulation and vision-language navigation.
B.1 Dual-Convergence Stopping Criterion Analysis
MAP uses a dual-convergence stopping criterion during mapping. Exploration stops when knowledge gains and state novelty both indicate diminishing discovery, subject to a minimum exploration floor.
- Mapping uses knowledge increment and state novelty to determine whether exploration has converged.The analysis visualizes ∆|Mt| and 1/N(ot) during a representative TextCraft mapping episode.
- Cond_A is satisfied when ∆|Mt| approaches zero for Wk = 3 consecutive steps, indicating no new spatial or affordance information.
- Cond_B is satisfied when the sliding-window average of r(ot) over Wn = 5 steps falls below ε = 0.5, indicating repeated states.
- A minimum exploration floor of Tmin = 3 steps prevents premature termination.
B.2 MAP-2K Dataset Details
MAP-2K is built from map-then-act exploration trajectories generated through teacher-student distillation and evaluated across diverse interactive environments. The setup specifies benchmark coverage, mapping budgets, and a TextCraft episode analysis.
- Figure 6 analyzes step-wise Knowledge Increment and State Novelty during a representative TextCraft mapping episode.
- MAP-2K is constructed through teacher-student distillation using GPT-4.1 and Claude 4.5 as expert cognitive annotators.Teacher models execute goal-free exploration and produce exploration trajectories that undergo ground-truth alignment checks.
- MAP is evaluated on ALFWorld, TextCraft, ScienceWorld, and ARC-AGI-3, spanning diverse task structures and environmental complexities.
- The evaluation uses 100 standard TextCraft test tasks and 200 ScienceWorld task instances.
- ARC-AGI-3 contains 6 distinct game environments with no explicit rules, goals, or instructions, requiring agents to infer mechanics through interaction.
- Mapping budgets are 10 steps in ALFWorld, 15 in TextCraft and ScienceWorld, and 30 in ARC-AGI-3, with 50 acting steps in the first three benchmarks.
C.2 Full Results on ARC-AGI-3
MAP’s full ARC-AGI-3 evaluation shows broad improvements over ReAct, while its exploration prompts and knowledge distillation construct reusable environment-level rules before task execution.
- Full ARC-AGI-3 Results: MAP improves over ReAct in 22 of 25 ARC-AGI-3 games, while ReAct scores near-zero across virtually all environments.The complete results indicate that the gains are broad rather than confined to the main-paper subset.
- Map QA Evaluation: The mapping evaluation tests object location, object-action affordances, negative knowledge, and task reasoning from the constructed cognitive map.These categories assess spatial layout, action consequences, non-existence claims, and map-supported planning decisions.
- Map QA Evaluation: Ground-truth answers come from the environment engine, and agents answer solely from their constructed map without further interaction.Accuracy is the proportion of correct answers in each category, averaged across evaluated task instances.
- Causal Adaptability: Controlled mid-episode relocation tests whether agents detect and adapt when target objects move during execution.The perturbation is introduced at a randomly sampled step, requiring adaptation to the changed environment.
- Causal Adaptability: The perturbation analysis measures success under shift, re-exploration behavior, and post-perturbation interaction cost.These metrics correspond to pass@1perturb, Re-exploration Rate, and ∆Steps.
- Causal Adaptability: A smaller ∆Steps indicates more efficient recovery after perturbation and therefore lower adaptation cost.∆Steps measures interaction steps from perturbation to episode termination.
- Global Exploration: Stage 1 uses focus-point generation and knowledge distillation to derive environment-general rules shared across tasks.The resulting knowledge base captures action syntax, interaction rules, and recurring error patterns for reuse across task instances.
E Task Mapping Prompt
The task-mapping prompt constructs a task-specific cognitive map before execution, then combines it with global knowledge for environment-grounded action; CoMAP instead interleaves mapping and acting.
- E Task Mapping Prompt: Stage 2 uses a Role-Purpose-Priority protocol to construct task-specific cognitive map Mt before execution.Prompt variants are supplied for ALFWorld, TextCraft, and ScienceWorld.
- F Knowledge-Augmented Execution Prompt: Stage 3 injects global knowledge Kg and task map Mt into the acting prompt as contextual priors.Kg supplies environment-general interaction rules, while Mt supplies task-specific layouts and object-action affordances.
- F Knowledge-Augmented Execution Prompt: The ALFWorld execution prompt combines navigation, receptacle interaction, object manipulation, and state-change actions with a cognitive map.Its rules require reaching locations before interaction, holding only one object, and checking admissible commands.
- F Knowledge-Augmented Execution Prompt: The TextCraft prompt pairs crafting actions and a cognitive map with rules for raw materials, intermediate items, and exact item naming.Raw materials cannot be crafted, intermediate items precede the final target, and spaces replace underscores in item names.
- F Knowledge-Augmented Execution Prompt: The ScienceWorld prompt supplies laboratory actions and a cognitive map alongside navigation and experiment-specific sequencing rules.Examples include navigating before interaction, heating water before measuring temperature, and looking around upon entering a location.
- G CoMAP Baseline Prompt: CoMAP maintains an internal world model while executing in one loop, without a dedicated mapping stage.Its prompt tracks layouts and affordances, records failed attempts, and interleaves targeted exploration with task progress.
- G CoMAP Baseline Prompt: MAP differs from CoMAP by constructing an explicit Mt during a dedicated mapping phase before knowledge-driven execution.CoMAP gathers environmental knowledge and completes the task simultaneously, whereas MAP separates the phases.
H.1 Long-Horizon Interactive Benchmarks
Across long-horizon interactive benchmarks, MAP’s cognitive maps provide exact spatial, ingredient, and action knowledge that replaces repeated trial-and-error with shorter successful executions.
- ALFWorld: In ALFWorld, MAP locates cup 2 and completes the task in 7 steps, whereas ReAct misidentifies a mug and fails after 37 steps.The case study reports an 81% efficiency increase for MAP.
- TextCraft: TextCraft’s map records exact action syntax, raw-material constraints, and recurring invalid-recipe errors.These rules distinguish craftable items from gatherable raw materials and flag incorrect names or quantities.
- TextCraft: The TextCraft cognitive map specifies the furnace minecart dependency structure, including furnace, stone crafting materials, minecart, iron ingot, and iron nugget requirements.The map provides exact item names and required quantities for the target construction.
- TextCraft: ReAct repeatedly tries stone and cobblestone for the furnace, receives invalid-recipe errors, and repeats the failed action.This trajectory illustrates trial-and-error caused by incorrect environmental or recipe knowledge.
- TextCraft: Using the cognitive map’s exact item name, MAP gathers stone crafting materials and completes the furnace minecart task.The successful trajectory retrieves the specified material before executing the mapped crafting plan.
- TextCraft: In TextCraft, MAP identifies the correct stone crafting materials and completes the task in 10 steps, while ReAct fails after 40 steps.The case study reports a 75% efficiency increase for MAP.
- ScienceWorld: In ScienceWorld, MAP retrieves object locations and prerequisite action sequences, finishing in 8 steps after ReAct fails in 61 steps.The case study reports an 87% efficiency increase for MAP.
H.2 Fluid Intelligence Benchmarks
MAP constructs cognitive maps across ARC-AGI-3 games with different mechanics, discovering layouts, action effects, and rules that support multi-level winning strategies.
- Fluid Intelligence Benchmarks: Across maze navigation, belt alignment, and color sorting games, MAP autonomously discovers spatial layouts, action effects, and game rules.The representative instances are TU93, VC33, and SB26.