Who Verifies the Graph? Misspecification Attacks on Causal Action Verification for Language Agents

Fabio Rovai

cs.AISep 30, 2026

Who Verifies the Graph? Misspecification Attacks on Causal Action Verification for Language Agents

Authors: Fabio Rovai

Organizations: The Tesseract Academy London, United Kingdom

Abstract

Causal action verifiers gate an agent's state-changing tool calls by checking whether each proposed intervention is identifiable against a committed action-state graph, and they issue a certificate that carries the identification argument and a one-sided lower confidence bound. One such verifier, CIVeX, reports zero false executions on a confounded tool-use benchmark. We red-team it by corrupting only the committed graph. Omitting a single bidirected edge takes it from zero false executions to 15.3% at the benchmark's published confounding strength, with 91% of its executions harmful and utility falling from +2.27 to +0.35. Reversing one arrowhead, so that a mediator is committed as a confounder, gives 48.9% false executions and no correct ones. Every one of these actions carries an internally valid certificate. An attestation step that tests each observationally certified execution against a bounded randomised sample detected both attacks, with 2 false alarms in 555 executions on a truthful graph; refusing what fails the test, or cannot be tested, gave zero false executions in every setting we measured. It does not restore beneficial execution: at the published strength 97.1% of beneficial actions are still never executed, because the same misspecification rejects them before attestation runs. Those rejections carry certificates too, and auditing them works, but its cost scales with the number of rejections rather than the number of executions. Recovering safety costs 127 experiments per 1,050 actions; recovering the lost value costs 614 more, at which point the audited verifier makes the honest graph's decisions on every instance and spends exactly its experiment budget. An audit that inspects only executions protects against wrongful action. Wrongful inaction has to be paid for separately.

Figures & tables

Figure 1: Omitting one bidirected edge, as a function of hidden-confounder strength. The honest graph is flat across the range. The denied graph is harmless below strength

1.5

, falls off a cliff between

2.0

and

3.0

, and from

3.0

returns negative utility. Dotted line: the benchmark’s published strength. Dashed line: the always-abstain floor.

n=1{,}050

per point.

Figure 2: Three misspecifications, each against its own correct-graph control (the three run on different data-generating regimes, so a single shared baseline would mislead). Bad controls fail into paralysis; the omitted edge and the reversed arrowhead fail into wrongful action.

n=1{,}050

per bar.

committed graph	false exec	correct exec	utility	beneficial lost
correct ( $T\rightarrow M$ )	$0.0\%$	$51.1\%$	$+2.26$	$0.0\%$
direction flip ( $M\rightarrow T$ )	$48.9\%$	$0.0\%$	$-1.36$	$100\%$

Table 1: One reversed arrowhead inverts the verifier. Per-seed false-execution range under the flip:

42.7

–

57.3\%

n=1{,}050

per row.

strength	experiments	falsified	none	attest	none	refuse	fallback
	attestation		false exec		utility
$0.0$	555	2	$0.0\%$	$0.0\%$	$+2.79$	$+2.76$	$+2.76$
$0.5$	555	79	$0.0\%$	$0.0\%$	$+2.79$	$+2.52$	$+2.76$
$1.0$	554	547	$0.0\%$	$0.0\%$	$+2.79$	$+1.05$	$+2.76$
$1.5$	474	474	$0.0\%$	$0.0\%$	$+2.62$	$+1.03$	$+2.60$
$2.0$	201	201	$1.5\%$	$0.0\%$	$+1.72$	$+1.05$	$+1.77$

Table 2: Attestation on the denied graph, itemised. Experiments: observational EXECUTEs that were attested (one experiment each, out of

1{,}050

actions). Falsified: attestations whose intervals were disjoint. False executions are shares of all actions. Utility includes the experiment cost. On the honest graph attestation is never invoked: it has zero observational EXECUTEs at every strength, because its bidirected edge sends every action to the experiment path, where it already spends 741 experiments. This table assumes, as the benchmark’s experiment path does not, that a randomised sample exists for every attested action; see the text for the case where it does not.

graph	defence	false exec	correct exec	utility	beneficial lost
correct	none	$0.0\%$	$51.1\%$	$+2.26$	$0.0\%$
correct	attest / fallback	$0.0\%$	$34.4\%$	$+1.69$	$32.8\%$
flipped	none	$48.9\%$	$0.0\%$	$-1.36$	$100\%$
flipped	attest / refuse	$0.0\%$	$0.0\%$	$+0.58$	$100\%$
flipped	attest / fallback, committed graph	$34.6\%$	$0.0\%$	$-0.81$	$100\%$
flipped	attest / fallback, graph-free	$0.0\%$	$0.0\%$	$+0.58$	$100\%$

Table 3: Attestation against the direction flip, honouring experiment availability (unattestable executions refused). Detection works; the fallback must not reuse the committed adjustment set. The last row is the rejection audit of Section 6 .

n=1{,}050

per row.

Figure 3: Published confounding strength. (a) Attestation of executions, with an experiment assumed for every attested action, removes the false executions and leaves the lost beneficial actions where they were (

97.1\%

with fallback,

100\%

with refuse). (b) Auditing a share of the rejections as well, with experiment availability honoured: beneficial actions come back roughly in proportion to experiments spent, and auditing every rejection lands on the honest graph (ringed).

n=1{,}050

per point.

graph	defence	experiments	false exec	correct exec	utility	beneficial lost
honest	none	741	$0.0\%$	$38.0\%$	$+2.27$	$28.1\%$
denied	none	0	$15.3\%$	$1.5\%$	$+0.35$	$97.1\%$
denied	attest / refuse †	177	$0.0\%$	$0.0\%$	$+1.05$	$100.0\%$
denied	attest / fallback †	177	$0.0\%$	$1.5\%$	$+1.12$	$97.1\%$
denied	attest / fallback	127	$0.0\%$	$1.0\%$	$+1.10$	$98.0\%$
denied	+ audit 10% of rejections	213	$0.0\%$	$5.6\%$	$+1.24$	$89.4\%$

Table 4: Safety is cheap to recover and value is not. Published confounding strength. Experiments are randomised samples drawn per

1{,}050

actions. † Assumes a randomised sample exists for every attested action; the other denied rows honour the benchmark’s availability flag and refuse executions they cannot attest.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

cell ( $n=1{,}050$ , 7 seeds)	false exec	per-seed range	utility	per-seed range
honest graph, $s=2.5$	$0.0\%$	$0.0$ – $0.0\%$	$+2.27$	$+2.14$ to $+2.49$
denied graph, $s=2.0$	$1.5\%$	$0.7$ – $2.0\%$	$+1.72$	$+1.57$ to $+1.92$
denied graph, $s=2.5$	$15.3\%$	$13.3$ – $17.3\%$	$+0.35$	$+0.12$ to $+0.55$
denied graph, $s=3.0$	$40.8\%$	$37.3$ – $44.7\%$	$-1.36$	$-1.51$ to $-1.17$
denied + attest/fallback, $s=2.5$	$0.0\%$	$0.0$ – $0.0\%$	$+1.12$	$+0.88$ to $+1.26$
denied + attest/fallback, pass-through, $s=2.5$	$4.3\%$	$2.0$ – $6.7\%$	$+0.92$	$+0.69$ to $+1.15$

Appendix

Table 5: Seed-level spread for the headline cells.

Explore similar work

May 9, 2026cs.AI

CIVeX: Causal Intervention Verification for Language Agents

A valid tool call is not necessarily a valid intervention. Tool-using language agents are guarded by schema validators, policy filters, provenance checks, state predictors, and self-verification, yet such safeguards do not certify that a state-changing action has an identifiable causal effect. In confounded workflows, the action that looks optimal in observational logs can reduce utility when executed. We introduce CIVeX, a causal intervention verifier that maps proposed actions to structural causal queries over a committed action-state graph, checks identifiability, and returns one of four auditable verdicts: EXECUTE, REJECT, EXPERIMENT, or ABSTAIN. Execution requires an assumption-scoped causal certificate carrying graph commitments, an identification argument, a one-sided lower confidence bound (LCB), provenance, and risk limits. On Causal-ToolBench (1,890 instances, 7 seeds), CIVeX yields zero observed false executions across moderate and adversarial confounding. Under adversarial confounding it reaches 84.9% accuracy and 81.1% of oracle utility (+2.23 vs +2.76) and is the only non-oracle method whose constrained utility under a zero-false-execution constraint exceeds the AlwaysAbstain floor. On IHDP and ZOZO Open Bandit (real production logs with uniform-random ground truth), CIVeX matches Oracle correct-execution within 0.1pp and cuts per-execute false-execution by >=50x over naive baselines. A chain-of-thought LLM verifier (Claude Opus, Sonnet) cuts false-execution by an order of magnitude over a terse baseline, yet under adversarial confounding Opus's utility falls to 74% of CIVeX's. Intervention identifiability, not action validity, is the missing primitive for reliable tool use.

Fabio Rovai

The Tesseract Academy

Causal Intervention Validation

Ask PDF

Sep 14, 2026cs.LG

Look Before You Leap: Pre-Action Verification for LLM Agents

An LLM agent acts on the world by emitting actions: shell commands to run, edits to apply. A wrong action does not always fail loudly; it can fail silently, producing a plausible but incorrect effect that raises no error. We argue that a cheap deterministic check, run before an action takes effect, is an effective and underused form of agent oversight, and we study it across two action modalities in one framework. The idea is to fix an action's correct effect by construction, before any executor runs, so that silent failure is measured directly and the verifier may abstain rather than guess. For shell commands, a static verifier over 9930 commands and 482 tools catches 95.8% of invalid commands at a 10.0% false-positive rate. Its syntax and binary checks are oracle-exact, giving zero false positives while catching half of all errors; the flag check is bounded only by help-text coverage and accounts for every false positive. For code edits, a benchmark of 640 edits over 224 files isolating the apply step exposes a sharp split. Content-anchored formats such as search/replace and diff fail cleanly, whereas location-anchored formats fail silently: line numbers corrupt 99.1% of files under a one-line shift, and function-name edits hit the wrong function 12.7% of the time. In both settings a refuse-when-unsure policy turns silent failures into recoverable ones at a tunable cost in applicability: selective grounding reaches 0.958 recall at 7.0% false positives, and an anchor-and-verify applier records one silent misapplication in 8320 trials (0.01%). We release both benchmarks, the verifiers, and the guards.

Asaad Althoubi

Oklahoma State University Stillwater, OK USA

Verification Framework Large Language Model Agents Edit

Ask PDF

Apr 26, 2026cs.CR

Proof of Execution: Runtime Verification for Governed AI Agent Actions

Agent systems increasingly execute rather than advise. When an AI agent queries regulated data, invokes effectful tools, and mutates persistent state, correctness is not captured by whether a terminal output looks plausible. The operative questions are whether each step was authorized under a contract, whether the recorded history is tamper-evident, and whether the trajectory can be reconstructed deterministically. We formalize this as runtime proof of execution. An execution is a triple

x = (C, T, R)

: a contract

C

, an Execution Causal Event Stream (ECES)

T

, and a replay context

R

. A well-formedness predicate and five validator-checkable invariants form the PoE validity predicate. Five semantic guarantees describe authorization, path compliance, null effect on deny, history integrity, and replayability. We prove soundness under explicit cryptographic and deployment assumptions: any PPT adversary that produces a PoE-valid execution violating a semantic guarantee yields a signature forgery, a hash collision, or a quantified deployment-failure event. The Prime Execution Model (PEM) separates planning, enforcement, effect, and recordkeeping into distinct authority planes; a lemma reduces trace completeness to Effector-exclusive credentialing. An Execution Attestation Certificate is issued only when PoE = 1. In a single-node TypeScript prototype, PoE adds approximately 2.7 ms on a minimal flow and 4.4% overhead on concurrent batch workloads; a standard eight-event trace compresses to approximately 1.1 KB; injected Gateway-bypass and trace-mutation attacks are rejected. PoE does not replace consensus, TEEs, or zkVMs; it binds authorization, effect, history, and replay into a single runtime-checkable object so that governed execution becomes attestable under contract.

James Rhodes, George Kang

AlphaBitCore, Inc.

Runtime Enforcement Integrity Runtime Artificial Intelligence Agents Proof

Ask PDF