💻 computer science

Verification of Neural Networks (Lecture Notes)

This paper presents lecture notes offering a theoretical introduction to neural network verification, covering architectures like feed-forward networks, RNNs, and transformers alongside specification languages and algorithmic techniques.

Original authors: Benedikt Bollig

Published 2026-04-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Benedikt Bollig

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 have built a incredibly complex, black-box machine that can recognize cats in photos, translate languages, or drive a car. You know it works well most of the time, but you don't know why it makes its decisions, and you're terrified it might suddenly decide a stop sign is a speed limit sign because a bird flew in front of the camera.

This lecture series by Benedikt Bollig is like a guidebook for mathematical detectives trying to figure out if these "black-box" machines (neural networks) are safe and reliable. Instead of just testing them with a million pictures, the author asks: Can we prove mathematically that this machine will never make a specific mistake?

Here is a breakdown of the paper's journey, using simple analogies:

1. The Goal: Proving the Machine is "Good"

The paper starts by saying that while we can train these machines, we need formal guarantees. It's like building a bridge: you don't just drive a few cars over it to see if it holds; you calculate the physics to prove it won't collapse.

The Challenge: Neural networks are "opaque." They are made of layers of math that are hard to interpret.
The Solution: The author proposes a "Specification Language." Think of this as writing a strict rulebook in a language the machine understands. For example: "If you see a dog, you must say 'dog' even if I add a tiny bit of noise to the picture."

2. The Simple Machines: Feed-Forward Networks

First, the paper looks at the simplest type of network (Feed-Forward). Imagine a factory assembly line where a package moves from one station to the next, getting processed at each stop, but never going backward.

The Good News: For these simple networks, the author proves we can solve the verification problem.
The Magic Trick: The author shows that we can translate the entire behavior of the network into a giant math puzzle (Linear Real Arithmetic). If we can solve the puzzle, we know the network is safe.
The Catch: While we can solve it, it might take a very long time if the network is huge (like trying to solve a Sudoku with a billion squares). However, for many practical rules, there are shortcuts that make it fast enough to be useful.

3. The Looping Machines: Recurrent Networks (RNNs)

Next, the paper looks at networks that process sequences, like reading a sentence word by word. These are like a robot that remembers what it just read to understand the next word.

The Bad News: The author proves that for these looping machines, verification is impossible in the general case.
The Analogy: It's like asking, "Will this robot ever get stuck in an infinite loop?" The math shows that for these specific types of machines, there is no algorithm that can give you a "Yes" or "No" answer for every possible scenario. It's a fundamental limit of logic, not just a lack of computing power.
Why? The author shows these machines are powerful enough to simulate "Probabilistic Finite Automata," which are known to be impossible to verify completely.

4. The Modern Giants: Transformers and Attention

Finally, the paper looks at the "Transformers" that power modern AI (like the one you are talking to right now). These use a mechanism called Attention.

The Analogy: Imagine a student reading a long essay. A standard reader reads word-by-word. An "Attention" mechanism is like a student who can instantly jump to any part of the essay to see how it connects to the current sentence. They can look at the whole page at once to decide what word comes next.
The Current State: The paper explains how these machines are built (layers of "Attention Heads" and "Feed-Forward" layers).
The Mystery: The author admits that while we understand how they work, we don't yet know if we can verify them.
- Some simple versions of these machines (Encoder-only) can do things like finding the maximum number in a list or checking if a sentence is sorted.
- However, because the full architecture is so powerful (it can theoretically simulate a Turing Machine, the most powerful computer model), the big question remains: Is there a way to mathematically prove these complex machines are safe? The paper says this is an open research problem.

Summary of the "Detective Work"

Simple Networks: We have a map and a compass. We can prove they are safe, though the journey might be long.
Looping Networks: We have hit a wall. The math says we cannot prove they are safe in all cases.
Transformers: We are standing at the edge of a new continent. We know they are powerful, but we haven't figured out the map yet. The paper suggests that finding a way to verify them is the next big challenge for scientists.

The paper doesn't promise to fix the machines or tell you how to use them in hospitals or self-driving cars today. Instead, it draws a clear line in the sand: "Here is what we can prove mathematically, here is what is impossible, and here is where we need to invent new math."

Based on the lecture notes by Benedikt Bollig, here is a detailed technical summary of the paper "Verification of Neural Networks."

1. Problem Statement

The paper addresses the challenge of providing formal guarantees for neural networks (NNs), which are increasingly deployed in safety-critical systems (e.g., autonomous vehicles, medical diagnostics). Unlike traditional software, NNs are "black-box" models trained on data, making their behavior opaque and difficult to verify using standard testing.

The core problem is verification: determining whether a neural network satisfies a specific mathematical specification (e.g., robustness, fairness, functional correctness) for all possible inputs within a defined domain. The paper explores the theoretical limits of this verification, specifically focusing on:

Decidability: Can we algorithmically determine if a specification holds?
Complexity: What is the computational cost of verification?
Expressiveness: How do different architectures (Feed-Forward, Recurrent, Transformers) and activation functions affect these properties?

2. Methodology

The author employs a theoretical computer science approach, combining:

Formal Logic: Using Linear Real Arithmetic (LRA) and extending it to Neural Network Logic (NNL) to define specifications.
Automata Theory: Utilizing Büchi automata (which operate on infinite words) to model real numbers and decide arithmetic theories.
Reductions: Proving undecidability or hardness by reducing known undecidable problems (like the emptiness of Probabilistic Finite Automata or the Modified Post Correspondence Problem) to neural network verification problems.
Architectural Analysis: Systematically analyzing Feed-Forward Neural Networks (FFNNs), Recurrent Neural Networks (RNNs), and Transformers (Attention mechanisms).

3. Key Contributions and Results

A. Feed-Forward Neural Networks (FFNNs)

Specification Language (NNL): The author defines Neural Network Logic (NNL), an extension of LRA that includes a predicate $N(x) = y$ representing the input-output relation of a network.
Decidability for ReLU:
- Theorem: The satisfiability problem for NNL with ReLU activation functions ( $\text{SAT}(\text{NNL}[\text{ReLU}])$ ) is decidable.
- Method: The proof translates the neural network into an equivalent LRA formula. Since LRA is decidable (via automata-theoretic techniques), NN verification is also decidable for ReLU networks.
Complexity:
- The existential fragment of NNL with ReLU ( $\exists\text{NNL}[\text{ReLU}]$ ) is NP-complete.
- The universal fragment is coNP-complete.
- Hardness: Even restricted "reachability" problems (checking if a network can reach a specific state from a specific input) are NP-hard, proven via reduction from 3SAT.
Beyond ReLU:
- For networks using activation functions like sigmoid ( $\sigma$ ), tanh, or NLReLU, the verification problem becomes equivalent to the First-Order Theory of the Real Exponential Field (REF).
- Status: The decidability of REF (Tarski's exponential function problem) is currently unknown, implying that verification for these general networks is an open problem.

B. Recurrent Neural Networks (RNNs)

Undecidability:
- Theorem: The emptiness problem for RNNs (determining if there exists any input sequence that the network classifies as positive) is undecidable.
- Proof Strategy:
  1. Show that (ReLU, sigmoid)-RNNs can simulate Probabilistic Finite Automata (PFAs).
  2. Rely on the known result that the emptiness problem for PFAs (specifically, checking if the acceptance probability equals or exceeds a threshold) is undecidable (reduced from the Modified Post Correspondence Problem).
- Implication: Since the basic emptiness problem is undecidable, most non-trivial verification tasks for RNNs are also undecidable.

C. Attention and Transformers

Architecture: The paper formalizes the Transformer architecture, including attention heads, multi-head layers, encoders, and decoders.
Expressiveness:
- Transformers are shown to be capable of computing complex functions (e.g., finding the maximum in a sequence, recognizing sorted sequences, and recognizing well-formed bracket strings) using Encoder-Only architectures.
- The paper demonstrates how to construct specific Transformers to perform these tasks using attention mechanisms (e.g., avg-argmax attention) and feed-forward layers.
Verification Status:
- Due to the Turing completeness of general Transformer architectures (they can simulate Turing machines), general verification is likely undecidable.
- The paper highlights that while specific, restricted fragments might be decidable, general positive decidability results for Transformers remain an open research area.

4. Significance and Implications

Theoretical Boundaries: The work clearly delineates the boundary between what is theoretically verifiable and what is not. It establishes that while simple ReLU networks are decidable (albeit NP-hard), adding recurrence (RNNs) or complex non-linearities (Exponential/Transcendental functions) pushes the problem into the realm of undecidability or unknown decidability.
Formal Specification: It provides a rigorous logical framework (NNL) to express properties like robustness (small input changes don't change output), fairness (ignoring sensitive features), and functional equivalence, moving beyond ad-hoc testing.
Guidance for Practitioners:
- For FFNNs, verification is possible but computationally expensive; practitioners should focus on existential fragments or use SMT solvers.
- For RNNs and Transformers, exact verification is theoretically impossible in the general case. This suggests that verification for these models must rely on abstractions, approximations, or restricted sub-classes of the architecture.
Future Research Directions: The paper identifies the verification of Transformers and the decidability of the Real Exponential Field as critical open problems. It suggests that future work should focus on identifying specific architectural constraints that restore decidability while maintaining utility.

Summary Conclusion

Bollig's lecture notes provide a foundational theoretical analysis of neural network verification. The central takeaway is that verification is decidable for feed-forward networks with ReLU activations (reducible to Linear Real Arithmetic) but becomes undecidable for recurrent networks and remains open for networks with transcendental activation functions or general Transformers. This underscores the necessity of developing specialized, approximate verification tools for modern deep learning architectures rather than relying on general-purpose exact verification.