cs.LGFeb 23, 2026
SaveGauS: Differentiable Scheduling Optimization via Gaussian Reparameterization
Organizations: Cornell University · University of Maryland, College Park
Abstract
Efficient operator scheduling is a fundamental challenge in software compilation and hardware synthesis. While recent differentiable approaches have sought to replace traditional ones like exact solvers or heuristics with gradient-based search, they typically rely on categorical distributions that fail to capture the ordinal nature of time and suffer from a parameter space that scales poorly. In this paper, we propose a novel differentiable framework, GauS, that models operator scheduling as a stochastic relaxation using Gaussian distributions, which fully utilize modern parallel computing devices like GPUs. By representing schedules as continuous Gaussian variables, we successfully capture the ordinal nature of time and reduce the optimization space by orders of magnitude. Our method is highly flexible to represent various objectives and constraints, which provides the first differentiable formulation for the complex pipelined scheduling problem. We evaluate our method on a range of benchmarks, demonstrating that Gaus achieves Pareto-optimal results.
Figures & tables
Figure 1: Impact of optimization objectives on scheduling — Impact of optimization objectives on scheduling. Nodes (operators) show resource requirements (number of dots) and bitwidths of storage units required (number of arrows). Max depth ( ) sets to . Left schedule minimizes resources ( ); right schedule minimizes memory footprint ( ).
Figure 2: Illustration of Gaussian reparameterization — Each operator is parameterized as an independent Gaussian over the scheduling timeline.
Figure 3: Formulation A: Latency constrained, resource and communication optimization — Problem instance size ( ) increases from left to right. A 15-minute time limit is applied to all methods. Relative solution quality is represented as the ratio between the methods’ solution quality and GauS, where lower values correspond to higher solution quality. Light crosses (labeled as inf) denote no feasible solution or quality exceeding GauS performance; filled crosses indicate GS-Schedule exceeded available CUDA memory (OOM). On shared feasible instances, GauS achieves a 71.8% geometric mean improvement over GS-Schedule.
Figure 4: Benchmark statistics
Figure 5: Formulation B: Latency constrained, memory footprint optimization — A 15-minute time limit is applied to all methods. Light crosses denote no feasible solution or quality exceeding GauS performance.
Figure 6: Formulation C: Latency, resources, and recurrence-constrained, memory footprint modulo optimization — A 15-minute time limit is applied to all methods. Light crosses denote no feasible solution or quality exceeding GauS performance. dec in EPFL has no feasible solution, thus omitted from the plot.
Figure 7: Quality-Speed tradeoff representative benchmarks – From left to right: RW_5, router, and bar on formulation A . Lines terminating before the 15-minute indicate no further improvement is made.
Appendix figures & tables10 assets
Supplementary material from the paper’s appendix.
Appendix
| EPFL | Random Workloads (RW) | ||||
|---|---|---|---|---|---|
| Name | Number of Nodes ( ) | Depth ( ) | Name | Number of Nodes ( ) | Depth ( ) |
| ctrl | 182 | 11 | RW_1 | 929 | 16 |
| int2float | 271 | 17 | RW_2 | 941 | 16 |
| dec | 312 | 4 | RW_3 | 949 | 15 |
| router | 344 | 55 | RW_4 | 4713 | 18 |
| cavlc | 703 | 17 | RW_5 | 4716 | 21 |
Table 1: Summary of Graph Statistics (Sorted by Nodes)
Figure 8: Sensitivity of GauS to its three core hyperparameters under Formulation A. Each panel sweeps one HP while the other two are held at the main-paper defaults ( , , ). Per swept value we first compute, for each of five EPFL benchmarks ( dec , cavlc , bar , arbiter , multiplier ; 3 seeds each), the ratio of its mean cost to its own best across the swept range, and average those ratios across benchmarks. The curves are then re-normalized by their minimum so that at the consensus-best value. The dashed line marks the value used in the main paper: it coincides with the consensus best for , and lies within of it for and lr.
| Benchmark | seeds | Gaussian | Logistic | Laplace | Cauchy | Winner |
| ctrl | 1 | 1.000 | 1.155 | 1.054 | 1.089 | Gaussian |
| int2float | 1 | 1.000 | 1.007 | 0.994 | 0.998 | Laplace |
| router | 1 | 1.000 | 1.006 | 0.939 | 0.895 | Cauchy |
| dec | 3 | 1.000 | 1.400 | 1.302 | 1.661 | Gaussian |
| cavlc | 3 | 1.000 | 1.004 | 1.019 | 0.952 | Cauchy |
| adder | 1 | 1.000 | 1.112 | 0.534 | 1.334 | Laplace |
Table 2: Distribution-family ablation on EPFL (Form A, icml objective). Cells are mean cost relative to Gaussian ( ); values below 1 indicate the family beats Gaussian. Bold marks the per-row winner. All four families share identical hyperparameters (no per-family retuning). Five benchmarks were run with 3 seeds and 14 with a single seed; hyp is excluded (load-time OOM for all four families).
Figure 9: GPU Profiling Results on EPFL — The bar charts show the GPU memory usage, corresponding to the left axis. The curve show the Avg. GPU utilization, corresponding to the right axis. Avg. GPU utilization is the averaged GPU utilization (%) during the entire execution. Because GS-Schedule is out-of-memory (OOM) on square, multiplier, and div, no data is provided for GS-Schedule on these benchmarks
Figure 10: Comprehensive tradeoff comparison of RW on Formulation B: Latency constrained, resource and communication optimization — A 15-minute time limit is applied to all methods. Heuristics such as FDS and List Scheduling are represented as horizontal lines to reflect their fast convergence to final solution quality.
Figure 11: Comprehensive tradeoff comparison of EPFL on Formulation A: Latency constrained, resource and communication optimization — A 15-minute time limit is applied to all methods.
Figure 12: Comprehensive tradeoff comparison of RW on Formulation B: Latency constrained, memory footprint optimization — A 15-minute time limit is applied to all methods. Heuristics such as FDS and List Scheduling are represented as horizontal lines to reflect their fast convergence to final solution quality.
Figure 13: Comprehensive tradeoff comparison of EPFL on Formulation B: Latency constrained, memory footprint optimization — A 15-minute time limit is applied to all methods. Heuristics such as FDS and List Scheduling are represented as horizontal lines to reflect their fast convergence to final solution quality.
Figure 14: Comprehensive tradeoff comparison of RW on Formulation C: Latency, resource, and recurrences constrained, memory footprint modulo optimization — A 15-minute time limit is applied to all methods. Heuristics such as FDS and List Scheduling are represented as horizontal lines to reflect their fast convergence to final solution quality.
Figure 15: Comprehensive tradeoff comparison of EPFL on Formulation C: Latency, resource, and recurrences constrained, memory footprint modulo optimization — A 15-minute time limit is applied to all methods. Heuristics such as FDS and List Scheduling are represented as horizontal lines to reflect their fast convergence to final solution quality. There is no feasible solution for dec, thus plot is left empty.
More in this topic
Differentiable Optimization
Differentiable optimization makes solvers and constrained decisions trainable with gradients for learning, control, design, and inverse problems.
See all 83 papers