acceptodds
Under review as a conference paper at ICLR 2027

Memory as Program: Should Agents Run Their Experience Instead of Rereading It?

Abstract

Memory allows LLM agents to carry experience from past interactions into new situations, where earlier successes and failures can inform their decisions. Yet many systems supply retrieved memories as context, leaving their influence on action selection to the model's interpretation. Memory used this way remains advisory, suggesting what to do without explicitly determining action admissibility or candidate values. We introduce **Memory as Program (MemAP)**, a framework that expresses an agent's control policy through executable programs configured by accumulated experience. MemAP exposes memory traces through a programmable symbolic interface, allowing executable programs to compare their decision contexts and use the associated feedback. During execution, these programs retrieve transferable experience, compute return-grounded action values, and enforce admissibility constraints, using novelty to guide exploration when return support is insufficient. Interaction feedback updates MemAP's program state, revising where stored experience applies and how it influences subsequent decisions while leaving program definitions fixed. On WebArena, MemAP achieves 61.9% success with GPT-4o, outperforming the evaluated memory-based baselines in overall success, and reaches 68.7% with GPT-5. Ablations also show that executing the same experience outperforms contextual reuse and that program-state adaptation further improves success. MemAP also better preserves transferable-precedent retrieval as memory grows, achieving twice A-MEM's Hit@5 at the largest tested scale, and reuses fixed source-site memory on held-out real-world websites with higher success and shorter successful trajectories than A-MEM.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Agentic Memory, Neuro-Symbolic Agent Control, Web Agents

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_5EQ6OpenReview ↗
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
  1. 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.

  1. 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.

  1. 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
  1. 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.

  1. 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
  1. 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.

  1. 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.

  1. 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
AuthorsOpenReview ↗

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.


Weakness 1 & Question 1(b): Robustness of hard programmatic gating under controlled noise in admissibility labels, symbolic parsing, and transferability relations; examples of an incorrect memory filtering a valid action

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.

MethodClean memoryWrong label †Wrong return †Over-broad context ‡Wrong entity type ‡Wrong transfer §
MemAP w/o reflection91.7→90.091.7 \rightarrow 90.06.7→6.76.7 \rightarrow 6.713.3→30.013.3 \rightarrow 30.080.0→81.780.0 \rightarrow 81.775.0→66.775.0 \rightarrow 66.751.7→53.351.7 \rightarrow 53.3
MemAP (full)98.3→100.098.3 \rightarrow 100.023.3→88.323.3 \rightarrow 88.348.3→90.048.3 \rightarrow 90.086.7→96.786.7 \rightarrow 96.783.3→95.083.3 \rightarrow 95.061.7→90.061.7 \rightarrow 90.0

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 FCF_C 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. FCF_C 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).

AuthorsOpenReview ↗

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).

SourceError typeErrors per task↓Repaired (%)↑
Admissibility labelingWrong label0.110.1181.881.8
Wrong return0.050.0580.080.0
Symbolic parsingOver-broad context0.090.0966.766.7
Wrong entity type0.020.02100100
Transferability estimationWrong transfer0.030.03100100

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).

AuthorsOpenReview ↗

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 kk 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 k=5k=5 candidate actions are generated in a single LLM call per step, not by repeated sampling.

MethodLLM calls ↓Input tokens ↓Output tokens ↓Latency (s) ↓SR (%) ↑Tokens per solved task ↓
ReAct7.7\mathbf{7.7}53.7k\mathbf{53.7k}584\mathbf{584}31.1731.1711.511.5472.0k472.0k
ASI8.98.992.8k92.8k84184129.52\mathbf{29.52}15.815.8592.7k592.7k
A-MEM9.49.465.3k65.3k92092030.8030.8030.330.3218.5k218.5k
NesyProAct20.320.3104.2k104.2k2,9262{,}92661.1961.1944.244.2242.4k242.4k
MemAP12.212.270.9k70.9k1,5411{,}54133.4433.4457.9\mathbf{57.9}125.1k\mathbf{125.1k}

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 componentLLM callsTokensLatency (s)
Parsing2.82.85.17k5.17k2.042.04
Reflection2.52.516.94k16.94k3.283.28

(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).

Reviewer_KhbxOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Memory as Program (MemAP), a framework that allows accumulated agent experience to directly influence action selection rather than being provided only as textual context. MemAP represents past experience using structured records of decision contexts, actions, feedback, and admissibility information. It then uses executable programs to retrieve transferable experiences, filter inadmissible actions, estimate action values from historical returns, and guide exploration. The system also updates its memory records, transferability relations, and decision thresholds based on interaction feedback, while keeping the underlying program definitions fixed. Experiments on WebArena show competitive performance, and additional studies demonstrate improvements in retrieval robustness, repeated-error prevention, and transfer to unseen websites. The ablations also suggest that executable memory control is more effective than simply providing the same experience as context.

Critical strengths
  1. The paper explores an interesting direction for agent memory. I agree with the motivation that retrieving a useful memory does not guarantee that an LLM will apply it correctly. Making the influence of memory on action selection more explicit is a promising approach.

  2. The proposed framework is relatively interpretable. Representing experience through structured contexts, actions, and outcomes makes it easier to understand how previous interactions affect current decisions. I particularly like the distinction between action admissibility and action valuation.

  3. The empirical results are strong overall. MemAP achieves competitive performance on WebArena and shows improvements in retrieval robustness as the memory bank grows. The additional evaluation on held-out websites also provides some evidence of transfer beyond the original environment.

  4. The ablation experiments are useful, especially the comparison between executable memory and memory provided as context. I also find the repeated-error experiment convincing, as it directly tests whether the system can avoid actions that are known to have failed in similar situations.

Critical weaknesses
  1. I am not entirely convinced about the algorithmic novelty of the proposed framework. Several components, including structural retrieval, action filtering, return-based action scoring, and novelty-guided exploration, are closely related to existing ideas in symbolic planning and experience-based decision making. The paper could better explain what is fundamentally new beyond combining these mechanisms into a memory system.

  2. The approach may be sensitive to incorrect historical feedback or symbolic matching. Since the system can explicitly exclude actions based on previous inadmissibility labels, an incorrect memory or an overly broad context match could prevent the agent from taking a valid action. This failure mode is not sufficiently evaluated.

  3. The memory-as-context ablation is informative, but it may not fully isolate the benefit of program execution. The contextual baseline no longer applies explicit constraints or action-value computations. It would be useful to compare against an agent that receives the same structured information and is explicitly instructed to perform these operations in context.

  4. The method relies on a structured representation of states and candidate actions. It is unclear how easily this approach generalizes to more open-ended agent tasks where the symbolic structure is difficult to identify or the action space is large and dynamic. The held-out website experiments are encouraging, but remain relatively limited in scale.

Questions for authors

see weaknesses above.

5 comments
AuthorsOpenReview ↗

Response to Reviewer Khbx (Part 1)

We thank the reviewer for the careful and constructive review, and for engaging closely with the motivation behind MemAP. In response, we sharpen the statement of what MemAP contributes, test it under incorrect memory, extend the memory-as-context ablation as suggested by the reviewer, and broaden the held-out evaluation to 300 tasks on the Online-Mind2Web benchmark. Please find our point-by-point responses below.


Weakness 1: Algorithmic novelty of structural retrieval, action filtering, return-based action scoring, and novelty-guided exploration relative to symbolic planning and experience-based decision making; what is new beyond combining them

We appreciate this point. MemAP addresses a central question: how can an agent run its experience instead of rereading it? Answering it requires memory to settle four things at each decision, namely which experience applies, which actions are ruled out, which action is preferred, and what to do when evidence is missing. The four components noted by the reviewer, rooted in symbolic planning and experience-based decision making, answer these in turn, retrieve →\rightarrow filter →\rightarrow score →\rightarrow explore. Our claimed contribution is not an advance in any individual step, but formulating them as one executable procedure that turns experience from text to be reread into memory as programs, which remain evolvable as experience accumulates.

This formulation draws on symbolic planning and experience-based decision making for its operations, and has, to our knowledge, not been explored in either line of work. Symbolic planning typically operates on a domain model specified in advance. Experience-based decision making typically absorbs experience into a value function or policy through training, and LLM agents largely reuse it by rereading it in context. MemAP parses the agent's text trajectories into step-level symbolic records, whose representation and transfer relations are both revised from feedback. From these records it builds the admissibility gates and score functions that decide each action, with constraints that bind at each decision yet remain defeasible (Weakness 2). With no domain model and no training, MemAP evolves its programs directly from the agent's own experience, which meaningfully extends this use of experience to unseen live websites, starting from an empty memory (Weakness 4).

Our work further offers evidence that running memory as programs makes the use of experience more precise and more transferable. (i) Retrieval stays precise as the memory grows (Hit@5 from 0.977 to 0.840 over 59 to 2,325 experiences, against 0.773 to 0.417 for the rereading baseline A-MEM, Figure 3). (ii) Cross-site generalization holds from Shopping to Amazon and Target (Table 2). (iii) Repeated errors are largely prevented (rate of 0.003, against 0.106 for A-MEM, Table 5). (iv) The success rate nearly doubles that of an agent applying the same structured information in context (57.9 against 29.1, Weakness 3). (v) The steps also depend on one another, as FCF_C and FVF_V together add 30.6pp over the variant with neither, more than the sum of their separate gains (13.6pp and 7.2pp; see our response to Reviewer p8xN, Question 3). Our paper thus brings the insight that the same experience yields more when it is run as programs than when it is reread.

What MemAP offers is a programmable, memory-induced policy. Its admissible action sets, transferability relations, and estimated returns are explicit objects learned from experience, so each can be inspected and corrected, which paves the way toward more auditable and governable agent control.

Following the reviewer's suggestion, we have revised Section 2 to position MemAP relative to symbolic planning and experience-based decision making along these lines.

AuthorsOpenReview ↗

Response to Reviewer Khbx (Part 2)

Weakness 2: Sensitivity to incorrect historical feedback or symbolic matching, where previous inadmissibility labels or an overly broad context match could prevent a valid action; evaluation of this failure mode

We appreciate this point, and the scenario described by the reviewer can occur. An incorrect memory can exclude a valid action when it is first encountered, but the exclusion is explicit, so it can be traced to the record that caused it and corrected. Each action rejected by FCF_C is linked to the record responsible for the rejection. The reflection step receives both, and revises the record when it conflicts with the stored observation.

To evaluate this failure mode, we add a targeted poisoning study on 60 previously solved WebArena shopping tasks with 86 critical decisions. Each condition corrupts the memory behind every critical decision, a deliberately severe setting. We run three consecutive rounds with persistent memory, with and without reflection.

MethodClean memoryWrong label †Wrong return †Over-broad context ‡Wrong entity type ‡Wrong transfer ‡
MemAP w/o reflection91.7→90.091.7 \rightarrow 90.06.7→6.76.7 \rightarrow 6.713.3→30.013.3 \rightarrow 30.080.0→81.780.0 \rightarrow 81.775.0→66.775.0 \rightarrow 66.751.7→53.351.7 \rightarrow 53.3
MemAP (full)98.3→100.098.3 \rightarrow 100.023.3→88.323.3 \rightarrow 88.348.3→90.048.3 \rightarrow 90.086.7→96.786.7 \rightarrow 96.783.3→95.083.3 \rightarrow 95.061.7→90.061.7 \rightarrow 90.0

Task success (%), round 1 → round 3. † Incorrect historical feedback: the label of the correct action is changed to inadmissible, or its return to failure (86 of 322 records each). ‡ Symbolic matching: a predicate is removed so that a record matches 1.2 additional contexts on average, entity types are replaced (86 records each), or transfer weights are inverted (28 of 33 learned cells).

Overall, task performance largely recovers within three rounds (88.3 to 96.7 by round 3, against 6.7 to 81.7 without reflection).

(i) Incorrect historical feedback has the largest effect at first and is mostly corrected (23.3 to 88.3 for wrong labels). By round 3, 89.5% of the corrupted labels and 87.2% of the corrupted returns have been revised. Without reflection, a wrong label is not corrected (6.7 in all rounds).

(ii) Symbolic matching errors have a smaller effect and also recover (61.7 to 86.7 in round 1, 90.0 to 96.7 by round 3). The additional contexts matched by a corrupted record fall from 1.2 to 0.7, and 92.8% of the retrieved records with a wrong entity type are re-typed.

(iii) A valid action excluded by an incorrect label is restored once reflection revises the record, as in the following example. In one task, we mark the required click on "Search" as inadmissible. FCF_C rejects it in round 1 and the task fails. Reflection finds that the stored observation shows the same click loading the results, corrects the label, and the task succeeds in round 2.

This suggests that MemAP is sensitive to an incorrect memory for a limited time, since its records are explicit and reflection revises most of the errors. We have added this study to the revised paper (Appendix A.10).

AuthorsOpenReview ↗

Response to Reviewer Khbx (Part 3)

Weakness 3: Extending the memory-as-context ablation to compare against an agent that receives the same structured information and is explicitly instructed to perform these operations in context

We appreciate the reviewer's rigor in examining this ablation. As the reviewer notes, the Memory-as-Context baseline does not apply the constraints or action-value computations carried out by the programs. As suggested, we add three baselines that separate the effects of applying the constraints and computing the action values in context rather than as programs. In each, the agent receives the same structured information and is explicitly instructed to perform these operations in context. The table below reports their results on WebArena-Lite, under the same setting as Table 3.

Constraints (FCF_C)Action values (FVF_V,FNF_N)SR(%)↑Constraint violations(%)↓Top-1 agreement(%)↑
🆕in contextin context29.129.16.36.391.791.7
🆕in contextprogram33.933.95.75.7100100
🆕programin context50.350.30095.995.9
programprogram57.9\mathbf{57.9}00100100

🆕 marks the new baselines added in the rebuttal, and the last row is the full MemAP.

Overall, executing constraints and action values as programs adds 28.8pp over performing them in context (57.9 vs. 29.1). Compared with the original Memory as Context (22.7, Table 3), providing the structured information and explicit instructions in context adds 6.4pp.

(i) Executing the constraints as programs brings the larger gain (29.1 to 50.3), and executing the action values a smaller one (29.1 to 33.9). In context, a constraint is one more instruction that the agent weighs against its own preference, and the action it excludes is one the agent once preferred. An agent that overrides the constraint repeats a failure already recorded, while a misranked action is still admissible and may succeed.

(ii) Executing both as programs removes the deviations seen in context (0% violations and 100% agreement). In context, the agent executes an excluded action in 5.7 to 6.3% of the decisions where a constraint applies, matches the program's top-ranked action in 91.7 to 95.9%, and follows the exploit/explore rule in 85.8%.

(iii) Executing the action values as programs also saves LLM calls and time. Computing the action values in context adds 7.2 LLM calls and 15.9 s of LLM time per task to the cost of the full MemAP (cost analysis in Appendix A.9).

In long-horizon execution, small per-step deviations compound into task failure. This suggests that executing memory through programs contributes meaningfully beyond providing the same information in context.

We have added these results to the ablation section of the revised paper(Section 4.4 and Appendix A.9).

Reviewer_p8xNOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes an additional programmable interface between an agent’s memory and its decision making. MemAP mainly helps the agent to decide the next action by parsing the interactions into symbolic records and uses the fixed function to do the decision making. There are three main steps, retrieving similar experiences and banning the failure action based on the memory, scoring the remaining actions by rewards from the function, and exploring less familiar actions. After the execution, it updates the memory records. The paper claims this is more effective than context-based memory. It is validated mainly on WebArena.

Critical strengths

The experiment results show that there is a clear and significant advantage over context-based memory, which supports the main claim of the paper.

Critical weaknesses

The experiments do not show the advantage of the proposed MemAP over other neuro-symbolic frameworks. At Table 1, all the baseline methods only have the result of one LLM backbone and most of them are GPT-4o. However, the paper claims that “MemAP achieves the highest overall success rate among the evaluated methods under both GPT-4o and GPT-5” and this claims might be too strong given the experimental setup. In particular, the paper only takes NesyProAct as the only other neuro-symbolic framework among the baselines and I think that it is the most direct comparison for the advantage of MemAP. However, the paper only provides the result for GPT-4o and there is no GPT-5 result on it. The same weakness appears in other analysis experiments, the memory-growth stress test, the repeated failure test, and the cross-website generalization. These experiments only compare with context-based methods without any neuro-symbolic baseline. I think it would be great if the paper can show more advantages when comparing to other neuro symbolic frameworks.

Questions for authors
  1. What are the average LLM calls and token cost per step, compared with the baselines? Such as parsing, reflection llms…
  2. Does the parser and reflection also use the same backbone model? Does it affect the performance if the parser and reflection use a weaker model?
  3. How does MemAP compare with a simple gating method of blocking failure action? The separate contributions of F_C and F_V remain unclear.
  4. What is the no-memory result in WebArena-Lite? In Table 4, is the cold-start SR the result of no memory? If so, why do the ablated variants perform worse than having no memory at all?
6 comments
AuthorsOpenReview ↗

Response to Reviewer p8xN (Part1)

We thank the reviewer for the constructive review, which helps sharpen the positioning of MemAP among neuro-symbolic frameworks. We provide additional comparisons with neuro-symbolic baselines under the suggested GPT-5 backbone and across our analysis experiments, together with analyses of cost, model sensitivity, and component contributions. Please find our point-by-point responses below.


Weakness 1: Comparison with other neuro-symbolic frameworks, including NesyProAct under GPT-5; scope of the "highest under both GPT-4o and GPT-5" claim

We appreciate the reviewer's rigor on the comparison with neuro-symbolic frameworks, and the suggested evaluation of NesyProAct under GPT-5. We provide a side-by-side evaluation of MemAP with NesyProAct [1] and a second neuro-symbolic framework, NSI [2], under GPT-5 on WebArena-Lite. NesyProAct and NSI keep what they learn in a skill library, whereas MemAP keeps every step as a record and uses these records to filter and score each candidate action.

Method (GPT-5)GitLabMapRedditShoppingAdminWikiOverall
NesyProAct [1]47.847.841.741.752.5\mathbf{52.5}54.554.548.648.633.333.349.149.1
NSI [2]63.3\mathbf{63.3}50.050.042.142.153.353.337.137.133.333.349.749.7
MemAP\color{#1F4E79}{\textbf{MemAP}}53.1\color{#1F4E79}{53.1}64.3\color{#1F4E79}{\mathbf{64.3}}42.9\color{#1F4E79}{42.9}76.1\color{#1F4E79}{\mathbf{76.1}}62.9\color{#1F4E79}{\mathbf{62.9}}66.7\color{#1F4E79}{\mathbf{66.7}}62.4(+12.7)\color{#1F4E79}{\mathbf{62.4}_{(+12.7)}}

MemAP outperforms both neuro-symbolic frameworks in overall success rate, by 13.3pp over NesyProAct and 12.7pp over NSI. This gap mainly stems from how MemAP uses its experience. Failed and successful attempts are both recorded and both used at decision time: recorded failures exclude actions, and recorded returns rank the remaining ones (see Question 3 for their separate contributions). The repeated-failure test under Weakness 2 is consistent with this account: given the same failure records, NesyProAct repeats a recorded failure in 4.2% of selections, and MemAP in 0.3%.

In addition, we note that NSI also evolves its skill library, with skill graphs honed after failures. MemAP's memory evolves online and at a finer grain: after each trajectory, reflection revises the individual records, their transfer relations, and the reuse thresholds.

We have carefully revised the claim on overall success rate in Section 4.2 to refer to the methods evaluated under each backbone, and we will add the full-WebArena GPT-5 results for NesyProAct and NSI to Table 1 in the final version.

[1] NesyProAct: Proactive Neuro-Symbolic Control for Web Agents. NeurIPS 2026.

[2] Lifting Traces to Logic: Programmatic Skill Induction with Neuro-Symbolic Learning for Long-Horizon Agentic Tasks. ICML 2026.

AuthorsOpenReview ↗

Response to Reviewer p8xN (Part 2)

Weakness 2: Comparison with neuro-symbolic baseline in the analysis experiments (memory-growth stress test, repeated-failure test, cross-website generalization)

We have added the neuro-symbolic baseline NesyProAct to all three analysis experiments, under the same settings as in the paper.

(i) Memory-growth stress test. This test measures whether the relevant experience is retrieved in the top 5 (Hit@5) as the memory grows, at four of the sizes plotted in Figure 3:

Memory size (experiences)592849592,325
Dense RAG0.7950.7950.6850.6850.5830.5830.5060.506
A-MEM0.7730.7730.6660.6660.5340.5340.4170.417
NesyProAct0.2270.2270.2320.2320.2230.2230.2230.223
MemAP (ours)\color{#1F4E79}{\textbf{MemAP (ours)}}0.977\color{#1F4E79}{\mathbf{0.977}}0.909\color{#1F4E79}{\mathbf{0.909}}0.891\color{#1F4E79}{\mathbf{0.891}}0.840\color{#1F4E79}{\mathbf{0.840}}

Compared with both the context-based baselines and NesyProAct, MemAP keeps the highest Hit@5 and declines slowly as the memory grows (0.977 to 0.840). Dense RAG and A-MEM decline more than twice as fast, and NesyProAct is insensitive to memory growth but stays at a lower level. These trends mainly stem from what each memory stores. Dense RAG and A-MEM store text and retrieve it by text similarity, which buries the relevant experience under similar-looking entries as the memory grows. NesyProAct stores skills that apply only when their preconditions match the current state, so its retrieval holds for a small share of the queries, and does not change with the memory size. MemAP stores each step as a separate record and matches records by symbolic structure rather than by text, which keeps the relevant experience distinct from similar-looking entries as the memory grows.

(ii) Repeated-failure test. This test gives all methods the same oracle failure records and measures how often the agent repeats a previously failed action. Since most repeats occur at a subset of decision points, we report the rate over all points and over the repeat-prone points, where the agent without memory repeats the failed action in at least 3 of 5 queries:

Repeated-failure testAll pointsRepeat-prone points
No memory0.2680.2680.9650.965
A-MEM0.1060.1060.3060.306
NesyProAct0.0420.0420.1530.153
MemAP (ours)\color{#1F4E79}{\textbf{MemAP (ours)}}0.003\color{#1F4E79}{\mathbf{0.003}}0.012\color{#1F4E79}{\mathbf{0.012}}

MemAP exhibits the lowest repeated-error rate (0.003 vs. 0.042 for NesyProAct). A-MEM and NesyProAct reduce repeats overall, but most of what remains falls on the repeat-prone points. Both leave the final choice to the LLM, which receives the failure records as prompt text or through a repair step and can still follow its own preference. MemAP makes the final choice in its programs, which filter out actions recorded as failed in the same context and rank the rest by estimated return, so its rate stays close to zero on the repeat-prone points as well (0.012).

(iii) Cross-website generalization. This experiment evaluates each method on Amazon and Target tasks using the memory it built on WebArena Shopping:

Cross-websiteShopping →\rightarrow Amazon SR (%)Shopping →\rightarrow Target SR (%)
No memory5.15.113.913.9
A-MEM15.415.411.111.1
NesyProAct12.812.813.913.9
MemAP (ours)\color{#1F4E79}{\textbf{MemAP (ours)}}25.6\color{#1F4E79}{\mathbf{25.6}}19.4\color{#1F4E79}{\mathbf{19.4}}

MemAP gains the most from Shopping memory on both websites (25.6 vs. 12.8 for NesyProAct on Amazon, 19.4 vs. 13.9 on Target). A-MEM and NesyProAct gain less on Amazon and show no gain on Target. A-MEM reuses experience by text similarity, and NesyProAct only when a skill's preconditions exactly match the current state. Both conditions are met less often on a new website. MemAP's transferability graph links states by symbolic structure, so Shopping experience is reused wherever the new website has a state with a similar structure.

We have added the additional results to Figure 3, Table 5, and Table 2.

AuthorsOpenReview ↗

Response to Reviewer p8xN (Part 3)

Question 1: Average LLM calls and token cost per step compared with the baselines

We provide a cost profile of every LLM call made by MemAP and the baselines, measured on WebArena-Lite with the same GPT-4o backbone and step budget.

(i) Cost per step and success rate

Cost per stepLLM calls ↓Tokens ↓SR (%) ↑
ReAct1.01.07.1k7.1\mathrm{k}11.511.5
ASI1.41.414.2k14.2\mathrm{k}15.815.8
A-MEM1.31.39.0k9.0\mathrm{k}30.330.3
NesyProAct2.52.513.1k13.1\mathrm{k}44.244.2
MemAP (ours)\color{#1F4E79}{\textbf{MemAP (ours)}}1.8\color{#1F4E79}{1.8}10.5k\color{#1F4E79}{10.5\mathrm{k}}57.9\color{#1F4E79}{57.9}
   ↳ parsing0.41\color{#1F4E79}{0.41}0.7k\color{#1F4E79}{0.7\mathrm{k}}
   ↳ reflection0.36\color{#1F4E79}{0.36}2.5k\color{#1F4E79}{2.5\mathrm{k}}

MemAP uses 1.8 LLM calls and 10.5k tokens per step, of which parsing and reflection take 0.41 and 0.36 calls. The policy remains the main cost (about 70% of the tokens per step), parsing is lightweight (about 7%), and reflection is infrequent (about 23%). Both are invoked per task rather than at every step, so the per-step figures are averages over steps.

(ii) Cost per task (non-policy: all LLM calls besides the policy)

Cost per taskPolicy tokens ↓Non-policy calls ↓Non-policy tokens ↓Latency (s) ↓
ReAct54.3k54.3\mathrm{k}000031.1731.17
ASI88.3k88.3\mathrm{k}2.32.35.4k5.4\mathrm{k}29.5229.52
A-MEM61.5k61.5\mathrm{k}2.02.04.7k4.7\mathrm{k}30.8030.80
NesyProAct52.1k52.1\mathrm{k}12.112.155.0k55.0\mathrm{k}61.1961.19
MemAP (ours)\color{#1F4E79}{\textbf{MemAP (ours)}}50.3k\color{#1F4E79}{50.3\mathrm{k}}5.3\color{#1F4E79}{5.3}22.1k\color{#1F4E79}{22.1\mathrm{k}}33.44\color{#1F4E79}{33.44}
   ↳ parsing↳2.8\color{#1F4E79}{↳2.8}↳5.2k\color{#1F4E79}{↳5.2\mathrm{k}}
   ↳ reflection↳2.5\color{#1F4E79}{↳2.5}↳16.9k\color{#1F4E79}{↳16.9\mathrm{k}}

MemAP uses fewer LLM calls and tokens than the neuro-symbolic baseline NesyProAct, and its token cost and latency are comparable to those of ASI and A-MEM, while its success rate is the highest. Compared with NesyProAct, it uses 1.8 vs. 2.5 LLM calls and 10.5k vs. 13.1k tokens per step. Its retrieval, filtering, and scoring are executed by programs without LLM calls, so parsing and reflection are its only non-policy calls. Per task, it makes 56.2% fewer non-policy calls than NesyProAct, uses 59.8% fewer non-policy tokens, and takes 45.4% less time. Compared with ASI and A-MEM, it only makes 0.4–0.5 more LLM calls per step, with tokens per step between theirs and latency per task within 4 s of theirs.

We have added this cost analysis to the revised paper (Appendix A.6).


Question 2: Do the parser and reflection use the same backbone? Does a weaker parser/reflection model hurt performance?

Yes, in all reported experiments the parser and reflection use the same backbone as the policy (GPT-4o in the GPT-4o setting, GPT-5 in the GPT-5 setting).

We provide a sensitivity test with a weaker model, as suggested: the policy stays at GPT-4o, and the parser, reflection, or both are replaced by GPT-4o-mini.

Parser VariantParserReflectionSR (%) on WebArena-Lite
DefaultGPT-4oGPT-4o57.9
Weaker parserGPT-4o-miniGPT-4o49.1(−8.8)49.1_{(-8.8)}
Weaker reflectionGPT-4oGPT-4o-mini54.5(−3.4)54.5_{(-3.4)}
Both weakerGPT-4o-miniGPT-4o-mini45.5(−12.4)45.5_{(-12.4)}

Weaker parser and reflection models reduce performance only moderately (−8.8pp and −3.4pp). With both replaced by GPT-4o-mini, MemAP stays at the level of the strongest baseline (45.5 vs. 44.2 for NesyProAct) and above every ablation that removes a component (at most 40.9). The parser matters more because it produces the symbolic interface that every program reads, so its errors enter each decision. Reflection writes the records used later, and a wrong record can be revised by later trajectories.

We have added this analysis to the revised paper (Appendix A.7).

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Author-Reviewer Discussion

Dear Area Chair and all Reviewers,

We sincerely thank you for your time and effort in evaluating our submission, and for the constructive feedback that has helped us improve this work. As the author-reviewer discussion concludes, we would like to provide a brief summary of the discussion and of the main updates.

Post-rebuttal, the reviewer assessments moved in a positive direction:

  • Reviewer p8xN (Rating 2 → 3): noted that the additional neuro-symbolic comparisons "show that MemAP has clear advantages among these methods," and raised the score to 3.

  • Reviewer 5EQ6 (Rating 4): noted that the rebuttal has resolved most of the questions, and maintains the assessment of clear acceptance.

  • Reviewer Khbx (Rating 3): is supportive of our paper, finding the empirical results "strong overall", and raised no further concern after our responses.

Across reviews, the recognized strengths include:

  1. An important problem formulation and central insight. The reviewers agree with the motivation that "retrieving a useful memory does not guarantee that an LLM will apply it correctly" (Khbx). The distinction between memory as advisory context and memory as an explicit decision-control signal is found "compelling", and described as "a clean and meaningful perspective on the memory–policy interface" (5EQ6). Making the influence of memory on action selection explicit is regarded as "a promising approach" (Khbx).

  2. An interpretable framework. Representing experience through structured contexts, actions, and outcomes "makes it easier to understand how previous interactions affect current decisions", and the distinction between action admissibility and action valuation is particularly appreciated (Khbx).

  3. Substantial empirical improvements in realistic interactive environments. The results show "a clear and significant advantage over context-based memory, which supports the main claim of the paper" (p8xN). The gains are considered strong and are obtained with actual browser-agent interaction on WebArena rather than static prediction (5EQ6), together with improved retrieval robustness as the memory grows and evidence of transfer to held-out websites (Khbx).

  4. Informative analysis experiments that isolate the central mechanism. The repeated-error experiment is found "convincing" (Khbx) and "particularly informative", as its oracle-memory setup controls for retrieval and memory coverage and "provides strong evidence for the paper's central mechanism" (5EQ6). The ablation comparing executable memory with memory provided as context is also considered useful (Khbx).

We summarize the key updates below that significantly strengthen the paper:

  1. MemAP outperforms other neuro-symbolic frameworks under the same backbone. With GPT-5, it reaches 62.4, against 49.1 for NesyProAct and 49.7 for NSI (p8xN).

  2. MemAP is robust to incorrect memory. Reflection revises the corrupted records, and success recovers to 88.3–96.7 within three rounds (Khbx, 5EQ6).

  3. Executing memory as programs contributes beyond providing the same information in context. MemAP reaches 57.9, against 29.1 for an agent instructed to perform the same operations in context (Khbx).

  4. MemAP is cost-efficient. It uses the fewest tokens per solved task among the compared methods (125.1k, against 242.4k for NesyProAct) (p8xN, 5EQ6).

  5. MemAP generalizes to open-ended tasks on live websites. On Online-Mind2Web, it reaches 32.3, against 27.0 for NesyProAct (Khbx).

These results and the corresponding discussions have been incorporated into the revised paper, and we believe the revision will be a valuable contribution to the ICLR community.

We hope this summary is helpful. Once again, we thank the Area Chair and all the reviewers for the thoughtful evaluation and for helping us improve this work.

With best wishes,

The authors of Paper 36637

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.