RoMeRL: Balancing Feedback Coverage and the Memory-Reward Trap in Self-Evolving Agent Memory via Reduced-Order Utility States

arXiv:2608.025082026-08-03

A fix for LLM agents whose growing memory dilutes feedback and lets irrelevant experiences get rewarded by mistake

Self-evolving LLM agents store past experiences as memories and learn a usefulness score for each, but as experience accumulates the number of scores to learn keeps growing, spreading feedback thin and letting shared task rewards mistakenly credit irrelevant memories — the 'memory-reward trap.' RoMeRL fixes this by replacing the ever-growing per-trajectory scores with just four fixed slots per task, organized by outcome polarity and memory dynamics. Across ALFWorld and LifelongAgentBench, this raised task performance while cutting cold-start memories, memory size, and LLM calls.

METAL LAB explanatory visual

RoMeRL: compressing growing memory into four fixed slots

Evidence statusMeasured results reported

The problemEach stored trajectory gets its own utility score, so the score space keeps growing with experience, and shared task rewards mistakenly credit irrelevant co-retrieved memories
Four fixed coordinatesCrossing success/failure with representative/recent-change gives four slots: PCC (best successful case), PAC (first success after failure), NCC (informative failure), NAC (most recent failure)
Online update and replacementNew experiences update or replace the content of the relevant slot, inheriting the prior utility score as a warm start instead of creating a new permanent variable
Theoretical basisFewer coordinates means more average feedback per coordinate, and a contamination-cleanup transition model bounds how much erroneous state can persist
Measured effectsOn ALFWorld and LifelongAgentBench: higher success rate, 80.0% lower Cold-Q ratio, about 6.0x higher feedback density, 84.4% smaller memory, 21.1% fewer LLM calls

An explanatory diagram made by METAL LAB, not a figure supplied by the paper's authors.

What they did

Problem: existing learning-based memory systems assign a separate utility score to every stored trajectory; as experience grows, this utility space keeps expanding, so limited feedback gets spread over an ever-larger set of memories.
Memory-reward trap: because a single task-level reward is jointly assigned to all memories retrieved together for that task, memories that made no real contribution can still receive positive updates and persist.
Method: RoMeRL keeps only four fixed 'semantic coordinates' per task — crossing outcome polarity (success/failure) with memory dynamics (consolidated representative vs. recent adaptive change) — named PCC, PAC, NCC, NAC, and updates or replaces their contents as new experiences arrive instead of adding new persistent variables.
Theory: the authors show that reducing the number of coordinates increases the average feedback each coordinate receives, and analyze a generic contamination-and-cleanup transition model to bound how much of the erroneous state can persist.
Results: on ALFWorld and LifelongAgentBench (OS, DB tasks), RoMeRL raised overall average success rate by 3.2 percentage points over the strongest baseline, cut the Cold-Q ratio (memories never updated) by 80.0%, increased feedback density by about 6.0x, and reduced memory size by 84.4% and LLM calls by 21.1%.

Figure 1: Memory-reward trap: Stronger exploration retrieves more low-access-count memories, including weakly relevant, noisy, outdated, or failed experiences. When such a memory appears in a successful episode, the shared trajectory reward can promote it despite no causal contribution. Exploration therefore increases feedback coverage but also raises the risk of reward misattribution.

Table 1: Main results over 10 epochs. We compare RoMeRL with non-learning and learning-based agent-memory baselines. LAB reports Last-Epoch SR / CSR, while ALFWorld reports SR for six task types: P&P, examine, clean, heat, cool, and Pick-2. Overall is the macro-average of last-epoch SR across the two LAB tasks and six ALFWorld task types. For MemP, MemRL, and RoMeRL, we also report average LLM calls and memory-pool size.
Method	Lifelong Agent Bench	ALFWorld	Overall Avg.	LLM Calls Avg Num.	Memory Avg Num.
OS Last / CSR	OS	Last / CSR	DB Last / CSR	DB	Last / CSR	P&P	Examine	Clean	Heat	Cool	Pick-2
OS
Last / CSR
DB
Last / CSR
Model	DS-V4-flash	DS-V4-flash	GPT-5.4-mini	–	–	–
No Memory	0.646	0.550	0.883	0.827	0.861	0.850	0.855	0.788	0.783	–	–
Pass@10	– / 0.756	– / 0.906	–	–	–	–	–	–	–	–	–
RAG	0.700 / 0.752	0.556 / 0.844	0.891	0.834	0.868	0.855	0.858	0.796	0.795	–	–
Mem0	0.691 / 0.733	0.575 / 0.841	0.897	0.841	0.873	0.858	0.872	0.805	0.802	–	–
MemP	0.768 / 0.796	0.631 / 0.942	–	–	–	–	–	–	–	570K	45K
MemRL	0.808 / 0.820	0.632 / 0.934	0.908	0.855	0.887	0.865	0.871	0.812	0.830	570K	45K
RoMeRL (ours)	0.824 / 0.838	0.680 / 0.952	0.968	0.957	0.901	0.862	0.880	0.826	0.862	450K	7K

Figure 2: Overview of RoMeRL. Top: the agent retrieves memories to construct the LLM context and updates memory utilities using task-level rewards. Although stronger exploration improves feedback coverage, it also expands the utility support exposed to erroneous reward propagation, increasing the risk of the memory-reward trap. Bottom: RoMeRL maps each task’s growing trajectory-indexed utility space into a fixed-dimensional state factorized by outcome polarity and memory dynamics. Its four semantic coordinates PCC, PAC, NCC, and NAC are updated through online retention, promotion, and replacement, thereby concentrating feedback over a bounded active support.

Table 2: Controlled MRT stress test on the OS task. The first-round memory pool contains 10% noisy entries, and results are reported after ten training rounds. Positive Noise Updates denotes the average number of positive utility updates received by noisy entries over the ten rounds, whereas Final Noise Ratio denotes the percentage of noisy entries in the memory pool at the end of round 10.
Method	Round-10 SR (%) ↑	Positive Noise Updates ↓	Final Noise Ratio (%) ↓
MemRL	79.2	3.7	1.02
MemRL + UCB	78.4	7.2	1.20
RoMeRL	82.0	2.4	0.15

Figure 3: Feedback density and Cold-Q ratio on the OS task. The Cold-Q ratio is the fraction of current representatives with no direct utility update since admission, i.e., nipost=0, while feedback density is their average number of post-admission updates.

Table 3: Cross-model memory transfer on LifelongAgentBench OS and DB tasks. Results with and without frozen transferred memory are reported as Validation Score / Average Steps (higher / lower is better), and Δ denotes the absolute score gain over the base agent.
Inference Model	Base	Transfer	Gain (Δ)
LifelongAgentBench–OS
GPT-5.4-mini	67.0 / 3.23	81.6 / 2.22	+14.6 / -1.01
Gemini-3.5-flash	74.0 / 4.53	81.4 / 3.02	+7.4 / -1.51
LifelongAgentBench–DB
GPT-5.4-mini	93.0 / 2.15	96.8 / 2.00	+3.8 / -0.15
Gemini-3.5-flash	96.2 / 2.44	97.6 / 2.18	+1.4 / -0.26

Figure 4: Coordinate ablation on the OS task. Solid and dashed curves denote SR and CSR.

Table 4: Model and API Configurations.
Component	Configuration / Version	Notes
Backbone LLM	DS-V4-flash	Used for LifelongAgentBench
	GPT-5.4-mini	Used for ALFWorld
Embedding Model	Text-Embedding-3-Large	Used for Intent and Query encoding
Generation Params	Temperature =0.0	General (Greedy decoding)
	Top-p =1.0	Default

Figure 5: Occupancy distribution of the factorized memory state on the OS and DB tasks. The bars report the percentage of occupied active-memory coordinates assigned to the PCC, PAC, NCC, and NAC.

Table 5: Hyperparameter Settings across Benchmarks.
		Benchmark Setting
Parameter	Description	Lifelong Bench (OS)	Lifelong Bench (DB)	ALFWorld
RoMeRL (Ours)
α	Learning Rate	0.3	0.3	0.3
ωQ	Q-Weight Balance	0.5	0.5	0.5
δ	Similarity Threshold	0.50	0.37	0.62
k1	Cosine Similarity Recall Size	10	10	5
k2	Final Memory Selection Size	5	5	3
Qinit	Initial Q-value	0.5	0.5	0.0
Baselines
kRAG	Retrieval Top-k	5	5	3
kSelfRAG	Retrieval Top-k	5	5	3
kMemP	Retrieval Top-k	5	5	3

Figure 6: Final Q-value composition on OS tasks for the MemRL baseline (Left) and RoMeRL (Right). Each bar shows the proportions of success-derived and failure-derived memories within a Q-value interval; the legends report the fraction of memories remaining at the initial Q=0.5 and the Pearson correlation between Q-values and memory-generation outcomes.

Table 6: Data split for Lifelong Agent benchmarks.
Benchmark	Runtime Learning	Transfer Learning	Split / Note
Lifelong Agent (OS)	500 tasks	500 tasks	7:3 Split (Seed 42)
Lifelong Agent (DB)	500 tasks	500 tasks	7:3 Split (Seed 42)

RoMeRL: Balancing Feedback Coverage and the Memory-Reward Trap in Self-Evolving Agent Memory via Reduced-Order Utility States figure 6

Findings

RoMeRL achieves an overall average success rate of 0.862, 3.2 percentage points above the strongest baseline's 0.830 (Table 1).
On the OS task, MemRL's Cold-Q ratio rises from about 29% to 44.9%, while RoMeRL reduces it from about 28% to 9.0%, and feedback density increases from 4.96 to 29.93, about 6.0x (Figure 3).
Average memory size drops from 45K to 7K (84.4% reduction) and LLM calls drop from 570K to 450K (21.1% reduction) (Table 1).
In a controlled noise-injection stress test, adding UCB exploration to MemRL raises positive noise updates from 3.7 to 7.2 and the final noise ratio from 1.02% to 1.20%, whereas RoMeRL limits these to 2.4 and 0.15% respectively while reaching the highest success rate of 82.0% (Table 2).
Transferring the frozen learned memory state across four different model-task combinations improves the validation score and reduces average execution steps in all four cases (Table 3).

Figure 7: LLM calls per section on the DB and OS task. RoMeRL achieves lower and steadily decreasing call counts, while MemRL maintains a consistently high level.

Where it can be used

Designing memory management for long-running task-automation or customer-facing agents that keep accumulating experience
Agent systems that need to bound memory storage and LLM-call cost under limited resources
Reusing previously learned procedural memory when switching an agent to a different LLM backbone

RoMeRL: Balancing Feedback Coverage and the Memory-Reward Trap in Self-Evolving Agent Memory via Reduced-Order Utility States figure 8

Limits and open work

Still relies on outcome-level (task-final) rewards, so it does not fully resolve causal credit assignment among memories.
Estimating the actual contamination/cleanup transition parameters (gamma, lambda) from the theoretical model would require coordinate-level causal labels from counterfactual rollouts, which has not been done.
Experiments are limited to ALFWorld and the OS/DB subsets of LifelongAgentBench; open-ended, longer-horizon settings are left for future work.
The four fixed coordinates (2x2 design) are presented as a minimal design; extensions with finer-grained rewards or other factorization criteria are not evaluated.

Why it matters

As agents run longer, their memory can grow without bound, raising storage cost and the risk of learning from misattributed rewards — a real concern for any long-running deployed agent. This work shows that a fixed-size memory structure, without retraining the underlying LLM, can maintain or improve performance while sharply cutting cost and contamination risk.

Terms in this paper

Cold-Q ratio · The fraction of current memory representatives that have never received a direct utility update since being added; lower means feedback reaches memories more effectively
Memory-Reward Trap (MRT) · When a shared task-level reward is credited to all co-retrieved memories, so memories with no real contribution still get positive utility updates
PCC/PAC/NCC/NAC · RoMeRL's four fixed memory slots: positive-consolidated, positive-adaptive, negative-consolidated, and negative-adaptive
Cumulative Success Rate (CSR) · The proportion of tasks solved at least once across multiple training epochs

Original abstract (English)

Learning-based memory systems for self-evolving LLM agents face two tightly coupled challenges. First, trajectory-indexed utilities grow with the interaction history, thereby dispersing limited feedback over an ever-expanding state space. Second, because trajectory-level rewards are jointly assigned to co-retrieved memories, irrelevant experiences may receive misleading utility updates and consequently enter the memory-reward trap. To address these challenges, we introduce Reduced-Order Memory Reinforcement Learning (RoMeRL), which represents the growing trajectory-indexed utility space using a fixed-dimensional per-task memory state factorized by outcome polarity and memory dynamics. RoMeRL incorporates new experiences through a fixed set of semantic coordinates whose contents are updated or replaced over time, thereby concentrating feedback over a bounded utility support. Theoretically, we show that this reduced-order parameterization increases the average feedback received by each utility coordinate and characterize the steady-state occupancy of erroneous coordinates under a generic coordinate-transition model. Empirically, across ALFWorld and LifelongAgentBench, RoMeRL improves task performance, reduces the Cold-Q ratio by 80.0%, increases feedback density by approximately 6.0 times, reduces the maintained memory size by 84.4%, and cuts LLM calls by 21.1%. These results show that reduced-order utility states support efficient self-evolving agent memory while limiting persistent reward contamination. Code is available at: https://github.com/YOUNG-fnxm/RoMeRL

Authors · Yi Yang

Read on arXiv

Latest papers

All papers →

Latest from METAL LAB

Figures: Yi Yang et al., arXiv:2608.02508, arxiv-nonexclusive