[2603.23610] Environment Maps: Structured Environmental Representations for Long-Horizon Agents

Computer Science > Artificial Intelligence arXiv:2603.23610 (cs) [Submitted on 24 Mar 2026 (v1), last revised 26 Mar 2026 (this version, v2)] Title:Environment Maps: Structured Environmental Representations for Long-Horizon Agents Authors:Yenchia Feng, Chirag Sharma, Karime Maamari View a PDF of the paper titled Environment Maps: Structured Environmental Representations for Long-Horizon Agents, by Yenchia Feng and 2 other authors 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 limit...