cs.CLNov 17, 2026

Runtime Verification of Multiple Natural Language Criteria for Agent Governance

Authors: Silviu Pitis, Parand A. Alamdari, Jessica Tang, Toryn Q. Klassen, Sheila A. McIlraith

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

Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Verifying Agents in Rubric-Graded Environments

    Nov 17, 2026Markus Dücker, Vaibhav Kumar, Yi Liu +4LLM Agent VerificationAI Agent Evaluation

  2. VeriHarness: Scaling Agentic Verification for Long-Horizon Tasks

    Oct 1, 2026Caiqi Zhang, Rujun Han, Zifeng Wang +4LLM Agent VerificationLong-Horizon LLM Agents