What exactly is a task-state horizon, and why does it matter?
A task-state horizon is the span of task-relevant world-state changes an agent must remember and track while completing a long task—like knowing a door was left open, an object was moved, or a device was turned off [5]. This is different from just counting how many steps a task takes; it's about the evolving state of the world that the agent's own actions and environmental changes create. The new RoboGraph benchmark defines this concept and shows that most of the 15 advanced AI models it tested perform worse as the task-state horizon grows, revealing a real bottleneck [5].
Why does this matter? If an agent only reacts to what it currently sees, it can forget that it already opened a drawer or that a stove was left on, leading to repeated actions or unsafe decisions. The papers converge on this: several frameworks explicitly separate 'task state' from 'sensory input' to avoid this confusion [3][6]. For example, the Task-State Representation (TSR) method for mobile GUI agents keeps a global instruction summary, a progress tracker, and an action verifier, so the agent doesn't have to hold everything in its working memory [3].
Does explicitly modeling task state actually improve performance?
Yes, in the studies that tested it, the gains are substantial. The TSR framework, which is a lightweight external wrapper that doesn't require changing the AI model itself, increased success rates by up to 12 absolute percentage points on complex cross-application mobile tasks [3]. In a text-based environment, the Spatio-Temporal Memory Agent (STMA), which adds a memory module and a dynamic knowledge graph, improved success rate by 31.25% over the previous best model [4]. These are not trivial improvements—they suggest that giving the agent a structured way to remember and update task state directly addresses a core weakness.
The improvements come from different angles but point the same way. The Graph-in-Graph (GiG) framework uses a graph neural network to encode environmental states and retrieve similar past experiences, achieving up to 37% higher Pass@1 (first-attempt success) on a cooking task benchmark [1]. ContextFlow treats task stages as explicit contracts and uses evidence packets to decide whether to continue, refine, or repair, which helps avoid 'stage lock' and unnecessary replanning [2]. Even an older method, the Scene Memory Transformer, showed that using attention over a memory of observations beats reactive policies in visual navigation [7]. So across different task types—cooking, navigation, mobile GUI—the pattern is consistent: explicit task-state tracking helps.
Where does task-state tracking still fall short?
Despite the gains, the evidence also shows that current methods don't fully solve the problem. The RoboGraph benchmark, which specifically tests varying task-state horizons, found that most of the 15 advanced models it evaluated still struggle with demanding horizons—even with state-tracking techniques [5]. This suggests that while these methods help, there's a ceiling, especially when tasks involve partial observability (you can't see everything at once) or when world states get overwritten by new information [6].
Another limitation is that many of these frameworks are evaluated in simulated or text-based environments, not real physical robots. For example, STMA was tested in TextWorld [4], and GiG was tested on Robotouille and ALFWorld, which are also simulated [1]. The WorldLines benchmark, which uses household traces with dialogues and state changes, highlights that translating long-term memory into embodied plans remains a persistent challenge [6]. So while the evidence is promising, it's not yet proof that these methods will work flawlessly in the messy, unpredictable real world.
About These Sources
This answer is built on 7 studies (all preprints) — published from 2022 to 2026, 6 from 2024 or later — selected as the most relevant from 7 studies that passed quality screening, drawn from 37 papers retrieved from a database of over 500 million.
Sources used in this answer
Embodied Task Planning via Graph-Informed Action Generation with Large Lanaguage Model
The GiG framework, using a graph-in-graph memory and bounded lookahead, improved Pass@1 by up to 22% on Robotouille Synchronous, 37% on Asynchronous, and 15% on ALFWorld compared to state-of-the-art baselines, with comparable or lower computational cost.
ContextFlow: Hierarchical Task-State Alignment for Long-Horizon Embodied Agents
ContextFlow introduces explicit stage contracts and evidence packets to address task-state misalignment, and its experiments and demonstration traces show that scoped updates (continue, refine, transfer, promote, repair) mitigate recurring task-state failures in long-horizon tasks.
A Task-State Representation for Long-Horizon Mobile GUI Agents
The Task-State Representation (TSR) framework, a training-free external wrapper that decouples task state from sensory input, increased success rates by up to 12 absolute percentage points on complex cross-application and memory-intensive mobile GUI benchmarks.
STMA: A Spatio-Temporal Memory Agent for Long-Horizon Embodied Task Planning
The Spatio-Temporal Memory Agent (STMA), which integrates a spatio-temporal memory module and a dynamic knowledge graph, improved success rate by 31.25% and average score by 24.7% over the state-of-the-art model in TextWorld across 32 tasks.
Compiling and Benchmarking Task-State Horizons for Embodied Agents
The RoboGraph benchmark, comprising 588 episodes across 84 scenes with varying task-state horizons, found that most of 15 advanced agentic models struggle with demanding task-state horizons, revealing gaps in maintaining, exploring, and updating task-relevant state.
WorldLines: Benchmarking and Modeling Long-Horizon Stateful Embodied Agents
The WorldLines benchmark, built from household traces with dialogues and state changes, shows persistent challenges in partial observability, overwritten world states, and translating long-term memory into embodied plans, with the ObsMem framework offering a stronger reference architecture.
Scene Memory Transformer for Embodied Agents in Long-Horizon Tasks
The Scene Memory Transformer (SMT), a memory-based policy that uses attention over embedded observations, outperformed reactive and other memory-based policies on a range of visual navigation tasks, demonstrating the value of long-term memory in partially observable environments.