Compiling Deep Learning with Dynamic Control Flow

125 concepts92 papers1 proposal

Deep learning frameworks traditionally operate under a silent agreement: the computation graph should be a static blueprint. In frameworks like early TensorFlow or TVM, a developer defines the network structure once, allowing an ahead-of-time (AOT) compiler to perform global optimizations. The compiler can fuse mathematical operators to minimize memory roundtrips, plan exact tensor lifetimes to optimize GPU memory layout, and schedule parallel execution streams across hardware.

However, modern AI applications increasingly break this blueprint. When processing data with irregular topologies—such as parse trees, molecular graphs, or variable-length text sequences—the execution path must adapt dynamically to each input. As Seiya Tokui et al. describe in Chainer: A Deep Learning Framework for Accelerating the Research Cycle, this requirement led to the rise of "Define-by-Run" frameworks like PyTorch and DyNet: The Dynamic Neural Network Toolkit (developed by Graham Neubig et al.), which rebuild the computation graph from scratch for every forward pass. While this imperative style offers immense developer flexibility, it introduces a massive performance penalty: because the graph changes constantly, global compiler optimizations become exceptionally difficult to apply.

Why Dynamic Control Flow Paralyzes Compilers

To understand why data-dependent branching, stochastic loops, and variable tensor shapes paralyze traditional deep learning compilers, we must look at how optimization pipelines are constructed.

Operator Fusion

Compilers achieve peak hardware efficiency by merging adjacent operations (such as a matrix multiplication followed by an element-wise activation function) into a single execution kernel. As Wei Niu et al. point out in DNNFusion: Accelerating Deep Neural Networks Execution with Advanced Operator Fusion and Haichen Shen et al. discuss in Nimble: Efficiently Compiling Dynamic Neural Networks for Model Inference, these advanced fusion strategies rely on knowing exact tensor shapes and execution sequences at compile time. When a model introduces conditional control flow or variable sequence lengths, the compiler cannot guarantee memory layouts, causing fusion optimizations to fail or forcing costly runtime re-compilation.

Memory Allocation and Rematerialization

In static graphs, memory managers can use Integer Linear Programming (ILP) to perfectly pack tensors into hardware memory based on fixed lifetimes, as seen in the work by Benoit Steiner et al. on MODeL: Memory Optimizations for Deep Learning. But when execution paths branch unpredictably, tensor lifetimes become non-deterministic. As Xunyi Zhao et al. observe in Rockmate: an Efficient, Fast, Automatic and Generic Tool for Re-materialization in PyTorch, standard static graph tracing fails entirely when encountering dynamic control flow, making offline memory planning or hierarchical re-materialization schedules impossible to compute ahead of time.

Scheduling and Hardware Placement

Optimizing how operations are distributed across heterogeneous hardware (like CPU-GPU boundaries or multi-stream GPU queues) typically assumes a fixed sequence of operations. Woosuk Kwon et al. demonstrate in Nimble: Lightweight and Parallel GPU Task Scheduling for Deep Learning that ahead-of-time scheduling dramatically accelerates inference, but fails when input-dependent paths alter the workload at runtime. Similarly, automated device placement systems, such as the reinforcement learning approach proposed by Azalia Mirhoseini in Device Placement Optimization with Reinforcement Learning, struggle to find optimal configurations when the underlying graph topology shifts dynamically.

Mechanisms for Bridging the Gap

The core of this research direction focuses on resolving this fundamental mismatch. How can we preserve the performance of static graph compilers while supporting the messy reality of dynamic control flow? Several key architectural patterns have emerged to bridge the gap.

In-Graph Control Flow and Specialized Virtual Machines

Rather than handling loops and conditionals on the CPU host side (which causes frequent stalls and prevents global optimization), systems can embed control logic directly into the distributed dataflow graph. Yuan Yu pioneered this by moving control logic "in-graph" within Dynamic Control Flow in Large-Scale Machine Learning, allowing distributed clusters to manage loops and conditionals natively. Alternatively, compilers introduce dynamic type systems and specialized virtual machines designed to interpret variable shapes and control paths without triggering expensive re-compilation cycles.

Dynamic Batching

When inputs have completely different structures (such as varying logical expressions or parse trees), batching them together for hardware acceleration is notoriously difficult. The authors of Deep Learning with Dynamic Computation Graphs solved this via dynamic batching.

Individual Irregular Inputs:
Input 1: (A + B) * C
Input 2: D * (E + F + G)

Dynamic Batching Execution Plan:
Step 1: Batch all '+' operations -> [A+B, E+F]
Step 2: Batch subsequent '+'     -> [Result_EF + G]
Step 3: Batch all '*' operations -> [Result_AB * C, D * Result_EFG]

This technique takes individual, irregular input graphs and automatically groups identical operations across different graphs into a single, unified static execution plan at runtime, achieving massive speedups without forcing developers to manually unroll or pad their data.

Multi-Stage Programming and Continuation-Passing Style

To avoid the overhead of maintaining an execution "tape" or "trace" during backpropagation, researchers have turned to programming language theory. Fei Wang 0046 et al. demonstrated in Backpropagation with Callbacks: Foundations for Efficient and Expressive Differentiable Programming that by using Continuation-Passing Style (CPS) and multi-stage programming, compilers can generate highly optimized, low-level automatic differentiation code directly from standard imperative source code. This eliminates the need for auxiliary data structures while natively supporting data-dependent structures like recursive neural networks.

Hybrid Imperative-Symbolic Co-Execution

Another powerful approach is to decouple the dynamic control flow from the heavy tensor computations. For instance, Terra, developed by Taebum Kim et al. in Terra: Imperative-Symbolic Co-Execution of Imperative Deep Learning Programs, runs a lightweight imperative Python "skeleton" to handle complex language features and mutations, while offloading the core mathematical execution to an optimized symbolic graph backend. Similarly, Cavs: An Efficient Runtime System for Dynamic Neural Networks, introduced by Shizhen Xu et al., separates static computation logic from the dynamic input graph to bypass the bottlenecks of traditional dynamic frameworks.

Beyond Standard Neural Networks

The challenge of dynamic control flow extends far beyond standard deep learning architectures into probabilistic programming and modern generative inference.

In Deep Probabilistic Programming Languages (PPLs), the execution path itself is often determined by the realization of random variables at runtime. As Dustin Tran et al. note in Deep Probabilistic Programming, static computational graphs create severe efficiency bottlenecks when handling these stochastic loops and complex recursions. To scale these models, compilers must adapt to non-deterministic reasoning paths, a challenge highlighted by Tony Chen et al. in A Domain-Specific Probabilistic Programming Language for Reasoning About Reasoning (or: a memo on memo) when compiling recursive probabilistic models for multi-agent reasoning.

Furthermore, modern Large Language Model (LLM) optimizations face similar hurdles. Speculative decoding algorithms generate irregular and unpredictable guess trees during generation. As Yue Guan et al. demonstrate in Yggdrasil: Bridging Dynamic Speculation and Static Runtime for Latency-Optimal Tree-Based LLM Decoding, bridging the gap between these dynamic drafting trees and static hardware runtimes requires specialized co-designed systems that can handle structural volatility without sacrificing kernel tuning.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_stochastic_control_flow_12e207d5,
  title = {stochastic control flow},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-control-flow/rdr_12e207d5531c4d21821890f1104567c8},
  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_stochastic_control_flow_12e207d5_v1,
  title = {stochastic control flow},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-control-flow/rdr_12e207d5531c4d21821890f1104567c8/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