Your Agent Needs to Remember What Passed

The two previous posts in this series looked at the checking side of an agent loop. Generate-and-Verify [2] paired an expensive guess with a cheap, trustworthy check. Self-Consistency [3] repeated a guess and took a vote. Neither post looked closely at what the loop keeps between attempts. This post does.

This one started with an October 2026 episode of Machine Learning Street Talk with Akarsh Kumar, an MIT PhD student and first author of the Digital Red Queen paper. In AI, evolution has a reputation as the dumb fallback for when you can’t take a gradient. Kumar disagrees: “I would just want to clarify evolution is anything but random” [1]. His reason is a short piece of arithmetic.

The Arithmetic: (1/p)^L Against L/p

Say a solution has L pieces, and any single attempt at a piece is right with probability p. Without memory, all L pieces have to be right in the same attempt. That happens with probability p^L, so you need about (1/p)^L attempts. Every extra piece multiplies the cost.

With memory, you get one piece right, keep it and move on. Each piece costs about 1/p attempts, so the whole solution costs about L/p. Every extra piece adds to the cost.

Both formulas are expected costs in a toy model with four assumptions. The pieces succeed independently of each other. The odds p stay the same on every attempt. Each attempt works on a piece that is still unsolved, and the check reliably tells you when that piece got better. A piece you kept stays correct when you change the others. Without independence, p^L is the wrong number. Without the last three, L/p is. The rest of this post keeps coming back to these assumptions, mostly to the check.

Kumar puts it like this: “if you solve like even one part of a puzzle and you hang on to that and you search for the other ones, you can turn your exponential search problem into a linear search problem.” And: “all it needs is your mutations to be good like 1% of the time” [1]. He uses 1% as an example value, and he doesn’t present it as a measured rate. Plugging it in:

At one piece the two columns agree. At ten pieces they are seventeen orders of magnitude apart.

A Toy Combination Lock, Simulated

I ran a small toy simulation of a combination lock with L digits, ten values each. Each step sets one random digit to a random value, and the change stays if the number of correct digits did not drop. Averaged over 300 runs per size, the 6-digit lock opened in about 140 steps, the 12-digit lock in about 370 and the 24-digit lock in about 880. Random guessing would need on the order of 10^6, 10^12 and 10^24 guesses.

Doubling the digits a little more than doubles the steps. The growth is close to linear, more like L·log L, because once the lock fills up, most changes land on a digit that is already right.

To be fair, the lock makes this easy. It reports how many digits are correct, which is exactly the per-piece score the arithmetic assumes. Many real problems report progress less cleanly.

What the LLM Contributes: A Higher Hit Rate

The L/p column hides a second condition: p can’t be close to zero. Before LLMs, program search used random edits. The AutoML-Zero paper notes that in its search space, good algorithms for even a trivial task “can be as rare as 1 in 10^12” [4]. At odds like that the linear column doesn’t help either, because 1/p is a trillion. Kumar says random program mutations have “literally around a 0% chance” of producing useful code, while LLMs “can’t give you 100% success, but they can give you way more than 1%” [1].

So the model and the loop do different jobs. The LLM raises p. Selection turns a higher p into progress. By selection I mean a verifier that decides what counts as better, plus a memory of what passed. Lose either one and the loop suffers, though in different ways. Without memory, the cost is exponential again. Even a model that gets each piece right half the time needs about 2^50, roughly 10^15, attempts to get fifty pieces right in one go. With memory but p near zero, the loop barely moves.

Self-consistency works differently. Repeated independent votes converge on the right answer only when that answer is the model’s unique most likely output, because nothing checks the answers [3]. With a verifier and a memory, a 1% hit rate can be enough if the toy-model assumptions roughly hold.

Digital Red Queen: Core War Warriors Evolved With an LLM

Kumar’s Digital Red Queen paper tests this on Core War, a programming game in which programs called warriors fight inside a shared memory [5]. Warriors are written in an assembly language called Redcode, which the paper calls relatively out of distribution for most LLM training data. The LLM proposes edits to a warrior, a battle simulation is the verifier, and MAP-Elites holds the memory [5].

MAP-Elites keeps the best solution in each cell of a grid of behaviours, so it ends up with many good solutions that behave differently from each other [6]. Kumar says they needed it because the Core War search space “is very deceptive”, and a greedy genetic algorithm “won’t work” [1].

Read the numbers carefully. Against 294 human-written warriors, one warrior written zero-shot by the LLM defeats 1.7% on average. Best-of-8 sampling gives a set that collectively defeats 22.1%. One evolutionary run per human opponent gives a set of specialists that collectively defeats 89.1% and defeats or ties 96.3%. A single evolved warrior defeats or ties only 27.9% on average [5]. So the “96%” from the interview describes the whole set. Individual warriors are brittle. Don’t read the two results as an ablation, though. Best-of-8 is eight samples. The specialist set comes from 294 opponent-specific evolutionary runs of 1,000 iterations each. So the jump from 22.1% to 89.1% doesn’t isolate what the verifier and the memory contribute.

Where Keeping Partial Wins Stops Working

The linear column rests on assumptions, and agent tasks break them in at least three ways.

Some pieces only pay off together. If two changes are useless apart and useful together, the verifier gives no credit for the first one. There is nothing to keep, and the search drifts back toward guessing both at once. Two fixes help: let a single proposal change related pieces together, or give the verifier a finer score that credits the first piece on its own.

Partial scores can mislead. When the steps that look like progress lead into a dead end, keeping the best partial solution locks you into it. That is the deception Kumar describes in Core War, and it is why the paper keeps an archive of different partial wins.

Verifiers can be gamed. Selection keeps whatever the verifier rewards. A test suite with gaps, or a judge model that can be talked into a pass, lets fake progress through as efficiently as real progress. Generate-and-Verify argued that a verifier that confidently accepts bad answers can be worse than none [2]. Memory compounds the damage, because every accepted mistake becomes the starting point for the next change.

A Checklist Before You Upgrade the Model

When an agent loop stalls, a common reflex is to reach for a bigger model. I’d check these first.

• Build the verifier before the loop: tests that run the code, evals with known answers, schema and type checks. The verifier defines what “better or equal” means. If it accepts something wrong, the loop keeps it.
• Keep an archive of different partial wins. Store the best version of each approach, so a dead end in one approach doesn’t take the whole search down with it [6].
• Measure how often a proposal is actually useful: the share of proposed changes that pass the verifier and improve the score. Log every proposal with its verifier result and you can read the number off the log. If that share is close to zero, the proposals aren’t working under the current verifier. Before you pick a fix, go through the possible causes: the model, the context it gets, the size of each change, a verifier that is too strict or noisy, and a score that gives no credit for partial progress. A better model or better context only helps with the first two.
• Never let unverified progress into memory. A 2026 preprint on agents that collect reusable skills found that past a critical pool size, new skills made performance worse. Defective skills became reference material for later ones, and removing them afterwards recovered only a small part of the loss [7]. In those experiments, a check before a skill entered the pool worked better than cleaning up afterwards [7]. So gate what goes in.

If You’re Running This on AWS

A model on Amazon Bedrock is the proposal step [8]. Your tests and evals are the verifier, and the history of accepted changes is the memory. For a coding agent that memory can be a git branch, or one branch per approach if you want an archive. Most of the design work goes into the verifier.

What Your Loop Keeps Between Attempts

Kumar’s argument is about evolution. It carries over to agents on problems where partial scores are honest. On those problems a modest generator makes steady progress when the loop keeps what works, and a strong generator in a loop that forgets is still guessing everything at once. An agent runs the left-hand loop when each retry throws away the last accepted state and has to rediscover every correct piece. Rewriting the whole file on each retry doesn’t put you there by itself, as long as the rewrite starts from the last checked version. Memory here means a checked baseline that the next change starts from. So before you swap in a bigger model, look at what your loop does with a change that passed.

What does your agent loop keep between attempts, and what checked it before it was kept?

Sources

• [1] Machine Learning Street Talk, “What Most People Get Wrong About Evolution | Akarsh Kumar” — interview, October 2026; quotes from the cold open [00:00], the Core War segment [43:30-44:30] and the closing argument [46:00-47:30].
• [2] Stefan Christoph, “Generate-and-Verify: What P vs NP Teaches Us About AI Reasoning” — July 2026; why a cheap, trustworthy check pays, and why a wrong one can be worse than none.
• [3] Stefan Christoph, “Self-Consistency Is Just Probability Amplification” — August 2026; voting over repeated samples and the condition under which it converges.
• [4] Real, Liang, So and Le, “AutoML-Zero: Evolving Machine Learning Algorithms From Scratch” — 2020; random search over programs, where good algorithms can be as rare as 1 in 10^12.
• [5] Kumar et al., “Digital Red Queen: Adversarial Program Evolution in Core War with LLMs” — 2026; LLM mutation with MAP-Elites, static-optimization results in Fig. 2 and Sec. 4.1.
• [6] Mouret and Clune, “Illuminating search spaces by mapping elites” — 2015; the MAP-Elites algorithm, one elite per behaviour cell.
• [7] “When Self-Evolution Backfires: Pre-Commit Gating against Skill Contamination in LLM Agents” — 2026 preprint; skill pools that degrade once defective skills accumulate, and post-hoc rollback that recovers little.
• [8] Amazon Bedrock User Guide, “Overview” — the managed service for foundation models, used here as the proposal step.