Environment Maps: Structured Environmental Representations for Long-Horizon Agents

Computer Science > Artificial Intelligence [Submitted on 24 Mar 2026] Environment Maps: Structured Environmental Representations for Long-Horizon Agents Yenchia Feng, Chirag Sharma, Karime Maamari Although large language models (LLMs) have advanced rapidly, robust automation of complex software workflows remains an open problem. In long-horizon settings, agents frequently suffer from cascading errors and environmental stochasticity; a single misstep in a dynamic interface can lead to task failure, resulting in hallucinations or trial-and-error. This paper introduces \textit{Environment Maps}: a persistent, agent-agnostic representation that mitigates these failures by consolidating heterogeneous evidence, such as screen recordings and execution traces, into a structured graph. The representation consists of four core components: (1) Contexts (abstracted locations), (2) Actions (parameterized affordances), (3) Workflows (observed trajectories), and (4) Tacit Knowledge (domain definitions and reusable procedures). We evaluate this framework on the WebArena benchmark across five domains. Agents equipped with environment maps achieve a 28.2% success rate, nearly doubling the performance of baselines limited to session-bound context (14.2%) and outperforming agents that have access to the raw trajectory data used to generate the environment maps (23.3%). By providing a structured interface between the model and the environment, Environment Maps establish a persistent foundation for long-horizon planning that is human-interpretable, editable, and incrementally refinable. Comments: 9 pages, 5 figures, accepted to ICLR 2026 the 2nd Workshop on World Models Subjects: Artificial Intelligence (cs.AI) Cite as: arXiv:2603.23610 [cs.AI]   (or arXiv:2603.23610v1 [cs.AI] for this version)   https://doi.org/10.48550/arXiv.2603.23610 Focus to learn more Submission history From: Chirag Sharma [view email] [v1] Tue, 24 Mar 2026 18:00:56 UTC (1,042 KB) Access Paper: HTML (experimental) view license Current browse context: cs.AI < prev   |   next > new | recent | 2026-03 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)