acceptodds
Withdrawn from ICLR 2027

ELVA: VERIFICATION BEGINS BEFORE THE VERIFIER

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Web agents can report success even when every observation they rely on is correct. This can occur when observation processing preserves individual facts but loses which entities and actions they refer to, allowing unrelated facts to be combined into an unsupported completion proof. We formalize this failure as *inadmissible conjunction*. Our key idea is that verification must begin when evidence is collected, before these relationships are lost. We introduce ELVA, a runtime that preserves these relationships and checks whether earlier evidence remains valid as execution proceeds. These checks determine whether observations can jointly support completion or whether the agent needs further observation or repair. For the supported task dependencies, we prove a conditional guarantee excluding completion proofs that reuse stale action references or evidence whose supporting links have broken. Across five WebArena-Verified sites, ELVA achieves 47.51% overall task success, exceeding the strongest reproduced baseline by 6.15 percentage points. A controlled diagnostic also shows lower false-completion and missed-valid-evidence rates than a local verifier without lineage keys at the same evidence horizon. The largest ablation effects come from preserving evidence before verification and using verification results to guide subsequent actions.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Web Agents, LLM Agents, Agent Verification, Evidence Composition, Evidence Provenance

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_3oSLOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The author found a new problem in agent systems: web ‌agents ‌assume ‌that combining facts that are true about different entities is also true, such as "Issue A is open" and "Issue B is assigned to Alice" implies "the issue is open and assigned to Alice." ELVA solves this problem by keeping provenance of each piece of evidence, i.e., which page, item and action it was collected from, and dropping the evidence when the provenance is lost, and the agent stops when the evidence is complete. When evidence is missing, the agent backtracks to observe rather than making assumptions.

Critical strengths

The paper points out a real and under-studied failure in web agents: true facts get combined the wrong way, so the agent wrongly claims success. Framing verification as something that has to start during evidence collection, not only at the end, is a useful and fresh perspective.

ELVA uses explicit rules for when evidence can be reused and when it expires, so every completion decision can be traced and inspected. It also comes with a formal guarantee, which is uncommon for web-agent systems.

The method beats strong baselines on all five WebArena-Verified sites, and a controlled diagnostic shows it reduces both false “done” claims and missed valid evidence. Ablations then show which parts of the system actually drive the gains.

Critical weaknesses

The task compiler is hand-written regex rules containing domain terms such as “issue,” “project,” and “product,” and the system is tested on only one benchmark with one LLM.

The paper does not compare against LLM-based or learned verifiers on the same checkpoints, and it reports no token, call, or latency costs. Without these it is hard to tell whether ELVA beats simpler alternatives in practice, and the modest gains on some sites (under 2 pp on Reddit and Map) make this matter more.

In practice, “inadmissible conjunction” looks a lot like the verifier hallucinating a link between two unrelated facts, which raises the question of whether a stronger LLM verifier with entity-aware context would solve it without the whole runtime. The paper doesn’t measure how often this failure actually happens in real agent errors compared with ordinary hallucination or reasoning mistakes, and it doesn’t compare against LLM-based verifiers, so the main motivation is asserted rather than shown.

The framework is hard to be moved to new tasks because there are many hand-tuned thresholds and penalties.

Questions for authors

How common is the problem? In ELVA’s or the baselines’ failed trajectories, what fraction of false completions are actually caused by inadmissible conjunction, compared with ordinary hallucination or reasoning errors? If this failure is rare, the motivation for the whole runtime is much weaker.

Comparison to LLM verifiers. How does CIV compare with an LLM-based verifier (e.g., a strong model given the full trajectory with entity IDs kept) on the same 1,600 checkpoints? Can a stronger model avoid this failure on its own, without the hand-built pipeline?

Cost. What are the token usage, number of LLM calls, and wall-clock time per task for ELVA compared with the baselines? Without this, it’s unclear whether the 6.15 pp gain comes from better verification or just from more steps and compute.

Generalization and hand-tuning. How many compiler rules and hyperparameters (thresholds, penalties, priors) were tuned on WebArena, and were they tuned on the same tasks used for evaluation? Have you tried ELVA on a different benchmark (e.g., WorkArena or Mind2Web-Live) or with a different policy LLM?

Compiler coverage. On how many evaluation tasks does the compiler miss or mistranslate a requirement? Since fail-closed checks can’t catch requirements the compiler never extracted, this directly limits the guarantee.

Reviewer_oGakOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces ELVA, which targets solving the issue of early termination, evaluated mainly on computer use agents. They target removing cases of ‘inadmissible conjunction’, where parts of completion criterion is misremembered as fulfilled due to resolving entities incorrectly. (i.e., Alice assigned to issue A, issue B is open -> wrongly used to confirm Alice assigned to an open issue). They remove these cases by proposing rule based / harness engineering techniques including a better DOM representation and additional verification procedure and validate them on WebArena-Verified v1.2.3.

Critical strengths

The idea of the ‘inadmissible conjunction’ failure mode is interesting, however, some work may be required to prove it is a real bottleneck.

Critical weaknesses
  • Does not clearly quantify how often inadmissible conjunction is a bottleneck for models, see questions section.
  • Only one model is used (Gemini 3.1 Flash-Lite), it is unclear if the method remains robust or if the issue remains prevalent for other models.
  • Only one dataset is considered (WebArena-Verified), other works have used OS-World, WebVoyager, etc.
  • As mentioned in limitations: efficiency is not considered, the framework may potentially be much less cost effective and should be baselined against using more naive methods with higher compute budget.
Questions for authors

It is unclear that the inadmissible conjunction issue focused on in this paper is an important bottleneck in modern agents, is there any experiments or references you can add to show this? E.g., define and measure inadmissible conjunction, show this is an issue across a few models and standard agent harnesses.

Reviewer_gUk5OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The papers topic is interesting enough - what information should be tracked so as to reliably estimate task completion in web agents? And then can we build a verification layer with proofs based on tis tracked information? The poper specifically looks at particular failure mode, where individually correct observations are incorrectly conjoined, leading to false completion estimates.

I think the paper’s biggest weakness is the borderline impenetrable writing style, which made it really hard for me to understand, and which seems to make this work hard to reproduce. Secondary concerns include potential overfitting to the benchmark, and the significance of the evaluations.

  1. In general I think the writing can be significantly improved. The writing is needlessly dense, and hard to understand.
  • Take this passage for example: “This certificate rule evaluates predicate states and named guards rather than unrestricted proof search. The controller maps verdicts and obligations to completion, observation, exact-resource readback, or bounded grounded repair. Stop proposals and state-changing actions invoke CIV and the controller. Missing bindings request evidence rather than establishing task failure.” A certificate rule evaluating unrestricted proof search makes no sense. And the test is replete with long lists of entities (“completion, observation, exact resource …”) which make the whole thing hard to read for humans. The whole paper is full of these dense paragraphs.
  • Or take “Let ReasonsG(Xt) collect unresolved reasons from the environment, task-constraint, coverage, answer-grounding, mutation, navigation, and terminal-mode checks.” What is a “reason”? As far as I can tell there’s no prior technical definition of “reason” in the prior text. And again, a long list of entities, with no real definitions or descriptions.
  • This type of writing repeats all over the paper. Section 4 is particularly hard to understand, which is unfortunate since its the technical bulk of the paper. Further, the descriptions in Section 4 seem borderline irreproducible - see for example, my comment on APDC below. The proposition in Section 4.5 seems obvious but I may not have understood it. There’s a lot of jargon and dense asides that make understanding hard.
  1. A second main concern I have is - for the dependency guards in A.2 - ho general are these? These seem specifically targeted to a specific task-type and hence potentially over-fit to the benchmark (which would call into question the significance of the improvement)

  2. Why was Gemini Flash Lite used for the evaluations? The results reported here seem significantly lower than for example the results reported in https://paper-submission-anoymous.github.io/webtactix_introduction/ and others.

  3. If I understand correctly, APDC is the most impactful component, more than the lineage verification itself (CIV). However the paper described APDC perfunctorily: “Action-Preserving DOM Compilation (APDC) constructs compact semantic units retaining role, name, actionable identifier, state, parent, and candidate action.”. How would someone reproduce this idea?

Critical strengths

Please see my review

Critical weaknesses

The paper's writing style is its biggest weakness. Please see my review.

Questions for authors

I think the paper would be significantly strengthened by a rewrite that explains the main components (APDC, CIV etc.) without resorting to dense minutae. Also, it would help to run evaluations with stronger LLMs that make the results comparable to previously reported results (right now the results in this paper are significantly lower)

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.