Research map / Learning theory and algorithms / Combinatorial and search optimization
Practical Performance Guarantees for Pipelined DNN Inference
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.
Formalizes max-throughput DNN pipeline partitioning (MTPP), proposes MIP relaxations giving per-instance lower bounds, and a topological-order plus DP heuristic (SliceGraph with BRKGA) whose near-optimality is certified on 369 production graphs.
Problem
Partitioning a DNN computation graph into k pipeline stages to minimize the bottleneck stage cost (including communication and memory overflow) is NP-hard, and practitioners lack a way to know whether a partition is good enough.
Approach
Combine a topological-order search (Kahn's algorithm with node priorities, optimized by BRKGA) with an optimal DP slicing of the order, and certify quality via a hierarchy of MIP lower bounds (three-superblock, guess-the-bottleneck, and exact formulations) computed offline.
Key results
- For k=16 on the production testbed, the exact MIP lower bound averages 0.9452 of the best partition versus 0.4598 for the simple combinatorial bound.
- The exact MIP closes the optimality gap by a factor of 9.855x relative to the simple bound at k=16.
- BRKGA with 10^4 evaluations gives the best partitions among the compared linear-ordering heuristics (e.g., ratio 1.910 at k=8 vs 1.950 for mla).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the exact MIP instead of the simple combinatorial lower bound | Pipeline partitioning lower-bound analysis · Production models, k=16 | lower-bound ratio: 0.4598 -> 0.9452 | Helped |
| Use the exact MIP instead of the simple combinatorial lower bound | Pipeline partitioning lower-bound analysis · REGAL, k=16 | lower-bound ratio: 0.5821 -> 0.8929 | Helped |
| Add communication costs to the simple lower bound using the three-superblock MIP | Pipeline partitioning lower-bound analysis · Production models, k=16 | lower-bound ratio: 0.4598 -> 0.5770 | Helped |
| Guess the bottleneck block and include superblock boundary edges | Three-superblock MIP · Production models, k=4 | lower-bound ratio: 0.7911 -> 0.8446 | Helped |
| Guess the bottleneck block and include superblock boundary edges | Three-superblock MIP · Production models, k=64 | lower-bound ratio: 0.5543 -> 0.5543 | No clear effect |
| Replace the exact MIP with bottleneck-guess MIP | Pipeline partitioning lower-bound analysis · Production models, k=16 | lower-bound ratio: 0.9452 -> 0.5780 | Hurt |
| Replace the exact MIP with bottleneck-guess MIP | Pipeline partitioning lower-bound analysis · REGAL, k=16 | lower-bound ratio: 0.8929 -> 0.5824 | Hurt |
| Use bottleneck-guess MIP instead of exact MIP | Pipeline partitioning lower-bound analysis · Production models, k=2 | lower-bound ratio: 0.9901 -> 0.9901 | No clear effect |
| Use bottleneck-guess MIP instead of exact MIP | Pipeline partitioning lower-bound analysis · REGAL, k=2 | lower-bound ratio: 0.9804 -> 0.9804 | No clear effect |
Surprising findings
- The three-superblock bottleneck relaxation is only modestly stronger than the simple bound (0.5770 vs 0.4598 at k=16), and the guess-the-bottleneck variant saturates at k=64 to the same value as the bottleneck relaxation.
- On REGAL graphs the exact MIP's advantage over other bounds appears only at moderate k, dropping to 0.3810 at k=64 due to solver time limits.
Limitations
- Production cost model and node/edge weights are proprietary, so the main testbed cannot be reproduced from released data.
- MIP lower bounds are costly (up to the 60-minute limit) and are meant for offline certification rather than in-compiler use.
- Some MIP instances fail to reach provable optimality within time limits, especially exact MIP at k=64.
Experimental setup
Datasets: production testbed of 369 computation graphs REGAL synthetic random graphs (1000)
Benchmarks: production testbed of 369 computation graphs REGAL synthetic graphs
Metrics: geometric mean of lower bound as fraction of best found part approximation ratio upper bound running time
Baselines: simple combinatorial lower bound random topological order minimum linear arrangement (mla) mla-weighted
Builds on: PipeDream GPipe BRKGA minimum linear arrangement
Closest papers by meaning
- Auto-reconfiguration for Latency Minimization in CPU-based DNN Serving (ICML 2025 · similarity 0.86)
- An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks (ICML 2025 · similarity 0.85)
- Provable Editing of Deep Neural Networks using Parametric Linear Relaxation (NeurIPS 2024 · similarity 0.85)
- Clip-and-Verify: Linear Constraint-Driven Domain Clipping for Accelerating Neural Network Verification (NeurIPS 2025 · similarity 0.85)
- AsyncMesh: Fully Asynchronous Optimization for Data and Pipeline Parallelism (NeurIPS 2026 · similarity 0.85)
- Scalable Neural Network Verification with Branch-and-bound Inferred Cutting Planes (NeurIPS 2024 · similarity 0.84)
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.