RefinementGuard: Counterexample-Directed Semantic Qualification for Hidden Agent-Tool Execution
Organizations: Rice University
Abstract
Tool runtimes can lower an agent-selected operation into a hidden parallel graph, reducing latency and context while risking semantic mistranslation. We introduce RefinementGuard: translation validation for hidden, effectful agent-tool lowerings, coupled to artifact-bound, fail-closed runtime admission. Qualification compares a candidate graph with an independent reference on isolated state using explicit parent-operation obligations. We evaluate two repository-level contracts, bug localization and patch validation, on controlled repositories. Among 100 activated, non-equivalent development/qualification faults adjudicated by one human, parent-semantic validation rejects 49/100 (operator-cluster bootstrap 95% CI [33.7%, 64.8%]). The objective is selective admission, not maximum mutation rejection: exact equality rejects 100/100 faults but also all 60 valid variants, whereas obligation-based validation accepts 60/60; its 51 residual misses identify concrete specification gaps. On a frozen disjoint input split, the held-out B2-B3 result is localization-only because 21 patch mutants fail structurally; B3 rejects 38/56 localization defects. In a controlled asynchronous-delay regime, the localization serial/guarded median-latency ratio is 4.50x, and hidden execution exposes 74.3% less parent-visible context than visible execution. Patch validation shows no demonstrated speedup; zero-delay runs expose overhead. End-to-end qualification thus detects lower-layer misses while preserving localization's parallelism.
Figures & tables
Appendix figures & tables17 assets
Supplementary material from the paper’s appendix.
Appendix
| Contract | Nodes | Parallel nodes | Principal semantic obligations |
|---|---|---|---|
| localizeBug | 15 | 7 | Applicable branch completeness; grounded evidence; provenance; allowed ordering; localization quality; visibility |
| validatePatch | 5 | 2 | Conservative pass; mandatory checks; patched-state revision; failure preservation; visibility |
| Layer | Available evidence | Principal checks | Deliberate blind spot |
|---|---|---|---|
| B0 | Contract, candidate parent outcome | Schema, serialization, failure envelope, budgets | Graph and reference behavior |
| B1 | Graph, bindings, declarations | Topology, types, reachability, effects, resources | Concrete execution and parent meaning |
| B2 | Graph, local contracts, node evidence | Node schema, pre/postconditions, commit, effect, timeout | Reference parent observation |
| B3 | Paired parent observations, obligations | Parent-visible semantic refinement | Qualification admission and mutation label |
| Guard | qualification certificate, current bindings, call context | Artifact, environment, mode, and domain match | Semantic re-evaluation |
| Work | Verified object / method | RefinementGuard boundary |
|---|---|---|
| AgentSpec / Agent-C [ 18 , 6 ] | Proposed actions; rules or SMT | Below an already selected tool |
| ABC / VeriGuard [ 1 , 11 ] | Behavioral or safety policy | Harness translation correctness |
| ProbGuard [ 19 ] | Unsafe-state prediction; probabilistic monitoring | Paired parent observations |
| Lean4Agent [ 20 ] | Workflow/trajectory; Lean proofs | Concrete hidden lowering |
| CAVA [ 21 ] | Canonical action identity; attestation | Parent-operation refinement |
| RefinementGuard | Hidden effectful lowering; paired obligations | Artifact-bound admission |
| Obligation | Conclusive rule |
|---|---|
| Status refinement | Candidate success requires canonical success. |
| Schema refinement | On candidate success, validate output against the registered parent schema. |
| Budget refinement | Candidate output object-token count does not exceed the configured parent budget. |
| Effect refinement | Source-root digest is unchanged and declared parent-visible effects exactly equal canonical effects. |
| Visibility refinement | No runtime value IDs, sandbox paths, fault controls, or forbidden raw traces escape. |
| Failure refinement | Canonical visible failure is not converted to candidate success. |
| Corpus / family | Layer | Rejected | Total | Wilson 95% CI |
|---|---|---|---|---|
| Local-contract, activated | B1 | 0 | 48 | [0.0, 7.4]% |
| Local-contract, activated | B2 | 48 | 48 | [92.6, 100.0]% |
| Development semantic | B0 | 12 | 100 | [7.0, 19.8]% |
| Development semantic | B1 | 0 | 100 | [0.0, 3.7]% |
| Development semantic | B2 | 0 | 100 | [0.0, 3.7]% |
| Development semantic | B3 | 49 | 100 | [39.4, 58.7]% |
| Corpus | Lower only | Lower + B3 | Unique B3 | All accept | Cumulative reject |
|---|---|---|---|---|---|
| Development ( ) | 0 | 12 | 37 | 51 | 49 (49.0%) |
| Held-out inputs ( ) | 21 | 3 | 35 | 18 | 59 (76.6%) |
| Corpus | Paired | Exact two-sided | ||
|---|---|---|---|---|
| Development / qualification | 100 | 49 | 0 | |
| Held-out-input localization | 56 | 38 | 0 |
| Reason code | Count | Reason code | Count |
|---|---|---|---|
| OUTPUT_SEMANTIC_MISMATCH | 23 | VISIBILITY_LEAK | 6 |
| OUTPUT_SCHEMA_MISMATCH | 10 | WRONG_STATE_REVISION | 5 |
| MANDATORY_BRANCH_OMITTED | 9 | PROVENANCE_INVALID | 2 |
| BUDGET_VIOLATION | 2 | PROVENANCE_MISSING | 1 |
| Development / qualification | Held-out-input localization | |||||
|---|---|---|---|---|---|---|
| Variant | Reject | Total | vs. full | Reject | Total | vs. full |
| Full B3 | 49 | 100 | – | 38 | 56 | – |
| Common only | 16 | 100 | 5 | 56 | ||
| Without G/P/V | 44 | 100 | 0.0625 | 36 | 56 | 0.5 |
| Without provenance | 49 | 100 | 1.0 | 38 | 56 | 1.0 |
| Canonical equality only | 100 | 100 | 56 | 56 | ||
| Corpus | Contract | Operator | Reject | Rate |
| Dev. | localizeBug | completion_order_ranking | 3/3 | 100% |
| Dev. | localizeBug | drop_error_search_branch | 3/3 | 100% |
| Dev. | localizeBug | drop_provenance | 3/3 | 100% |
| Dev. | localizeBug | drop_symbol_search_branch | 4/4 | 100% |
| Dev. | localizeBug | leak_raw_observation | 2/3 | 66.7% |
| Dev. | localizeBug | narrow_search_scope | 2/7 | 28.6% |
| Condition | Stable decision code | Candidate starts | Canonical fallback | Coverage |
|---|---|---|---|---|
| All bindings and guard clauses match | execute_certified_graphlet | yes | no | unit + E5 |
| Qualification absent | fallback_missing_certificate | no | yes | unit + smoke + integration |
| Bound digest absent | fallback_invalid_digest | no | yes | source audit |
| Bound digest changed | fallback_stale_artifact | no | yes | unit + smoke |
| Environment clause fails | fallback_environment_mismatch | no | yes | source audit |
| Effect mode differs | fallback_effect_mode | no | yes | source audit |
| Check | localizeBug | validatePatch |
|---|---|---|
| Registered parent semantic tool called | ||
| Caller did not select internal nodes | ||
| Parent cannot observe hidden internal state | ||
| Trajectory references admission artifact | ||
| Stale variant prevented candidate start | ||
| Valid qualification admitted | – |
| localizeBug | validatePatch | ||||
|---|---|---|---|---|---|
| System | Latency ms | Context | System | Latency ms | Context |
| Serial canonical | 819.8 | 1205.0 | Serial canonical | 239.0 | 193 |
| No-parallel candidate | 843.7 | 1097.5 | No-parallel candidate | 223.6 | 208 |
| Visible graph | 163.7 | 4275.0 | Visible graph | 225.4 | 632 |
| Handcrafted parallel | 162.8 | 1097.5 | Handcrafted parallel | 222.1 | 208 |
| Unguarded hidden | 164.8 | 1097.5 | Unguarded hidden | 219.8 | 208 |
| localizeBug | validatePatch | ||||
|---|---|---|---|---|---|
| System | Latency ms | Context | System | Latency ms | Context |
| Serial canonical | 30.5 | 1205.0 | Serial canonical | 244.6 | 193 |
| No-parallel candidate | 27.4 | 1097.5 | No-parallel candidate | 230.9 | 208 |
| Visible graph | 24.9 | 4275.0 | Visible graph | 223.9 | 632 |
| Handcrafted parallel | 25.2 | 1097.5 | Handcrafted parallel | 231.2 | 208 |
| Unguarded hidden | 26.4 | 1097.5 | Unguarded hidden | 226.0 | 208 |
| Contract | Comparator | Cases | Median difference (ms) | Comparator/guarded 95% CI |
|---|---|---|---|---|
| localizeBug | Serial canonical | 40 | [4.38, 4.62] | |
| localizeBug | Unguarded hidden | 40 | [0.89, 0.95] | |
| validatePatch | Serial canonical | 40 | [0.95, 1.09] | |
| validatePatch | Unguarded hidden | 40 | [0.84, 0.99] |
| Contract | Metrics common to all systems and delay regimes | Tolerance result |
|---|---|---|
| localizeBug | MRR 1.0; recall@1/3/5 1.0; ground-truth-line evidence 1.0; snippet recall 1.0 | 12/12 cells pass |
| validatePatch | Passed accuracy 1.0; false-pass rate 0; false-fail rate 0; zero degradation versus serial | 12/12 cells pass |
| Contract | Run | Cases | Pass / preserve | Exposed failure | Semantic scope |
|---|---|---|---|---|---|
| localizeBug | Schedules | 320 | 320 | 0 | B1–B3 |
| localizeBug | Faults | 480 | 160 | 320 | B1–B3 |
| validatePatch | Schedules | 320 | 0 | 320 | B1 only; B2/B3 N/A |
| validatePatch | Faults | 480 | 0 | 480 | B1 only; B2/B3 N/A |