💻 computer science

Provably Lossless Acceleration of DNN Mutation Testing via Memoization

This paper introduces Mure, the first provably lossless framework that accelerates DNN mutation testing by memoizing common computation prefixes between original models and mutants, achieving an average 44.54% reduction in computational cost without sacrificing accuracy.

Original authors: Ali Ghanbari, Ben Greenman, Sasan Tavakkol, Shibbir Ahmed

Published 2026-07-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ali Ghanbari, Ben Greenman, Sasan Tavakkol, Shibbir Ahmed

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 teach a robot how to recognize cats. You build a giant, complex brain made of layers of tiny switches (neurons) that learn from thousands of pictures. But how do you know if your robot is actually smart, or just lucky? In the world of software testing, there's a clever trick called "mutation testing." It's like playing a game of "spot the difference" where you intentionally break the robot's brain in tiny, random ways—flipping a switch here, twisting a wire there—to see if your test pictures are good enough to catch the mistake. If the robot still thinks a dog is a cat even after you broke it, your tests aren't doing their job.

The problem is that this game is incredibly slow and expensive. To test a modern robot brain, you might have to break it thousands of times and run it through millions of pictures for every single break. It's like trying to find a needle in a haystack by rebuilding the entire haystack, breaking a tiny piece of straw, and then checking the whole thing again, over and over. Most people trying to speed this up have had to cheat a little, using shortcuts that guess the results. But guessing in science is risky; if you guess wrong, you might think your robot is safe when it's actually broken. This paper introduces a new way to play the game that is fast, but refuses to cheat.

The "Copy-Paste" Shortcut for Robot Brains

Meet Mure (pronounced like "moo-ray"), a new tool designed by researchers Ali Ghanbari, Ben Greenman, Sasan Tavakkol, and Shibbir Ahmed. Think of a Deep Neural Network (the robot's brain) as a long assembly line in a factory. Raw materials (the pictures) enter at the start, pass through many stations (layers), and come out as a finished product (the answer).

When you want to test the factory by breaking a machine at the very end of the line, you don't need to rebuild the entire factory from scratch every time. You just need to fix the broken machine and the few stations after it. The stations before the break are exactly the same as the original factory.

Mure uses a technique called memoization, which is a fancy word for "remembering what you already did." Here is how it works in the real world:

The Assembly Line: Imagine you have a factory making 100 slightly different versions of a toy car. In 99 of them, the first 10 steps of the assembly line are identical. Only the last 2 steps are different.
The Old Way (Vanilla Testing): The old method would build the entire car from scratch for every single version. It would run the first 10 steps, then the last 2, then start over, run the first 10 steps again, then the last 2. It's a lot of wasted energy.
The Mure Way: Mure says, "Wait a minute! The first 10 steps are the same for everyone." So, it runs the first 10 steps once and saves the result in a "memo table" (like a sticky note on the wall). Then, for every single mutant car, it just grabs the sticky note, skips the first 10 steps, and only builds the last 2 steps.

The Big Discovery: Speed Without Cheating

The researchers proved mathematically that Mure is provably lossless. This is the most important part. In the past, other tools tried to speed things up by taking shortcuts that might miss a few errors (they were "lossy"). They were like a chef who tastes the soup but skips checking the salt, hoping it's fine. Mure is different; it is a chef who checks the salt exactly the same way as the original recipe, just by using a pre-measured cup instead of weighing it every time.

The paper proves that Mure produces exactly the same results as the slow, boring, "do-it-all-from-scratch" method. It doesn't miss any broken robots. It just does the work faster.

What the Numbers Say

The team tested Mure on 15 different robot brains of all shapes and sizes, from simple ones to massive, complex ones with millions of parts. They ran these tests on standard computers (no fancy supercomputers or graphics cards were used).

The Speed Gain: On average, Mure made the testing process 44.54% faster. That means if a test used to take 100 minutes, it now takes about 55 minutes.
The Trade-off: They compared Mure to other "cheating" shortcuts (called DM# and BSS). Those shortcuts were even faster (up to 88.97% faster), but they made mistakes. They sometimes said a robot was fine when it was actually broken, or vice versa. Mure refused to make those mistakes.
The "How Much Did You Break It?" Test: The researchers also asked, "What if we break more of the robot?" They tested breaking 1%, 3%, and 5% of the robot's neurons. As they broke more parts, the speed-up got smaller (because there was less of the "first 10 steps" left to reuse). However, even when they broke 5% of the neurons, Mure still offered a 20% speed boost.

Why This Matters

This isn't just about saving time; it's about trust. In safety-critical fields like self-driving cars or medical diagnosis, you can't afford to guess. If a test says a car is safe, it must be 100% sure. Mure allows engineers to run these heavy, expensive safety checks much faster without sacrificing that 100% certainty.

The researchers showed that by being smart about what parts of the brain to reuse, you can cut the cost of testing nearly in half. They didn't just guess this would work; they built the tool, ran the experiments, and proved the math. It's a reminder that sometimes, the best way to go fast isn't to run harder, but to remember what you've already done.

Technical Summary: Provably Lossless Acceleration of DNN Mutation Testing via Memoization

Problem Statement
Mutation analysis has reemerged as a critical technique for assessing the adequacy of test datasets for Deep Neural Networks (DNNs). However, performing mutation analysis on DNNs is computationally prohibitive due to the need to generate and exhaustively test a vast number of mutant models. Existing acceleration techniques attempt to mitigate this cost through "lossy" approximations, which trade efficiency for accuracy by introducing errors in the calculated mutation score. These errors can lead to incorrect judgments regarding test dataset quality. While lossless (sound) acceleration techniques exist for conventional software, they have not been effectively adapted for DNNs, leaving a gap between the need for rigorous testing and the practical constraints of computational cost.

Methodology: The Mure Framework
The paper introduces Mure, the first provably lossless framework for accelerating DNN mutation testing via memoization. The core insight driving Mure is that DNN mutants and the original model share substantial redundant computation. Specifically, if a mutant modifies layers starting at index $n$ , all layers preceding $n$ remain identical to the original model. Mure exploits this by executing only the "mutated suffix" of each mutant while reusing the "common prefix" computed once from the original model.

The Mure workflow proceeds through the following steps:

Dependence Graph Construction: Mure analyzes the target DNN to construct a layer dependence graph, capturing how layers depend on one another. This is crucial for handling complex architectures (e.g., residual blocks) where layers may not depend strictly on their immediate predecessors.
Mutant Clustering: Mutants are grouped based on their "memoization boundaries." The boundary is defined as the set of indices of the deepest layers before the first mutated layer upon which the mutated region depends.
Instrumentation and Memo Table Construction: For each cluster, Mure instruments the original model to extract activation values at the boundary layers. These values are stored in a memo table, mapping test data points to the specific activation vectors required to feed the mutated suffixes.
Mutant Chopping: For each mutant, Mure constructs a "chopped mutant" by discarding the unmutated prefix and replacing it with a fabricated input layer that accepts the pre-computed activation vectors from the memo table.
Execution: The chopped mutants are executed using the memoized inputs. Only the mutated suffix is computed, significantly reducing the computational load.

Theoretical Guarantees
The authors provide formal proofs establishing two key properties:

Soundness (Losslessness): Mure is proven to be equivalent to exhaustive "vanilla" mutation testing. The chopped mutants produce outputs identical to the full mutants, ensuring zero error in the mutation score. This holds provided that the mutation operators do not alter the physical structure of the model (i.e., they do not add or delete layers/neurons) and the model operates in a deterministic inference mode.
Acceleration: A speed-up theorem demonstrates that Mure is guaranteed to reduce execution costs whenever multiple mutants share a non-trivial prefix. The cost reduction is proportional to the number of mutants in a cluster and the computational cost of the shared prefix.

Experimental Results
The authors implemented Mure in Python using Keras and TensorFlow and evaluated it on 15 DNN models across various architectures (FCNN, CNN with/without residual blocks, RNN) and datasets (MNIST, CIFAR-10, Caltech-101, IMDB, etc.).

Performance vs. Baselines: Compared to a vanilla approach, Mure reduced the computational cost of mutation testing by an average of 44.54%.
Comparison with State-of-the-Art: When compared to existing lossy techniques (DM# and BSS), Mure offered lower average acceleration (44.54% vs. 63.59% and 88.97%, respectively). However, unlike these baselines, Mure incurred zero mutation score error. The lossy techniques exhibited mutation score errors ranging from 0.12% to over 19%, which the authors note could impact downstream analyses.
Impact of Mutation Ratio: The study analyzed the effect of the "mutation generation selection ratio" (the percentage of neurons mutated). As this ratio increased from 1% to 5%, the speed-up decreased predictably due to reduced shared computation. However, even at a 5% mutation ratio, Mure maintained a speed-up of over 20%.

Significance and Claims
The paper claims that Mure represents a significant advancement by providing the first provably lossless acceleration for DNN mutation testing. Its significance lies in enabling rigorous test quality assessment and downstream tasks (such as test prioritization, fault localization, and robustness evaluation) without the trade-off of accuracy inherent in current lossy methods. The authors emphasize that Mure does not define a new testing adequacy criterion but rather preserves the exact semantics of vanilla mutation testing while drastically reducing its cost. The work establishes that structural sharing in DNNs can be systematically exploited to achieve substantial efficiency gains without compromising the integrity of the mutation analysis results.

The "Copy-Paste" Shortcut for Robot Brains

The Big Discovery: Speed Without Cheating

What the Numbers Say

Why This Matters

More like this