Research map / Probabilistic and scientific modeling / Bayesian optimization
GauS: Differentiable Scheduling Optimization via Gaussian Reparameterization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GauS, a differentiable operator-scheduling framework that relaxes each operator's start step into a Gaussian random variable (2|V| parameters), optimized with augmented Lagrangian and GPU vectorization, and is the first differentiable method for modulo (pipelined) scheduling.
Problem
Operator scheduling (regular and modulo/pipelined) is NP-hard; exact solvers scale poorly, heuristics are suboptimal, and prior categorical differentiable relaxations (GS-Schedule) ignore ordinal time and have O(D|V|) parameters.
Approach
Model each operator's start time as a Gaussian N(mu, sigma^2), discretize by integrating the PDF over unit intervals (rounding), derive expected resource, memory, dependency and recurrence violations in closed form, and optimize (mu, sigma) with gradient descent under an augmented Lagrangian, with a legalization pass to produce feasible schedules.
Key results
- GS-Schedule's solutions are about 30% to 3x worse than GauS (geometric mean gap of 71.8%) on formulation A.
- GauS reaches equivalent solution quality to exact/previous methods one to two orders of magnitude faster, per the authors.
- Shuffling the distribution's d-axis degrades EPFL costs by an average of 35% in the temporal-proximity ablation.
Surprising findings
- Replacing the Gaussian CDF with logistic, Laplace, or Cauchy yields comparable results (geomean within ~8% of Gaussian), suggesting the family is a tuning knob rather than essential.
Limitations
- Independent per-operator Gaussians ignore correlations between connected nodes; full Gaussian Process would cost O(|V|^2).
- May converge to suboptimal solutions; legalization is needed to ensure feasibility.
- Evaluated on a 15-minute limit with a single run per problem and no variance reported.
Experimental setup
Datasets: EPFL benchmark suite random workloads (RW) from GS-Schedule
Benchmarks: EPFL RW
Metrics: objective cost (resource, memory, communication) runtime to solution GPU memory and utilization feasibility
Baselines: CPLEX Gurobi GS-Schedule List Scheduling Force-Directed Scheduling
Builds on: GS-Schedule Gumbel-Softmax augmented Lagrangian method modulo scheduling SDC+LP
Closest papers by meaning
- Differentiable Combinatorial Scheduling at Scale (ICML 2024 · similarity 0.87)
- Tight Time Complexities in Parallel Stochastic Optimization with Arbitrary Computation Dynamics (ICLR 2025 · similarity 0.84)
- B$^3$-PWL: GPU-Batched Branch-and-Bound for Piecewise-Linear Optimization with SOS2 Constraints (NeurIPS 2026 · similarity 0.82)
- Accelerating Optimization via Differentiable Stopping Time (NeurIPS 2025 · similarity 0.82)
- ACCO: Accumulate While You Communicate for Communication-Overlapped Sharded LLM Training (NeurIPS 2025 · similarity 0.81)
- Dynamic Operator Optimization for Efficient Multi-Tenant LoRA Model Serving (AAAI 2025 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.