💻 computer science

Query Languages for Machine-Learning Models

This paper explores the application of first-order logic with summation (FO(SUM)) and its recursive extension IFP(SUM) as query languages for neural networks represented as weighted graphs, presenting illustrative examples and analyzing their expressiveness and computational complexity.

Original authors: Martin Grohe

Published 2026-01-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Martin Grohe

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 a massive, complex machine learning model, like a neural network. To a computer scientist, this is a "weighted graph"—a web of nodes (neurons) connected by lines (edges), where every line has a specific number (a weight) attached to it.

The author of this paper, Martin Grohe, asks a simple but profound question: How can we ask questions about these machines?

Usually, we just feed data into a neural network and get an answer. But what if we want to ask, "How many connections does this network have?" or "If I remove this specific wire, does the answer change?" or even "What is the total area under the curve of this network's output?"

To answer these questions, the paper proposes two special "languages" (logics) designed specifically to talk to these weighted machines. Think of these languages as a new kind of remote control for neural networks.

Here is a breakdown of the two languages and what they can do, using simple analogies:

1. The First Language: FO(SUM)

The "Counting and Adding" Remote

Think of FO(SUM) as a very smart calculator that can look at the network and perform two main tasks:

Look around: It can check if a connection exists (like asking, "Is there a wire between Node A and Node B?").
Add things up: It has a special "Sum" button. It can find a group of things (like all the triangles in a network) and add up their weights.

What it can do:

Count: It can tell you exactly how many edges (wires) or triangles exist in the network.
Find the best: It can find the "lightest" or "heaviest" triangle in the network.
Simulate simple networks: If the neural network is shallow (not very deep), this language can actually calculate the output of the network for a specific input. It's like simulating a short chain of dominoes.
Find "useless" wires: It can identify wires that, if removed, wouldn't change the final result.

The Catch (The Limitation):
FO(SUM) is like a person who can only look at a small neighborhood at a time. It struggles with deep networks. If the neural network has many layers (a very long chain of dominoes), this language gets lost. It cannot easily calculate the final result of a very deep network because it lacks a way to "loop" or "remember" steps as it goes deeper.

2. The Second Language: IFP(SUM)

The "Recursive" Remote

To handle deep networks, we need a more powerful tool. Enter IFP(SUM).

Think of this as the First Language with a "Loop" button. In computer terms, this is called a "fixed-point" operator. It allows the language to say: "Keep doing this calculation, using the result of the last step as the input for the next step, until you reach the end."

What it can do:

Handle any depth: Because it can loop, it can simulate the calculation of a neural network no matter how deep or complex it is. It can trace the signal from the very first input all the way to the final output.
Complex math: It can perform the heavy lifting required to evaluate the network's function.

The Catch (The Limitation):
While IFP(SUM) is powerful, it has a speed limit.

The "Explosion" Problem: If you aren't careful, the numbers it calculates can get astronomically huge (like squaring a number over and over again). To fix this, the paper introduces a "safe" version called sIFP(SUM), which prevents the numbers from growing too fast, ensuring the calculation finishes in a reasonable amount of time.
Not everything is possible: Even with this powerful remote, there are some questions it cannot answer. For example, asking "Is there any input that makes this network output a non-zero number?" is a question that is too hard for this language to solve efficiently, even though a human could theoretically figure it out with enough time.

The Big Picture: "Model-Agnostic" Questions

The paper also discusses a special type of question called "Model-Agnostic."

Imagine you have two different neural networks, Network A and Network B. They are built differently (different numbers of neurons, different wires), but they both do the exact same job (they give the same answer for every input).

A Model-Agnostic question is one where the answer depends only on the job the network does, not on how it is built.
- Example: "Does this network output zero for every input?" (This is true for both A and B if they do the same job).
A Non-Agnostic question depends on the specific wiring.
- Example: "How many wires does this network have?" (Network A might have 100, Network B might have 50, even if they do the same job).

The Surprise Finding:
The paper reveals a disappointing but important truth:

FO(SUM) (the simple language) is terrible at asking Model-Agnostic questions about general networks. It can only ask trivial things (like "Is the network empty?"). It can't tell you if the network is "always zero" unless the network is very shallow.
IFP(SUM) (the powerful language) is better, but even it has limits. There are some questions about what a network does that are so complex that even this powerful language cannot express them.

Summary

This paper is about building a dictionary and a grammar for talking to neural networks.

FO(SUM) is a basic dictionary good for counting and simple sums, but it gets lost in deep networks.
IFP(SUM) is a dictionary with a "loop" feature that can handle deep networks, but it has speed limits and still can't answer every possible question about what a network does.

The author concludes that while we have made progress in creating these languages, there are still many mysteries about how much we can truly "ask" a neural network to reveal about its own inner workings.

Technical Summary: Query Languages for Machine-Learning Models

Problem Statement

The paper addresses the challenge of formally analyzing and querying machine learning (ML) models, specifically neural networks, which are inherently "hybrid models" combining discrete structures (graph topology) with continuous numerical components (weights and biases). While finite model theory has successfully analyzed relational databases and discrete computational problems, standard logics lack the mechanisms to handle the numerical aggregation and arithmetic required to describe the behavior of weighted structures like neural networks.

Existing approaches to ML analysis often rely on fixed, generic explanation methods (e.g., counterfactuals for specific inputs) or treat models as black boxes. The author argues for a perspective rooted in database theory and finite model theory, proposing that ML models should be treated as data structures subject to flexible, logical queries. This allows for the investigation of both local component functionality and global semantic properties (e.g., robustness, correctness, or integrals over the function space) without being restricted to specific input evaluations.

Methodology

The paper investigates two specific logics designed for weighted finite structures (structures with a finite universe and weight functions mapping to extended real numbers, $\mathbb{R}_\perp$ ):

FO(SUM): First-order logic extended with a summation operator ( $\sum$ ) and conditional terms. This logic allows for the aggregation of weights over definable sets within the structure.
IFP(SUM): The recursive extension of FO(SUM) using inflationary fixed-point operators. This enables the definition of inductive processes, necessary for evaluating neural networks of unbounded depth.

The methodology involves:

Formalizing Neural Networks: Representing Feedforward Neural Networks (FNNs) as weighted directed acyclic graphs with specific vocabulary ( $\{wt, bias, \le_{in}, \le_{out}\}$ ).
Defining Semantics: Establishing the semantics of these logics over weighted structures, where terms evaluate to values in $\mathbb{R}_\perp$ and formulas to Boolean values.
Expressiveness Analysis: Determining which properties of FNNs (e.g., evaluation, counting parameters, finding useless edges, computing integrals) can be expressed in these logics.
Complexity Analysis: Analyzing the data complexity of evaluating these queries, considering both uniform circuit complexity classes (e.g., $\mathsf{TC}^0$ ) and polynomial time ( $\mathsf{P}$ ).
Model-Agnostic Queries: Investigating queries whose outcomes depend solely on the function computed by the network ( $f^N$ ) rather than the specific architecture or weights, distinguishing between "model-agnostic" and "fully model-agnostic" properties.

Key Contributions and Results

1. Expressiveness of FO(SUM)

Bounded Depth Evaluation: FO(SUM) can express the evaluation of FNNs of bounded depth. The logic can recursively define the value of a node up to a fixed depth $d$ using summation to aggregate weighted inputs and conditional terms to simulate the ReLU activation function.
Global Properties: The logic can define global properties such as the total number of weights, the set of "useless" edges (edges whose removal does not change the output), and integrals over the function computed by the network (via cylindrical cell decomposition of piecewise-linear functions).
Limitations on Unbounded Depth: FO(SUM) cannot express the evaluation function for FNNs of unbounded depth. The logic is limited to local properties; it cannot simulate the unbounded recursion required for general FNN evaluation.
Model-Agnostic Limitations: A central negative result (Theorem 3.14) states that any FO(SUM) sentence that is model-agnostic (invariant under different architectures computing the same function) on the class of all FNNs must be trivial (either true for all or false for all). Thus, non-trivial model-agnostic queries (like checking if a network outputs zero everywhere) are not expressible in FO(SUM) for unbounded depth.
Bounded Depth Equivalence: However, for FNNs of bounded depth ( $N_d(m, 1)$ ), FO(SUM) is surprisingly powerful. Theorem 3.18 establishes that any query expressible in first-order logic over the ordered field of reals expanded by the function ( $FO(\mathbb{R}_{lin}, f)$ ) is also expressible in FO(SUM). This is achieved by simulating quantification over reals via quantification over the cells of the function's cylindrical decomposition.

2. Expressiveness of IFP(SUM)

Unbounded Depth: IFP(SUM) overcomes the depth limitation of FO(SUM) by introducing fixed-point operators. It can express the evaluation function for FNNs of unbounded depth (Example 4.1).
Complexity and Scalar Fragments: While standard fixed-point logic over ordered structures captures polynomial time, IFP(SUM) over weighted structures faces a complexity hurdle: terms can grow exponentially in size (e.g., repeated squaring). To address this, the paper introduces the scalar fragment sIFP(SUM), which restricts multiplications and divisions involving intensional symbols.
- Theorem 4.5: The data complexity of sIFP(SUM) is in P (polynomial time) over rational weighted structures.
Expressiveness Limits: Despite capturing polynomial time in the Blum-Shub-Smale model, IFP(SUM) (and sIFP(SUM)) cannot express all polynomial-time computable model-agnostic queries. Theorem 4.7 demonstrates the existence of a polynomial-time decidable model-agnostic query on $N(1, 1)$ that is not expressible in IFP(SUM), even with binary weights. This limitation stems from the logic's inability to perform arbitrary computations on the numerical values (lack of variables ranging over numbers).
Reduced FNNs: The paper introduces "reduced FNNs" (factoring through a bisimilarity-like equivalence). Theorem 4.8 shows that for FNNs where the reduced form has weights of bounded bit-size, sIFP(SUM) captures all polynomial-time decidable model-agnostic queries.

3. Complexity Results

FO(SUM): The data complexity of evaluating FO(SUM) expressions is in uniform $\mathsf{TC}^0$ (Theorem 3.9). This class allows for threshold gates and iterated addition, sufficient for the arithmetic operations required.
sIFP(SUM): The data complexity is in P (Theorem 4.5).

Significance and Claims

The paper positions itself as a "personal perspective" and a foundational step in applying finite model theory to ML. Its primary significance lies in:

Formalizing ML Querying: It provides a rigorous logical framework for querying the internal semantics of neural networks, moving beyond black-box evaluation to structural and functional analysis.
Bridging Discrete and Continuous: It demonstrates how meta-finite model theory (extending finite model theory to hybrid structures) can be applied to neural networks, which are naturally represented as weighted graphs.
Defining Limits of Expressiveness: The results delineate clear boundaries between what can and cannot be expressed logically. Notably, it highlights that while bounded-depth networks are amenable to logical analysis via FO(SUM), unbounded depth introduces complexity that requires recursion (IFP) but still faces fundamental expressiveness barriers regarding model-agnostic properties.
Complexity Insights: The work connects logical expressiveness with computational complexity, showing that even with fixed-point operators, capturing all polynomial-time model-agnostic properties requires restrictions on the numerical bit-size of the weights.

The author concludes that while significant progress has been made in [22, 23], many open questions remain, particularly regarding the extension of results to arbitrary input dimensions, the lifting of bounded-depth assumptions without complexity-theoretic assumptions, and the inter-definability of different aggregation operators. The paper does not claim to solve the "explainable AI" problem entirely but offers a theoretical toolkit for defining and analyzing specific types of explanations and verifications.