Minimizing Peak Memory via Computation Graph Scheduling

18 concepts10 papers1 proposal

When executing a deep neural network, we typically think about optimizing for speed or accuracy. However, hardware constraints—ranging from microcontrollers with kilobytes of RAM to GPUs training multi-billion parameter models—frequently turn memory capacity into the primary bottleneck.

To manage this, a powerful insight has emerged: a neural network is a Directed Acyclic Graph (DAG) of mathematical operations, and the order in which we choose to execute these operations dictates how much memory the network consumes at any given moment. By intelligently scheduling the execution sequence, we can drastically reduce the peak resident memory footprint without altering the model's weights or architecture.

The Intuition: Lifecycles of Tensors

To understand why execution order matters, consider a neural network with two independent, parallel branches that eventually merge.

    [Input]
    /     \
[Op A1]  [Op B1]
   |        |
[Op A2]  [Op B2]
    \     /
   [Merge]

If an execution engine interleaves the operations—running Op A1, then Op B1, then Op A2, then Op B2—it must simultaneously hold the intermediate activations of both Branch A and Branch B in memory.

Conversely, if the engine executes Branch A completely (Op A1 $\rightarrow$ Op A2) before starting Branch B, the memory allocated for Branch A's intermediate tensors can be reclaimed or overwritten before Branch B even begins. As noted by Gagrani et al., executing operations in a suboptimal sequence leads to excessive peak memory usage because it forces too many intermediate tensors to coexist.

By analyzing the dataflow graph, compilers can prioritize operations that allow large data buffers to be released early. Steiner et al. demonstrated that strategically reordering independent operations can reduce the peak resident memory set by nearly 40%. This scheduling flexibility is particularly vital for irregularly wired networks where execution paths are non-trivial, as highlighted by Hou et al.. Optimizing this sequence allows complex models to fit into highly constrained environments, such as commodity microcontrollers, without sacrificing performance (Liberis et al.).

Algorithmic Frameworks for Graph Scheduling

Finding the absolute optimal execution order is a complex combinatorial problem. Researchers have framed the search for the ideal topological sort using several distinct mathematical paradigms:

  • Minimax Optimization: Huang et al. model neural network execution as a pathfinding problem on a DAG, framing memory minimization as a minimax problem. The goal is to discover an execution path that minimizes the maximum memory peak encountered at any single stage of the computation.
  • Dynamic Programming: To handle the chaotic search space of irregular architectures, Hou et al. utilize dynamic programming. By identifying and memoizing repeated subproblems within the graph topology, they make the optimal scheduling search computationally tractable.
  • Pebble Games and Lifecycles: Zhao et al. employ a "pebble-game" heuristic to track the lifecycle of data blocks across the entire graph. This global view allows the system to map out exact reuse strategies between completely unrelated nodes.
  • Integer Linear Programming (ILP): Steiner et al. formulate tensor scheduling and memory allocation as a joint ILP problem, mathematically proving an optimal layout for packing data into physical memory.
  • Predictive Graph Neural Networks: Because traditional optimization techniques can be slow, Gagrani et al. introduced a non-autoregressive, transformer-based Graph Neural Network (GNN) called Topoformer. The GNN learns to predict high-quality topological orderings thousands of times faster than standard solvers.

Graph-Aware Memory Allocation

Determining the optimal execution schedule is only half the solution; the underlying runtime system must be able to act on it. General-purpose memory allocators (like standard OS or GPU allocators) are unaware of the neural network's structure, leading to fragmentation and delayed memory reclamation (Fang et al.).

Because a static execution schedule makes the lifecycle of every tensor completely deterministic, a graph-aware memory allocator can pre-calculate exactly when a buffer becomes obsolete. As shown by Fang et al., the system can reclaim and reuse memory chunks immediately after their last use in the computation graph, safely reassigning the same physical memory address to an unrelated future operation.

Time Step:    1   2   3   4   5
Tensor X:    [=======]
Tensor Y:            [===========]  <-- Reuses same memory space

To eliminate allocation overhead entirely, frameworks often use a pointer-reset or pre-allocated workspace strategy. Instead of invoking dynamic allocation during execution, Neubig et al. demonstrate that frameworks can pre-allocate large memory blocks at initialization and manage them via fast integer pointer arithmetic.

Similarly, Xu et al. utilize dedicated, pre-allocated buffers for forward and backward passes. This deterministic management guarantees that large tensors are handled without triggering out-of-memory errors caused by fragmented free space.

When models grow so large that they exceed physical memory capacity entirely, these static schedules can be extended to coordinate out-of-core memory scheduling, swapping tensors to CPU RAM or triggering redundant recomputations (Wahib et al.).

Key Foundational Work

Ordering Chaos: Memory-Aware Scheduling of Irregularly Wired Neural Networks for Edge Devices (2020) — contributed 5 concept elements to this direction.
TurboTransformers: An Efficient GPU Serving System For Transformer Models (2020) — contributed 3 concept elements to this direction.
μNAS: Constrained Neural Architecture Search for Microcontrollers (2020) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_execution_order_optimization_0e56ba40,
  title = {execution order optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/execution-order-optimization/rdr_0e56ba406f314533bf8e56e89c9b8295},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_execution_order_optimization_0e56ba40_v1,
  title = {execution order optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/execution-order-optimization/rdr_0e56ba406f314533bf8e56e89c9b8295/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake