Space-Efficient TREC for Enabling Deep Learning on Microcontrollers

A convolution layer applied to an image repeats near-identical work because neighbouring image patches look alike, and a recent trick called TREC turns that redundancy into a trainable clustering step that computes each group once — but it does this by adding a large hash matrix and cluster tables that a microcontroller with a few hundred kilobytes cannot spare; this paper (Renmin and NC State) makes TREC free of that overhead by reusing columns of the network's own weight matrix as the hash vectors, so the same numbers do double duty.

Why this problem is worth solving

The redundancy being exploited is real and large, and it lives in the input rather than the weights.

Finding those groups cheaply is done with a hashing trick that has an awkward memory cost.

What people did before, and where it broke

• Compute the convolution in full with an optimised library. The standard route on microcontrollers, using vendor kernels tuned for the chip. Where it broke. It does every multiply-accumulate, including all the redundant ones, so a layer takes as long as its full operation count allows — hundreds of milliseconds to seconds for the networks here.
• Exploit input similarity with random hash vectors. A prior software approach clusters similar input rows using randomly chosen hash vectors and reuses the centre’s result. Where it broke. The random vectors are extra state to store, and worse, the randomness makes the inference accuracy fluctuate — a drop of several percent, varying run to run, which is unacceptable for a deployed model.
• Make the reuse a trainable operator. The immediate predecessor folds the clustering into the network so the hash vectors are learned and accuracy is stable. Where it broke. It still stores a dedicated hash matrix and per-cluster containers, which for the larger networks here exceed the microcontroller’s entire memory, so those models simply cannot run.
• Shrink the model with pruning and quantisation. The established way to fit a network on a small device: remove weights and use narrow integers. Where it broke. These attack the redundancy in the weights, which is a different and complementary problem; they make the model fit but do nothing about the repeated computation over similar input patches.
• Build special hardware for input reuse. Some designs exploit input similarity in silicon. Where it broke. A microcontroller is fixed commodity hardware; you cannot add an accelerator, so any solution has to be pure software fitting the chip as it is.
• The gap. The computation-saving idea worked but carried a memory cost that was invisible in the cloud and fatal on the device, and the memory-saving techniques worked but did not touch the computation. Nobody had made the reuse itself free of extra storage.

How the hash matrix stops needing to exist

The idea

The hash vectors and the weight columns are the same kind of object, so one set can be both. The clustering step multiplies each unrolled input row by a set of hash vectors and keeps the signs; the convolution multiplies each unrolled input row by the filter columns and keeps the products. These are the same operation — dot products of the identical input rows against some columns — differing only in what is done with the result afterward. Once you see that, the extra hash matrix is revealed as redundant storage: take the first few columns of the weight matrix the layer already holds, treat them as the hash vectors, and the partial products against those columns serve simultaneously as hashing projections and as a slice of the real output. The same numbers do double duty, and the dedicated hash matrix — the majority of the added overhead, more than 90 percent of it for the largest network — vanishes. Discovering that a circuit or a stored value put there for one purpose already computes exactly what a second purpose needs is the same pleasing move the encrypted-search work covered elsewhere on this site makes about the exclusive-or already sitting in flash chips, reused for free.

Reusing the weights forces a training discipline, and getting it right is what keeps accuracy stable. The obvious objection is that hash vectors and weights normally evolve independently during training, so binding them together should degrade one or the other. The predecessor operator kept them separate for exactly that reason, which is why it needed the extra matrix. The resolution is to bind them deliberately: the hash vectors are columns of the weight matrix, and in the backward pass the gradient for their hashing role is copied directly from the gradient of those weight columns, so they are updated as one thing and never diverge. Any clustering error introduced this way is passed forward and then corrected in the next backward pass, and because the filters are trained to be independent of one another, the reused columns remain independent enough to hash usefully. The measured result is accuracy that stays within a fraction of a percent, against the several-percent random fluctuation that the earlier random-hash approach suffered. This is the same lesson the microcontroller vector-classifier work covered elsewhere on this site records, that a step which looks harmless to remove or repurpose can be the thing holding accuracy together, and the repurposing has to be paid for with the right training arrangement.

On a flat, tiny memory the second overhead — the cluster tables — has to be paid only for clusters that occur. Even with the hash matrix gone, the operator has to store a representative for each cluster, and the naive way pre-allocates an array for every possible cluster identifier. With a handful of hash bits the number of possible clusters is large, most never appear, and pre-allocating for all of them wastes the scarce memory. The fix is a streaming structure: a stack holding one running centre per cluster that has actually been seen, plus a reverse index mapping a cluster identifier to its slot in the stack, so a cluster costs memory only when a row lands in it, and the running centre is updated in place as more rows arrive. Combined with the kernel reuse, this brings the dynamic overhead down by more than 70 percent. Refusing to reserve capacity for a worst case that the data almost never reaches, and paying only for what actually materialises, is the same discipline the sparse-mapping flash-translation work covered elsewhere on this site applies when it stores an address map whose size tracks the mappings that exist rather than the ones that could.

Following one convolution layer through space-efficient reuse

The multiply-accumulate is done with the chip's 16-bit fused instructions, two rows and two columns at a time to reuse loaded values, since these small cores have narrow arithmetic and no floating-point unit.

Why it works

• The clustering projection and the convolution share their expensive operation. Both multiply the same unrolled input rows against a set of column vectors → so choosing the hash vectors to be leading columns of the weight matrix means the projection is a byproduct of the multiplication the layer performs regardless → and the dedicated hash matrix, most of the added overhead, need not be stored at all.
• Binding the gradients keeps the reused columns valid as hash vectors. Weights and hash vectors would normally drift apart under independent training, which is why the predecessor kept them separate → but copying the hash-role gradient from the weight-column gradient updates them as one, with clustering errors corrected in the following backward pass → giving stable accuracy within a fraction of a percent where random hashing fluctuated by several.
• Independent filters make independent hash vectors for free. A hash family needs its vectors to be mutually independent to cluster well → and the filters of a convolution are trained independently of one another, so the weight columns already are → so reusing them costs nothing in clustering quality.
• Streaming the cluster centres pays only for clusters that occur. With many possible clusters and most unused, pre-allocating an array each wastes scarce memory → so a stack of running centres plus a reverse index allocates a slot only when a row first lands in a cluster → cutting the remaining dynamic overhead by more than 70 percent.
• Removing operations translates directly to time on these chips. On a microcontroller, latency rises linearly with the number of operations, with no cache hierarchy or parallelism to hide waste → so eliminating more than 96 percent of a layer’s multiply-accumulates shows up almost directly as speedup → giving the 3.4-to-5-times end-to-end gains.

What it costs (trade-offs and scope)

• The core reuse idea is not this paper’s; the space-efficiency is. The redundancy-eliminating operator and its theory come from a prior work. The contribution here is making it fit and run on microcontrollers, so the headline speedups are largely inherited and the novel part is the storage elimination that enables them.
• The reuse saves less than the redundancy it finds. More than 96 percent of operations are identified as redundant, but the actual per-layer speedup averages around four times, not thirty — because the clustering, projection and recovery are themselves work, and that overhead eats much of the theoretical gain.
• The benefit is concentrated in a few layer types. Speedups range from about 1.0 times on some layers to nearly 19 on the most computation-heavy ones; the average is carried by the wide, channel-rich layers, and many layers barely benefit at all.
• The models must be aggressively compressed first, by other means. The networks only fit because pruning, quantisation and layer folding remove over 90 percent of the static size beforehand. Reuse addresses computation and dynamic memory; it does nothing for the model’s own footprint, and the whole pipeline depends on the offline compression working.
• The number of hash bits is a tuned trade-off, per layer. More bits give finer clusters and safer accuracy but less reuse; fewer give more saving but risk accuracy. The paper reports configurations found by search, so deploying on a new model means re-tuning.
• Applying reuse to more layers erodes accuracy. The kernel-reuse study shows accuracy holding above 84 percent only while fewer than sixteen layers use it, declining as more do — so the technique is applied selectively, not everywhere, and the best trade-off is model-specific.
• The scope is small convolutional networks on two boards. Three compact vision networks on the CIFAR-10 dataset, on two STM32 microcontrollers. No transformers, no other datasets, and the two boards are closely related, so generality across chip families is asserted rather than shown.
• Weights live in flash, which is a workable but load-bearing assumption. Keeping weights in flash rather than fast memory costs only about one percent of latency and frees space for activations — but putting activations in flash instead costs over 20 percent, so the placement that makes it fit is specific and fragile.
• The correctness argument for kernel reuse is informal. Robustness and convergence are argued to carry over from the prior operator by inheriting its properties, rather than established afresh for the modified training, and the error-correction claim is qualitative.
• Latency is measured, but energy is only modelled. The case for deployment leans on energy efficiency, yet the energy benefit is inferred from an operation-count model rather than measured on the board.
• Sparse inputs need a separate conversion step, described in an appendix, so the dense-convolution framing that the main method assumes does not cover every layer a real network contains.

The evaluation

Check yourself

Sources

The paper is “Space-Efficient TREC for Enabling Deep Learning on Microcontrollers” by Jiesong Liu, Feng Zhang, Jiawei Guan, Hsin-Hsuan Sung, Xiaoguang Guo, Xiaoyong Du and Xipeng Shen, published at ASPLOS 2023, pages 644-659, DOI 10.1145/3582016.3582062. The authors are at Renmin University of China and North Carolina State University.

This explainer is written from the full 16-page text. Everything above comes from the paper’s own sections: the background on microcontroller architecture and memory hierarchy, on prior input-reuse work with random hash vectors and its accuracy instability, on model-compression techniques for lasting redundancy, and on locality-sensitive hashing; the overview distinguishing lasting from transient redundancy and introducing the transient-redundancy-elimination convolution operator; the review of the operator’s four steps — locality-sensitive clustering, centroid multiplication, recovery, and summation — and its computation savings; the space-efficiency section quantifying the hash-matrix and cluster overhead against four boards, and presenting kernel reuse with its detailed workflow, its gradient-copying training rule, and its correctness, robustness, convergence and space-saving arguments, together with the two-step stack substitution using a reverse index; the implementation section on offline pruning, quantisation and batch-norm folding, on meeting accuracy requirements, on the recovery step, the 16-bit SIMD matrix-multiply kernel, and the placement of weights in flash and activations in fast memory; and the evaluation covering the two boards and three networks, the end-to-end latency and accuracy comparison against a tuned library, random-hash reuse and a dictionary method, the single-layer speedups and redundancy ratios, the static and dynamic space savings, and the study of how kernel reuse across more layers trades accuracy against space.