Introduction
Most traditional deep learning frameworks rely on static computation graphs. This architecture works perfectly for data that fits into neat, uniform tensors—such as images or fixed-length sequences—allowing the framework to batch multiple inputs together for massive parallelization on GPUs.
However, many real-world problems involve Dynamic Computation Graphs (DCGs). For example, in natural language processing, sentences are often represented as parse trees of varying depths and branching factors. In chemistry, molecules are represented as graphs where every input has a unique arrangement of atoms and bonds. In these cases, every single input requires a different computation graph. Traditionally, researchers had to either process inputs one by one (which is painfully slow) or manually engineer complex workarounds to force-fit these structures into batches.
This paper introduces dynamic batching, a technique that allows deep learning models to handle inputs with varying structures as efficiently as standard fixed-size inputs. By automatically grouping similar operations across different irregular graphs into a single static execution plan, the authors achieve up to a 160x speedup over unbatched implementations and provide a high-level library, TensorFlow Fold, to make these complex models much easier to write.
Methodology
The authors propose a two-part solution to tackle the inefficiencies of DCGs: an algorithm for dynamic batching and a functional library called TensorFlow Fold.
The Dynamic Batching Algorithm
Instead of building a new graph for every input, the algorithm takes a collection of individual computation graphs and rewrites them into a single, batched execution schedule. This involves several key steps:
- Depth Assignment: It assigns a "depth" to every node in the input graphs based on its dependencies.
- Operation Grouping: It identifies all instances of the same operation (e.g., an LSTM cell or an embedding lookup) occurring at the same depth across all input graphs in the batch.
- Static Emulation: It uses a static "master graph" containing a loop. In each iteration (representing one depth level), it executes all batched operations of the same type.
- Data Routing: It uses
gatherandconcatoperations to move data between the batched operations, effectively "wiring" the dynamic connections on the fly.
TensorFlow Fold
To make this dynamic batching usable, the authors built a library of combinators—high-level building blocks inspired by functional programming (like Map, Fold, and Reduce). This allows developers to define recursive models (like a Tree-LSTM) compositionally without worrying about the underlying batching logic. By using functional combinators, the authors significantly reduced boilerplate code, making it easier for researchers to iterate on model architectures rather than debugging low-level tensor shapes.
Experiments and Results
The authors evaluated their approach using synthetic benchmarks (randomly generated binary trees) to measure raw throughput, the Stanford Sentiment Treebank (SST) to test Tree-LSTMs on NLP parse trees, and molecular graphs to demonstrate Graph Convolutions for chemical compound screening.
Key Findings
- Massive Speedups: On a GPU, dynamic batching was over 160x faster than unbatched execution for large trees. Even compared to perfectly hand-optimized manual batching (which is only possible if all trees have the exact same shape), the overhead of dynamic batching was relatively small.
- Code Conciseness: Models implemented with TensorFlow Fold were significantly shorter than their original counterparts. For example, a Tree-LSTM implementation was reduced from 219 lines of code to just 119 (a 46% reduction).
- State-of-the-Art Performance: The Tree-LSTM implemented via Fold achieved a new state-of-the-art result on the Stanford Sentiment Treebank at the time (53.6% fine-grained accuracy). This was largely because the library made it easy to experiment with and ensemble different model variants.
Core Insights
A major takeaway from this work is that batching is not just "between" inputs. Dynamic batching can group operations from different nodes within the same input graph as well as across different graphs. Furthermore, the success of this method proves that you don't need a natively dynamic framework to run dynamic models; by using a loop and clever indexing, a static graph can act as a universal engine for any graph structure.
Limitations and Future Work
While highly effective, the approach has limitations. The concat and gather operations required to route data between operations incur overhead. The authors noted a "cost ratio" where dynamic batching can be up to 60% slower than manual batching for training when the shapes happen to be identical. Additionally, batching very large or deep graphs can lead to high memory consumption, as the system must maintain state for all tensor types across the entire batch. Finally, the specific implementation described is tightly coupled with TensorFlow's primitives.
Future work could involve deeper integration into compilers to further reduce the overhead of the data-routing operations, paving the way for even faster dynamic graph processing.
Summary updated