- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes EvoState, a training-free memory module for LLM agents doing long multi-step tool use. It stores key facts from tool outputs, such as IDs and current values, in a structured state and updates them as new results arrive. When building each prompt, it includes facts the agent will still need. Across three benchmarks (AppWorld, BFCL, CRMArena-Pro), EvoState improves task success over the strategy keeping the full history (+2–7 pp), while using 10–29% fewer tokens.
Critical strengths
S1. Important problem. Long-horizon tool-using tasks require agents to reuse exact values from earlier outputs, and truncation and summarization could drop or distort these values. The paper targets this practical failure mode.
S2. Careful evaluation. The paper covers several benchmarks and reports the cost of every memory-management call and failed run. It also uses three runs with significance tests and openly reports where gains are not significant.
Critical weaknesses
W1. Insufficient differentiation from existing context-management and memory methods. Many methods already try to summarize interaction histories, organize reusable information, maintain task-related state, and prompt LLMs to preserve important details. However, the main text does not provide a sharp characterization of which capabilities existing methods lack or why their mechanisms are insufficient to solve difficult tasks. I recommend authors to provide a comparison table explicitly showing which functionalities differ between EvoState and the closest existing methods, or, which functionalities are absent from each existing method. Also, qualitative comparison figure showing when and why they fail while EvoState succeeds would be helpful.
W2. Unclear distinction between LLM-based and rule-based components. The main text's method section does not state clearly whether each operation is performed by an LLM or by pre-defined rules (e.g., which records are classified as protected, how fields and spans are selected in assembly, and how the verifier V and Merge operation works in Eq (6), and more). I suspect that pre-defined rules likely drive the gain over prior baselines: removing LLM consolidation (N4) costs only 4.8 pp, while removing protection in assembly (N6) costs 19.4 pp. Please mark each component as LLM-based or rule-based in the main text, and add a concrete example of what the rules do.
Questions for authors
See weaknesses
6 comments
Initial Response to Reviewer TCnD(Part 2/2)
We further clarify the specific details you asked about below.
Which records are protected.
Section 3.4 of the main text and Appendix A.4 designate currently valid exact dependencies, state records needed to continue execution, outstanding task requirements, and records needed for the current working stage as protected content. Dependency identification uses fields in tool responses and suffix rules; the specific scope is described in Appendix A.6.1. The end of a stage does not by itself automatically release dependencies still needed by subsequent actions. Requirement discharge and fact invalidation, in turn, change their protection status or reading priority accordingly.
How fields and text spans are selected.
The Assembler first includes mandatory and protected information, then selects optional content. For excessively long observations, it first uses a compact format that preserves fields and values. If the observation is still too long, fields and text spans are selected based on task relevance, entity information, and identified dependencies. Content not included in the current input remains in the original records; input selection and source deletion are two distinct operations. Candidates beyond the soft target must also satisfy the admission conditions in Appendix A.6.5 and are always subject to the model’s hard capacity limit. The complete procedure is provided in Algorithm 2 of Appendix A.4.
How the Verifier (V) works.
The Verifier performs support checks on identified concrete values in proposals and their sources, checks whether requirement discharge has applicable evidence, and checks whether summaries cover the information needed to permit replacement of source records. The specific criteria are described in Appendices A.6.2–A.6.4.
How Merge works.
Merge handles duplicate and conflicting operations, prioritizes direct tool evidence over conflicting proposals, and applies compatible edits in the prescribed order. Combined updates are first applied to a copy of the state and committed only after passing rule checks. If a check fails, the system falls back to rule-generated updates or rejects the update, depending on the configuration. The procedure is provided in Algorithm 1 of Appendix A.2.
An actual editing cycle.
Appendix G.2 presents a complete update after a tool returns eight playlists and their song IDs:
- The rules generate three operations: write the grouped song IDs into Task State; retain the action that obtained these lists and its authentication bindings; and retain the complete tool observation.
- The LLM proposes two operations: compress five older records into a summary and remove one superseded record.
All five operations pass the rule checks and are committed together, reducing Current Trace from 12 records to 9. The song IDs and their groupings are preserved. After broader login observations are summarized, the exact login dependencies still needed for subsequent calls are also retained. The Actor then uses this information to complete deduplication, song queries, and artist following, and the task ultimately passes all 4 official checks. This case concretely illustrates how rule-generated updates, LLM proposals, and dependency retention work together within a single editing cycle.
The different performance drops of N4 and N6.
We agree with the reviewer that the N6 result highlights the importance of the assembly policy in our current system. However, the larger drop in N6 does not establish that predefined rules are the primary source of the gains, because N4 and N6 are not matched ablations:
- N4 disables conditional LLM consolidation while retaining rule-based state updates and the original assembler. Mean success rate decreases from 86.11% to 81.35% (−4.76 percentage points).
- N6 retains state storage and editing but changes dependency protection, necessary-state priority, and admission rules beyond the soft target. Mean success rate decreases to 66.67% (−19.44 percentage points).
These results show that the tested assembly-policy changes have a substantial effect on performance, but the two drops cannot be compared as estimates of the relative contributions of LLM consolidation and rule-based assembly. We clarify the intervention scope in Appendix D.1 and provide the complete results in Table 32.
Thank you for the detailed response. I will maintain my score.
My main concern remains. The new comparison table and qualitative cases for W1 are helpful, but they remain in the appendix and describe what EvoState does rather than what existing methods lack or why existing methods fail at the mechanism level. As the response acknowledges, the distinction from prior methods is that EvoState handles fact replacement, requirement resolution, and cross-stage dependency retention through explicit rules rather than leaving them to the Actor. Consistent with this, the ablations suggest the rules drive most of the gain: without LLM consolidation, EvoState still reaches 81.35% on Normal, above all tuned baselines. The paper does not explain how the many rule constants were chosen, so it remains unclear whether the gains generalize beyond these API environments.
Initial Response to Reviewer TCnD(Part 1/2)
Thank you for the reviewer’s specific suggestions regarding method distinctions and module responsibilities. We have added comparisons with existing methods, trajectory cases on the same tasks, and descriptions of the responsibilities of rules and LLMs, and have further clarified the scope of interpretation of the relevant ablation experiments.
W1. Differences from existing methods
The main distinction of EvoState is not simply the addition of structured memory or summarization, but the joint maintenance of changes in the validity of historical information, task completion conditions, and dependencies of subsequent actions, which are then used to assemble the next input.
For example, after a stage ends, the exact IDs obtained during that stage may still need to be reused across stages. When a new observation invalidates an old fact, its old value can still be retained as historical evidence, but is no longer prioritized as the current value. Task requirements, in turn, can only be discharged with matching evidence.
Table 7 in Appendix A.7 provides a functional comparison with existing methods. The core distinctions can be summarized as follows:
EvoState directly defines these operations as state-maintenance rules during execution, making this a dynamic process.
For the qualitative cases you suggested, we added two comparisons on the same tasks in Appendix G.7:
G.7.1: Subsequent use of an already-read song list.
In a note-update task involving 13 songs, Retrieval Memory had already read the target note, but the subsequently selected Actor input did not contain the note body. The trajectory then exhibited repeated searches and note reads, eventually passing 1/8 official checks. EvoState’s subsequent inputs retained the list of songs to process and the release-month information already obtained, eventually passing 8/8 checks while using 46.20% fewer total tokens than Retrieval Memory.
G.7.2: Reuse of song–playlist associations after a stage transition.
In a playlist-migration task involving 18 songs, HiAgent’s input after a subgoal transition did not directly provide the complete song–playlist mappings. The subsequent trajectory exhibited repeated logins, repeated file reads, and code and call errors, eventually passing 0/7 official checks. EvoState retained the required song list and relevant associations, completed the migration, and passed 7/7 checks while using 51.96% fewer total tokens than HiAgent.
The official checks, interaction counts, and token usage for both tasks are reported in Table 55. Because each method executes its own complete trajectory, we treat these only as qualitative comparisons.
In addition, Figure 6(c) in the main text compares progress rate and token usage for five methods at 202 identical execution states. Table 27 in Appendix C.3.4 includes the complete results, providing a controlled comparison with external methods independent of the above cases.
W2. Rule-based and LLM-based responsibilities
We have directly marked these responsibilities in §3.3–3.4 of the main text and listed them in full in Table 5 of Appendix A.5: