SoD2: Statically Optimizing Dynamic Deep Neural Network Execution

The optimizations that make neural networks fast — fusing operators, planning memory — all assume every tensor's shape is known ahead of time, but modern models increasingly decide their shapes and even which layers to run based on the input, so today's mobile engines either recompile on every new input (slower than the inference itself) or waste memory on worst-case guesses; this work from the University of Georgia and William and Mary builds SoD2, which classifies each operator by how dynamic it really is and propagates symbolic shapes through the graph, recovering statically almost everything the old optimizations need and running up to 3.9 times faster while cutting peak memory up to 88 percent.

The argument in one glance

Problem

The optimizations that speed up neural networks assume shapes are known ahead of time

Running a deep neural network fast on a phone depends on a few key compiler optimizations: fusing many small operators into one to cut memory traffic, planning the order operators run to reduce peak memory, and laying out where each tensor lives in memory. Every one of these needs to know the shapes and sizes of the tensors before the model runs. That was fine for static models, where each layer's input and output shapes are fixed and the execution path never changes. But models are increasingly dynamic: their tensor sizes depend on the input, and sometimes even which layers run depends on the input.
What people did

Handle dynamism by recompiling, over-allocating, or interpreting shapes at runtime

Existing mobile engines cope in blunt ways. Static engines like TensorFlow Lite and MNN re-initialize — essentially recompile — whenever the input shape changes, or conservatively allocate the maximum memory any input could need, and for dynamic control flow they execute every possible path and throw away the invalid results. A more dynamic engine, TVM with its Nimble extension, runs a virtual machine with shape functions that infer output shapes at runtime and allocate memory on the fly.
Why it fell short

Every fallback pays a heavy tax because it treats dynamism as opaque

All of these are expensive because they give up on static reasoning. Recompiling on each new shape often takes longer than the inference itself — on a Galaxy S21, re-initializing a model can cost many times the inference time. Worst-case allocation wastes memory a phone cannot spare. Executing every control-flow branch burns compute on results that get discarded. And the runtime shape functions and dynamic allocation of the virtual-machine approach add their own overhead on every inference. None of them ask how dynamic each operator actually is.
This paper's idea

Recover statically almost everything, and defer only what is truly dynamic

SoD2's insight is that dynamism is not all-or-nothing. It classifies each operator by how its output shape depends on the input — some are fully determined by input shapes alone, some need a few input values, a few are only knowable after execution. Then a data-flow analysis, Rank and Dimension Propagation, threads shape information through the whole graph as known constants, symbolic constants, or expressions over them. This recovers enough static knowledge to fuse, plan execution and memory, and pre-generate specialized code, leaving only the genuinely dynamic parts for runtime.

Why this problem is worth solving

The heart of the matter is that a whole toolbox of optimizations quietly depends on a fact dynamic models take away, so it is worth being precise about the dependency.

A deep neural network is a graph of operators passing tensors between them, and the compiler makes it fast with a set of transformations that all assume the tensor shapes are known before the model runs. Operator fusion merges adjacent operators into one to avoid writing intermediate results to memory, but it can only do so if it knows the operators iterate over the same index space — that is, the same shapes. Execution planning picks the order to run operators to minimize peak memory, but it cannot compare orderings without knowing how big each tensor is. Memory allocation decides where each tensor lives in a linear buffer and when it can be freed, which again needs sizes. For a static model these are all knowable up front, so the compiler can do this work once, offline, and ship an optimized binary. A dynamic model breaks the premise. Its shapes may depend on the input — a language model taking anywhere from 32 to 512 tokens, a vision model taking images of varying resolution — and in some models the very set of operators that runs depends on the input, as when a network skips layers it deems unnecessary. When the shapes are unknown at compile time, every one of those optimizations is disabled, and the model runs slow. Since dynamic models are becoming the norm, driven by the need to adapt to different devices, inputs, and accuracy targets, recovering those optimizations is what makes the difference between practical and impractical on a phone.

The reason the existing fallbacks are so costly is that they treat the model as either fully known or fully unknown, with nothing in between.

Faced with an unknown shape, today’s engines pick one of a few blunt strategies, each paying for its bluntness. The static engines recompile the whole model whenever the input shape changes — running shape propagation, layout selection, scheduling, tuning, and allocation afresh — and the paper measures this re-initialization taking many times longer than the inference it precedes, which is only tolerable if the same shape recurs across many inferences. Because real applications feed continuously changing inputs, that rarely holds. The alternative, allocating the maximum memory any input could ever need, wastes the scarce memory of a mobile device and can make large models impossible to run at all. For dynamic control flow, executing every branch and discarding the invalid outputs burns compute proportional to the number of paths. The most dynamic engine instead interprets shapes at runtime with special shape functions and allocates memory on the fly, trading recompilation for per-inference interpretation overhead. What unites all of them is that they never distinguish an operator whose output shape is a simple function of its input shape — knowable symbolically without any concrete numbers — from one whose shape genuinely cannot be known until it executes. Treating both as opaque throws away the large fraction of a dynamic model that is, in fact, statically analyzable — which is exactly the waste SoD2 targets.

What people did before, and where it broke

Recompile the model when the input shape changes (TensorFlow Lite, MNN). Re-run the whole static optimization pipeline for each new shape. Where it broke. The re-initialization — shape propagation, scheduling, tuning, allocation — often takes many times longer than the inference itself, which only amortizes if a shape recurs, but real inputs change continuously.
Conservatively allocate the maximum memory any input could need. Size every buffer for the worst case so no reallocation is needed. Where it broke. It wastes the limited memory of a mobile device and can make large models unrunnable, exactly where memory is most precious.
Execute every control-flow branch and discard invalid results. Handle input-dependent paths by running all of them. Where it broke. Compute grows with the number of possible paths, most of which are thrown away, so a model that dynamically skips work ends up doing all of it.
Interpret shapes at runtime in a virtual machine (TVM with Nimble). Use shape functions to infer output shapes and allocate memory dynamically during execution. Where it broke. The runtime shape interpretation and dynamic allocation add overhead on every inference, and interpreting shapes at runtime limits static optimizations like fusion.
The gap. Every approach treated a dynamic operator as fully opaque, recompiling, over-allocating, or interpreting at runtime, never separating the parts of a dynamic model that are statically knowable from the parts that genuinely are not. What was missing was an analysis that classifies each operator’s dynamism and recovers, statically, everything derivable, deferring to runtime only what truly must be — which is what fast dynamic-model inference needs.

How SoD2 works

Recovering static shape knowledge from a dynamic model

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

The idea

Recover the shapes symbolically instead of surrendering them to runtime. The whole loss comes from treating an unknown shape as unknowable, when in truth most dynamic shapes are simple functions of a few unknowns — a tensor is “batch by 512” even if the batch varies. SoD2’s rank-and-dimension propagation carries known constants, symbolic constants, and expressions over them through the graph, so the compiler learns that two tensors share a shape, or that a dimension is fixed, without any concrete numbers, and can then apply the optimizations that unknown shapes had blocked. Using symbolic shape reasoning to unblock the optimization of a graph whose tensor sizes are not known until runtime is exactly the technique the recommendation-model compiler covered elsewhere on this site relies on, representing each shape as a symbolic expression and propagating it so transformations that a concrete-shape view cannot see become possible.

Do statically everything that can be done statically, and defer only the rest. The blunt fallbacks fail because they are all-or-nothing, paying a full runtime price for models that are mostly analyzable. SoD2 draws the line finely: its operator classification tells it precisely which outputs are fully determined by input shapes, which need a few input values, and which are only knowable after execution, so it front-loads all the derivable work and leaves runtime only the genuinely execution-dependent parts. Splitting a problem into the part you can settle ahead of time and the part that must wait for the input, and paying the dynamic cost only for the latter, is the same discipline the SLAM-runtime work covered elsewhere on this site follows, characterizing offline what it can and adapting online only what truly depends on the moment.

Isolate the truly dynamic operators so the static regions can be optimized cleanly. A single operator whose shape is unknowable until it runs would, if left in place, poison the analysis of everything downstream. SoD2 instead treats such an operator as a boundary, partitioning the graph there into subgraphs that are each internally analyzable, so a fully-optimizable region is not held hostage by one dynamic neighbor. Quarantining the one troublesome dimension so the rest can be reasoned about and bounded independently is the same decoupling the resource-resizing work covered elsewhere on this site performs, cordoning off the hard-to-control part so the tractable part can be handled on its own terms.

Following a variable-length text model through SoD2

Optimizing a language model whose input length varies

Tracing a variable-length model shows how symbolic shapes rescue the optimizations.

Step 1 of 5

A code model must accept text of any length from 32 to 384 tokens

A transformer-based model like CodeBERT takes a sequence whose length changes with every input. Its intermediate tensors are all shaped "sequence length by hidden size," where the sequence length is unknown until the input arrives, so a conventional engine cannot statically fuse or plan around them.

A static engine would recompile for each new length, often costing more than the inference.

Why it works

Symbolic shapes let fusion happen where concrete shapes are unknown. Fusion needs to know two operators share an index space, which unknown shapes hide → but propagating symbolic shapes reveals that two tensors have the same shape or a fixed dimension → so SoD2 fuses them into one version instead of failing or emitting a version per possible shape.
Symbolic sizes make execution and memory planning static that others do at runtime. Choosing an execution order and memory layout to minimize peak memory needs comparable sizes → but expressions in a few symbolic constants can be compared even without concrete numbers → so SoD2 computes near-optimal plans offline rather than paying runtime interpretation and allocation.
Partitioning at the unknowable operators keeps the static regions optimizable. One operator whose shape is known only after it runs would block analysis of everything after it → but marking its output as not-a-constant turns it into a partition boundary → so each surrounding subgraph is analyzed and optimized independently rather than all of it being given up.
Recovered shape relations tame the multi-version code explosion. Generating shape-specialized code for hotspots like convolution explodes when every shape is unknown → but the propagated relations pin the code to the few specific shapes that actually occur → so hotspots get fast specialized versions without a combinatorial blowup.
Doing the derivable work statically avoids the recompilation and over-allocation tax. Existing engines recompile or allocate for the worst case on every input → but SoD2 recovers offline everything the input does not truly determine, deferring only the genuinely dynamic parts → so it sheds those taxes and adds just 3 to 7 percent over a fully-static optimizer.

What it costs (trade-offs and scope)

Genuinely execution-determined shapes still wait for runtime. Operators whose output shape can only be known after materializing their value — like selecting nonzero elements or data-dependent loops and conditionals — get only partial static optimization, so a model dominated by these benefits less than a mostly-shape-dynamic one.
The operator classification is built by hand for a fixed operator set. SoD2 classifies the roughly 150 operators of the ONNX standard; a new operator or a different framework must be classified to be handled, and the authors leave an automatic classification tool to future work.
Some planning still happens at runtime. Memory allocation for the dynamic parts is still performed at execution time; the propagation makes it lightweight and near-optimal, but it is not eliminated.
Multi-version code trades size and tuning cost for speed. Generating several shape-specialized versions increases code size modestly and relies on a genetic-algorithm auto-tuner that adds offline tuning effort.
The wins depend on how statically recoverable a model is. Image models with large memory footprints see the biggest gains; heavily control-flow-dynamic models, where much is only knowable at runtime, benefit less, so the reported 1.7-to-3.9-times range reflects real model-to-model variation.
It is a mobile-focused extension of one framework. SoD2 is built on a specific static-DNN compiler and evaluated on Snapdragon phones across ten models; the approach is general, but the results and the roughly 3-to-7-percent overhead versus the fully-static baseline are for this setting.

The evaluation

Three ways to run a dynamic-shape model on a phone

Property	Recompile per shape (MNN, TFLite)	Runtime shape VM (TVM-Nimble)
How it handles unknown shapes
Fusion of dynamic operators	Limited; needs known shapes	Limited by runtime interpretation
Memory strategy
Dynamic control flow		Run all branches
Result versus SoD2	Recompilation can exceed inference time	Up to 8.6 times more memory, 2.7 times slower

Three ways to run dynamic deep neural networks on mobile, evaluated on ten cutting-edge models (StableDiffusion, SegmentAnything, YOLO-V6, CodeBERT, SkipNet, BlockDrop, and others) on Snapdragon 888 and 835 phones against ONNX Runtime, MNN, TVM-Nimble, and TensorFlow Lite. SoD2 runs 1.7 to 3.9 times faster and uses 27 to 88 percent less peak memory than these frameworks, with its RDP-driven optimizations — fusion, execution planning, memory planning, and multi-version code — responsible for most of the gain, while adding only 3 to 7 percent overhead versus a fully-static optimizer on frozen-shape models.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

SoD2 is a clean compiler idea aimed at a real and growing problem: the optimizations that make neural networks fast all assume static shapes, yet models are increasingly dynamic, and existing mobile engines either recompile per input (often costing more than the inference), over-allocate memory, run every branch, or interpret shapes at runtime. Its insight is that dynamism is a spectrum, not a binary. By classifying each operator’s dynamism degree and propagating ranks and dimensions as known constants, symbolic constants, and expressions, it recovers statically almost everything the optimizations need — fusion, execution and memory planning, shape-specialized code — deferring to runtime only the genuinely unknowable. The results are strong: 1.7 to 3.9 times faster and 27 to 88 percent less peak memory than four production frameworks, with only 3 to 7 percent overhead against a fully-static optimizer. Read it with its scope. Truly execution-determined shapes, like data-dependent selection and loops, still wait for runtime and get only partial optimization; the operator classification is hand-built for ONNX’s set, with automatic classification left to future work; some memory planning remains at runtime; and the gains vary widely by model, with image models gaining most and heavily control-flow-dynamic ones least. The durable lesson is that when a system faces uncertainty, the right move is rarely to give up on static reasoning wholesale, but to find precisely how much can still be known ahead of time and pay the dynamic price only for the remainder.

Background

Why models that change their own computation are the new normal

It helps to see SoD2 against a broad shift in how neural networks are built: away from a fixed pipeline that does the same arithmetic on every input, toward models that adapt what they compute to what they are given. Language models take sequences of wildly different lengths; vision models take images of varying resolution; and a growing class of models decides, per input, which layers or branches to run at all, spending computation only where the input warrants it. This adaptivity is what lets one model serve many devices, input types, and accuracy targets, but it is precisely what defeats a compiler that assumed the work was fixed. The Mixture-of-Experts inference work covered elsewhere on this site is a vivid instance of the same trend, where which expert sub-networks fire is chosen per token, so the model’s actual computation is decided by the input rather than fixed in advance, and the systems challenge becomes serving that data-dependent structure efficiently. The broad lesson is that as models increasingly route, skip, and resize themselves based on their inputs, the systems that run them must move from optimizing a fixed computation to reasoning about a family of possible computations — recovering what structure they can statically, and handling the rest gracefully at runtime.

If you remember only three things

1. The compiler optimizations that make DNNs fast — operator fusion, execution-order planning, and memory allocation — all require knowing tensor shapes before the model runs, but dynamic DNNs make shapes (and sometimes which operators run) depend on the input. Existing mobile engines cope by recompiling when the input shape changes (often costing many times the inference time), allocating worst-case memory (wasteful on a phone), executing all control-flow branches and discarding invalid results, or interpreting shapes at runtime in a virtual machine (per-inference overhead) — all treating a dynamic operator as fully opaque.
2. SoD2 recognizes dynamism is a spectrum. It classifies each of ONNX's ~150 operators into four degrees — output determined by input shapes alone, by input shapes plus some input values, or only knowable after execution — and runs Rank and Dimension Propagation, a forward-and-backward data-flow analysis that threads shapes through the graph as known constants, symbolic constants, and expressions over them (like "L by 512" for an unknown length L). This recovered static knowledge unblocks four optimizations: fusion (one symbolic version instead of a version per shape), static execution planning (partitioning at the unknowable operators and searching each static subgraph), lightweight runtime memory planning (near-optimal, within about 1.05 times of optimal), and shape-specialized multi-version code for hotspots — deferring to runtime only the genuinely execution-determined parts.
3. On ten dynamic models (StableDiffusion, SegmentAnything, YOLO-V6, CodeBERT, SkipNet, BlockDrop, and more) on Snapdragon 888 and 835 phones, SoD2 runs 1.7 to 3.9 times faster and uses 27 to 88 percent less peak memory than ONNX Runtime, MNN, TVM-Nimble, and TensorFlow Lite, adding only 3 to 7 percent overhead versus a fully-static optimizer on frozen-shape models. Its limits: truly execution-determined shapes still wait for runtime with only partial optimization, the operator classification is hand-built for ONNX (automatic classification is future work), some memory planning stays at runtime, multi-version code adds tuning cost, and gains vary by model — image models with large footprints benefit most, heavily control-flow-dynamic models least.

Check yourself

Check your understanding

1. Why do the standard DNN speed optimizations fail on dynamic models?
2. What is the core idea behind SoD2's approach to dynamism?
3. How does SoD2 handle an operator whose output shape genuinely cannot be known until it runs?
4. Which statement best reflects the scope and limits of SoD2?

Sources

The paper is “SoD2: Statically Optimizing Dynamic Deep Neural Network Execution” by Wei Niu, Gagan Agrawal, and Bin Ren, published at ASPLOS 2024, DOI 10.1145/3617232.3624869. The authors are at the University of Georgia and William and Mary.

This explainer is written from the full 15-page text. Everything above comes from the paper’s own sections: the introduction and existing-frameworks discussion establishing that static optimizations need known shapes and that current engines handle dynamism by re-initialization (measured taking many times the inference time), conservative maximum allocation, running all control-flow branches, or runtime shape functions in a virtual machine; the operator classification into four dynamism degrees (Input Shape Determined Output, Input Shape Determined Output Shape, Input Shape and Value Determined Output Shape, and Execution Determined Output) over the roughly 150 ONNX operators with their forward and backward transfer functions; the Rank and Dimension Propagation data-flow analysis carrying known constants, symbolic constants, op-inferred constants, and not-a-constant through the graph; the four RDP-enabled optimizations — operator fusion generating a single symbolic version rather than exponentially many, static execution planning via graph partitioning at not-a-constant operators, runtime memory allocation planning that lands within about 1.05 times of optimal (versus 1.16 times for a greedy baseline), and shape-specialized multi-version code with a genetic-algorithm auto-tuner; and the evaluation on ten dynamic models across Snapdragon 888 and 835 phones against ONNX Runtime, MNN, TVM-Nimble, and TensorFlow Lite, reporting 1.7-to-3.9-times speedups, 27-to-88-percent memory savings, geometric-mean memory ratios of 3.64, 1.37, and 8.62 times for the baselines, the optimization breakdown, and the 3-to-7-percent overhead versus the static DNNFusion baseline on frozen models.