Step-Level Memory Credit That Survives Noisy Judges

Language-model agents with frozen weights can still improve across sessions by writing experiences to an external memory: successful routines, diagnosed failures, reusable tips. They then retrieve the useful ones on later tasks. Two things decide whether this memory helps or hurts. The first is who judges success. In practice this is usually another language model, and it makes mistakes. The second is how a single end-of-task verdict gets split among the many memories that were in the prompt. Today both are handled crudely. Every retrieved memory gets credit for the whole episode's outcome, and the judge's verdict is treated as ground truth. Irrelevant memories that happened to ride along on a success therefore build up utility, and false-positive verdicts write broken routines into memory as if they were verified.

We propose to fix both problems with one design. Credit goes to memories at the level of individual steps: a memory is rewarded or blamed by the progress made on the steps where the agent actually used it, not by the final outcome. The retrieval rule is a softened, regularized choice over memories rather than a greedy top-k. Its softness is not a free knob tuned by grid search. It is set from a measured estimate of how wrong the judge is, using a known exact equivalence between regularized decision rules and worst-case reward corruption. The claim is that dense step-level credit removes the feedback starvation that has pushed recent systems to throw away per-memory utilities. Dense credit is also noisier, and that equivalence tells us, with a certificate, how much hedging the noise demands.

Core Claim

Recent work on self-evolving agent memory concluded that fine-grained per-memory utilities are a dead end. RoMeRL showed that trajectory-indexed utilities (as in MemRL) leave about 45% of memories never updated ("Cold-Q"), and that retrieving bundles of memories causes a "memory-reward trap" in which noise items inherit credit from successes. Its remedy is to collapse all memory utility onto four fixed coordinates: success or failure, crossed with consolidated or recent. RoMeRL states that it still uses only outcome-level rewards. Our first claim is that its compression is a symptom of sparse feedback rather than a necessity. Step-level process supervision is known to deliver much denser signal: Process vs. Outcome Reward matches outcome-RL search agents with 5,000 rather than 90,000 training examples. If each memory is credited through the steps that cite it, per-item utilities should stop starving.

Our second claim concerns the cost of that density. Step-level judges are noisier and easier to game than outcome checks. SCAN documents systematic under- and over-estimation in automated step labels. Entropy-Regularized Process Reward Model reports that process reward models get exploited at large best-of-N budgets. This is where the duality results come in. Your Policy Regularizer is Secretly an Adversary and Regularized Policies are Reward Robust prove that maximizing reward minus a KL penalty is exactly equivalent to playing against an adversary who perturbs the reward within a specific feasible set. For a single retrieval decision with estimated utilities $u(m)$ over memories $m$, a prior $\pi_0$ and temperature $\beta$, the regularized rule is

$$\pi(m) \propto \pi_0(m)\, \exp\big(u(m)/\beta\big).$$

In the form derived by Brekelmans et al., this rule is the minimax solution against every utility corruption $\Delta$ satisfying

$$\sum_m \pi_0(m)\, \exp\big(\Delta(m)/\beta\big) \le 1.$$

Its worst-case corruption is the negative advantage. In plain terms, the adversary does the most damage by deflating exactly the memories the agent currently prefers. We use this result in two ways. First, it gives a rule for setting $\beta$: estimate the judge's corruption $\Delta$ on a small human-verified audit set, then pick the smallest $\beta$ whose feasible set contains it. Second, it gives a principled stress test: corrupt the judge in the theory-predicted worst-case direction rather than with random flips.

The scope is deliberately narrow. State Entropy Regularization for Robust RL proves that no regularizer depending only on the nominal environment and the policy can handle general misspecification of the environment's dynamics. We therefore claim robustness to judge and reward corruption only, not to changed website layouts or other environment drift.

Research Program

The agent is a frozen open-weight model with an external memory of distilled experiences. Following Agent Workflow Memory, these include abstracted workflows, plus failure notes of the kind RoMeRL keeps. At each step the agent receives a retrieved set of memories and must tag which memory, if any, its action relies on. We verify the tags by checking whether removing the memory changes the action under the same random seed on a sample of steps. This yields an attribution from steps to memories.

Each step receives a progress signal from one of two sources. The clean source is the annotated subgoal matching of AgentBoard, whose progress rate correlates above 0.95 with human judgment. The realistic source is a learned step evaluator: a small step-level Q-value model trained by Monte Carlo rollouts and step-level preference optimization, as in Step-Level Q-Value Models, or an LLM progress judge. A memory's utility is updated with the progress change on steps that cite it. Memories present in the prompt but not cited receive no update, which is the direct remedy for the memory-reward trap.

Retrieval samples from the regularized rule above. The prior $\pi_0$ comes from embedding similarity to the current task, and $\beta$ is calibrated from the audit set. The analysis side has two parts. We derive the per-step version of the feasible set when utilities are estimated from noisy progress deltas. We then check empirically whether the certified lower bound on true utility actually holds as corruption grows.

Two pieces of prior work are relevant but differ in kind. SE-Search combines memory with dense reward, but its memory lives only within a single session, and its rewards are exact-string heuristics used to train weights. Adversarial Training for Process Reward Models makes the step judge itself more robust through a generator-versus-judge game, but in stateless single-turn math. That method is complementary: a better judge shrinks $\Delta$, and our method hedges whatever $\Delta$ remains.

Baselines

The naive reference point is the same frozen agent with no memory, run on identical tasks. The second reference is MemRL-style trajectory-level utilities with greedy top-k retrieval. RoMeRL reports that MemRL reaches an overall success rate of 0.830 across ALFWorld and LifelongAgentBench.

The strongest existing memory method on our main benchmarks is RoMeRL itself, which reports 0.862 overall on ALFWorld plus LifelongAgentBench, an 80% reduction in Cold-Q (from about 45% to 9%), and 84.4% less stored memory. It is the right competitor because it attacks the same credit-misattribution failure with a different cure: compression instead of dense attribution. We will rerun RoMeRL ourselves on the same backbone, the same task order, the same memory-size cap and the same budget of LLM calls. Beating it means higher success at matched calls, together with a lower Cold-Q ratio and less utility mass on spurious memories. It also means a flatter degradation curve as judge corruption increases.

On WebArena the competitor is online Agent Workflow Memory, which reports 35.5% success against a 23.5% baseline. It relies on an LLM judge, which makes it the natural setting for testing evaluator contamination. We will run it with the same judge and the same backbone as our method.

Three ablations isolate the key ingredients. Step-level attribution with greedy retrieval isolates the effect of density without hedging. Outcome-level credit with regularized retrieval isolates hedging without density. Step-level credit with $\beta$ grid-tuned per corruption level, compared against $\beta$ set by the dual calibration, isolates whether the theory adds anything beyond a well-tuned temperature. Every tuned method gets the same number of tuning runs.

Why not just…?

Why not just tune the retrieval temperature on MemRL or RoMeRL? This is the real threat. Any softmax retrieval is already entropy-regularized, so the duality might amount to a fancy interpretation of temperature tuning. The experiment that settles it compares dual-calibrated $\beta$ against grid-tuned $\beta$ across several corruption levels, with the corruption level unknown at tuning time. If a single grid-tuned value matches calibrated $\beta$ everywhere, we will report that the contribution reduces to step-level attribution plus a tuning shortcut. We will not claim more than that.

Why not just use a better judge, such as majority voting or an adversarially trained step model? Better judges shrink the noise, but nothing in the file suggests they remove it. SCAN's best denoised step labels reach a ProcessBench F1 of 59.1, far from clean. ER-PRM documents exploitation at large best-of-N budgets. We will include a stronger-judge condition. Our method should help less when the judge is cleaner, which is exactly what the calibration predicts, and still help under residual noise.

Why not just keep RoMeRL's four coordinates and feed them step-level rewards? This is plausible and cheap, so we run it as a hybrid baseline. If the hybrid matches per-item utilities, then compression and density are complements, and RoMeRL's design survives. If per-item utilities win once feedback is dense, RoMeRL's starvation argument was really about sparsity.

Why not just do leave-one-out counterfactual credit, rerunning the episode without each memory? It gives the cleanest attribution, but it multiplies rollouts by the bundle size. That is the same cost problem the process-reward literature already flags for Monte Carlo labeling. We run it on a small task subset as an oracle upper bound to measure how much attribution accuracy our cited-step tags lose.

Proposed Experiments

The main suites are ALFWorld and LifelongAgentBench, which give direct comparability with RoMeRL, and WebArena, for comparability with Agent Workflow Memory under a real LLM judge. AgentBoard's annotated ALFWorld subgoals serve as the clean dense signal for analysis. We report success rate and AgentBoard progress rate. We also report the Cold-Q ratio, and spurious utility mass: the share of total utility held by memories whose removal does not change outcomes on held-out probes.

Judge corruption is injected at increasing rates in three ways: the judge's natural errors, uniform random flips, and flips aimed at the theory-predicted worst case, which deflate the highest-advantage memories. The first decisive check is whether worst-case-directed corruption hurts greedy baselines more than random corruption of equal size. This tests whether the duality has picked out a real attack. The second is whether the certified lower bound on true utility holds empirically for our method up to the calibrated noise level and breaks beyond it. The third is whether per-item step-level credit closes RoMeRL's Cold-Q gap without compression. If none of the three holds, the idea fails, and the notes above say which simpler story replaces it.