💻 computer science

On the Decompositionality of Neural Networks

This paper introduces the formal concept of "neural decompositionality" based on semantic preservation at decision boundaries and proposes the SAVED framework to empirically evaluate and achieve modular decomposition, revealing that while language Transformers largely support such decomposition, vision models often exhibit intrinsic limitations.

Original authors: Junyong Lee, Baek-Ryun Seong, Sang-Ki Ko, Andrew Ferraiuolo, Minwoo Kang, Hyuntae Jeon, Seungmin Lim, Jieung Kim

Published 2026-04-10

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Junyong Lee, Baek-Ryun Seong, Sang-Ki Ko, Andrew Ferraiuolo, Minwoo Kang, Hyuntae Jeon, Seungmin Lim, Jieung Kim

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, incredibly smart robot chef. This chef can cook thousands of different dishes perfectly. But there's a problem: the chef is a "black box." You can't see how it works. If you want to fix a mistake in how it chops onions, you have to take apart the whole robot, risk breaking the part that makes the soup, and hope for the best.

In the world of AI, these robots are Neural Networks. They are amazing, but they are usually treated as one giant, unchangeable blob.

This paper asks a simple but revolutionary question: "Can we take this giant robot chef apart into smaller, specialized helpers without ruining the food?"

The authors call this concept "Decompositionality." But they don't just mean cutting the robot into pieces physically; they mean cutting it in a way that preserves the logic of how it makes decisions.

Here is the breakdown of their discovery, using some everyday analogies:

1. The Problem: The "Black Box" Chef

Currently, if you want to make a neural network smaller or easier to understand, you usually just "prune" it (cut out unused parts) or split it up. But most of the time, people only check if the robot still gets the right answer on a test.

The Flaw: Imagine a student who memorized the answers to a math test. If you change the numbers slightly, they fail. But if you only check their score on the original test, they look perfect.
The Real Issue: The authors argue that just getting the right answer isn't enough. We need to know if the robot still understands the boundary between decisions. For example, does the robot know exactly where a "cat" stops being a "cat" and starts looking like a "dog"? If you split the robot, does it still know that boundary?

2. The Solution: The "Decision Boundary" Map

The authors say that the most important part of a neural network isn't the middle of the decision space (where it's easy to tell a cat from a dog); it's the Decision Boundary.

The Analogy: Think of a map of a city. The middle of a neighborhood is easy to navigate. The border between two neighborhoods is where things get tricky. If you are standing right on the line between "Cat Territory" and "Dog Territory," a tiny step could change your identity.
The Goal: A successful decomposition must preserve the rules of the game right at the border. If you split the robot, the new smaller robots must still agree with the big robot on who is a cat and who is a dog, especially for the tricky, borderline cases.

3. The Two Rules of a Good Split

The authors created a "Contract" (a set of rules) to see if a split is valid. You need both of these to happen at the same time:

Rule A: Semantic Fidelity (The "Truth" Rule)
The new smaller robots must still make the right decisions, especially near the borders. If the big robot says "This is a cat," the small robot must also say "This is a cat," even if the picture is blurry.
- Analogy: If you split a law firm into three smaller teams, all three teams must still give the same legal advice on the most difficult, borderline cases.
Rule B: Structural Divergence (The "Independence" Rule)
The smaller robots must actually be different from each other. They shouldn't just be three copies of the same robot hiding in different boxes. They need to use different parts of the brain to do their jobs.
- Analogy: If you split a law firm, you don't want three teams that all read the exact same books and use the exact same lawyers. You want one team to specialize in contracts, another in criminal law, and another in family law. They need to be distinct.

The Catch: Most methods fail one of these rules.

Some methods keep the "Truth" but fail the "Independence" (they just copy the whole robot three times).
Some methods get "Independence" but fail the "Truth" (they cut the robot so much it starts hallucinating).

4. The Experiment: SAVED (The Detective)

The authors built a tool called SAVED to test this. It's like a detective that:

Finds the "borderline" cases (the tricky inputs).
Tries to split the robot into smaller parts.
Checks if the smaller parts still agree with the big robot on the borders (Rule A) AND if they are actually using different parts of the brain (Rule B).

5. The Big Discovery: It Depends on the Type of Brain

This is the most surprising part of the paper. They tested this on different types of AI:

Language Models (like BERT): Success! 🎉
When they tried to split a language model (which reads text), it worked perfectly. The model naturally had "specialists" for different words and topics. You could split it up, and the pieces still understood the tricky boundaries of language.
- Analogy: A library is naturally organized by genre. You can easily separate the "Mystery" section from the "Science" section without losing the plot.
Vision Models (like CNNs and ViTs): Failure. ❌
When they tried to split image models (which look at photos), it failed. The models couldn't be split without losing their ability to distinguish tricky images.
- Analogy: Imagine a painting where every single brushstroke is a mix of red, blue, and yellow to create the whole picture. If you try to cut the canvas into pieces to separate the "red" part from the "blue" part, the image falls apart. The information is too mixed up (entangled) to be separated cleanly.

The Takeaway

This paper changes how we think about AI. It tells us that not all AI models can be broken down into smaller, modular pieces.

For Language: We can start building AI systems that are like a team of specialists, where we can swap out or fix individual parts easily.
For Vision: We have to accept that these models are more like a giant, tangled knot. You can't just untie them without untying the whole thing.

The authors have given us a formal way to measure this. Before, we just guessed if a model was "modular." Now, we have a contract to sign: "Does this split keep the truth at the borders, and are the pieces actually different?" If the answer is yes, we can finally start building AI that is easier to maintain, test, and trust.

1. Problem Statement

Despite the success of deep neural networks (DNNs) in vision and NLP, they are typically treated as monolithic "black boxes." This limits software engineering practices such as modular reasoning, component-wise optimization, and systematic verification.

The Gap: While empirical methods exist for pruning and decomposing networks, the field lacks a principled, semantic definition of when a neural network can be meaningfully decomposed.
Limitations of Current Approaches: Existing work relies heavily on aggregate test accuracy as a proxy for decomposition quality. However, accuracy is a sparse approximation of the input space. Two models can have similar accuracy but vastly different decision boundaries (the regions where class semantics transition). A decomposition that preserves accuracy but distorts the decision boundary fails to preserve the model's true semantic behavior.
Core Question: When does a neural network admit a semantically meaningful decomposition into structurally distinct components?

2. Methodology: The SAVED Framework

The authors propose a formal framework called SAVED (Semantic-Aware Verification-Driven Decomposition) to define and evaluate "decompositionality."

A. Formal Definition: Neural Decompositionality

The paper defines decompositionality not as a procedure, but as an intrinsic semantic-structural contract between a reference model ( $F_\theta$ ) and its decomposed version ( $F^\downarrow_\theta$ ). The contract requires two orthogonal conditions:

Boundary-Aware Semantic Fidelity: The decomposed model must agree with the original model within a $\tau$ $τ$ -neighborhood of the decision boundary ( $N_\tau$ $N_{τ}$ ). This ensures that the model's behavior during class transitions (where errors are most likely) is preserved.
- Metric: Boundary-aware disagreement probability ( $Dis_\tau$ ).
Structural Divergence: The components must be structurally distinct and non-trivially smaller than the original.
- Overlap Constraint: Components must not share too many parameters/neurons (Overlap $\le \gamma$ ).
- Reduction Constraint: Each component must be significantly smaller than the original (Size $\le 1-\eta$ ).

B. Theoretical Abstraction

Since verifying global decompositionality over continuous input spaces is intractable, the authors introduce Local Decompositionality:

They approximate the decision boundary neighborhood using low logit-margin inputs (inputs where the model is least confident).
They use Hoeffding's inequality to provide probabilistic guarantees that empirical disagreement on a finite sample set approximates the true global disagreement.

C. The SAVED Pipeline

SAVED operationalizes this definition through four stages:

Structural Decomposition: Creates initial binary components (e.g., one per class).
Boundary-Aware Input Generation: Uses gradient-based perturbations (PGD) followed by binary search refinement to generate inputs lying arbitrarily close to the decision boundary.
Semantic-Structural Refinement (LBMask):
- Learns structured binary masks (per-neuron or per-channel) for each component.
- Optimizes masks to minimize boundary disagreement (semantic fidelity) while maximizing structural separation (minimizing overlap) and enforcing sparsity.
- Uses a "straight-through estimator" to allow gradient-based optimization of discrete masks.
- Performs "dimension surgery" to ensure pruned components form valid, self-contained sub-networks.
Contract Evaluation: Empirically checks if the resulting decomposition satisfies the $(\epsilon, \kappa, \gamma, \eta)$ thresholds.

3. Key Contributions

Formal Notion of Decompositionality: The first work to define decompositionality as a semantic-structural contract centered on the decision boundary, moving beyond simple accuracy metrics.
SAVED Framework: A practical, boundary-aware framework that combines counterexample mining, probabilistic coverage, and structured pruning to realize and verify decompositionality.
Empirical Insights: A comprehensive study across CNNs, NLP Transformers, and Vision Transformers revealing that decompositionality is an architecture-dependent property, not just a result of the pruning algorithm.

4. Experimental Results

The authors evaluated SAVED on BERT (NLP), ResNet (CNN), and DeiT (Vision Transformer) across various datasets (DBPedia-14, AG News, CIFAR-10).

RQ1: Realizability: Decompositionality is realizable but conditional.
- Success: On BERT (DBPedia-14), LBMask successfully satisfied the full contract (low boundary disagreement + low structural overlap + significant size reduction).
- Failure: On AG News, structural separation was achieved, but semantic fidelity failed (high disagreement), suggesting task complexity or class count affects decomposability.
RQ2: Necessity of Both Metrics:
- Methods preserving semantic fidelity (e.g., unstructured Wanda) often resulted in structural collapse (components shared nearly identical supports, $\approx 99\%$ overlap).
- Methods achieving structural sparsity (e.g., structured pruning) often destroyed semantic fidelity near boundaries.
- Conclusion: Both semantic fidelity and structural separation are strictly necessary; neither alone constitutes a valid decomposition.
RQ3: Architectural Bias:
- NLP Transformers (BERT): Exhibit sparse, class-specific representations, making them highly amenable to decomposition.
- Vision Models (CNNs & ViTs): Rely on distributed, entangled representations. They exhibit a fundamental trade-off: improving structural separation inevitably destroys boundary semantics, and vice versa. They largely fail the decompositionality contract.

5. Significance and Implications

Shift in Perspective: Decompositionality is a property of the model's representation, not just the decomposition algorithm. It depends on how class-discriminative information is organized (sparse vs. distributed).
Software Engineering for AI: Provides a rigorous foundation for treating neural networks as modular systems, enabling local verification, component reuse, and systematic repair.
Verification Scalability: When decompositionality holds (as in BERT), decomposed components allow for more efficient formal verification, as reasoning over smaller, semantically isolated modules is computationally cheaper than verifying the monolithic model.
Future Directions: Suggests the need for decomposition-aware training (e.g., penalizing cross-class co-activation) to induce modular representations in vision models, which currently resist post-hoc decomposition.

In summary, the paper establishes that while neural networks can be decomposed, doing so semantically is a non-trivial constraint that depends heavily on the underlying architecture's representational structure. The proposed framework provides the tools to measure and enforce this constraint.