Optimizing Dynamic Computational Graphs for Machine Learning

This direction is split into other directions: stochastic control flow. Its last version stays readable and citable here.

Version 1 of 1183 papers202 conceptsfrozen 2026-10-04

Most high-performance machine learning systems are built on a convenient lie: that the structure of a program is known before it begins. This "static graph" assumption allows compilers to pre-calculate memory layouts, fuse operations, and schedule tasks across GPUs with surgical precision. However, as we move toward autonomous agents, recursive models, and Mixture-of-Experts (MoE) architectures, this assumption is crumbling.

The research direction emerging across these papers focuses on bridging the gap between the flexibility of eager execution (where code runs line-by-line) and the efficiency of static optimization (where the whole program is optimized at once).

The Static Graph Assumption and Its Limits

In traditional deep learning, a model is a Directed Acyclic Graph (DAG). Because the graph is fixed, systems like Checkmate by Ajay Jain can use Mixed Integer Linear Programming (MILP) to find the mathematically optimal way to trade computation for memory. Similarly, MODeL uses ILP to perfectly pack tensors into memory before execution starts.

But modern applications break this. Ravi Teja Mullapudi and colleagues note in HydraNets that routing inputs through specialized "branches" creates conditional execution paths that standard frameworks struggle to handle efficiently. When the execution path depends on the data—such as a loop that runs until a model reaches a confidence threshold—static compilers like Elk or Graphi cannot pre-allocate resources because they don't know which path the data will take.

From Offline Planning to Online Adaptation

To solve this, researchers are moving optimization from the "compile-time" phase to the "runtime" phase. Instead of a fixed plan, the system makes greedy, intelligent decisions as the program unfolds.

A prime example is Dynamic Tensor Rematerialization (DTR). While Checkmate requires a static graph to plan which tensors to delete and recompute, Altan Haan and Tianqi Chen developed DTR as a greedy online algorithm. It monitors memory pressure in real-time and chooses which tensors to evict based on their recomputation cost and staleness, allowing it to support models with dynamic control flow that static methods cannot touch.

This shift to online adaptation extends to hardware. AWB-GCN, developed by Tong Geng and Ang Li, tackles the unpredictability of Graph Convolutional Networks. Because the connectivity of a graph is only known at runtime, they implemented hardware autotuning that rebalances workloads across processing elements on-the-fly, rather than relying on a static schedule.

Bridging the Programmability Gap

Researchers are also trying to give users the best of both worlds: the ease of Python-style imperative programming with the speed of symbolic graphs. JANUS by Joo Seong Jeong uses speculative optimization to transparently convert dynamic code into optimized dataflow graphs. If the speculation fails (e.g., a branch goes a different way than expected), the system falls back to a safe execution mode.

In the realm of Large Language Models (LLMs), SGLang by Lianmin Zheng introduces a way to handle structured programs where the execution path is determined by the model's own output. By using a "RadixAttention" mechanism to manage the KV cache across dynamic branches, it achieves massive throughput gains that traditional static inference engines cannot provide.

The Challenge of Irregularity and Scale

As we scale to "ultra-large" models, the problem of device placement—deciding which GPU handles which operation—becomes a moving target. Yanqi Zhou and the authors of GDP point out that while reinforcement learning can find good placements for static graphs, these methods struggle when the graph structure evolves.

Even at the hardware level, the "irregularity tax" of dynamic graphs is a major bottleneck. The DPU (DAG Processing Unit) by Nimish Shah is a specialized processor designed specifically for these irregular, sparse graphs. It uses asynchronous compute units and hardware-level synchronization to handle dependencies that change during execution, moving away from the rigid, bulk-synchronous models of standard GPUs.

Conclusion

The transition from static to dynamic computational graphs represents a fundamental shift in how we think about machine learning infrastructure. Whether it's Division-of-Thoughts dynamically re-planning sub-tasks between local and cloud models, or Fluid relaxing dependencies for "approximate concurrency," the goal is the same: systems that are as flexible as the algorithms they run, without sacrificing the performance that makes modern AI possible.

Papers in this version

Showing 60 of 183 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_optimizing_dynamic_computational_graphs__6218857f,
  title = {Optimizing Dynamic Computational Graphs for Machine Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimizing-dynamic-computational-graphs-for-machine-learning/rdr_6218857ffa6f4bfc925aab5092e0d459},
  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_optimizing_dynamic_computational_graphs__6218857f_v1,
  title = {Optimizing Dynamic Computational Graphs for Machine Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimizing-dynamic-computational-graphs-for-machine-learning/rdr_6218857ffa6f4bfc925aab5092e0d459/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}