acceptodds
Under review as a conference paper at ICLR 2027

When Can an Underspecified Language Agent Act? Certain-Action Verification via Outcome Invariance

Abstract

Tool-using language agents must decide whether to act, clarify, or declare a request non-actionable under underspecification. Existing confidence and clarification methods focus on recovering a likely intent, but action safety depends on whether feasible interpretations induce different policy-relevant outcomes. We introduce CAVI, a contract-relative framework that represents interface-feasible task completions and certifies action only when all represented completions collapse to one outcome class. Otherwise, it returns outcome-distinguishing counterexamples or a machine-checkable non-actionability certificate. Under conservative completion coverage, faithful outcome abstraction, exact verification, and transaction-stable execution, CAVI certificates are sound for atomic or transaction-scoped actions. At the verifier level, across 120,000 requests in 12 domain-distribution cells, CAVI reaches the matched zero-false-action frontier while certifying 36.42% of requests; independent enumerative and symbolic implementations agree on all labels, and 1.2 million metamorphic checks produce no label failure. A frozen 2,160-call cross-domain parser confirmation yields 0 false actions and 0 false certificates among 533 certificates while certifying 24.68% of calls, and exposes high completion under-approximation and low clarification recall as the remaining parser boundary. We then test the same decision principle end-to-end: in a blind executable validation on held-out tasks in local state-mutating application sandboxes, CAVI operates as a consequential-action gate inside an LLM agent loop, reducing the false action rate to versus for direct execution while cutting unnecessary clarification to versus under conservative always-clarify interaction. Conservative completion coverage remains an important boundary; a mechanical semantic audit found one proposal–task mismatch among 83 CERTAIN_ACTION certificates, exposing proposal faithfulness as an additional agent-integration boundary. CAVI thus converts model-proposed task hypotheses into conditional, auditable action guarantees rather than relying on confidence alone.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Outcome Invariance, Certain-Action Verification, Contract-Relative Certification

Reviews

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

The paper introduces CAVI, which decides whether an agent should act, ask for clarification, or declare a request non-actionable by comparing the outcomes of possible interpretations. It provides a conditional soundness result, a synthetic benchmark, and evaluations with model-generated interpretations and executable agent sandboxes. The reported results suggest that outcome-based checking can reduce unnecessary clarification while limiting incorrect actions.

Critical strengths

Comparing consequences rather than surface interpretations is a useful way to decide when clarification matters. The targeted outcome-abstraction experiment provides concrete support: PolicyOmega asks unnecessary questions on 29/80 tasks versus 78/80 for FullState, and 42 paired cases isolate the abstraction effect on identical represented spaces and concrete outcomes.

The paper explicitly separates its conditional theorem from end-to-end correctness. The parser coverage audits, transaction checks, and disclosed proposal–intent mismatch make the limits of certification visible. These diagnostics are useful beyond aggregate task success.

Critical weaknesses

The decision rule appears to discard a consequential form of ambiguity. Appendix A.1 allows a completion to be consistent with the request but non-executable, with F(z) empty. Suppose a request could refer to order A or B, A cannot be cancelled, and B can. With exact coverage, F(z_A) is empty and F(z_B) contains one outcome, so the stated rule returns CERTAIN_ACTION. Yet cancelling B is not justified if the user meant A. The theorem about equivalence of reachable outcomes can still hold, but it does not resolve this permission-to-act question. The paper needs either an additional condition or a clear justification for excluding blocked interpretations from the decision.

Several central evaluation quantities do not reconcile under their stated definitions. Section 6 defines NCR as correct clarifications among 720 gold-clarification calls, but Table 3 reports 1,554 clarification decisions and only 73 correct clarifications. With only 1,440 calls outside that gold class, at least 114 of those decisions must be correct clarifications. Appendix B also reports grounded coverage as both 91/105 and 90/105. Finally, the 44/60 executed gold-act tasks in Section 6.1 need reconciliation with the 57 successes across FS, HU, and SD in Table 7. These discrepancies affect the safety–interaction assessment, rather than only presentation.

Questions for authors

How does CAVI handle a mixture of executable and non-executable interpretations that are all consistent with the request? Does the implementation represent non-execution as a distinct outcome, require universal executability, or apply another rule absent from the formal definition?

Please provide the parser’s three-way confusion matrix, including terminal-failure routing, and reconcile the NCR, coverage, and executed-task counts identified above. In particular, does 44/60 refer to eventual execution or a more restricted stage of the trajectory?

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

This paper proposed a verification framework that determines whether a underspecified request can be safely executed based on outcome invariance across feasible interpretations. it provides soundness guarantees and synthetic benchmsrks to evaluate the method. The results show reduced unsafe actions and unnecessary clarifications.

Critical strengths
  1. The outcome invariance offers a principled alternative to confidence-based action decisions, with explicit theoretical guarantees and clearly stated assumptions.
  2. The paper combines large-scale verifier tests, independent implementation checks, and end-to-end agent experiments. The reduction in unnecessary clarification while maintaining low false-action rates is promising.
Critical weaknesses
  1. The soundness guarantee relies critically on conservative completion coverage and faithful action proposals. However, 46.83% of schema-valid parser outputs under-approximate the completion space. The end-to-end evaluation identifies a mismatch beyween proposal and intent. These findings raise concerns about how reliably the theoretical guarantees transfer to practical agents.
  2. There is limited evidence of superiority and generalization. At the verifier level, several strong baselines match CAVI's performance and cost. The main distinction is certificate generation, however, the complete replay validation remains unfinished.
Questions for authors
  1. How can conservative completion coverage be reliably established at deployment without access to oracle completions, especially when the parser omits outcome-relevant interpretations?
  2. Can the authors demonstrate improvements over stronger outcome-aware baselines on structurally held-out tasks?
Reviewer_mkbUOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes CAVI, a framework that decides whether an LLM agent should act, clarify, or decline an underspecified request. It enumerates the feasible completions of the request and certifies action only when all of them produce the same policy-relevant outcome. The authors prove conditional soundness under coverage, abstraction-faithfulness, and transaction-stability assumptions. They evaluate CAVI on a synthetic 120k-instance benchmark, a parser study, and a 105-task sandbox. There it cuts false actions compared with direct execution and asks for fewer unnecessary clarifications than always-clarify.

Critical strengths

None.

Critical weaknesses

I don't think the technical contribution of this paper is worth reviewing for the following major concerns. And the following list is not exhaustive of the critical weaknesses.

  • This paper is hard to read; process vocabulary crowds out the contribution. The jargon is dense and heavy. Missing parentheses (e.g. “...when uncertainty is high Kuhn et al. (2023)”) likely due to a \citet/\citep slip.
  • “Kuhn et al. (2025), Clarify when necessary” has the wrong authors. The paper is real, but its authors are Michael JQ Zhang and Eunsol Choi. The listed author list appears to be fabricated.
  • Libkin (2011), AIJ 175(7–8) is wrong. “Certain answers as objects and knowledge” appeared in Artificial Intelligence 232 (2016), with a preliminary version at KR’14.
  • The theorem is essentially definitional. Theorem 1 says: if the represented space covers the true one (A1), the abstraction is faithful (A2), verification is exact (A3), and state is stable (A4), then a singleton outcome set implies safety. That follows in a few lines, as the proof itself shows. All the difficulty sits in A1 and A2, and the paper assumes both rather than solving them. The coNP membership and hardness results are standard and add little.
  • The headline Arena result is circular. Arena gold labels are computed from outcome classes over Z_true. CAVI (oracle) then decides from the outcome classes of the same oracle completion space. Zero FAR in 12/12 cells and “matching the frontier” follow by construction. Table 2 is also odd. ExactEVPI, OutcomeRuleChecker, ActionEqualityCert. and PolicyUniqueCert. have identical FAR, Q and Act (0.3642) to CAVI. The only difference is the “Cert” column, which is zero for them because they don’t emit certificates. The claimed advantage is therefore a labeling artifact.
Questions for authors

I do not have any question.

Reviewer_sN1xOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposed a CAVI (Certain-Action Verification via Outcome Invariance) framework, determining whether AI agents can safely execute underspecified requests. Instead of relying on intent confidence, this work constructs a conservative space of feasible task completions and certify an action when all reachable outcomes belong to the same policy-relevant ewuivalence class. Otherwise, it requests clarification or returns a non-actionability certificate. The framework provides conditional soundness guarantees and incorporates outcome abstraction, machine-checkable certificates, and transaction rechecking. Experiments on synthetic benchmarks and executable agent sandboxes demonstrate reduced false actions and unnecessary clarification compared with direct execution and clarification-based baselines.

Critical strengths

S1. Novel outcome-oriented perspective. The paper provides an interesting perspective on underspecified agent requests, shifting the decision criterion from intent confidence to policy-relevant outcome invariance. This offers a principled way to distinguish harmless ambiguity from ambiguity requiring clarification.

S2. Clear formalization and explicit safety conditions. The paper provides a structured formulation of outcome-invariance certification, including conditional soundness guarantees, policy-defined outcome abstractions, and transaction rechecking. The explicit characterization of trusted assumptions and failure boundaries is valuable.

S3. Systematic controlled evaluation and failure analysis. The paper evaluates CAVI across large-scale synthetic benchmarks, independent verifier checks, parser experiments, and state-mutating agent sandboxes. The detailed audits of completion coverage, outcome-schema sensitivity, and proposal–intent mismatches provide useful insights into the framework's limitations.

Critical weaknesses

W1. Limited practical feasibility and scalability. CAVI requires verifying outcome invariance across feasible task completions, which may incur substantial overhead for large candidate spaces and complex multi-step operations. Stateful or irreversible tool calls further require reliable simulation and state isolation, as highlighted by AppWorld [1] and ToolEmu [2]. Although symbolic verification mitigates enumeration costs, the experiments mainly cover structured, factorable domains. CAVI also increases LLM calls from 1.00 to 2.89 per task, without reporting end-to-end latency or state-management overhead (Appendix A.6 and B).

W2. Strong dependence on difficult-to-guarantee safety assumptions. CAVI's soundness relies on conservative completion coverage, faithful outcome abstraction, and accurate execution semantics, which are challenging to establish in open-ended environments [3, 4]. The paper reports that 46.83% of schema-valid parses exhibit known under-approximation (Table 3), while 15/105 executable tasks violate the coverage assumption, including 8 receiving CERTAIN ACTION certificates (Appendix B). Moreover, removing critical outcome fields yields a 33.33% false-certificate rate in targeted audits. The reliability of certification under unknown interpretations or unmodeled side effects remains insufficiently established.

W3. Outcome invariance does not ensure end-to-end task correctness. CAVI verifies agent-proposed actions without independently ensuring their consistency with the original user request. Proposal faithfulness remains an external assumption, despite recent work demonstrating the importance of action-level task alignment [5, 6]. This limitation is evident in the paper's executable evaluation, where an event creation was certified despite the user's deletion request, resulting in a semantic certificate error (1/83, Section 6.1 and Appendix B). Without explicit request–proposal alignment verification, valid certificates may still authorize incorrect operations.

[1] Trivedi et al. AppWorld: A Controllable World of Apps and People for Benchmarking Interactive Coding Agents. ACL 2024. https://aclanthology.org/2024.acl-long.850/

[2] Ruan et al. Identifying the Risks of LM Agents with an LM-Emulated Sandbox. ICLR 2024. https://proceedings.iclr.cc/paper_files/paper/2024/hash/7274ed909a312d4d869cc328ad1c5f04-Abstract-Conference.html

[3] Le-Cong et al. Can LLMs Reason About Program Semantics? A Comprehensive Evaluation of LLMs on Formal Specification Inference. ACL 2025. https://aclanthology.org/2025.acl-long.1068/

[4] Li et al. OSVBench: Benchmarking LLMs on Specification Generation Tasks for Operating System Verification. AAAI 2026. https://doi.org/10.1609/aaai.v40i37.40437

[5] Ning et al. When Actions Go Off-Task: Detecting and Correcting Misaligned Actions in Computer-Use Agents. ICML 2026. https://proceedings.mlr.press/v306/ning26c.html

[6] Jia et al. The Task Shield: Enforcing Task Alignment to Defend Against Indirect Prompt Injection in LLM Agents. ACL 2025. https://aclanthology.org/2025.acl-long.1435/

Questions for authors

How does CAVI handle continuous-valued latent variables, intermediate states, or execution outcomes, where explicit enumeration is infeasible? Can the proposed symbolic verification establish outcome invariance over such potentially infinite spaces while maintaining soundness and practical efficiency?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.