Keeping Only the Surprising Steps: One-Pass Simplification of Agent Histories

Language-model agents that act in an environment keep appending every action and every observation to their prompt. Long stretches of that history are the textual version of a ship cruising down a straight shipping lane: the agent reopens a drawer it already checked, gets "Nothing happens" again, or polls a page that has not changed. Work on GPS and ship tracking learned long ago to throw such points away. The retained points are the "characteristic points," where motion changes, and a simplifier can drop the rest in a single pass while guaranteeing that the kept points reconstruct every dropped one within an error bound. We propose to do the same for agent histories. As each observation arrives, the agent's own model measures how predictable that observation was given the history it has kept so far. If it was predictable to within a fixed bound, the step is folded into a short marker and removed from the context. If it was not, it is committed as a characteristic step.

The appeal is practical. The per-token log-probabilities needed for the test are computed anyway when the observation is fed into the model, so scoring costs no extra forward passes. Decisions are made once, at arrival, and never revisited, so the committed history only grows at the end and the cached attention state for earlier tokens stays valid. The method also gives a concrete, checkable meaning to "this step carried no new information," which the current approaches to agent memory lack. Those approaches rely on post-hoc language-model summaries or on the agent choosing when to fold its own context.

Core Claim

The claim is narrow. For the kind of contextual noise that comes from redundancy, meaning repeated, near-duplicate, or steady-state observations, an information-bounded one-pass filter recovers most of the benefit of language-model summarization of the history. It does this at close to zero added cost and without breaking the cached prefix. It also fails in a predictable way on the other kind of noise, which is novel but irrelevant content, and we will show that as well.

The criterion borrows the fitting-function idea of One-Pass Error Bounded Trajectory Simplification. That paper's OPERB method checks each new GPS point only against a local fitting line, not against the whole path, and so runs in linear time and constant memory with a strict distance bound $\zeta$. Here the "fitting function" is the language model conditioned on the retained history. For step $t$, with action $a_t$ and observation tokens $o_t = (o_t^{(1)},\dots,o_t^{(m)})$, define the mean surprisal

$$ s_t = -\frac{1}{m}\sum_{i=1}^{m}\log p_\theta\big(o_t^{(i)} \mid \tilde h_{<t},\, a_t,\, o_t^{(<i)}\big), $$

where $p_\theta$ is the agent's own model and $\tilde h_{<t}$ is the simplified history kept so far. Step $t$ is dropped when $s_t < \zeta$. When that happens, its cached entries are rolled back and replaced by a short patch marker such as "(repeated: open drawer 2 → nothing happens, ×3)." The marker plays the role of OPERB-A's patch points, which merge short segments without reprocessing the path. The guarantee mirrors the geometric one: every discarded observation could have been regenerated from the kept history at a per-token cost below $\zeta$ nats.

We deliberately do not use the obvious alternative criterion, which is to drop a step if removing it barely changes the agent's next action. Less is More: Empowering GUI Agent with Context-Aware Simplification trains toward this kind of agreement by minimizing the KL divergence (a measure of difference between two probability distributions) between compressed and full-history outputs. The trouble is that noise sensitivity means irrelevant context does move the policy. Bring the Apple, Not the Sofa shows that a mention of an unrelated object can halve robot success. A policy-preservation test would therefore protect exactly the distracting steps. An information-preservation test does not have this failure mode, although it has a different one, which we test directly.

Relation to Prior Work

Four papers motivate the gap. An Efficient Context-Dependent Memory Framework for LLM-Centric Agents (CDMem) shows that history noise matters. Removing its "expert filter," which uses a language model to condense finished trials into knowledge chunks, drops ALFWorld success from 85.8% to 72.3%. That filter runs after the trial ends, not during it. Scaling Long-Horizon LLM Agent via Context-Folding compresses history online and rolls back cached tokens. It requires the agent to emit branch and return tool calls, trained with reinforcement learning and an external judge. Our method needs neither a policy trained to fold nor a judge. AgentBoard documents that open-weight models stall after about six steps, which is where history bloat plausibly starts to bite. Finally, LongLLMLingua compresses prompts using a small model's perplexity. Its compression depends on the question, so it must re-compress for every query and cannot reuse cached state. Our score does not depend on the query and is fixed at arrival.

The streaming mechanics come from the trajectory literature: the local check and patch points of OPERB and OPERB-A, the joint spatial-temporal bound of One-Pass Trajectory Simplification Using the Synchronous Euclidean Distance, and the change-detection statistics used to find maneuvering points in Extracting Maritime Traffic Networks from AIS Data Using Evolutionary Algorithm and Analysis of Terminal Area Airspace Operation Status Based on Trajectory Characteristic Point Clustering. The SED paper matters because it keeps timing information when points are dropped. Our patch markers preserve step counts for the same reason: an agent that forgets it already tried something tends to loop.

Two papers constrain the scope. Contextual Drag and Off-Trajectory Reasoning show damage from erroneous or injected reasoning. That content is typically surprising, so our filter will keep it. We do not claim to fix contextual drag. We measure whether the filter leaves drag unchanged, as we expect it to.

Research Program

The implementation is a wrapper around an open-weight agent, Llama3-70b and a Qwen model of similar scale, in ReAct style. It reads the prefill logits over each observation, computes $s_t$, and either commits the step or rolls back its cached entries and appends or updates a patch marker. Commercial models that do not expose prompt log-probabilities are out of scope, which is why CDMem's GPT-4o-mini numbers can only serve as context.

The analysis has three parts. First, we calibrate $\zeta$ and trace a curve of compression ratio against success rate, analogous to OPERB's plots of output size against error bound. Second, we check fidelity directly. At random points in a run we ask factual questions about the world state, such as "where is the mug?" or "which drawers have been opened?" We answer them from the full history and from the simplified history, and we require the two to agree. Third, we run a controlled noise study. We inject two kinds of noise into ALFWorld and ScienceWorld observations. Redundant noise consists of repeated status lines and near-duplicate re-descriptions. Novel-irrelevant noise consists of descriptions of unrelated objects, in the style of the VLA study. We predict the filter recovers most of the lost success under redundant noise and little under novel-irrelevant noise. This defines where the idea applies.

Baselines

The naive reference point is the unmodified ReAct agent with full history on the same backbone. On AgentBoard, Llama3-70b reaches a 41.9% progress rate as reported in AgentBoard. We will re-run this number under our harness, not simply copy it. Beating this baseline means higher success and progress rates at a smaller active context.

The cheapest serious competitor is a rule-based filter. It removes observations that exactly or nearly duplicate an earlier one, using normalized string match plus a lexical-overlap threshold, and adds the same patch markers. We run it alongside a sliding window that keeps the last $k$ steps. On ALFWorld, where "Nothing happens" dominates the redundancy, the rule-based filter may match us. Beating it therefore has to happen on tasks where redundancy is paraphrased rather than verbatim: WebShop, ScienceWorld, and the AgentBoard tool tasks. We will tune its threshold with the same number of development runs we spend tuning $\zeta$.

The strongest method-level competitor is language-model summarization of the history. We run it two ways. The first is a per-step 3B summarizer, the kind of small pre-filter that restored VLA performance to about 98.5% of clean in Bring the Apple, Not the Sofa. The second is a reimplementation of CDMem's expert filter on our backbone. For the second, the reported anchor is CDMem's 85.8% ALFWorld success and 56.0 ScienceWorld score with GPT-4o-mini. That backbone differs from ours, so the fair comparison is our reimplementation with a matched summarizer budget. The question is whether we match its success at a fraction of the added latency and recomputed prefill tokens. LongLLMLingua applied to the history gives a query-aware compression point, and we charge it for its per-turn re-compression.

For long horizons we report Context-Folding's 62.0% pass@1 on BrowseComp-Plus against 47.8% for ReAct as context. We cannot match its reinforcement-learning training budget. Our claim there is limited to training-free gains over ReAct, and we treat any gap to 62.0% as the cost of not training.

Three ablations isolate the key ingredient. The first drops steps at random at the same rate as our filter. The second scores surprisal of the action instead of the observation. The third removes the patch markers. We also compare against a post-hoc version that applies the same surprisal rule to the finished history, to separate the value of the criterion from the value of one-pass operation.

Why not just…?

Why not just have a small language model summarize the history? This is a real threat on accuracy, and the VLA filtering result suggests it can work well. Its costs are an extra model call per step and a rewritten context that invalidates the cached prefix. CDMem's version also only runs after the trial ends. We do not expect to beat it on accuracy under every condition. The experiment settles whether we match its success on AgentBoard at near-zero added compute. If the summarizer is clearly better on success at matched context size, the right conclusion is that surprisal is a cheap first stage in front of it, not a replacement, and we will report it that way.

Why not just deduplicate repeated observations with string matching? On ALFWorld this may be nearly as good, and we say so. The surprisal test is a model-based generalization of deduplication: it also catches paraphrased re-descriptions, unchanged page content with different timestamps, and outcomes the model could infer. The paraphrased-redundancy injection and the WebShop and tool tasks decide whether that generality buys anything. If it does not, the rule wins and the idea should be dropped.

Why not let the agent fold its own context, or train the generator to extract what it needs? Context-Folding and Ext2Gen (Aligning Extraction and Generation for Robust Retrieval-Augmented Generation) do this, with reinforcement learning or preference training. Ext2Gen was only tested on static retrieval question answering. Our method is training-free and could be layered under a folding agent. The comparison on BrowseComp-Plus tells us how much of folding's gain a training-free filter captures. What Do Agents Learn from Trajectory-SFT is a reminder that trained agents can become brittle to changes in how actions are named. We will check that our patch markers do not induce similar format reliance.

Decisive Checks

We run ALFWorld, ScienceWorld, WebShop, and the AgentBoard tool tasks with the two open-weight backbones, three seeds each. We report success rate, progress rate, active context tokens, recomputed prefill tokens, and wall-clock time per episode.

The idea survives if three results hold. First, with no loss in success, the filter removes at least half of the history tokens relative to full history on tasks with heavy redundancy. Second, it beats string deduplication on the paraphrased-redundancy tasks. Third, it comes within a few points of the language-model summarizer at a small fraction of that summarizer's recomputation cost.

The noise study must show the predicted asymmetry: substantial recovery under redundant injection, little under novel-irrelevant injection. It must also show no change in contextual-drag accuracy on the drag suites. Seeing this asymmetry is what would confirm that the filter removes redundancy and not relevance. If the filter instead helped equally on novel-irrelevant noise, our account of why it works would be wrong. The world-state probe must show that the simplified history answers state questions as well as the full history at the chosen $\zeta$. That result is the empirical check on the error bound.