🤖 machine learning

VNN-LIB 2.0: Rigorous Foundations for Neural Network Verification

This paper presents VNN-LIB 2.0, a rigorously formalized standard for neural network verification that introduces a "network theory" abstraction to decouple the specification from evolving ONNX models, while providing a precise syntax, type system, and semantics mechanized in Agda to ensure internal consistency and interoperability.

Original authors: Ann Roy, Allen Antony, Andrea Gimelli, Matthew L. Daggitt

Published 2026-05-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ann Roy, Allen Antony, Andrea Gimelli, Matthew L. Daggitt

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to get a team of different robots to solve a puzzle together. In the world of Artificial Intelligence, these "robots" are neural networks (the brains behind AI), and the "puzzle" is verification (checking if the AI will make a safe or correct decision).

For a long time, the people who built these robots and the people who checked them didn't speak the same language. They used a standard called VNN-LIB 1.0, but it was like a dictionary with missing words, no grammar rules, and definitions that changed every time someone looked at them.

This paper introduces VNN-LIB 2.0, a brand new, rigorous "language" that fixes these problems. Here is how the authors explain it using simple concepts:

1. The Problem: A Broken Translator

Think of VNN-LIB 1.0 as a translator that was trying to speak two languages at once but kept getting confused.

No Grammar: It didn't have strict rules for how to write a question. So, one robot might understand a sentence one way, and another robot might understand it differently.
Limited Vocabulary: It could only handle simple puzzles (one input, one output). Real-world AI often has complex inputs (like an image and some text) and multiple outputs.
Floating Point Confusion: Computers use "approximate" numbers (like 3.14159...), but the old standard didn't specify if you should treat them as exact math or rough approximations. This led to dangerous errors where a robot thought it was safe, but it wasn't.
The "Black Box" Issue: The old standard relied on a file format called ONNX (the blueprint for the AI). But ONNX didn't have a strict, official definition of what its symbols meant. It was like giving a robot a blueprint drawn in crayon that keeps changing its mind about what a "wall" is.

2. The Solution: The "Network Theory" (The Universal Adapter)

The biggest innovation in this paper is a concept called a Network Theory.

Imagine you are building a universal power adapter. You don't want to build a new adapter for every single country's wall socket (every version of ONNX). Instead, you create a universal interface that says: "As long as the socket provides electricity, voltage, and a ground, I can plug in."

The Network Theory ( $\Psi$ ): This is that universal interface. It doesn't care exactly how the ONNX blueprint is drawn. It just asks: "Do you have a way to define a number? A shape? A connection?"
The Result: VNN-LIB 2.0 can now talk to any version of ONNX, even future ones, without needing to be rewritten. It separates the question (the query) from the blueprint (the model), allowing them to evolve independently.

3. The New Language: VNN-LIB 2.0

With this new foundation, the authors built a much smarter language with three main upgrades:

Richer Sentences (Syntax): You can now ask about complex scenarios. Instead of just checking one robot, you can ask, "If Robot A and Robot B work together, do they stay safe?" You can also peek inside the robot's "brain" to check its hidden thoughts (hidden layers), not just the final answer.
Strict Grammar (Type System): The language now forces you to be precise. If you try to add a "temperature" to a "color," the language will say, "No, that doesn't make sense." This prevents the computer from making math errors by mixing up different types of numbers.
Clear Meaning (Semantics): Every word in the new language has a mathematically proven definition. There is no guessing. If you write a query, the computer knows exactly what mathematical problem you are asking it to solve.

4. The "Real-World" vs. "Perfect Math" Option

The paper acknowledges a tricky situation: Some robots are checked using "perfect math" (Real numbers), while the actual robot runs on "approximate math" (floating-point numbers).

The Old Way: This was a hidden danger. The checker would say "Safe," but the real robot might crash.
The New Way: VNN-LIB 2.0 lets you explicitly say, "I know this is using approximate math, but I want to check it using perfect math anyway." It puts a warning label on the query: "Proceed with caution, this might be slightly inaccurate." This allows researchers to use powerful tools without pretending the math is perfect when it isn't.

5. The "Gold Standard" Proof

To make sure they didn't make any mistakes in writing this new language, the authors didn't just write it down; they programmed it into a math-proving robot called Agda.

Think of Agda as a super-strict editor that checks every single rule of the new language to ensure there are no logical holes.
Because the language is "mechanized" in Agda, anyone can now use this proof to verify that their own tools (solvers) are working correctly. It turns the standard from a "suggestion" into a "mathematically guaranteed contract."

Summary

In short, VNN-LIB 2.0 is a new, strict, and flexible language for asking AI safety questions. It fixes the broken grammar of the past, allows for complex questions about multiple AI models, and provides a mathematically proven foundation so that when a tool says "This AI is safe," we can actually trust that it means exactly what it says.

Technical Summary: VNN-LIB 2.0: Rigorous Foundations for Neural Network Verification

Problem Statement

The neural network verification community has increasingly relied on the VNN-LIB standard (Version 1.0) to facilitate interoperability between solvers and higher-level tools. However, Version 1.0 suffers from four critical deficiencies that prevent it from serving as a rigorous formal foundation:

Lack of Formal Syntax: Version 1.0 does not formally define the query language syntax, leading to mutually incompatible implementations by different solvers.
Limited Expressivity: The standard assumes a single network with a single input and output. It cannot natively support multiple networks, multiple inputs/outputs, or access to hidden layers, forcing users to merge models artificially, which obscures the relationship between verified artifacts and deployed models.
Absence of a Type System: There is no mechanism to specify numeric types (e.g., floating-point vs. real-valued), creating ambiguity and potential unsoundness when solvers treat finite-precision arithmetic as real-valued.
Lack of Semantics: The standard lacks a formal semantics, making it impossible to formally prove the correctness of solvers, query generators, or transformations, and hindering the development of proof certificates.

A unique challenge for VNN-LIB, distinguishing it from standards like SMT-LIB, is that queries are not self-contained; they specify properties of external neural network models (typically in ONNX format). Since ONNX itself lacks a formal semantics and continues to evolve, defining a rigorous VNN-LIB standard requires decoupling the query language from specific ONNX versions while maintaining compatibility.

Methodology

The authors address these challenges by developing the theoretical foundations for VNN-LIB 2.0. The core methodological innovation is the introduction of the Network Theory ( $\Psi$ ).

1. Network Theory Abstraction

The authors define a "network theory" as an abstract specification capturing the minimal syntax, typing judgments, and semantics required from a neural network model format to define VNN-LIB.

Decoupling: $\Psi$ acts as an interface. A concrete implementation of $\Psi$ (e.g., for ONNX v1.20.0) provides specific definitions for element types, tensor representations, model structures, and node output references.
Modularity: VNN-LIB 2.0 is defined relative to an abstract $\Psi$ . This allows the standard to remain stable even as ONNX evolves; only the instantiation of $\Psi$ needs updating for new ONNX versions, not the VNN-LIB standard itself.
Formalization: The entire standard, including syntax, typing, and semantics, is mechanized in the Agda interactive theorem prover to ensure internal consistency and rule out ambiguities.

2. Formal Syntax and Expressivity

Building on the network theory, the authors define a formal grammar for VNN-LIB 2.0 that significantly extends expressivity:

Multiple Networks: Queries can declare multiple networks, supporting scenarios like teacher-student verification or encoder-decoder architectures.
Network Equivalence: The standard introduces equal-to (referencing the exact same model file) and isomorphic-to (referencing models with the same graph structure but potentially different weights) declarations. This allows solvers to share deductions (e.g., variable bounds) across network copies.
Hidden Nodes: The declare-hidden construct allows constraints on intermediate layer outputs, essential for reasoning about encodings or attention mechanisms.
Multi-dimensional I/O: Support for arbitrary numbers of inputs and outputs, accommodating multi-modal networks.

3. Type System and Semantics

Typing: A formal type system enforces numeric soundness. It ensures that arithmetic operations and comparisons are performed on compatible types (e.g., preventing mixing of float32 and int32 without explicit coercion rules). The type system relies on the judgments provided by the underlying network theory $\Psi$ .
Semantics: The semantics of a query are defined as a mathematical satisfiability problem. Given a set of models $M$ (instantiated from $\Psi$ ) and an input assignment $X$ , the semantics determine if there exists an assignment where all assertions evaluate to true.
Real-Valued Queries: To accommodate existing solvers that treat models as functions over real numbers ( $\mathbb{R}$ ), the standard introduces a mechanism for "real-valued queries." By using a distinguished real type, the query author explicitly authorizes the solver to interpret models over $\mathbb{R}$ , acknowledging potential unsoundness due to floating-point imprecision. This is achieved by constructing a specific network theory $\Psi_{\mathbb{R}}$ derived from the base theory.

Key Contributions

Network Theory ( $\Psi$ ): The introduction of a novel abstraction that defines the minimal semantic interface required from a model format, enabling VNN-LIB to be defined independently of specific ONNX versions.
Formal Syntax and Grammar: A precise, context-free grammar for VNN-LIB 2.0 that supports multiple networks, hidden layers, and complex input/output structures.
Formal Type System: A typing system that enforces numeric type soundness relative to the network theory, addressing ambiguity in numeric representations.
Formal Semantics: A rigorous mathematical definition of query semantics parameterized by the network theory, enabling formal proofs of correctness for tools consuming or generating VNN-LIB.
Mechanization: The complete standard is formalized in Agda, providing a canonical reference implementation and a foundation for machine-checked proofs.
Real-Valued Extension: A modular approach to supporting real-valued analyses via a derived network theory, balancing the need for soundness with the reality of current solver capabilities.

Results and Validation

Internal Consistency: The Agda formalization validates the internal consistency of the syntax, typing, and semantics, ensuring the standard is free from the ambiguities present in Version 1.0.
Expressivity Demonstration: The paper demonstrates how a simple transformation of the network theory $\Psi$ yields a complete instance for real-valued queries, showcasing the flexibility of the abstraction.
Community Adoption: The standard has received positive feedback from the verification community. Leading solver teams have committed to supporting VNN-LIB 2.0, and the new standard is scheduled to be used in the VNN-COMP 2026 competition.
Tooling Support: The authors have released a high-performance C++ library (with Python and Julia bindings) implementing a parser and type checker compliant with the new standard, alongside the Agda formalization.

Significance

The paper claims that VNN-LIB 2.0 provides robust and rigorous foundations for trustworthy neural network verification. Its significance lies in two complementary areas:

Practical Interoperability: By extending expressivity (multiple networks, hidden nodes) and standardizing syntax, it enables the community to specify and verify richer properties in a unified manner, facilitating better benchmarking and tool comparison.
Theoretical Rigor: By providing formal semantics and a type system, it establishes a "rigorous contract" between tools and solvers. This allows for the formal verification of the tools themselves (solvers, optimizers, proof checkers) and resolves subtle issues regarding numeric soundness (e.g., distinguishing between real-valued and floating-point semantics).

The authors emphasize that while the work is theoretical, it has concrete consequences: it ensures unambiguous interpretation of queries, provides the language to resolve technical issues, and lays the groundwork for formally verified proof certificates in the future.