FlowState: Execution State as Memory for Long-Horizon LLM Agents

AI summary

Overview

Research area: Artificial Intelligence — LLM agents, long-horizon task execution, and agent memory / context management (cs.AI).

Technical level: Intermediate. The core idea is intuitive, but the paper formalizes it with state-transition notation, validation rules, and a full execution algorithm.

Scope: This paper proposes FlowState, a memory framework that treats an agent's execution state — semantically typed nodes plus their relations and references to raw tool outputs — as persistent, revisitable memory across requests, and evaluates it on MemoryArena and τ³-Bench.

What This Paper Is About

LLM agents working on long-horizon tasks need information from earlier interactions, but keeping the full history inflates context cost while compressing it can destroy details that only become relevant later. FlowState's goal is to separate persistent retention of information from what is currently visible in context, so an agent can keep a compact working context yet still reach back to earlier decisions, constraints, and original tool evidence when new information makes them relevant.

Key Contributions

1. A unified memory representation centered on execution state. Execution states are extended into reusable memory units spanning requests, connected through semantic types (preferences, knowledge, attributes, judgements, artifacts), node relations, and evidence references to raw tool observations.
2. Incremental maintenance and progressive access inside a single execution loop. Incremental State Update (ISU) maintains the current state, while Progressive State Access (PSA) reveals historical states and supporting evidence on demand, allowing memory to accumulate during execution and inform decisions.
3. A concrete architecture separating retention from visibility. A Persistent State Repository (ℳₖ) holds full contents outside the model context, a lightweight Historical State Index (Gₖ) of identifiers and concise summaries is placed in context, and an Active State (S_{k,t}) holds only current-request states plus disclosed historical states.
4. Empirical gains in both success and token efficiency, with ablations, subtask-depth analyses, and experiments across three base models (DeepSeek-V4-Flash, GPT-5.6-terra, Qwen3.5-397B-A17B).

Main Findings

• Headline improvement on MemoryArena: Compared with a full-context baseline using the same DeepSeek-V4-Flash model, FlowState improves average success rate on MemoryArena by 4.55 percentage points and average pass rate on τ³-Bench by 13.95 percentage points, while reducing total token consumption by 43.2% and 40.6%, respectively.
• Best on eight of nine MemoryArena performance metrics: FlowState reaches a Progress Score of 42.89% on Bundled Web Shopping, 11.78 percentage points above the strongest memory-system baseline, and a Progress Score of 12.57% on Group Travel Planning, 5.61 percentage points above the best baseline. It also has the best Math Progress Score and the best success rate and Progress Score on Physics.
• State tracking plus retrieval does not combine for free: ZipAct+BM25 beats both standalone components only on Math Progress Score, and FlowState surpasses ZipAct+BM25 on all nine performance metrics.
• τ³-Bench gains generalize: On Airline, Pass Rate rises from 58.0 to 78.0 and DB Accuracy from 70.5 to 78.0, with token use down 61.21%; on Retail, Pass Rate rises from 73.7 to 81.6 and DB Accuracy from 80.7 to 86.0, with tokens down 22.24%. Retail Action Accuracy decreases by 4.9 percentage points.
• Gains hold across base models: With DeepSeek-V4-Flash, GPT-5.6-terra, and Qwen3.5-397B-A17B, mean success rate and Progress Score are higher for all three, alongside 28.3%–56.3% lower mean relative token usage. Across all nine model–task combinations in the appendix, Progress Score improves and token consumption falls, success rate improves in eight cases and is preserved in one.
• ISU is essential for task success: Removing ISU drops success rate to 0.00 in both Group Travel Planning and Bundled Web Shopping, with lower Progress Score as well.
• PSA trades a little raw recall for large token savings: Removing PSA raises token use from 128.93M to 160.27M on Group Travel Planning and from 44.83M to 115.37M on Bundled Web Shopping; the no-PSA variant scores slightly higher Progress Score on Web Shopping (44.67 vs 42.89) but a lower success rate (3.33 vs 5.33).
• Advantage persists at later subtask depths: FlowState has the highest nAUC in all three domains (Web Shopping 65.58, Travel Planning 35.17, Formal Reasoning 80.66) and the lowest decline rate on Travel Planning (4.66) and Formal Reasoning (3.68). On Formal Reasoning it matches ZipAct+BM25 at the final reported depth.
• Not reported: GPT-5.6-terra results for Group Travel Planning appear as “–” in the main MemoryArena table; the paper does not report those values.

Methodology in Plain English

The authors model a sequence of user requests, each handled through multiple reasoning-and-acting steps, with the model's parameters fixed throughout. Around that loop they build three pieces of bookkeeping:

• A repository (kept out of the prompt). Every state node created so far is stored with its source request, identifier, category, and full content. If a newly created node cites a raw tool output, that output is stored as a node too. Nodes persist and historical ones cannot be deleted.
• An index (kept in the prompt). At the start of each request, the agent gets a compact list of prior states — just identifiers and short summaries — grouped by request.
• An active state (the working memory). This contains only states created during the current request, plus any historical states that have been explicitly pulled in, plus relations between them.

At each model call the agent reads the request, the latest tool observation, the index, and the active state, and emits three things: a proposed state change, a list of historical states it wants to see, and an execution decision (call a tool, answer, or do nothing yet).

The state change goes through ISU: the agent may add nodes, and may update or remove only nodes created in the current request, so it never rewrites the whole state — an unchanged budget preference simply stays put while a new price observation updates a lodging judgement. Changes are validated against execution rules before being committed.

The request to see history goes through PSA: using index identifiers, summaries, and relations already visible in the active state, the agent names specific historical nodes to disclose. Validation is applied, and only the requested contents and relations are added. Importantly, seeing a relation to another node does not reveal that node's contents, so the agent can choose to follow the link in a later step. Information disclosed at step t only affects decisions from the next model invocation, so the agent can deliberately emit no action and defer.

At the end of a request, newly created states and relations, plus referenced raw tool results, are written into the repository for future requests. Evaluation uses MemoryArena (Bundled Web Shopping, Group Travel Planning, Formal Reasoning: Math and Physics) and τ³-Bench (Airline, Retail), against Full Context, ReasoningBank, BM25, Mem0, ZipAct, and ZipAct+BM25.

Why This Matters

The paper reframes agent memory as state management plus on-demand disclosure rather than "store everything and retrieve by similarity" or "compress and hope nothing important was lost." It shows empirically that the two failure modes it targets — context bloat and lossy compression — can be addressed simultaneously, with success rates and token use improving together rather than trading off.

Real-world applications:

• Multi-session travel and shopping assistants, where an earlier booking, its cancellation terms, and a later price change must all be weighed together (the paper's running hotel-booking example).
• Customer service and back-office agents governed by business rules, the setting τ³-Bench models in airline and retail domains.
• Enterprise workflow and procurement agents that must respect constraints set many steps or sessions earlier while producing reusable artifacts.
• Multi-step analytical or technical assistants such as math and physics problem solving, where later steps depend on earlier intermediate results.

Industry relevance: Token consumption is a direct operating cost, and the reported reductions (43.2% on MemoryArena, 40.6% on τ³-Bench on average; up to 84.30% on Web Shopping with GPT-5.6-terra) are the kind of number that matters for deployed agent products. The design also keeps a persistent, auditable repository with source-request provenance and links back to raw tool observations — relevant to teams that need to explain or trace agent decisions.

Future Directions

• Safe retention and data governance. The authors state that their benchmark evaluation does not establish deployment safety and that real use would require controls over data access and retention, checks on provenance and validity, and safeguards for consequential actions. Designing and testing those controls is an open problem.
• Handling stale or superseded memory. Related work cited in the paper (MINTEval on multi-target interference under frequent updates; STALE on agents failing to recognize invalidated memories) suggests the next step is deciding not just what to disclose but whether a recalled state is still valid.
• Closing the action-accuracy gap. Retail Action Accuracy fell by 4.9 percentage points even as Pass Rate and DB Accuracy improved, which points to open questions about how state disclosure interacts with low-level action selection.
• Scope beyond the evaluated settings. Only selected MemoryArena environments and two τ³-Bench domains are tested; the paper does not report a direct comparison with concurrent work such as MAGE, which also organizes execution history hierarchically, leaving head-to-head evaluation and broader domain coverage open.

Target Audience

Researchers and engineers working on LLM agents, agent memory architectures, and context engineering — particularly those building multi-session assistants where cost per task and retention of earlier commitments both matter. It is also useful for readers following the state-tracking versus long-term-memory debate, since it explicitly positions itself against both full-context and compression-only approaches and includes an ablation isolating each mechanism.

Authors’ abstract

Long-horizon tasks require LLM agents to continually draw on information from earlier interactions. However, retaining the full history increases context costs, while compressing it risks losing details needed later, and the relevance of historical information often becomes apparent as the task progresses. To address these challenges, we propose FlowState, which treats execution state as memory that can be retained and revisited across requests, unifying current decision-making with the reuse of historical information. FlowState preserves semantically typed state nodes, their relations, and references to raw tool observations, separating persistent retention from on-demand access. Within a single execution loop, Incremental State Update (ISU) maintains the current state based on new inputs and feedback, while Progressive State Access (PSA) progressively reveals historical states and supporting evidence as needed during reasoning. Together, these mechanisms enable agents to reassess prior decisions in light of new information and guide subsequent actions. Compared with a full-context baseline using the same DeepSeek-V4-Flash model, FlowState improves the average success rate on MemoryArena and the average pass rate on $τ^3$-Bench by 4.55 and 13.95 percentage points, respectively, while reducing total token consumption by 43.2% and 40.6%. These results demonstrate the performance and efficiency advantages of FlowState on long-horizon tasks.