- Rating
- 4
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This project proposes Memory as Program (MemAP), a framework that changes how accumulated agent experience influences subsequent decisions. Rather than retrieving memory as textual context and leaving its behavioral effect to the LLM's in-context interpretation, MemAP represents past state–action–feedback experience through a programmable symbolic interface. Retrieved experience is then used to explicitly constrain candidate-action admissibility, compute return-grounded action values, and guide exploration when prior support is insufficient. The program state, including memory records, transferability relations, and decision thresholds, is further updated from interaction feedback while the executable decision functions remain fixed.
The paper evaluates MemAP primarily on WebArena and reports strong improvements over several memory-augmented and agent baselines. In particular, I found the repeated-error probe useful because it controls the available memory and isolates the difference between presenting failure experience as context and enforcing it through programmatic action filtering/scoring.
Critical strengths
- The problem formulation and central insight are interesting and important.
I find the distinction between memory as advisory context and memory as an explicit decision-control signal compelling. Many existing agent-memory approaches focus on what to store and how to retrieve it, while the behavioral effect of retrieved memory is still mediated by the LLM's interpretation. MemAP instead asks how memory can directly affect action admissibility and valuation. This is a clean and meaningful perspective on the memory–policy interface.
- The empirical improvements are substantial and are evaluated in realistic interactive agent environments.
The experiments involve actual browser-agent interaction in WebArena rather than only static natural-language prediction. The agent executes primitive browser actions, and task success is determined by the standard WebArena evaluator based on the final environment state. The reported gains are strong, including 61.9% success with GPT-4o and 68.7% with GPT-5.
- The repeated-error experiment is particularly informative.
The oracle-memory setup controls for retrieval and memory coverage, allowing the experiment to more directly test whether the same failure experience has a stronger behavioral effect when compiled into programmatic constraints rather than simply supplied as text. The large reduction in repeated-error rate provides strong evidence for the paper's central mechanism.
Critical weaknesses
- Hard programmatic gating may amplify errors in the memory construction pipeline, but robustness to such errors is insufficiently evaluated.
The main advantage of MemAP is that applicable memories become binding decision signals rather than advisory context. However, this also introduces a potentially important failure mode: if symbolic parsing, transferability estimation, or admissibility labeling is incorrect, an otherwise valid action may be incorrectly suppressed. The paper states that record-level returns and admissibility labels are assigned or revised by the reflection agent, so these quantities are themselves model-generated assessments rather than perfect ground truth.
For example, suppose an agent previously clicked "Submit" and the task failed because a required field had not been filled. If reflection incorrectly attributes the failure to the Submit action itself and marks it inadmissible in an overly broad symbolic context, future valid Submit actions could be filtered before the policy is allowed to reconsider them. In a contextual-memory system, the LLM might still recover from an imperfect memory by reasoning about the current state; under hard gating, an incorrect memory can instead become an enforced constraint.
The current repeated-error experiment convincingly shows the benefit of enforcing correct failure memories, but it does not test the complementary case in which the stored constraint is noisy or incorrect. I would like to see a robustness analysis under controlled noise, e.g., corrupted admissibility labels, symbolic parsing errors, or incorrect transferability relations. This seems especially important because the method effectively trades the under-enforcement problem of contextual memory for a potential over-enforcement problem when the memory itself is wrong.
- The paper does not provide a sufficiently complete end-to-end cost and latency analysis.
MemAP introduces additional machinery beyond a standard agent loop, including candidate-action generation, symbolic parsing, memory retrieval and maintenance, and trajectory-level reflection. While the filtering and scoring programs themselves may be computationally lightweight, maintaining the program state still relies on model-based parsing and reflection. The paper reports shorter successful browser trajectories in several experiments, but browser steps alone are not equivalent to inference or system cost. In particular, the paper does not systematically report:
- the number of LLM/API calls per task,
- input/output token consumption,
- end-to-end wall-clock latency,
- overhead of parsing and reflection,
- or total inference cost relative to the main baselines.
Therefore, it remains unclear whether MemAP's higher task success and shorter interaction trajectories come at a substantially larger inference budget. I do not think every baseline needs to be perfectly compute-matched, but an end-to-end system-cost comparison is important for understanding the practical trade-off introduced by this method.
Questions for authors
- How reliable is the programmatic action-filtering pipeline in practice?
In particular, can the authors quantify errors in symbolic parsing, transferability estimation, or admissibility labeling, and provide examples of cases where an incorrect memory causes a valid candidate action to be filtered? I think the authors should discuss deeply about it.
- What is the end-to-end computational overhead of MemAP compared with representative baselines?
Could the authors report LLM/API calls, input/output token consumption, and wall-clock latency per task? It would also be helpful to clarify how the k candidate actions are generated in practice, e.g., in a single model invocation or through multiple sampling calls.
- How should one think about the robustness–cost trade-off?
If additional LLM-based verification is needed to prevent incorrect hard gating, how much does this reduce the efficiency advantage or practical appeal of programmatic memory control?
I find the paper conceptually interesting and empirically promising. In particular, reframing memory from an advisory piece of context into an explicit control signal is a meaningful idea, and the realistic WebArena evaluation together with the repeated-error probe provides encouraging evidence for the proposed direction.
My main concerns are about the robustness of hard programmatic gating under imperfect memory or reflection, as well as the additional end-to-end computational overhead introduced by candidate generation, symbolic parsing, memory maintenance, and trajectory-level reflection.
Overall, I am currently willing to give this paper a Accept. However, the quality of the rebuttal will significantly affect my final assessment.
6 comments
Response to Reviewer 5EQ6 (Part 2)
Question 1(a): Reliability of the action-filtering pipeline in practice; quantifying errors in symbolic parsing, transferability estimation, and admissibility labeling
We appreciate the reviewer's rigor on the practical reliability of MemAP's pipeline. To quantify it in ordinary runs, we add a manual analysis of the errors in symbolic parsing, transferability estimation, and admissibility labeling. We find that errors from all three sources are infrequent (0.02 to 0.11 per task for each type, 0.30 in total), and most are repaired by reflection within the same run (66.7 to 100%).
We run MemAP on 100 randomly sampled WebArena shopping tasks in sequence with persistent memory, using GPT-4o and the same evaluator as in the paper. Two annotators independently check every logged record and transfer update against the page observations, with a third resolving disagreements, and their annotations are not fed back to the agent. An error counts as repaired when a later update corrects it within the run (criteria in Appendix A.10).
| Source | Error type | Errors per task↓ | Repaired (%)↑ |
|---|---|---|---|
| Admissibility labeling | Wrong label | ||
| Wrong return | |||
| Symbolic parsing | Over-broad context | ||
| Wrong entity type | |||
| Transferability estimation | Wrong transfer |
Errors found by the annotators in 100 tasks. Repaired: corrected by a later update within the same run.
(i) The most frequent error, a wrong label, is still infrequent and mostly repaired (first row). This is the case in the reviewer's "Submit" example.
(ii) Most errors are repaired without human feedback. Reflection revises a record when it conflicts with the stored observations. This repairs all wrong entity types and transfer relations, and about four in five wrong labels and returns.
(iii) Over-broad contexts are repaired least often, and they also affect success the least. Such a record is revised when a state it wrongly matches is visited, which may not occur within 100 tasks. Under poisoning, this condition keeps the highest success among the corrupted ones (Weakness 1, (ii)).
Each condition of the poisoning study injects 1.43 errors of one type per task, a heavier load than observed here (Weakness 1 & Question 1(b)). This suggests that the pipeline is reasonably reliable in practice, as its errors are infrequent, mostly repaired, and lighter than the load tested under poisoning.
We have added this analysis and its annotation criteria to the revised paper (Appendix A.10).
Response to Reviewer 5EQ6 (Part 3)
Weakness 2 & Question 2: End-to-end inference cost compared with the baselines, including LLM calls, input and output tokens, and wall-clock latency; overhead of parsing and reflection; how the candidate actions are generated
We appreciate the reviewer's attention to end-to-end cost. We add a full cost accounting against the baselines, and find that the LLM cost of memory in MemAP is a few parsing and reflection calls per task, and MemAP uses the fewest tokens per solved task.
We log every LLM call of each method on the same WebArena-Lite tasks, with GPT-4o and the same step budget, and exclude the benchmark evaluator for all methods. The candidate actions are generated in a single LLM call per step, not by repeated sampling.
| Method | LLM calls ↓ | Input tokens ↓ | Output tokens ↓ | Latency (s) ↓ | SR (%) ↑ | Tokens per solved task ↓ |
|---|---|---|---|---|---|---|
| ReAct | ||||||
| ASI | ||||||
| A-MEM | ||||||
| NesyProAct | ||||||
| MemAP |
Per-task averages. Tokens per solved task: total input and output tokens divided by the number of solved tasks.
(i) MemAP adds a moderate overhead over ReAct, ASI, and A-MEM, and is below NesyProAct. Compared with the first three, it makes more LLM calls (12.2 against 7.7 to 9.4), produces more output tokens (1,541 against 584 to 920), and takes slightly longer (33.44 s against 29.52 to 31.17 s), with input tokens within their range. Compared with NesyProAct, the strongest baseline and the other method that applies symbolic operations to candidate actions, it is lower in calls, tokens, and latency (fourth row), with higher success.
(ii) The LLM cost of memory is confined to parsing and reflection, as the programs call no LLM. Parsing and reflection take 5.3 calls and 22.1k tokens per task (table below). The programs run on CPU in 1.71 s of the 33.44 s per task. Proposing the candidate actions takes 6.9 calls per task, against 7.7 calls for ReAct.
| MemAP component | LLM calls | Tokens | Latency (s) |
|---|---|---|---|
| Parsing | |||
| Reflection |
(iii) Per solved task, MemAP uses the fewest tokens, as its higher success outweighs the overhead (125.1k against 218.5k to 592.7k, last column of the first table).
These figures include reflection, the step that revises incorrect memory (Question 3). This suggests that running memory as programs keeps its LLM cost to a few calls per task, which the gain in success outweighs.
We have added both tables to the revised paper (Appendix A.6).
Response to Reviewer 5EQ6 (Part 1)
We sincerely thank the reviewer for the careful review and the encouraging feedback. We also appreciate the insightful comments on robustness and end-to-end cost. We provide point-by-point responses below, including new results on both.
We appreciate the reviewer's careful analysis of this failure mode. As the reviewer points out, when a memory is wrong, hard gating can enforce the error, as in the "Submit" example. We respectfully note that such errors are infrequent in ordinary runs (0.30 per task;
Question 1(a)). When one occurs, the rejected candidate is linked to the record that rejected it, so the error can be traced. Since memory in MemAP is an evolving program, reflection can then revise the wrong record after the trajectory, when it conflicts with the stored observation, which keeps its operation reasonably robust.As suggested, we add a targeted poisoning study. On 60 previously solved WebArena shopping tasks with 86 critical decisions, we corrupt the memory behind every critical decision, one type of error at a time (1.43 errors per task, a deliberately severe setting). Following the three noise types suggested by the reviewer, we test five conditions: a wrong label and a wrong return for admissibility labeling (†), an over-broad context and a wrong entity type for symbolic parsing (‡), and inverted weights for transferability relations (§). We then run three consecutive rounds with persistent memory, with and without reflection, using GPT-4o and the same evaluator as in the paper.
Each cell reports task success (%), round 1 → round 3. † Labels and returns: the correct action is relabeled inadmissible, or its return is set to failure (86 of 322 records, 26.7% in each case). ‡ Symbolic parsing: one predicate is dropped from each entity, so that a record matches 1.2 additional contexts on average, or its entity types are replaced with random types (86 of 322 records, 26.7%, in each case) § Transferability relations: transfer weights are inverted (28 of 33 learned cells).
Overall, an incorrect memory lowers success when it is first encountered and is largely corrected as the program evolves. By round 3, success under every corruption is back to 88.3 or above, whereas without reflection it shows little recovery (first row).
(i) Incorrect labels and returns have the largest effect at first and are mostly corrected. A wrong label is the reviewer's "Submit" example, where FC removes a valid action before scoring. A wrong return costs less, as the action remains admissible. By round 3, reflection has revised 89.5% of the corrupted labels and 87.2% of the corrupted returns.
(ii) Symbolic parsing errors have a smaller effect and also recover. These errors change which records a state matches, while the labels and returns in the records stay correct. Reflection narrows the over-broad records (from 1.2 to 0.7 additional contexts) and re-types 92.8% of the retrieved records with a wrong entity type.
(iii) Incorrect transferability relations recover through exploration. An inverted relation usually retrieves no experience, so the agent explores, and the resulting outcomes re-estimate the relation (weight error from 0.43 to 0.14).
(iv) A valid action filtered by an incorrect memory is restored once reflection revises the record, as in the following example (
Question 1(b)). In the task "What is the price range of teeth grinding mouth guard in the One Stop Market?", we mark the required click on "Search" as inadmissible. FC rejects the click in round 1 and the task fails. Reflection finds that the stored observation shows the same click loading the search results and restores the label, and the task succeeds in round 2.With hard gating, an error enforced from an incorrect memory is mostly revised within three rounds. With contextual memory, an error from ignoring a correct memory can recur across tasks (repeated-error rate of 0.106 for A-MEM with correct failure records, Table 5). This suggests that, in the trade-off raised by the reviewer, hard gating in MemAP replaces a recurring error with one that is infrequent and revised as the program evolves.
We have added this study to the revised paper (Appendix A.10).