How Far From Series-Parallel Are Neural Network Graphs, and Does It Matter for Peak Memory?

Every time a deep learning framework runs a model, it has to pick an order in which to execute the operations of the model's computation graph. This is a directed acyclic graph (DAG) whose nodes are tensor operations and whose edges carry intermediate tensors. The order matters for memory. A tensor occupies memory from the moment it is produced until its last consumer runs, so two valid orders of the same graph can differ sharply in peak memory. Peak memory, more than arithmetic, often decides whether a model fits on an accelerator.

Choosing the memory-minimizing order is NP-hard in general. There is, however, a clean exception. New Tools for Peak Memory Scheduling shows the problem becomes fixed-parameter tractable on series-parallel graphs. Fixed-parameter tractable means solvable in time exponential only in a small structural number, here the maximum out-degree $d$, and polynomial in graph size. Series-parallel graphs are graphs built purely by chaining blocks in sequence and placing blocks side by side between a shared split and merge.

Many real models are series-parallel, or almost so. A ResNet residual block, a transformer's residual add, and the shared input to query, key and value projections all nest cleanly. What breaks the structure is a small number of "long-range" edges: an encoder output read by every decoder layer, DenseNet concatenations, some tensors reused in backward passes. This proposal asks whether the cost of exact scheduling grows with how many such violating edges a graph has rather than with its size. It then measures whether real graphs have few enough of them for the answer to matter.

Core Claim

We conjecture that peak-memory scheduling in the node-sum model of Jin et al. is fixed-parameter tractable in the combined parameter $(d, k)$. Here $k$ is the minimum number of edges whose removal leaves a series-parallel graph. The target running time is

$$ 2^{O(d\log d \,+\, k\log k)}\cdot \mathrm{poly}(n), $$

where $n$ is the number of operations. The $d\log d$ term is inherited from the series-parallel algorithm. The $k\log k$ term comes from enumerating the relative orderings of the $2k$ birth and death points of the long-range tensors.

The second, empirical half of the claim is that across a broad model suite, training and inference graphs have small $k$ after standard preprocessing. If both halves hold, exact peak-memory schedules become computable for most of the graphs that compilers actually see.

If the conjecture fails, we expect to prove W[1]-hardness in $k$, meaning no algorithm of this form exists under standard assumptions. That would itself tell compiler writers that long-range edges, not graph size, are where heuristics must take over.

Why This Gap and Not a Neighbouring One

The research file lists several bridges between parameterized complexity and deep learning systems. Two of them leave openings that motivate this work.

New Tools for Peak Memory Scheduling supplies the method and the motivation. Its key results are these:

  • Every DAG has a dominant schedule, one that uses no more memory than any other schedule at every step.
  • Isolated subgraphs can be replaced by a single path representing their dominant schedule, a step the paper calls linearization.
  • These two ideas yield the $2^{O(d\log d)}\mathrm{poly}(n)$ algorithm for series-parallel graphs.
  • The problem stays strongly NP-complete even on out-trees and on pumpkin graphs (chains of parallel paths).

The paper offers nothing for graphs that are merely close to series-parallel, which is the case that matters in practice.

The other bridges point elsewhere. Parallel Scheduling of DAGs under Memory Constraints computes the worst memory over all orders in polynomial time, as a maximum topological cut, and adds dependency edges to cap it. That problem is related but different: it bounds the risk of a parallel runtime scheduler rather than finding the best sequential order. Streaming Task Graph Scheduling for Dataflow Architectures targets latency on spatial hardware and does not touch peak memory.

The parameterized complexity literature constrains the design. It repeatedly shows that tractability is fragile: a single added edge flips Shallow-Light Steiner Network from tractable to W[1]-hard in Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network, and moving from claw-free to $K_{1,4}$-free graphs makes Dominating Set W[2]-hard in Dominating Set is Fixed Parameter Tractable in Claw-free Graphs. We therefore treat hardness in $k$ as a live outcome, not a formality.

Finally, Tight Running Time Lower Bounds for Vertex Deletion Problems proves that deleting vertices to reach a hereditary property cannot be done in $2^{o(n)}$ time under the Exponential Time Hypothesis. This warns us that computing $k$ exactly could be expensive. For two-terminal series-parallel recognition, however, we expect near-SP inputs to be handled by decomposition-based search bounded in $k$. If that fails, we will fall back to the approximate $k$ that a greedy reduction yields; the bound degrades but the algorithm stays correct.

Research Program

Step 1: a structural census. We extract forward and forward-plus-backward graphs from the 84 models of TorchBench: Benchmarking PyTorch with High API Surface Coverage. We also use the ResNet-50 graph (over 54,000 nodes) and the transformer encoder graph (about 5,000 nodes) from the dataflow study above. For each graph we measure three things:

  • the maximum out-degree $d$;
  • the edge distance $k$ to series-parallel, found by repeatedly applying series and parallel reductions and recording which edges block them;
  • where the blocking edges sit in the model architecture.

This census is a contribution even if the algorithm stalls. It replaces the folk belief that "networks are nearly series-parallel" with a measured distribution.

One preprocessing choice matters a great deal. Very high out-degree nodes, such as a weight tensor broadcast to many uses, can be split into small fan-out trees at no memory cost in the node-sum model. We will report $d$ before and after this splitting, because it decides whether the $d\log d$ term is benign.

Step 2: the algorithm. Removing the $k$ violating edges leaves a series-parallel skeleton. Each violating edge $u\to v$ corresponds to a tensor that is live from the execution of $u$ to the execution of $v$. It adds a constant memory offset over an interval whose endpoints lie inside particular branches of the skeleton's decomposition tree.

Our approach handles the skeleton in two parts:

  • Every decomposition subtree containing no endpoint is linearized by its dominant schedule, exactly as Jin et al. do.
  • Subtrees containing endpoints are merged by enumerating the interleaving of the at most $2k$ endpoints. Each enumerated interleaving reduces to a series-parallel instance with fixed offsets.

The technical risk is whether dominance survives these offsets. An offset that is active on only part of a parallel merge could make the dominant interleaving of two branches depend on where the offset starts. We will either prove that a bounded number of candidate merges suffices, or turn the failure into a W[1]-hardness reduction from a multicoloured clique-type problem in which each violating edge encodes one colour choice.

Step 3: recomputation. Production systems also trade memory for compute by recomputing some activations instead of storing them. We extend the model to allow this only after Step 2 is settled. The question there is whether the same $k$-parameterized structure survives.

Baselines

The naive reference point is the framework's default execution order: PyTorch eager program order and the topological order the compiler emits. Every method is scored on peak memory under the identical node-sum accounting applied to that same graph. This baseline answers whether any of the effort is worth it on real models. Beating it means a reduction in peak memory on a meaningful fraction of models, not on average alone.

The strongest exact competitor is a generic integer linear programming formulation of peak-memory scheduling. It follows the ILP style that Parallel Scheduling of DAGs under Memory Constraints uses for small graphs, run with a modern commercial or open solver. It is the strongest competitor because it is exact when it finishes and needs no structural theory. We give it the same wall-clock budget per graph as our algorithm, on the same machine, and report the solve time, the best schedule found, and the optimality gap at timeout. Our method beats it if it returns certified optima on graphs where the solver times out or leaves a gap, and matches it wherever both finish. No reported result found on Lacuna for exact or ILP peak-memory scheduling on TorchBench, ResNet-50 or transformer computation graphs, so this baseline is run by us rather than quoted.

The strongest heuristic competitor is a greedy memory-aware list scheduler that always runs the ready operation with the smallest net memory increase. We also include the RespectOrder idea from Marchal et al., adapted to sequential order. Both get the same graphs and no tuning advantage.

The key ablation isolates the handling of long-range edges. We delete the $k$ violating edges, run Jin et al.'s series-parallel algorithm on the skeleton, and then repair the schedule by charging each long-range tensor at its forced interval. If this "SP-ify and repair" variant matches our algorithm, the enumeration machinery adds nothing and the contribution reduces to the census.

Why not just…?

Why not just use the greedy memory-aware heuristic? On graphs that are cleanly series-parallel, greedy may well be near-optimal, and we expect it to be. The evidence against relying on it everywhere is indirect. Jin et al. prove NP-completeness already on out-trees and pumpkin graphs, so no polynomial greedy rule can be optimal on every instance. TorchBench reports that compiled models can use over 5x the memory of eager mode. That bloat comes partly from buffer and fusion decisions rather than ordering, so we do not claim scheduling explains it. The census will show directly how often greedy is suboptimal and by how much, broken down by $k$. If the gap is negligible at every observed $k$, we will say so.

Why not just hand the graph to an integer programming solver? This is the real threat. Solvers routinely handle thousands of variables, and the transformer encoder graph has about 5,000 nodes. Our answer is empirical, not rhetorical. The baseline comparison above measures where the solver stops certifying optimality as graph size and $k$ grow, with ResNet-50's 54,000 nodes as the stress case. If the solver certifies optima on the full suite within budget, the algorithmic contribution becomes theoretical only. The proposal would then reposition around the census and around the hardness boundary as an explanation of solver behaviour.

Why not just rely on activation recomputation? Recomputation changes the trade-off rather than removing it. A recomputed schedule still has an execution order whose peak memory depends on the graph structure, and it is typically planned on top of an ordering. We address this in Step 3 rather than claiming orthogonality. Until then, results are scoped to the no-recomputation setting that Jin et al. also assume, and we say so.

Proposed Experiments

The first decisive check is the census distribution of $k$ and post-splitting $d$ across the TorchBench graphs and the two DaCeML graphs. The project's practical value hinges on most graphs having $k$ in the single or low double digits. Synthetic DAGGEN graphs from Marchal et al. serve as a control in which $k$ is large by construction.

The second check compares peak memory and solve time across our algorithm, the ILP, greedy, and the SP-ify-and-repair ablation. We plot the gap to the best certified optimum against $k$. The proposal's prediction is specific: the ablation's gap should grow with $k$ while ours stays at zero, and the ILP's solve time should grow with $n$ while ours grows mainly with $k$. If the ablation's gap stays at zero, or ILP time is flat in $n$, the core claim is wrong in practice.

The third check is theoretical: a proof of the running-time bound, or a W[1]-hardness reduction parameterized by $k$. Either outcome settles the open question that Jin et al. leave behind.