Abstract
Computation graph scheduling is a critical yet challenging task in compiler optimization, often relying on inaccurate hardware proxy models. Traditional reinforcement learning methods typically optimize for a single best schedule according to these proxies, leading to poor performance when proxy errors occur. This paper proposes a generative approach using Generative Flow Networks (GFlowNets) to sample a diverse set of high-performing candidate schedules. By training with a novel Log-Partition Variance loss and a Topoformer architecture, the model achieves superior robustness to proxy inaccuracies and demonstrates strong zero-shot generalization to unseen graph structures.
Introduction
Efficiently scheduling operations on hardware—determining the order and core assignment for tasks—is a classic NP-hard problem. Because direct evaluation on physical hardware is prohibitively slow, researchers use "proxies": simplified mathematical models that estimate execution time. However, these proxies often fail to capture complex hardware behaviors like memory bank conflicts or bus contention. Traditional machine learning approaches, such as Reinforcement Learning (RL), tend to converge on a single optimal schedule based on the proxy. If the proxy is flawed, this "optimal" schedule may perform poorly in real-world deployment. This work addresses the need for a scheduler that is robust to such inevitable proxy inaccuracies.
Methodology
The authors introduce a generative scheduling pipeline that leverages GFlowNets to produce a diverse batch of high-quality candidates rather than a single point estimate.
Technical Innovations
- GFlowNets for Scheduling: Unlike standard RL, which maximizes expected reward, GFlowNets are trained to sample schedules with a probability proportional to their estimated speedup. This approach naturally discovers multiple "modes" or diverse ways to achieve high performance.
- Log-Partition Variance (LPV) Loss: To handle graphs of varying sizes, the authors developed the LPV loss. This objective avoids the difficult task of explicitly estimating the "total flow" (log Z), leading to more stable training in conditional settings.
- Temperature Conditioning: The model is conditioned on a temperature parameter, allowing users to tune the trade-off between diversity and peak performance at inference time without retraining.
- Topoformer Architecture: A specialized Transformer-based encoder incorporates the graph's topology, ensuring the model respects precedence constraints between operations.
Experimental Setup
The method was evaluated on a broad spectrum of problems, including 1,000 synthetic graphs from five random distributions (e.g., Erdos-Renyi, Barabasi-Albert) and real-world computation graphs from commercial AI products ranging from 12 to 128 nodes.
Key Results
The GFlowNet approach was compared against strong baselines, including Proximal Policy Optimization (PPO) and Genetic Algorithms (BRKGA).
Robustness and Diversity
GFlowNet consistently outperformed baselines when subjected to simulated proxy errors, such as noisy runtimes or bandwidth limitations. For example, in "Latency Limited" scenarios, GFlowNet achieved a speedup of 2.11, significantly higher than PPO's 1.87.
Crucially, GFlowNet produced significantly more diverse candidate sets. Its Graph Edit Distance (GED) score—measuring structural differences between schedules—was approximately 94.8, nearly double that of the BRKGA baseline (55.9). This diversity serves as a buffer: if the proxy is wrong about one specific schedule, it is unlikely to be wrong about all diverse candidates in the same way.
Zero-Shot Generalization
By conditioning on the computation graph, the model learned general scheduling principles. It successfully generalized to unseen synthetic graph distributions and real-world AI workloads, maintaining its performance edge and high diversity without further training.
Conclusion and Future Work
This research demonstrates that diversity is a powerful proxy for robustness in hardware scheduling. While the current model scales to graphs of approximately 128 nodes, future work will focus on scaling the Topoformer and GFlowNet sampling to handle thousands of nodes found in massive computation graphs. Additionally, integrating classical scheduling heuristics into the GFlowNet framework could further accelerate the discovery of high-quality schedules.
Summary updated