Delayed, Bucketed Duplicate Detection for Web Agents That Loop

Language-model agents that browse websites or call tools often walk in circles. They reopen the same page, retry the same failing form submission, or run a "keep refining" loop that never changes anything. Classical search solved a version of this problem decades ago by keeping a record of visited states and refusing to expand a state twice. Agents cannot simply copy that solution, because two agent states are rarely identical byte for byte. The same product page reloads with a new timestamp, a different ad, or a reordered sidebar. Deciding whether two states are "the same" is expensive: it needs a model call or a careful structural comparison, not a hash lookup.

This note proposes borrowing the core trick of delayed duplicate detection (DDD). DDD is a family of external-memory search methods that do not check each new state for duplicates as it is generated. Instead they buffer a whole layer of new states, group them by a cheap key, and remove duplicates in one batch pass. In those methods the expensive operation was a random disk read. In agents it is a semantic equivalence judgment. We claim that layer-batched, bucket-scoped equivalence checking lets a branching, looping agent merge revisited states and cut off loops that make no progress. It should match or beat the best local-backtracking agents on WebArena while spending fewer environment steps and fewer equivalence-check calls than immediate, check-against-everything deduplication.

Core Claim

Hardware is not what transfers from the external-memory search literature to agents. Three structural ideas transfer instead. First, duplicate checks can be deferred and batched, as in Korf's sort-based and hash-bucket DDD (Delayed Duplicate Detection: Extended Abstract; Best-First Frontier Search with Delayed Duplicate Detection). The second paper reports that hash bucketing ran 40% faster than sorting because every possible duplicate of a state falls in the same bucket. Second, an abstraction of the state can define a duplicate-detection scope: a small set of neighboring blocks outside which no duplicate can exist. This is Zhou and Hansen's structured duplicate detection (Structured Duplicate Detection in External-Memory Graph Search; Domain-Independent Structured Duplicate Detection). Third, a locality bound says how many past layers must be kept for comparison. Edelkamp and Jabbar define it as the length of the shortest action sequence that returns to an equivalent state (Cost-Optimal External Planning).

Applied to an agent, the cheap key becomes a structural signature of the observation, for example a URL path template plus a hash of the page's skeleton with volatile text stripped. The expensive equivalence check runs only inside buckets. When a loop iteration produces a state judged equivalent to one already inside the locality window, the loop has made no progress and is cut. When two parallel branches reach equivalent states, they are merged into one node. The search tree then becomes a graph with join points, which is exactly the non-linear structure that DAG-only systems cannot express.

The new element is the treatment of semantic state equivalence as a batched, scope-limited operation inside agent search. Existing agents either handle loops with local remedy branches and no shared state registry (Devil's Advocate: Anticipatory Reflection for LLM Agents), retrieve similar past experiences by vector search without eliminating states (FlowSearcher: Synthesizing Memory-Guided Agentic Workflows for Web Information Seeking), or forbid cycles outright (Can Dependencies Induced by LLM-Agent Workflows Be Trusted?).

Research Program

We will build a layered search agent for WebArena (WebArena: A Realistic Web Environment for Building Autonomous Agents). At each layer, the agent proposes several candidate actions per frontier state, in the style of tree-search agents. The resulting observations are written to a buffer rather than checked one at a time.

When the layer completes, three things happen in order. Each buffered state is assigned to a bucket by its structural signature. Within each bucket, a single model call receives all the bucket's states together with the retained states from the last $L$ layers that share the same signature, and partitions them into equivalence classes. One state per class is kept as the representative, and its incoming edges are redirected to it. States equivalent to an ancestor on their own path are marked as no-progress cycles and dropped from the frontier.

The equivalence prompt is deliberately conservative. Differences in form contents, cart state, login state, or any field the task mentions count as non-equivalent. The point is that wrongly merging two states destroys real progress, while failing to merge two states only wastes some steps.

The cost argument is simple. Immediate deduplication compares each of the $N$ new states in a layer against each of the $M$ retained states. Bucketed delayed deduplication issues roughly one call per non-empty bucket. A pairwise variant costs

$$C_{\text{bucketed}} = \sum_{i} \binom{b_i + r_i}{2} \ll N M,$$

where $b_i$ is the number of new states and $r_i$ the number of retained states in bucket $i$. The inequality holds whenever the signature spreads states across many buckets.

The structured duplicate detection literature warns that the method's efficiency depends on the quality of the abstraction. A coarse abstraction produces scopes that are too large, and a fine one causes thrashing (Structured Duplicate Detection in External-Memory Graph Search). We expect the same trade-off with signatures: coarse signatures produce large buckets and expensive judgments, while fine signatures miss near-duplicates that land in different buckets. We will therefore study three signature granularities. The first is URL only. The second is URL template plus page skeleton. The third adds a hash of visible form values.

We will estimate the locality bound $L$ empirically for each site from the lengths of the shortest action sequences that return to an equivalent state. A back navigation, for example, gives $L=1$. We will then test whether truncating retention at that $L$ loses any merges compared with keeping the full history. This is the agent analogue of Edelkamp and Jabbar's result that only the last $L$ layers need to be kept.

As a secondary setting, we will apply the same machinery to the iterative-refinement loops that SeqCV explicitly cannot handle. These are tasks where an artifact is revised repeatedly. There, "equivalent state" means the artifact is functionally unchanged, and a duplicate means the refinement loop has converged or begun to oscillate.

Baselines

The naive reference point is a standard plan-then-act agent with no search and no deduplication. Anticipatory Reflection reports this baseline at 19.8% WebArena success with GPT-4 (Devil's Advocate: Anticipatory Reflection for LLM Agents). It tells us how much of any gain comes from searching at all.

The strongest existing methods are Anticipatory Reflection, which reports 23.5% WebArena success with GPT-4, and LATS, which the same paper reports at 22.7%. Anticipatory Reflection is the most direct competitor. It already adds non-linear backtracking into precomputed remedy branches and reduced episode-level plan revisions by 45%. It therefore targets the same failure we target, but without a shared registry of visited states. We will rerun both under the same backbone model, the same 812 tasks, the same per-task cap on environment steps, and the same total token budget. We will not compare against the reported numbers directly, because our backbone will differ. Our method beats them if it achieves higher success at equal token budget, or equal success with substantially fewer environment steps and tokens, and the difference is significant under paired per-task tests.

Three ablations isolate the key ingredient. The first, an exact-hash ablation, replaces semantic equivalence with exact hashing of the normalized observation. It tests whether the semantic step is needed at all. The second, an immediate-dedup ablation, checks each new state against all retained states using embedding nearest neighbors followed by the same equivalence prompt. Its call budget is matched to ours. It tests whether delay and bucketing matter, or only deduplication itself. The third, a no-scope ablation, uses one global bucket and tests the role of the abstraction.

Why not just…?

Why not just hash the URL or the cleaned page and keep an in-memory set? This is the most serious threat, and it may partly win. If most loops on WebArena are exact revisits after normalization, the semantic machinery adds cost and nothing else. The exact-hash ablation settles this directly. We will also hand-label 500 state pairs drawn from real trajectories and report what fraction of true duplicates exact hashing misses. If that fraction is small, say under a tenth, we will narrow the claim to the iterative-refinement setting. There, artifacts change in volatile surface details, so exact hashing is unlikely to suffice.

Why not just let the model notice repetition from its own context, as reflection agents do? The WebArena authors report that GPT-4 agents repeatedly fell into loops and labeled 54.9% of feasible tasks as impossible. They also report a best success rate of 14.41% (WebArena: A Realistic Web Environment for Building Autonomous Agents). Anticipatory Reflection attributes "repetitive failure loops" to post-hoc reflection over long trajectories. Context-based noticing also cannot see sibling branches, so it cannot merge them. We will measure loop-trap rate, defined as the fraction of episodes ending in a revisited state at the step cap, for a Reflexion-style baseline against our method.

Why not just compare every new state immediately using embeddings? Embedding similarity with a threshold is cheap. However, it conflates states that look alike but differ in a filled field or a cart item, and that is precisely the costly error. Adding a verifier call to every embedding match brings back the cost of $N M$ comparisons. The immediate-dedup ablation at a matched call budget is the experiment that decides whether batching within buckets earns its place.

Why not just forbid cycles, as SeqCV does? Linearization worked well for creative tasks in Can Dependencies Induced by LLM-Agent Workflows Be Trusted?, but its authors state it cannot express refinement loops. WorkflowBench workflows also routinely require loops and conditionals (WorkflowLLM: Enhancing Workflow Orchestration Capability of Large Language Models). Our refinement-loop experiment compares against a fixed-iteration linear unrolling to show what forbidding cycles costs.

Proposed Experiments

The main experiment runs all agents on the 812 WebArena tasks. It reports success rate, environment steps, tokens, equivalence-check calls, and loop-trap rate, broken down by site.

The first decisive check is equivalence precision and recall against the 500 hand-labeled pairs. A false-merge rate above a few percent would mean the method destroys progress, so we will report task success conditioned on whether a false merge occurred.

The second decisive check sweeps signature granularity and the locality window $L$. The structured duplicate detection account predicts a U-shaped curve in judge cost as granularity varies. It also predicts that retaining $L$ equal to the empirical locality bound recovers nearly all merges found with full history. If neither prediction holds, the analogy to structured duplicate detection is wrong and we will say so.

For generality, we will run the same agents on the GAIA validation set (GAIA: a benchmark for General AI Assistants). Level 2 and Level 3 tasks require long tool chains in which revisits are common. As context, two-stage agent synthesis reports 47.18% GAIA test accuracy (On-Demand Multi-Agent Workflow Synthesis for Multimodal Long-Horizon Reasoning). We treat that figure as a reference for scale, not a matched baseline, because its backbone and budget differ.

The result that would most clearly support the proposal combines four outcomes. Semantic deduplication catches a substantial share of duplicates that exact hashing misses. Bucketed delayed checking matches immediate checking's recall at a fraction of its calls. Success on WebArena exceeds Anticipatory Reflection at equal budget. Loop-trap rate falls sharply.