Early deep learning optimization frameworks operated under a convenient illusion: they treated neural networks as a simple, sequential chain of layers. In this one-dimensional world, tasks like memory allocation, layer fusion, and pipeline parallelization are straightforward. If you want to split a network across two GPUs or decide where to drop and recompute activations to save memory, you simply pick a single cut point in the chain. This point acts as a perfect separator—everything before it belongs to the past, and everything after it belongs to the future.
However, modern architectures—ranging from residual networks and multi-scale U-Nets to multi-branch transformers—are fundamentally non-linear directed acyclic graphs (DAGs). They feature long-range skip connections, parallel processing branches, and complex data flows. As noted by Zhao et al., traditional optimization frameworks that rely on decomposing a model into a linear sequence of blocks cannot effectively process these arbitrary, non-sequential topologies. When an optimization algorithm assumes a chain but encounters a complex graph, its underlying mathematical assumptions break down.
Why Graph Topologies Break Classical Optimization
To understand why non-linear topologies disrupt standard optimization, consider the problem of activation re-materialization (or checkpointing). During the backward pass of training, an accelerator needs the forward activations to compute gradients. Storing every single intermediate tensor causes models to hit a "memory wall." A sequential re-materialization algorithm solves this by saving activations at a few "checkpoint" layers and discarding the rest, recomputing them on the fly when needed.
In a linear chain, clearing an activation means you only need to recompute it from the nearest upstream checkpoint. But in a graph with a long skip connection that bypasses multiple layers, a single cut no longer isolates the upstream and downstream execution flows. The skip connection carries data from far upstream directly to a downstream merge point, bypassing the intermediate layers entirely.
Linear Chain:
[Layer 1] -> [Layer 2] -> [Layer 3] -> [Layer 4]
^ Perfect Separator Cut
Non-Linear Graph (Skip Connection):
+---------------------------------------+
| v
[Layer 1] -> [Layer 2] -> [Layer 3] -> [Layer 4]
^ Cut intersects the skip path!
If you place a checkpoint inside those intermediate layers, the framework must still hold the skip connection's tensor in memory for a long duration. To recompute a single node, you might accidentally trigger the recomputation of multiple parallel branches, or you might be forced to store multiple overlapping tensors. This topological complexity introduces severe challenges across the entire systems lifecycle:
- Memory Management: As Gusak et al. observe, the absence of automated, provably optimal strategies for non-linear topologies forces practitioners to rely on manual tuning and brittle heuristics for modern architectures.
- Pipeline Parallelism: Slicing a model across multiple accelerators becomes highly irregular. Jhoo et al. point out that existing distributed frameworks struggle to trace and partition non-sequential data-flow graphs effectively without incurring massive communication overhead.
- Hardware Compilation and Fusion: Compilers that optimize execution by fusing adjacent layers struggle when data flows iteratively or non-linearly between different components, leading to idle hardware periods or "bubbles" (Liu et al.; Lin et al.).
Formalizing Optimization over Arbitrary DAGs
To solve these problems, researchers have shifted from 1D sequential heuristics to generalized graph-theoretic frameworks. The core idea is to redefine how we traverse, partition, and schedule the computational graph by leveraging the mathematical properties of DAGs.
Topological Lower Sets
Instead of viewing the network as a sequence of layers, the problem can be modeled using the concept of topological lower sets. A lower set is a subset of nodes in a graph where, if a node is included, all of its upstream predecessor nodes must also be included.
Kusumoto et al. formulated the recomputation problem as finding an optimal sequence of lower sets within the execution graph. Because lower sets inherently respect the dependency structure of the graph—regardless of how many skip connections or parallel branches exist—performing dynamic programming over these sets guarantees an optimal memory-computation trade-off for any arbitrary network architecture.
Hierarchical Graph Partitioning
When graphs scale to thousands of nodes, searching for the optimal execution path over all possible lower sets faces a combinatorial explosion. To make this practical, recent frameworks introduce hierarchical decomposition.
Gusak et al. developed a hierarchical approach that recursively partitions massive, irregular computation graphs (like U-Nets) into isolated sub-blocks. By isolating these sub-blocks, the framework can use Integer Linear Programming (ILP) to find mathematically optimal re-materialization schedules within each block locally, scaling to massive networks while maintaining strict bounds on memory and computational overhead.
Topological Slicing for Distributed Execution
The challenge of non-sequentiality is equally acute when distributing a model across multiple hardware units. In classical pipeline parallelism, a linear model is cut into sequential stages, with each stage assigned to a different GPU. In a branched or multi-modal network, a naive cut can result in massive communication overhead if a branch crosses the partition boundary multiple times.
To overcome this, modern distributed frameworks co-optimize graph tracing, partitioning, and scheduling:
- Balanced Graph Sharding: Rather than slicing layers blindly, frameworks like the one proposed by Luo et al. map irregular DAGs with multiple branches into balanced execution stages. This global graph awareness eliminates the idle hardware bubbles that typically plague non-linear distributed training.
- Macro-Topology Heuristics: To avoid the high computational cost of running exact mathematical solvers during compilation, the authors of DiviML leverage a module-based splitting heuristic. By exploiting the inherent macro-topology (the natural boundaries of large structural blocks) of modern networks, they rapidly map irregular structures onto heterogeneous hardware platforms with minimal latency.
Rethinking the Architectural Paradigm
Beyond optimizing existing models, recognizing the limitations of sequential architectures opens up new ways to design and conceptualize neural networks. If optimization frameworks can natively handle complex topologies, we can move away from rigid layer-by-layer feed-forward structures entirely.
For example, Lamb introduces Neural Function Modules (NFMs), which treat layers like functions taking sparse arguments via attention, enabling dynamic bottom-up and top-down feedback loops that bypass linear constraints. On the mathematical front, Vera explores collapsing sequential operations into a single associative operation using conformal geometry, though extending this mathematical collapse to non-sequential branching paths remains an active frontier.
Ultimately, moving past the sequential constraint allows deep learning systems to match the structural complexity of the problems they are trying to solve, ensuring that hardware efficiency keeps pace with architectural innovation.
Key Foundational Work
NeuralPower: Predict and Deploy Energy-Efficient Convolutional Neural Networks (2017) — contributed 1 concept elements to this direction.
Convolutional neural networks at constrained time cost (2015) — contributed 1 concept elements to this direction.