A microcontroller has two separate memory walls. Flash, the read-only storage, must hold the model's weights. SRAM, the small fast working memory (often 2 KB to 512 KB), must hold the intermediate feature maps that are alive at any single moment of inference. Compression methods mostly shrink the first wall and ignore the second. Some make the second worse. A conventional layer factored into low-rank pieces stores fewer weights, but it creates a new intermediate feature map whose size grows with the chosen rank. Quantizing weights to 4 bits saves Flash and does nothing for SRAM unless the activations are also quantized. The engineer therefore faces one discrete choice per layer: weight bit-width, activation bit-width, factorization rank, and how finely to tile the computation. The plan as a whole must fit both walls at once, and today it is chosen by days of black-box architecture search or by greedy guesswork.
We propose to write this choice down as an explicit combinatorial packing problem and solve its linear programming (LP) relaxation. An LP relaxation lets each discrete choice be fractional, which makes the problem convex and fast to solve. We then use one structural fact about the relaxation to round its solution: only a handful of layers can be fractional at an optimal vertex. Rounding those few layers by exhaustive enumeration yields a deployable plan, a certificate of how far that plan can be from the best possible plan under the accuracy proxy, and a full budget-versus-accuracy curve that can be re-targeted to a new chip in seconds rather than by re-running search.
Core Claim
The claim has two parts. The first is about formulation. Compression for on-chip deployment should be posed as a multiple-choice packing problem. Every layer picks exactly one option. Flash and latency are additive global budgets. Peak SRAM is a family of local constraints, one per execution step, each summing only the tensors alive at that step. Once posed this way, parameter-only compression is visibly the wrong objective. The 2 KB-RAM results of SpArSe already show that pruning weights does not bound working memory, and our formulation makes the rank-induced activation growth explicit.
The second part is about the algorithm. At an optimal vertex of the LP, the number of layers whose choice is fractional is at most $K + T$. Here $K$ is the number of global budgets (two: Flash and latency) and $T$ is the number of SRAM step constraints that are tight. This follows from counting nonzeros in a basic solution. In practice $T$ is one or two, because peak memory is usually attained at one or two steps, so only three or four layers need rounding. The approach is in the spirit of the controlled-fractionality idea of Ene et al., who keep only a constant number of coordinates fractional so that a knapsack-constrained relaxation can be rounded without breaking the budget. Their scheme pays a constant of $(1/\epsilon)^{O(1/\epsilon^4)}$. Ours gets small fractionality for free from LP vertex structure, so the cost of exact rounding is the option count raised to $K+T$, which is small enough to compute. A partial-enumeration step, in the style of classical knapsack approximation schemes, is then layered on top: we guess the few most expensive layer choices before solving the LP. This turns the additive rounding error into a tunable relative one.
Formulation
Let layer $l$ have a finite option set $O_l$. Each option $o$ fixes weight bits, activation bits, factorization ranks and tile count. Let $x_{l,o} \in [0,1]$ be the relaxed indicator that layer $l$ uses option $o$. Let $c_{l,o}$ be the option's estimated accuracy cost, $f_{l,o}$ its Flash bytes, and $a_{l,o,t}$ the SRAM bytes it contributes at execution step $t$. The relaxation is
$$\min_x \sum_{l}\sum_{o \in O_l} c_{l,o}\,x_{l,o} \quad \text{s.t.} \quad \sum_{o} x_{l,o}=1 \;\forall l,\qquad \sum_{l,o} f_{l,o}\,x_{l,o}\le F,\qquad \sum_{l\in \mathrm{live}(t)}\sum_{o} a_{l,o,t}\,x_{l,o}\le S \;\forall t,$$
with an analogous latency row. Here $F$ and $S$ are the chip's Flash and SRAM capacities, and $\mathrm{live}(t)$ is the set of layers whose tensors occupy memory at step $t$ under the runtime's buffer schedule. The factorized options borrow the treatment of multiplicative rank budgets from Approximately Optimal Core Shapes for Tensor Decompositions. That paper chooses Tucker ranks under a product-of-ranks parameter budget, turns the product into a sum with logarithms to obtain a knapsack-with-matroid problem, and proves a PTAS using singular-value energy as an error proxy. We reuse that proxy to prune each layer's rank grid to its proxy-Pareto-optimal points before building $O_l$. Their work optimizes one parameter budget on data tensors. Ours optimizes a sum of per-layer costs under several resource budgets, one of which (SRAM) their parameter-only model cannot represent.
The cost $c_{l,o}$ is the weak link. We start with a separable proxy: the measured validation-loss increase when only layer $l$ is compressed with option $o$. We then explicitly test whether these costs are additive. If they are not, we add pairwise terms between adjacent layers. On a chain network these can still be handled exactly by dynamic programming. The known gap between the singular-value proxy and the true reconstruction error on VicRoads in Ghadiri et al. is a warning that the proxy, more than the solver, may limit results.
Research Program
The work has four parts. First, we build an option generator and memory model that matches a real compiled runtime. The SRAM accounting must reproduce the buffer schedule of a TinyEngine-style compiler as described in MCUNet, including its in-place depthwise convolution. Tile options follow the height-wise slicing of TinyOps, restricted to internal SRAM only. We limit bit-width options to those for which we have working kernels (8 and 4 bits, plus 2-bit weights if kernel work permits). This keeps every plan physically deployable rather than theoretical, which is the hardware-realization gap flagged by LLMCBench.
Second, we prove the fractionality bound and the resulting guarantee. With partial enumeration of the $g$ costliest choices, the rounded plan is within a factor of roughly $(1+(K+T)/g)$ of the LP optimum on the proxy. This follows the standard knapsack argument: after the guessed layers are fixed, every remaining fractional layer is no costlier than any guessed one. We also want to establish when this bound is tight.
Third, we sweep budgets. A parametric LP produces the full proxy Pareto frontier over $(F, S)$, with a certified lower bound at every point. Re-targeting to a new chip then means reading off a new point, not re-searching. This answers the "static deployment brittleness" limitation of compiled search pipelines.
Fourth, we measure, on hardware, how much heuristic plans leave on the table relative to the certified bound.
Baselines
The naive reference point is uniform INT8 post-training quantization of the fixed backbone, run through the same compiled runtime. This is the industry default confirmed by MLPerf Tiny. Where it does not fit a budget, it is reported as infeasible rather than as an accuracy. Uniform INT4 for weights and activations is the second naive point. Both use identical calibration data and the same short fine-tuning budget that every method receives after its plan is chosen.
The greedy baseline repeatedly applies the single layer change with the best estimated accuracy cost per byte saved until both walls are satisfied. It gets exactly the same option sets and the same cost table, so any gap is attributable to search rather than information. This mirrors the RRE-greedy comparison in Ghadiri et al., who report their integer program running up to 1000x faster than greedy. They report no reconstruction-error value that we can quote.
The strongest competitor on solution quality is an exact integer program on our own formulation, solved by an off-the-shelf solver. It sees the same options, costs and constraints, and runs under the same wall-clock limit per budget point. It is the real threat, discussed below. Beating it means matching its plan quality within the certified gap while producing the full frontier faster. Matching it is the expected outcome on small option sets, and we would report it as such.
The strongest existing system is MCUNet's joint architecture search with its compiled engine. MCUNet reports 70.7% ImageNet top-1 on an STM32H743 with 3.4x lower peak SRAM than MobileNetV2 with CMSIS-NN. TinyOps reports 68.2% top-1 for MNASNet on STM32F746, though it relies on external SDRAM. We start from the MCUNet searched backbone and compress it to budgets below those it was searched for. Beating MCUNet there means higher top-1 than re-scaling MCUNet's own search to the smaller budget, at measured, not estimated, peak SRAM.
Three ablations isolate the key ingredients. A parameter-only variant drops the SRAM rows, in the manner of a pure parameter-budget formulation; we then count how often its plans violate SRAM on the board. A rank-blind variant ignores rank-induced activations. A third variant replaces vertex-based rounding with independent per-layer sampling from the fractional solution, which the LP-rounding literature predicts will break hard budgets.
Why not just…?
Why not just solve the integer program exactly? For a 50-layer network with tens of options per layer, a commercial solver will very likely find the optimum in seconds. On those instances our rounding adds nothing to plan quality, and we say so. The proposal's value there is the formulation, especially the SRAM rows and the rank-induced activations, and the certified frontier. The solver competition only matters once option sets grow to the full product of ranks, bit-widths and tile counts, and once one solve per budget point becomes thousands of solves for a frontier sweep. We will report solver time and optimality gap against option-set size. If the exact program stays fast at full scale, the paper is reframed honestly as "formulation plus measured heuristic gap," with the LP serving only as a certificate.
Why not just use greedy per-byte selection? Greedy handles one additive budget reasonably. Peak SRAM, however, is a maximum over steps, and the step that sets the peak moves as layers change. A greedy move that saves Flash at a non-peak layer looks attractive but does nothing for the binding SRAM step. Ghadiri et al. already found greedy missing globally better configurations in the single-budget case. Our same-information comparison will show whether the gap widens once the second wall is added. If it does not, that is a useful negative result.
Why not just run architecture search or Bayesian optimization? Search can explore architectures we hold fixed, so it is not strictly dominated. However, SpArSe reports multiple GPU days per search, and MCUNet needed a two-stage search just to make the space tractable. Neither offers any bound, and both must be rerun when the budget changes. We treat search and our method as complementary: search picks the backbone, and our method compresses it to each deployment target. The MCUNet-at-smaller-budget comparison tests whether that division of labor wins.
Why not just stream from external memory? Streaming of the kind TinyOps uses needs an external memory interface. The 2 KB / 32 KB parts targeted by SpArSe have none. Off-chip access also brings the latency cliff documented for Edge TPUs. We restrict ourselves to internal-memory-only deployment, where this alternative does not exist.
Proposed Experiments
Benchmarks are drawn from MLPerf Tiny and the MCU literature: ImageNet on STM32H743-class and smaller Cortex-M parts, Visual Wake Words, Speech Commands, and CIFAR-10, plus the 2 KB-RAM / 32 KB-Flash CIFAR10-binary regime of SpArSe. SpArSe reports models 7.4x smaller than Bonsai and ProtoNN in that regime; no reported accuracy number for it was found on Lacuna. Metrics are top-1 accuracy after a fixed short fine-tune, measured peak SRAM and Flash from the deployed binary, latency on the board, and solver time per frontier.
Three checks decide the outcome. First, does the empirical count of fractional layers at LP optima stay at or below $K+T$? Is $T$ small in practice? If many SRAM steps are simultaneously tight, the enumeration becomes expensive and the guarantee weakens. Second, does the separable cost proxy rank plans correctly? We will report the rank correlation between proxy cost and true post-fine-tune accuracy on held-out plans. If it is poor, the certificate is about the wrong quantity, and fixing the proxy becomes the main problem. Third, at budgets below MCUNet's search targets, do certified plans beat greedy, uniform quantization, and re-scaled search in measured top-1 while never violating on-board SRAM? Meanwhile, the parameter-only ablation should violate SRAM on a substantial fraction of budgets. If that ablation rarely violates SRAM, the central motivation is weaker than claimed, and we would report that directly.
References
- SpArSe: Sparse Architecture Search for CNNs on Resource-Constrained Microcontrollers
- A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
- Approximately Optimal Core Shapes for Tensor Decompositions
- MCUNet: Tiny Deep Learning on IoT Devices
- TinyOps: ImageNet Scale Deep Learning on Microcontrollers
- LLMCBench: Benchmarking Large Language Model Compression for Efficient Deployment
- MLPerf Tiny Benchmark
- Exploring edge TPU for network intrusion detection in IoT