Generalizing Reuse Patterns for Efficient DNN on Microcontrollers

Running a neural network on a tiny microcontroller is hard because there is almost no compute, and a good trick is computation reuse — noticing that many little tiles of an image look alike, computing the answer once, and reusing it for the rest — but every prior method groups pixels for that comparison in one fixed way; this paper (NC State and William & Mary) shows that the choice of how to group is really just a reordering of the rows and columns of the matrix the convolution already builds, which blows the space of possible groupings wide open, and adds two quick formulas to predict a grouping's accuracy and speed so the best one can be picked without retraining — yielding up to 2.2 times speedup or up to 8 percent more accuracy.

The argument in one glance

Problem

A neural network barely fits on a microcontroller, and reuse could help more than it does

Microcontrollers are the tiny, cheap, energy-frugal processors inside smart cameras, appliances, and sensors, and there is growing demand to run computer-vision neural networks on them directly. The trouble is that these networks are computationally heavy and the microcontroller has almost no compute or memory to spare. One of the most effective ways to lighten the load is computation reuse: real images are full of redundancy, so many small tiles of an image, or of a layer intermediate output, look nearly identical, and if you cluster the similar ones you can compute the expensive part just once and reuse that result for all the tiles in the cluster. Prior work showed this can eliminate over 90 percent of a convolution layer computation with little accuracy loss. But every method to date groups the data for that comparison in one single, fixed way, which quietly leaves most of the opportunity on the table.
What people did

Cluster the one obvious unit and reuse the centroid

Existing reuse methods take the most straightforward grouping: a neuron vector is just the flattened values of one tile of pixels in a channel. They cluster these vectors, compute the result for each cluster centroid, and copy that result to every similar vector in the cluster, then sum up the outputs.
Why it fell short

One fixed grouping is a single point in a huge space

Defining the neuron vector one fixed way is a narrow choice, and it is only one of an enormous number of ways the same data could be grouped for reuse. Different groupings expose different redundancies and yield different trade-offs of speed and accuracy, and the best grouping varies from input to input. Prior work could not explore this because the only way it knew to evaluate a grouping was to retrain the whole network with it and measure — far too slow to search a large space, so the alternatives went unexamined and reuse never reached its potential.
This paper's idea

Generalized reuse: groupings are matrix reorders, and two models pick the best

This work shows that the choice of how to group data for reuse is equivalent to reordering the rows and columns of the matrix the convolution already forms, plus a choice of direction (vertical or horizontal) and granularity — a systematic reuse space vastly larger than the single conventional pattern, and easy to generate by permutation. It then adds two fast analytical models, one predicting a grouping accuracy impact and one its latency, so promising groupings can be picked without retraining, delivering up to 2.2 times speedup or up to 8 percent higher accuracy over conventional reuse.

Why this problem is worth solving

The setting makes efficiency non-negotiable, because the hardware is about as small as a computer gets.

A microcontroller is a tiny, inexpensive, low-power processor — a simple core like an Arm Cortex-M with a few hundred kilobytes of on-chip memory and a couple of megabytes of flash, and no separate accelerator. Hundreds of billions of them are deployed in the world, in appliances, cars, wearables, and sensors, and there is strong interest in running vision neural networks directly on them so a device can see without sending data to a server. But a neural network’s convolutions demand far more arithmetic and memory than such a chip has to spare, so ordinary inference is painfully slow or simply does not fit. That gap is why microcontroller inference leans so heavily on removing redundant work: with no compute to waste, any computation you can avoid entirely is worth more here than almost anywhere else, which makes squeezing the most out of a technique like reuse directly valuable.

The technique in question turns a convolution into a matrix multiply and then attacks the repetition inside it.

Deep reuse accelerates a convolution by first rewriting it, in the standard im2col form, as the multiplication of an input matrix by a weight matrix — each tile of the input becomes a row segment, called a neuron vector, and each kernel becomes a column. Because real images are redundant, many of these neuron vectors are nearly identical, so deep reuse clusters them using locality-sensitive hashing, which maps similar vectors to the same short hash and thus into the same cluster. It then multiplies only each cluster’s representative, or centroid, by the weights, and copies that centroid’s result to every vector in the cluster, avoiding the redundant multiplications. A recent version, TREC, learns the hash functions during training for better clustering. The key parameter throughout is the reuse pattern: exactly how the data is carved into neuron vectors, because that determines which things get compared for similarity, and every prior method fixed this one way — a decision this paper reopens.

What people did before, and where it broke

Compress the model. Shrink the network itself with quantization, pruning, or smaller filters so it fits and runs faster. Where it broke. These target redundancy among the network’s parameters and are oblivious to the redundancy in the input data and activation maps, which is a separate and large source of waste they leave untouched.
Deep reuse with a fixed neuron vector. Cluster the flattened tiles of a channel and reuse each cluster’s centroid result. Where it broke. It fixes the reuse pattern to a single, most-obvious grouping, so it captures only the redundancy that that one grouping happens to expose and misses everything a different grouping would reveal.
Learn the clustering (TREC). Improve reuse by learning the hash functions during training so similar tiles cluster better. Where it broke. It makes the clustering smarter but still within the one fixed reuse pattern; it does not question how the data is carved into neuron vectors in the first place, which is where the larger opportunity lies.
Search reuse patterns by retraining. If one wanted to try alternative groupings, evaluate each by retraining the network with it and measuring accuracy and latency. Where it broke. Retraining is slow, so this is only feasible for a handful of patterns; against a large space of possible groupings it is hopeless, which is why the alternatives were never explored.
The gap. No one had a systematic way to describe the full space of reuse patterns, a cheap way to generate them, or a way to evaluate them without retraining — so reuse stayed locked to a single grouping, far short of what the data redundancy actually allows.

How generalized reuse works

From one fixed grouping to a searchable space of matrix reorders

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

A reuse pattern is not fixed — it is a knob, and it opens a whole space. The quiet assumption in all prior reuse work was that a neuron vector is simply a flattened tile: the one natural way to slice the data. This paper points out that this is a choice, and choices have alternatives. Which elements you gather into a neuron vector decides what gets compared for similarity, and different groupings surface different redundancies and strike different balances between how much computation is saved and how much accuracy is lost. Naming this the reuse space, and recognizing that conventional reuse is just one point in it, reframes the whole technique from a fixed transformation into a search problem with room to win. Exploiting the redundancy in data by reshaping how a computation is organized, rather than accepting one canonical layout, is the same instinct the video-transformer matrix-condensing work covered elsewhere on this site is built on, restructuring the computation to collapse the repetition the default arrangement leaves scattered.

The space of groupings is just the space of matrix reorders. An abstract space of arbitrary groupings would be unwieldy, but the paper second insight makes it concrete and cheap: changing which elements form a neuron vector is exactly equivalent to permuting the rows or columns of the im2col matrix the convolution already builds, then slicing it the ordinary way. A column reorder groups different elements than a row reorder, and any grouping you want can be reached by some permutation, achievable with a one-line reshape. This turns a vague design space into a mechanical generator: enumerate reorders and you enumerate reuse patterns. Reordering the layout of a matrix to expose an optimization that the original ordering hides is the same move the format-and-schedule co-optimization work covered elsewhere on this site relies on, where permuting how data is arranged is precisely what unlocks efficiency a fixed layout would forfeit. Generalized reuse adds one more axis on top of the reorder: a direction. Conventional reuse only compares vectors vertically down a panel; the new horizontal direction compares along a row, approximating the weighted sum of two similar vectors by their average times the summed weights, wringing out redundancy the vertical view cannot see.

Predict the outcome instead of retraining to find it. Opening the space creates a new problem: it is now enormous, and the old way to judge a pattern was to retrain the network with it and measure, which is far too slow to try many. The paper answers with two analytical models that estimate a pattern effect directly from the math. The accuracy model uses the squared Frobenius norm of the clustering error — how far each vector sits from its cluster centroid — as a proxy for how much a pattern will hurt accuracy, and the latency model approximates the speedup by counting the multiplications a pattern eliminates. Together they rank candidates cheaply, so the search focuses full, expensive evaluation on only a small, promising subset rather than the whole space. Replacing an exhaustive, costly search of a large optimization space with a fast predictive model that steers toward the good configurations is the same strategy the Bayesian compiler-optimization work covered elsewhere on this site is built on, using a cheap surrogate to avoid measuring every point when only a few are worth trying.

Following a convolution through generalized reuse

Choosing and applying a reuse pattern for one layer

A trace, from the paper, of how generalized reuse accelerates a convolution layer on a microcontroller by picking a good grouping instead of the fixed one.

Step 1 of 5

Form the im2col matrix and consider the reorders

The layer convolution is written as the im2col input matrix times the weight matrix. Instead of clustering the neuron vectors as they fall out of the default tiling, generalized reuse treats the row and column orderings of the input matrix as knobs, each ordering yielding a different way to group elements into neuron vectors.

A column reorder and a row reorder produce different neuron blocks; any desired grouping corresponds to some permutation, generated with a simple reshape.

Why it works

A fixed grouping only sees the redundancy it happens to align with. One canonical neuron-vector definition exposes just the similarities that fall along it → but treating the grouping as a searchable reuse space lets other groupings surface redundancy the default hides → so more computation can be reused, raising speed or accuracy beyond the single conventional pattern.
Matrix reorders make the huge space cheap to generate. An abstract space of arbitrary groupings would be intractable to enumerate → but every grouping equals a row or column permutation of the im2col matrix, produced by a trivial reshape → so the whole space is mechanically explorable instead of requiring hand-designed rules.
A second reuse direction finds redundancy the first cannot. Comparing vectors only vertically down a panel misses similarities that lie along a row → but the horizontal direction compares along rows and uses the distributive law to reuse when two vectors are alike → so patterns capture redundancy in both orientations of the matrix.
Analytical models replace retraining, so the search is feasible. Judging a pattern by retraining the network is far too slow for a large space → but the squared-Frobenius accuracy model and the computation-counting latency model estimate a pattern effect directly → so candidates are ranked cheaply and only a few need a full check.
The gains are robust across networks and devices. A trick that helped only one setup would be a curiosity → but the reuse-space idea and its models apply regardless of the specific network or microcontroller → so the paper reports consistent benefits, 1.03 to 2.2 times faster or 1 to 8 percent more accurate, across four DNNs and two microcontrollers.

What it costs (trade-offs and scope)

The models are estimators, not guarantees. The accuracy model uses the squared Frobenius clustering error as a proxy and the latency model counts eliminated computations; these predict well enough to prune the space, but they are approximations, so a small set of candidates still needs full evaluation to confirm the real accuracy and speed, and a pattern the models rank highly could underperform in practice.
It accelerates reuse-amenable layers, chiefly convolution. The technique targets convolution, where im2col and neuron-vector clustering apply and where vision workloads spend their time; although reuse can extend to fully connected and recurrent layers, the paper concentrates on convolution, so networks or layers without exploitable data redundancy benefit less.
The benefit rides on data redundancy, which varies. Reuse works because real images and activation maps repeat themselves, and the best pattern differs from input to input; inputs with little redundancy offer little to reuse, and the input-dependence means the chosen pattern is a good general fit rather than optimal for every image.
Generalization adds selection overhead. Expanding the reuse space means there is now a pattern-selection step, running two models over many candidates, that conventional reuse did not have; the paper makes this cheap with analytical models, but it is real work that must stay small relative to the inference savings to be worthwhile.
Evaluation is at the scale of small vision networks on microcontrollers. The gains are shown on four networks including CifarNet and ZfNet across two microcontroller models; this is the right target for the problem, but it is a demonstration on compact vision DNNs, not a study across large models or many hardware classes.

The evaluation

Three ways to run a convolution on a microcontroller

Property	No reuse	Conventional deep reuse	Generalized reuse
Source of savings
How a grouping is chosen	Not applicable
Cost of exploring alternatives	Not applicable
Reuse directions considered	None
Reported result	Baseline compute

From the paper's evaluation on four networks (including CifarNet and ZfNet) across two microcontroller models. Generalized reuse consistently improves on conventional reuse, giving either speedup at similar accuracy or accuracy gain at similar speed, by searching a far larger reuse space with two analytical models instead of retraining.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The contribution is conceptual and clean: it shows that the fixed reuse pattern everyone used is a single point in a large reuse space, that the space is generated simply by reordering the rows and columns of the im2col matrix and adding a horizontal reuse direction, and that two fast analytical models — a squared-Frobenius accuracy estimate and a computation-counting latency estimate — let the space be searched without retraining. Read the results in that light. The models are proxies that prune the space, so a small set of candidates still needs full verification. The technique targets convolution and depends on real data redundancy, which varies by input, so the chosen pattern is a strong general choice rather than a per-image optimum. Generalization adds a selection step that must stay cheap to pay off, which the analytical models are designed to ensure. And the evaluation is on compact vision networks and two microcontrollers, the right setting for the problem but not a sweep across large models. Within those bounds the message is convincing: by reconceiving how data is grouped for reuse, generalized reuse consistently beats conventional reuse, 1.03 to 2.2 times faster or 1 to 8 percent more accurate.

Background

Why squeezing microcontrollers is its own kind of hard

It helps to see why so much ingenuity goes into a chip most people never think about. Microcontrollers are the most numerous computers on earth, embedded by the hundreds of billions in the ordinary objects around us, and pushing intelligence onto them — letting a camera or a sensor understand what it sees without shipping data to the cloud — is a large part of what edge computing promises: lower latency, lower energy, and better privacy. But the resource gap is brutal. A vision network expects gigabytes and gigaflops; a microcontroller offers a few hundred kilobytes and a modest core with no accelerator. Closing that gap is not a matter of a faster clock but of doing dramatically less work for the same result, which is why techniques that eliminate redundant computation are so central here. That pressure, of fitting a demanding neural network into a device with almost nothing to spare, is the same pressure the edge-inference pipelining work covered elsewhere on this site operates under, restructuring how a model runs so it can execute at all on tightly constrained hardware. Generalized reuse pushes on the same problem from the angle of redundancy: given that the data repeats itself, find the grouping that lets the tiny processor skip as much repeated arithmetic as possible.

If you remember only three things

1. Running vision DNNs on microcontrollers is hard because the chips have almost no compute or memory, and computation reuse — clustering similar tiles of the input or activation map so a result computed once serves all similar tiles — is a powerful remedy (prior work removed over 90 percent of a convolution layer computation), but every method fixed the grouping unit, the neuron vector, to one obvious definition, capturing only a fraction of the available redundancy.
2. This paper introduces generalized reuse on two insights: the way data is grouped for reuse is a choice that forms a large reuse space, and any grouping is equivalent to a row or column reorder of the im2col matrix the convolution already builds, making the space trivially generatable by permutation; it also adds a new horizontal reuse direction (comparing vectors along a row via the distributive law) alongside the conventional vertical one, drastically expanding explorable patterns.
3. Because the enlarged space is too big to search by retraining per pattern, two analytical models — an accuracy model using the squared Frobenius norm of clustering error and a latency model counting eliminated computations — rank candidates cheaply so only a promising few need full evaluation; across four networks and two microcontrollers, generalized reuse consistently beats conventional reuse by 1.03 to 2.2 times in speed or 1 to 8 percent in accuracy.

Check yourself

Check your understanding

1. What is a reuse pattern, and what limited prior reuse-based DNN methods?
2. What is the key insight that makes the enlarged space of reuse patterns easy to generate?
3. Why does the paper introduce two analytical models, and what do they estimate?
4. What were the results, and what are the limits?

Sources

The paper is “Generalizing Reuse Patterns for Efficient DNN on Microcontrollers” by Jiesong Liu (North Carolina State University), Bin Ren (William & Mary), and Xipeng Shen (North Carolina State University), published at ASPLOS 2025 (Volume 2), pages 451-466, DOI 10.1145/3676641.3716257.

This explainer is written from the full text of the authors’ copy of the paper. Everything above comes from the paper’s own sections: the introduction motivating DNN inference on microcontrollers and computation reuse (with the observation that model-compression techniques target parameter redundancy but are oblivious to input-data redundancy, and that prior reuse removes over 90 percent of a convolution layer’s computation with little accuracy loss); the background on microcontrollers (the Cortex-M4 based STM32F469I with its limited SRAM and flash) and on locality-sensitive hashing for clustering; the review of deep reuse and its four-step process (clustering neuron vectors of the im2col input matrix, computing centroid results, recovering the rest by duplication, and summing) and its TREC extension that learns the hash vectors during training; the two insights of generalized reuse (that the neuron-vector definition and granularity define a reuse pattern forming a reuse space, and that any such pattern is equivalent to a row or column reorder of the im2col matrix, generatable by permutation); the reuse space’s three dimensions (reuse order via reordering, reuse direction, and reuse granularity) and the new horizontal reuse direction that compares vectors along a row and uses the distributive law (approximating a weighted sum of two similar vectors by their average times the summed weights); the two analytical models (the accuracy model based on the squared Frobenius norm of the clustering error and the latency model based on counting eliminated computations) used to select promising patterns without retraining; and the evaluation on four networks including CifarNet and ZfNet across two microcontroller models, reporting 1.03 to 2.2 times speedups at similar accuracy or 1 to 8 percent accuracy improvements over conventional reuse.