MicroVSA: An Ultra-Lightweight Vector Symbolic Architecture-based Classifier Library for Always-On Inference on Tiny Microcontrollers

Machine learning on the smallest microcontrollers — the 8-bit parts with two kilobytes of RAM that make up much of the market — is essentially impossible with neural networks, so MicroVSA (Northeastern and UC Riverside) implements a different classifier entirely, one built from binary vectors and exclusive-or, and finds that a small algebraic rearrangement removes the bit-shuffling that had been eating the whole benefit of packing eight values into a byte.

Why this problem is worth solving

There is a whole family of models that never needed multiplication.

The natural representation on a small machine creates an awkward arithmetic problem.

What people did before, and where it broke

• Compress a neural network until it fits. Residual recurrent networks, layered recurrent architectures, and patch-based convolution all reduce the memory a model needs while keeping accuracy respectable. Where it broke. The demonstrations run on 32-bit parts with tens to hundreds of kilobytes of RAM — the tier above the one where cost and power actually bite.
• Port classical models to the smallest parts. Tree-based and prototype-based classifiers have been shown running on 8-bit microcontrollers in milliseconds. Where it broke. Their published results are on simplified benchmarks such as two-class handwritten digits, which the authors argue do not represent real deployment.
• Use hyperdimensional vectors with ten thousand elements. The classical form of this model family, which is genuinely robust and needs no multiplication. Where it broke. Ten thousand dimensions per vector is far too large for a device with two kilobytes of memory, and the vectors are built heuristically by repeated retraining rather than learned, which makes them hard to shrink deliberately.
• Store one binary value per byte. The straightforward implementation of a binary model, and the one the original design used. Where it broke. Seven of every eight bits in flash are wasted, and each elementwise operation handles one value when the hardware could handle eight.
• Pack the values and unpack them when summing. The obvious fix, and it does reduce flash by a factor of eight. Where it broke. The unpacking is a loop of mask, add and shift per bit, so the operation count comes out roughly the same as before packing. The memory win is real and the speed win vanishes.
• The gap. Everything either fits the wrong tier of device, solves the wrong tier of problem, or wins on memory while giving the gain straight back in cycles. The packed representation is clearly right and the arithmetic around it was making it pointless.

How eight values in a byte stop costing more than they save

The idea

A step that existed for a different machine was costing everything on this one. The original design puts a sign function between the two halves of the computation, and it is there for a good reason on the hardware it was designed for: taking the sign first means the following multiplication can be replaced by an exclusive-or, which is what a reconfigurable chip wants. On a microcontroller that reason evaporates, and the sign turns out to be the thing forcing every bit of a packed word into a separate running total — which is why the bits have to be extracted one at a time, and why packing them saved memory but no cycles. Take the sign out and the class vector can be distributed into the sum, so every bit of every result accumulates into one place. Now the whole byte can be handled at once, and since a byte has only 256 possible values, a 256-entry table answers in a single memory access what a loop of masking and shifting was doing in twenty-four. Enumerating every case in advance because the space happens to be small enough to hold, and turning a computation into a lookup, is the same manoeuvre the quantum decoder work covered elsewhere on this site makes when it runs an expensive matching algorithm offline over every error pattern a near-term code can produce.

Packing narrow values into a wide word is an old idea whose difficulty is always the unpacking. One exclusive-or on a packed word does eight, sixteen or thirty-two elementwise multiplications, which is the entire argument for the representation and the reason flash usage falls eightfold. What the measurements here make plain is that the argument is incomplete until you can also get the results back out cheaply. The obvious route — count the set bits and subtract twice that from the word size — is blocked by the fact that no microcontroller instruction set provides a population count, which is a small and consequential gap in what these parts offer. The route the paper takes instead is to make the extraction unnecessary rather than fast. The lesson that packing wide is only half the technique, and that the payoff depends entirely on the surrounding arithmetic being arranged to accept it, is exactly what the narrow-integer accelerator work covered elsewhere on this site is about, where a number-theoretic packing trick from the 1990s only becomes worth using once four instructions exist to make it pay.

The improvement is genuinely conditional, and the paper draws the boundary rather than hiding it. Distributing the class vector inward has a cost: the exclusive-or now involves three operands instead of two, so the inner work has to be repeated for every class. The original arrangement is roughly constant in the number of classes and the new one grows linearly with it, which puts a crossover at about four classes on 8-bit parts, eight on 16-bit, and eleven on 32-bit — beyond which the older algorithm wins and is kept in the library for that reason. A second boundary runs the other way. Wider words pack more values but cost more to unpack, so processing a 64-element vector takes 24 operations on an 8-bit part and 30 on a 32-bit one, and even a part with a single-cycle bit-extract instruction only reaches 26. Only spending two kilobytes on a larger table brings the 32-bit count down to 20. A technique whose advantage inverts below a threshold, so that the honest presentation is a crossover rather than a speedup, is the same shape as the encrypted string matching work covered elsewhere on this site, whose in-storage variant is faster above a certain database size and slower beneath it.

Following one inference through a byte-wide classifier

Feature vectors and class vectors are stored the same way. A working model here is between 0.43 and 25 kilobytes of flash in total, with the human-activity model at 2.46.

Why it works

• Binary vectors need no multiplier, and small parts have no multiplier worth using. Every operation in this model family is an exclusive-or and an addition → which is precisely what an 8-bit microcontroller does cheaply, while multiplication and floating point are what it does badly or not at all → so the model and the machine fit each other without any of the quantisation and calibration that shrinking a neural network requires.
• Packing turns memory savings into parallelism for free. Storing one bit per byte wastes seven-eighths of scarce flash → and packing them means a single exclusive-or instruction performs as many elementwise multiplications as there are bits in a word → giving both an eightfold flash reduction and eight-way parallelism from one change in representation.
• Removing an unnecessary step is what lets the packing pay. The sign function forced each bit of a packed result into a separate accumulator, which is why extracting them cost as much as packing saved → but it existed only to enable an optimisation for reconfigurable hardware, so removing it lets the class vector distribute inward and send every bit to one accumulator → which is what makes the whole byte processable at once.
• A table replaces arithmetic the instruction set does not provide. Summing the bits of a byte would be one population-count instruction, and no microcontroller has one → but a byte has 256 possible values and the answer for each can be computed ahead of time → so a 256-entry table gives in one memory access what a loop was doing in at least twenty-four cycles.
• Where the model sits in memory decides which loop order wins. These parts mostly have no cache, so performance is set by how often values must be reloaded → and whether the class matrix, a column of it, or the intermediate results fit in registers depends on the part and the model → so four traversal orders are provided and the right one is worth up to 2.63 times.

What it costs (trade-offs and scope)

• The central optimisation loses above a class count, and that count is small. Removing the sign function makes the inner work repeat per class, so operations grow linearly where they used to be roughly flat. The crossover sits at about four classes on 8-bit parts, eight on 16-bit and eleven on 32-bit, and the paper notes it may vary considerably with instruction set and compiler settings. Both algorithms are shipped for this reason.
• Removing the sign function also changes accuracy in both directions. Small models gain about 4.0 percent on average and large ones lose about 2.5 percent, so the two variants are genuinely alternatives rather than an upgrade.
• Training is out of scope and inherited. The paper states that training these models is an ongoing research problem it is not addressing, and adopts the prior methodology unchanged. Every accuracy figure therefore reflects what that training achieves.
• Wider words are worse per element, not better. A 64-element vector takes 24 operations on an 8-bit part and 30 on a 32-bit one, with a single-cycle bit-extract instruction only reaching 26. Getting below the 8-bit count requires spending two kilobytes of RAM on a bigger table.
• The obvious lookup table is sometimes slower than no table. On one 32-bit part the 256-entry version runs at 0.82 times the speed of a bit-manipulation sequence with no table at all, because that part has a deep pipeline and the sequential loads stall it.
• Choosing among the four traversal strategies is manual. They differ by up to 2.63 times and the right one depends on register count, cache presence, class count and model dimension. Guidance is given as a table; nothing selects automatically.
• Two of the 8-bit optimisations are empirical rather than sound. Narrowing the accumulator relies on observed value ranges staying well inside the theoretical ones, and the loop-tiling scheme uses an 8-bit accumulator whose range the paper notes exceeds a signed byte by one. Both are verified per model after training rather than guaranteed by construction.
• It wins on size and accuracy against classical models, and loses on speed. Decision trees and random forests run faster; the argument is that the smallest model here beats the largest of those on both accuracy and memory on three of four datasets, at latencies from half a millisecond to two hundred.
• It is slower than a convolutional network on one head-to-head. On a hand-posture task it reaches slightly higher accuracy in a third of the flash and a thirtieth of the RAM, but takes 2.808 milliseconds against 1.520. A smaller variant is faster than the network at a cost of 2.14 percent accuracy.
• Several comparisons span different chips. Prior work used whatever hardware its authors had, so the runtime comparisons put this system on one part against published figures from another — in one case a 84-megahertz core against a 160-megahertz one. The paper is open about this and the numbers are still not head to head.
• The streaming variant saves memory and latency, not work. Its operation count is stated as identical; what it buys is not having to buffer the input window and being able to release a result earlier.
• Scope is classification on a handful of datasets. Four tasks, with the ten-class one both the weakest in accuracy at small dimensions and outside the crossover on every word size.

The evaluation

Check yourself

Sources

The paper is “MicroVSA: An Ultra-Lightweight Vector Symbolic Architecture-based Classifier Library for Always-On Inference on Tiny Microcontrollers” by Nuntipat Narkthong, Shijin Duan, Shaolei Ren and Xiaolin Xu, published at ASPLOS 2024, pages 730-745, DOI 10.1145/3620665.3640374. The authors are at Northeastern University and the University of California, Riverside.

This explainer is written from the full 16-page text. Everything above comes from the paper’s own sections: the taxonomy of embedded device tiers with representative parts, tools and costs, and the argument that published work fits either the wrong device tier or the wrong problem tier; the background on vector symbolic architectures covering the binary and bipolar formats, the feature, value and class vectors, the binding and bundling operations and their binary equivalents, and the low-dimensional variant that recasts the structure as a binary neural network trainable by standard methods at roughly one-hundredth the dimension; the three classifier designs, comprising the packed binary implementation with its data representation and lookup-table accumulation, the rearranged version that removes the sign function with its accompanying analysis of accuracy, model size and operation growth against class count, and the streaming variant for windowed time-series input with its partitioned feature and class groups; the implementation section covering the four traversal strategies with their register and cache trade-offs and the summary of when each applies, the accumulator-width and loop-tiling optimisations for 8-bit parts, and the operation-count table and larger-lookup-table optimisation for 32-bit parts; and the evaluation covering the four datasets and their preprocessing, the ten development boards and their toolchains, the per-strategy runtime table, and the comparisons against tree-based classifiers, against prior compressed neural network work, and against a vendor-optimised model zoo.