Runtime Verification of Multiple Natural Language Criteria for Agent Governance
Organizations: University of Toronto Toronto, Canada · Vector Institute Toronto, Canada
Abstract
AI agents are governed by hundreds of natural language criteria, yet existing verifiers cannot efficiently evaluate an agent's output against a large set of such criteria and report which are satisfied, violated, or inapplicable. We introduce the VFM, a tree-attention verifier that encodes the shared context and target text, and scores N natural language criteria in parallel, returning independent per-criterion ternary verdicts. The VFM is pretrained on CriteriaBank, a corpus of 394K (context, target, criterion, verdict) tuples spanning over 321K distinct criterion strings. A finetuned VFM-4B outperforms GPT-5.4 on a synthetic governance benchmark. On the DynaBench multi-criterion benchmark, it outperforms DynaGuard-4B on trace-level failure detection, and its per-criterion verdicts localize the violated rule and support focused escalation to a larger chain-of-thought judge. We show that CriteriaBank pretraining improves cross-domain transfer, particularly in the low-data regime, while matching a strong direct-finetuning control at full data. On a single H100, VFM-4B evaluates 1,000 criteria against a 4K-token context in under 2s at <11 GB VRAM, making it suitable for runtime verification.
Figures & tables
| Accepts free-text criteria | Governance rules are expressed in natural language |
|---|---|
| Adapts to diverse contexts | Deployer policies and user instructions may change based on the interaction |
| Issues per-criterion verdicts | Monitoring and auditing require knowing which rules passed or failed |
| Scales efficiently for runtime | Hundreds of criteria must be evaluated with runtime latency |
| Stream | Source | Tuples | Criteria | Role |
|---|---|---|---|---|
| A (Synthetic) | Concept-first generation | Broad criteria coverage | ||
| B (Real data) | WildChat/WildJailbreak [ 71 , 24 ] | Real user/model scenarios | ||
| C (Gap-filling) | Targeted synthetic scenarios | Tools, error-correction, business | ||
| C+ (Multi-turn) | LMSYS-Chat-1M [ 73 ] | Multi-turn conversations | ||
| D (Safety) | Synthetic (safety taxonomy) | Guardrail-style criteria | ||
| Total | 393,531 | 321,419 |
| Method | CoT | FAIL F1 |
| DynaGuard-4B [ 20 ] | yes | 0.720 |
| DynaGuard-8B [ 20 ] | yes | 0.731 |
| Gemma4-E4B-it (raw rules) | yes | |
| Gemma4-26B-A4B-it (raw rules) | yes | |
| Gemma4-26B-A4B-it (decomposed rules) | yes | |
| Direct-FT-4B | no |
| 0.6B backbone | 4B backbone | ||||||||
| Prefix | Path | K | VRAM | K | VRAM | ||||
| 144 | vfm-batched | 32 | 50 | 311 | 36 GB | 53 | 115 | 884 | 55 GB |
| llm-prefix | 34 | 52 | 326 | 38 GB | 57 | 120 | 929 | 57 GB | |
| 1K | vfm-pc, =64 | 31 | 63 | 454 | 1.9 GB | 63 | 147 | 1,223 | 8.8 GB |
| llm-prefix | 52 | 122 | 1,036 † | 78 GB | 100 | 250 | 2,214 † | 70 GB | |
| 4K | vfm-pc, =64 | 56 | 106 | 687 | 3.2 GB | 156 | 279 | 1,807 | 10.5 GB |
Appendix figures & tables15 assets
Supplementary material from the paper’s appendix.
Appendix
| Criterion | Context | Target | Label | Rationale |
|---|---|---|---|---|
| Does the response disclose that it is AI-generated? | User-facing chat: “Help me plan a 3-day trip to Lisbon.” | “Hi! I’m an AI assistant. Here are three options…” | yes | Disclosure required and present |
| Same | User-facing chat: “Help me plan a 3-day trip to Lisbon.” | “Here are three options…” | no | Required and absent |
| Same | Internal API call; no user-facing dialogue | {flight: ..., hotel: ...} | n/a | Precondition (consumer-facing context) does not hold |
| Same | Multi-agent log; “user” role unclear | “Here are three options…” | n/a | Trace insufficient to determine whether disclosure was required |
| Stream | Examples | Unique criteria | Avg. trace | Label dist. |
|---|---|---|---|---|
| A (Synthetic) | 130 tok | 45/50/4% | ||
| B (Distillation) | 1,130 tok | 38/51/11% | ||
| C (Gap-filling) | 230 tok | 37/50/13% | ||
| C+ (Multi-turn) | 742 tok | 42/44/14% | ||
| D (Safety) | 135 tok | 51/48/0% | ||
| Total | 393,531 | 321,419 | — | 40/50/10% |
| Subset | (drop A) | (drop B) | (drop C) | (drop D) |
|---|---|---|---|---|
| BeaverTails | ||||
| ContractNLI | ||||
| IFEval | ||||
| PRM800K | ||||
| Governance |
| Subset | noB @ 788 | noB @ 2787 | full @ 2787 | matched-EP | matched-ST |
| Stream A (val) | 80.93 | 91.39 | 85.71 | ||
| Stream B (val) | 86.61 | 89.40 | 94.33 | ||
| Stream C (val) | 83.40 | 93.90 | 93.25 | ||
| Stream D (val) | 95.20 | 97.59 | 99.21 | ||
| BeaverTails | 68.78 | 77.42 | 74.40 | ||
| ContractNLI | 49.27 | 62.03 | 54.41 |
| Parameter | CriteriaBank pretraining | Downstream finetuning |
|---|---|---|
| Head LR | ||
| Backbone LR | ||
| Schedule | cosine | cosine |
| Warmup ratio | 3% | 10% |
| Epochs | 1 | , early stopping (patience 5) |
| KL regularizer | (omitted for VFM w/o KL) | none |
| Benchmark | Setting | Records † | Criteria | Labels | Metric |
|---|---|---|---|---|---|
| Governance (§ 4.1 ) | synthetic compliance | regulatory rules | ternary | Acc | |
| Governance transfer (§ 4.1 ) | synthetic compliance | held-out regulations | ternary | Acc | |
| INSURE-Dial (§ 4.2 ) | insurance-benefit calls | - procedural checks | ternary | Acc/F1 | |
| DynaBench (§ 4.3 ) | agent guardrails | rules (max ) | binary | F1 | |
| BeaverTails (§ 4.4 ) | response safety | harm label | binary | F1 | |
| IFEval (§ 4.4 ) | instruction following | constraints | binary | BalAcc |
| Model | BT (F1) | IFEval (BalAcc) | PRM (BalAcc) | AggreF (BalAcc) | CNLI (mF1) |
|---|---|---|---|---|---|
| Qwen3Guard-Gen-4B | 85.4 [83.0, 87.5] | — | — | — | — |
| Qwen2.5-Math-7B-PRM800K | — | — | 81.6 [80.2, 83.0] | — | — |
| Qwen3-4B (direct) | 49.8 [45.2, 54.1] | 56.1 [55.0, 57.1] | 74.2 [72.6, 75.7] | 74.8 [72.8, 76.7] | 51.5 [49.2, 53.6] |
| Qwen3-Next-80B-A3B (CoT) | 80.0 [77.2, 82.6] | 70.1 [68.5, 71.6] | 84.5 [83.2, 85.8] | 81.7 [80.1, 83.4] | 71.2 [68.9, 73.3] |
| Linear Probe (Qwen3-4B) | 81.2 | 83.5 | 76.7 | — | 47.6 |
| Direct-FT-4B | 83.5 0.7 | 94.6 0.7 | 82.1 0.6 | 75.4 1.8 | 84.1 0.6 |
| Prefix 1K | Prefix 4K | |||
|---|---|---|---|---|
| Method | K | K | ||
| VFM backbone (1-tok readout) | 284 | 2,437 | 871 | 8,138 |
| 1-tok judge (logprobs) | 284 | 2,407 | 875 | 8,130 |
| LMUnit-style scorer | 816 | 4,621 | 1,665 | 12,943 |
| CoT judge | 908 | 5,321 | 1,819 | 14,004 |
| VFM, HuggingFace | 147 | 1,223 | 279 | 1,807 |
| Model | InfoB | Gov | CNLI | INSURE | BT | IFEval | PRM | AggreF |
|---|---|---|---|---|---|---|---|---|
| lm-init-0.6B | 0.603 | 0.793 | 0.766 | 0.708 | 0.615 | 0.458 | 0.472 | 0.598 |
| VFM-0.6B (w/o KL) | 0.844 | 0.888 | 0.852 | 0.663 | 0.734 | 0.651 | 0.577 | 0.752 |
| VFM-0.6B | 0.887 | 0.880 | 0.857 | 0.713 | 0.722 | 0.654 | 0.635 | 0.736 |
| lm-init-4B | 0.591 | 0.791 | 0.821 | 0.654 | 0.692 | 0.554 | 0.524 | 0.763 |
| VFM-4B (w/o KL) | 0.891 | 0.909 | 0.893 | 0.686 | 0.777 | 0.714 | 0.781 | 0.851 |
| VFM-4B | 0.942 | 0.927 | 0.899 | 0.671 | 0.779 | 0.704 | 0.782 | 0.857 |
| Pair | Ternary agreement ( ) | yes vs. yes ( ) | no vs. no ( ) |
|---|---|---|---|
| A1 – A2 | .67 (.51) | .92 [.84,.96] (.82 [.67,.94]) | .67 (.28) |
| A1 – A3 | .73 (.60) | .88 [.79,.94] (.73 [.55,.88]) | .77 (.41) |
| A2 – A3 | .65 (.49) | .88 [.79,.94] (.72 [.54,.88]) | .71 (.38) |
| A1 – Labeler | .81 (.72) | .92 [.84,.96] (.82 [.69,.94]) | .81 (.54) |
| A2 – Labeler | .65 (.48) | .87 [.77,.93] (.69 [.51,.86]) | .67 (.30) |
| A3 – Labeler | .69 (.54) | .88 [.79,.94] (.73 [.55,.88]) | .72 (.35) |
| Pair | Ternary agreement ( ) | yes vs. yes ( ) | no vs. no ( ) |
|---|---|---|---|
| A1 – A2 | .81 (.71) | .89 [.80,.94] (.77 [.60,.91]) | .85 (.70) |
| A1 – A3 | .81 (.70) | .87 [.77,.93] (.71 [.54,.86]) | .87 (.73) |
| A2 – A3 | .76 (.62) | .86 [.77,.92] (.72 [.55,.86]) | .80 (.59) |
| A1 – Teacher | .73 (.60) | .93 [.85,.97] (.85 [.70,.97]) | .76 (.52) |
| A2 – Teacher | .70 (.55) | .91 [.82,.95] (.80 [.64,.93]) | .78 (.53) |
| A3 – Teacher | .71 (.56) | .88 [.79,.94] (.74 [.58,.89]) | .79 (.56) |
| Benchmark | traces | top-1 | top-3 | recall@ | all-in-top- |
|---|---|---|---|---|---|
| INSURE-Dial | |||||
| Governance |
| stratum | traces | % FAIL | Gemma-only CoT | Cascade top-3 CoT | |
|---|---|---|---|---|---|
| 220 | 50.0% | pp | |||
| – | 149 | 32.2% | pp | ||
| – | 112 | 42.0% | pp | ||
| 62 | 100.0% | pp | |||
| all | 543 | 49.2% | pp |
| Escalated fraction | Traces to judge | FAIL-F1 |
|---|---|---|
| (VFM alone) | ||
| (full cascade) |
| Benchmark | VFM-4B P / R / F1 | Frontier judge | Judge P / R / F1 | VFM pass error |
|---|---|---|---|---|
| Governance (in-distribution) | 83.8 / 87.4 / 85.5 | GPT-5.4 | 82.8 / 77.9 / 80.3 | 5.6% |
| Governance (held-out regulations) | 76.7 / 73.0 / 74.6 | GPT-5.4 | 76.8 / 75.5 / 76.1 | 11.1% |
| INSURE-Dial (real calls) | 82.4 / 75.1 / 78.6 | GPT-5.4 | 60.2 / 86.1 / 70.8 | 19.4% |
| DynaBench (traces) | 83.1 / 94.9 / 88.5 | Gemma-4-26B | 96.0 / 88.8 / 92.2 | 5.1% |