Environment Maps: Structured Environmental Representations for Long-Horizon Agents

View PDF HTML (experimental)

Abstract: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; updated formatting issue

Subjects:

Artificial Intelligence (cs.AI)

Cite as: arXiv:2603.23610 [cs.AI]

(or arXiv:2603.23610v3 [cs.AI] for this version)

https://doi.org/10.48550/arXiv.2603.23610

arXiv-issued DOI via DataCite

Submission history

From: Chirag Sharma [view email] [v1] Tue, 24 Mar 2026 18:00:56 UTC (1,042 KB) [v2] Thu, 26 Mar 2026 01:28:12 UTC (1,042 KB) [v3] Fri, 27 Mar 2026 03:53:46 UTC (1,042 KB)