🤖 AI

Compiling High-Level Neural Network Specifications into VNN-LIB Queries

This paper introduces the first algorithm for compiling high-level neural network specifications into optimized, numerically sound VNN-LIB queries, overcoming unique variable constraints to support complex logical fragments like quantifiers and multi-network specifications within the Vehicle framework.

Original authors: Matthew L. Daggitt, Wen Kokke, Robert Atkey

Published 2026-02-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Matthew L. Daggitt, Wen Kokke, Robert Atkey

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

The Big Picture: Translating "Human Thoughts" into "Robot Instructions"

Imagine you are an architect designing a building. You have a beautiful, high-level vision: "I want a room where the sunlight hits the floor at a 45-degree angle, but only if the window is open." This is your High-Level Specification.

Now, imagine you need to talk to a construction robot that only understands a very specific, rigid language. It doesn't care about "sunlight" or "angles." It only understands a list of exact coordinates for every single brick and a strict set of rules like: "If brick A is here, then brick B must be there." This is the VNN-LIB format (the language neural network solvers speak).

The Problem:
In the world of traditional software, we have translators (like the ones mentioned in the paper, e.g., Dafny) that can take your high-level architectural vision and automatically turn it into the robot's rigid instructions.

But for Neural Networks (the AI brains), this translator didn't exist. If you wanted to verify an AI, you had to be a robot yourself. You had to manually write out every single brick coordinate and every complex math equation. If you wanted to say, "Check if the AI behaves well when I change the input slightly," you had to do the heavy lifting of figuring out exactly how that change ripples through the math. It was like trying to build a skyscraper by hand-painting every single brick without a blueprint.

The Solution:
This paper introduces a new, smart Translator (an algorithm) that takes your high-level, human-friendly description of how an AI should behave and automatically converts it into the rigid, low-level instructions the robot needs.

The Three Big Hurdles (and how they fixed them)

The authors explain that building this translator was hard because of three specific "glitches" in the system:

1. The "No New Variables" Rule

The Analogy: Imagine the robot is working in a tiny, locked room. It has a fixed set of tools (variables) on the wall. It cannot accept new tools you bring in.
The Challenge: In your high-level spec, you might say, "Let's call this input x and that input y." But the robot only knows Input 1 and Input 2.
The Fix: The translator is a math wizard. Instead of just renaming things, it solves the puzzle. If you say x = Input 1 + Input 2, the translator figures out how to rewrite your rule using only Input 1 and Input 2. It does the algebra for you so the robot doesn't need new tools.

2. The "Too Many Bricks" Problem

The Analogy: If you have a 10x10 grid of bricks, that's 100 bricks. If you have a 784x784 grid (like a standard image), that's over 600,000 bricks.
The Challenge: If the translator tries to solve the math for every single brick individually, it would take longer than the age of the universe. This is the "exponential explosion" problem.
The Fix: The translator is smart enough to look at the structure of the grid. Instead of solving for 600,000 individual bricks, it solves for the "rows" or "columns" first. It groups the work together. This makes the process fast enough to be useful, even for large images.

3. The "Duplicate Work" Problem

The Analogy: Imagine you ask the robot to check the same door three times in a row. It's a waste of time.
The Challenge: When translating complex rules, the system might accidentally create multiple copies of the same check (e.g., checking if the AI is safe for "Input A" and then again for "Input B," even though A and B are actually the same thing).
The Fix: The translator has a "spotter." It looks at all the checks it's about to make, realizes "Hey, these two are actually the same," and merges them into one. This saves a massive amount of time.

Why This Matters (The "So What?")

Before this paper, if you wanted to verify an AI, you had to be a math expert who spoke the robot's language. You were stuck in the weeds of the details.

With this new tool:

You can speak naturally: You can write specifications like "The car should stop if a pedestrian is detected," without worrying about the raw pixel math.
You can handle complex rules: You can ask about "what if" scenarios involving multiple versions of the AI or chained processes (like an encoder-decoder), which was previously impossible or too hard to write down.
It's fast: The paper proves that for most real-world problems, this translation happens almost instantly, scaling linearly (if the problem gets twice as big, the translation takes twice as long, not a million times longer).

The Bottom Line

This paper builds the bridge between human intent and machine verification. It allows engineers to write high-level, logical rules about how AI should behave, and automatically compiles them into the strict, low-level code that safety-checkers need to prove the AI is safe. It turns the job of "AI Safety" from a manual, error-prone craft into a scalable, automated engineering discipline.

1. Problem Statement

The formal verification of traditional software has been revolutionized by high-level specification languages (e.g., Dafny, F*) that compile to low-level SMT-LIB queries. However, neural network verification lacks similar infrastructure. Current tools require users to write specifications in low-level formats (like VNN-LIB) that are close to the solver's internal representation.

The core challenge, termed the "embedding gap," arises from fundamental differences between SMT-LIB and VNN-LIB:

Variable Restrictions: VNN-LIB restricts queries to a fixed, finite set of variables representing only the network's direct inputs and outputs. It cannot introduce arbitrary intermediate variables for user-defined logic.
Transformation Complexity: High-level specifications often involve user variables (e.g., normalized inputs, quantified tensors) that must be mathematically transformed into network variables. In SMT-LIB, a compiler can simply declare new variables. In VNN-LIB, the compiler must solve simultaneous equations to express user variables in terms of network variables (e.g., solving $x_0 = a_0 + a_1$ for $a_0$ ).
Scalability: Naive variable elimination (e.g., Gaussian elimination) is $O(n^3)$ and becomes intractable for large tensors (e.g., MNIST inputs with $n=784$ ).
Expressivity Limitations: Existing high-level tools (e.g., DNNV, CAISAR) avoid these complexities by restricting users to templates or subsets of logic, preventing the expression of data normalization, first-class quantifiers, or properties involving multiple network applications.

2. Methodology

The authors present a novel compilation algorithm that translates a high-level specification language (a fragment of First-Order Logic extended with tensors) into an optimized tree of VNN-LIB queries. The process involves three main stages:

A. Source and Target Languages

Source Language: Supports quantifiers (exists, forall), tensor operations (stacking, indexing, arithmetic), and network applications. It allows user variables to be transformed before entering the network.
Target Language: VNN-LIB 2.0, which consists of network declarations and assertions over network inputs/outputs only. The compiler outputs a tree of queries (conjunctions/disjunctions) to handle complex logical structures.

B. Intermediate Language and Compilation Flow

The compilation proceeds via an intermediate language of proto-queries (lists of implicitly disjuncted constraints) to optimize variable elimination.

Quantifier Elimination:
- exists quantifiers are eliminated by compiling the body into proto-queries and then removing the user variable.
- forall quantifiers are converted to exists by negating the body (De Morgan's laws).
- Constraint: The algorithm does not support alternating quantifiers (e.g., $\exists \forall$ ), as current solvers only handle satisfiability.
Variable Elimination (Algorithm 7):
- The compiler attempts to solve for user variables using an abstract algebraic solver (e.g., linear arithmetic solver).
- Optimization 1 (Direct Substitution): If the solver finds an equality (e.g., $u = x_1$ ), it substitutes the user variable directly, avoiding element-wise expansion.
- Optimization 2 (Hierarchical Decomposition): If direct solving fails, the algorithm recursively eliminates child variables (tensor elements) in a depth-first manner. This prevents the $O(n^3)$ blow-up in common cases where constraints are sparse or solvable at higher tensor levels.
Network Application Optimization (Algorithm 9):
- The compiler detects redundant network applications. If two applications of the same network have provably equal inputs (derived from equality constraints in the specification), they are merged into a single application.
- This is achieved by computing equivalence classes over the hierarchy of tensor indices induced by the equality constraints.

C. Soundness

The algorithm is numerically sound. It relies on the soundness of the underlying algebraic solver. If the solver correctly handles the numeric domain (e.g., Reals or Floats), the compilation preserves the semantics of the original specification.

3. Key Contributions

First General-Purpose Compiler: The first algorithm capable of compiling high-level FOL specifications with tensors into VNN-LIB queries.
Enhanced Expressivity: The supported language fragment includes features previously unavailable in neural network specification tools:
- Free transformation of user variables before network input.
- First-class quantifiers.
- Arbitrary nested applications of multiple networks (supporting hyper-properties like monotonicity or teacher-student distillation).
- Non-linear constraints (dependent on the solver).
Asymptotically Optimal Performance: The algorithm achieves linear time complexity relative to the size of input tensors for common specifications, avoiding the exponential blow-up of naive approaches.
Implementation: The algorithm is implemented within the Vehicle framework and is open-source.

4. Results and Performance Evaluation

The authors evaluated the compiler on three benchmark categories:

ACAS Xu: A large, interpretable specification for aircraft collision avoidance.
Robustness: Standard $\epsilon$ -ball robustness properties.
Monotonicity: Properties involving multiple network applications.

Key Findings:

Linear Scaling: Compilation time scales linearly with the number of input elements for robustness and monotonicity specifications. This is asymptotically optimal because the number of assertions in the output query is also linear.
Speed: The entire ACAS Xu specification (10 properties) compiled into 42 queries in 0.47 seconds.
Ablation Study: Removing the hierarchical optimization (forcing element-wise solving) caused compilation times to become impractical even for small networks, validating the necessity of the proposed algorithm.

5. Significance

This work bridges the critical gap between human-readable intent and solver-level encodings in neural network verification.

Accessibility: It lowers the barrier to entry for non-experts, allowing them to write precise, solver-independent specifications without manually managing the "embedding gap."
Real-World Applicability: By allowing data normalization to be part of the specification, users can write constraints in real-world units (e.g., meters/second, radians) rather than normalized tensor values.
Engineering Discipline: It moves neural network verification from a niche research field toward a scalable engineering discipline by providing the necessary infrastructure for high-level abstraction, similar to what exists in traditional software verification.

In summary, the paper provides a robust theoretical and practical solution to the algorithmic challenges of compiling high-level logic into the restrictive VNN-LIB format, enabling more expressive, efficient, and accessible formal verification of neural networks.