Abstract
Neural networks that compute over graph structures are a natural fit for problems in a variety of domains, including natural language (parse trees) and cheminformatics (molecular graphs). However, since the computation graph has a different shape and size for every input, such networks do not directly support batched training or inference. They are also difficult to implement in popular deep learning libraries, which are based on static data-flow graphs. We introduce a technique called dynamic batching, which not only batches together operations between different input graphs of dissimilar shape, but also between different nodes within a single input graph. The technique allows us to create static graphs, using popular libraries, that emulate dynamic computation graphs of arbitrary shape and size. We further present a high-level library of compositional blocks that simplifies the creation of dynamic graph models. Using the library, we demonstrate concise and batch-wise parallel implementations for a variety of models from the literature.
Introduction
Standard deep learning libraries were originally built around static computation graphs, excelling when every input in a batch shares the same shape (e.g., fixed-resolution images). However, many real-world domains involve Dynamic Computation Graphs (DCGs). In Natural Language Processing, sentences have unique parse tree structures; in chemistry, molecules have varying graph topologies. Historically, researchers had to choose between processing inputs one by one—which fails to utilize GPU parallelism—or complex manual padding and truncation.
This paper introduces a significant architectural shift through dynamic batching and the TensorFlow Fold library, designed to bring the efficiency of GPU-accelerated batching to irregular, non-static data structures.
The Dynamic Batching Algorithm
The core contribution is an algorithm that takes a collection of individual computation graphs and rewrites them into a single, batched execution plan. It utilizes depth-based scheduling, assigning a depth to every node and grouping instances of the same operation (e.g., an LSTM cell) that occur at the same depth across the entire batch.
As illustrated in Figure 1, the system uses tf.gather and tf.concat operations to move data between these batched operations. This effectively "weaves" different input structures together into a single pass, allowing a static engine to emulate dynamic logic by treating graph topology as data (indices) rather than fixed structure.
TensorFlow Fold: Compositional Blocks
To simplify the creation of these models, the authors released TensorFlow Fold, a high-level library using functional programming combinators. Instead of manually defining tensors, users utilize blocks like Map (applying functions to sequences), Fold (processing recursive structures), and Record (handling structured data).
Figure 2 shows various model topologies supported by the library. By using these functional blocks, complex models like Tree-LSTMs can be written in roughly half the lines of code compared to traditional implementations, significantly accelerating research iteration.
Key Results and Performance
The authors evaluated their approach using synthetic binary trees, the Stanford Sentiment Treebank (SST), and molecular graphs. Key findings include:
- Massive Speedups: On a GPU, dynamic batching was up to 120x faster than processing inputs individually. Even on CPUs, it provided a ~28x speedup.
- State-of-the-Art Accuracy: Their Tree-LSTM implementation achieved state-of-the-art results on the SST with an ensemble accuracy of 53.6% (fine-grained) and 90.2% (binary).
- Efficiency: The system showed no measurable penalty for processing batches where every tree had a different shape compared to batches where all trees were identical.
Conclusion and Limitations
While TensorFlow Fold was a breakthrough for static-graph engines, the industry has largely shifted toward "Eager Execution" frameworks (like PyTorch or TensorFlow 2.0). However, dynamic batching remains a critical technique for maximizing GPU utilization on irregular data. The primary trade-off remains the overhead of concat and gather operations, which can occasionally make dynamic batching slightly slower than perfectly hand-optimized static batches for very simple models.
Summary updated