pith. sign in

arxiv: 2606.07777 · v1 · pith:BFIPUAOVnew · submitted 2026-06-05 · 💻 cs.DC

Large-Scale Regularized Matching on GPU Clusters

Aida Rahmattalabi , Gregory Dexter , Sanjana Garg , Qinquan Song , Shenyinying Tu , Yuan Gao , Zhipeng Wang , Rahul Mazumder This is my paper

Pith reviewed 2026-06-27 20:45 UTC · model grok-4.3

classification 💻 cs.DC
keywords distributed linear programmingGPU clusterscolumn-sharded parallelismridge regularizationmatching problemsPyTorch solverblock-diagonal structure
0
0 comments X

The pith

A PyTorch multi-GPU solver solves million-user block-diagonal LPs with near-linear scaling and explicit stability control via ridge regularization.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a distributed solver for repeatedly solved linear programs that arise in ad allocation and content matching. These programs have millions of users and thousands of items but possess sparse block-diagonal structure. The solver uses column-sharded parallelism across GPUs, fused kernels, and batched operations so that only item-level dual variables are reduced during communication. Ridge regularization with a continuation schedule is added to reduce solution variability across runs, and an operator-centric interface replaces schema-bound CPU solvers. The result is order-of-magnitude wall-clock improvement over DuaLip-Scala together with 3.86x scaling on four GPUs and the ability to handle instances that exceed single-GPU memory.

Core claim

The central claim is that column-sharded parallelism on a GPU cluster, combined with ridge-regularized objectives and a continuation schedule, yields near-linear scaling while controlling temporal instability, and that an operator-centric programming model decouples formulation from the distributed solve loop.

What carries the argument

Column-sharded parallelism with communication limited to a reduction over item-level dual variables, implemented via fused Triton kernels and batched PyTorch operations on ridge-regularized LPs.

If this is right

  • Production instances that exceed single-GPU memory become solvable under fixed hardware budgets.
  • Downstream systems experience less churn because successive solves produce more stable allocations.
  • New families of constraints can be expressed without modifying the distributed infrastructure or solve loop.
  • Wall-clock time drops by roughly an order of magnitude relative to existing CPU-based solvers on the same workloads.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same sharded design could be applied to other repeated large-scale matching problems outside advertising, such as recommendation or logistics.
  • The regularization parameter schedule offers a tunable knob between speed and fidelity that downstream users could expose as an SLA parameter.
  • Operator-centric composition might simplify integration with automatic differentiation pipelines for end-to-end learning of matching objectives.

Load-bearing premise

The target linear programs possess sparse block-diagonal structure across users that keeps communication limited to item-level reductions.

What would settle it

A timing experiment on eight GPUs for a fixed item count showing sub-linear scaling or an experiment in which solution variability across independent runs remains comparable to unregularized baselines.

Figures

Figures reproduced from arXiv: 2606.07777 by Aida Rahmattalabi, Gregory Dexter, Qinquan Song, Rahul Mazumder, Sanjana Garg, Shenyinying Tu, Yuan Gao, Zhipeng Wang.

Figure 1
Figure 1. Figure 1: Triton fused projection vs. PyTorch-eager Duchi (single H100). (Top) p95 per-iteration time; [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Geometric bucketing vs. single-slab baseline (Triton kernel, single H100). (Top) p95 per-iteration [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Scaling from 1–16 GPUs (16-GPU spans 2 H100 nodes). (Top) Solve time; (Bottom) speedup vs. 1 [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Effect of diagonal preconditioning. We report [PITH_FULL_IMAGE:figures/full_fig_p013_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Effect of regularization continuation. Decaying [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Scala–DuaLip (PyTorch) parity. Each panel shows the dual objective versus AGD iteration for the [PITH_FULL_IMAGE:figures/full_fig_p015_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Relative error in dual objective compared to the Scala solver. The error drops below 1% within the [PITH_FULL_IMAGE:figures/full_fig_p016_7.png] view at source ↗
read the original abstract

Production decision systems such as ad allocation or content matching involve millions of users and thousands of items, reducing to large-scale linear programs with sparse block-diagonal structure across users. These LPs are solved repeatedly on recurring cadences over slowly evolving inputs. Three system gaps stand out. Scale: production instances routinely exceed the memory capacity of GPU solvers such as cuPDLP and D-PDLP under fixed hardware budgets. Temporal instability: solution variability across runs induces downstream churn and complicates SLAs, yet existing solvers provide no explicit control. Extensibility: CPU-based solvers such as DuaLip-Scala converge slowly and couple problem formulation to fixed schemas, making new constraint families difficult to express. We present a distributed multi-GPU LP solver built natively in PyTorch with systems-algorithm co-design for this structure. It adopts column-sharded parallelism with fused Triton kernels and batched operations to reduce per-iteration overhead. As users grow, only local computation increases, while communication is limited to a reduction of item-level dual variables, yielding near-linear scaling with GPU count at fixed item size. We also adopt ridge-regularized LPs to improve stability, a control absent from existing GPU solvers. A continuation schedule over the regularization parameter balances convergence speed and solution fidelity. Finally, we introduce an operator-centric programming model that replaces DuaLip-Scala's schema-bound interface with composable primitives, enabling new formulations without modifying the solve loop or distributed infrastructure. On synthetic workloads, our system achieves order-of-magnitude wall-clock speedup over DuaLip-Scala, near-linear multi-GPU scaling (3.86x on 4 GPUs), and scales beyond the reach of existing GPU solvers.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper presents a PyTorch-native distributed multi-GPU LP solver for large-scale matching problems (e.g., ad allocation) that exhibit sparse block-diagonal structure across users. It uses column-sharded parallelism with fused Triton kernels to limit communication to item-level dual reductions, ridge regularization with a continuation schedule for stability, and an operator-centric model for extensibility. On synthetic workloads matching the assumed structure, it reports order-of-magnitude wall-clock speedup over DuaLip-Scala, 3.86x scaling on 4 GPUs, and the ability to handle instances beyond existing GPU solvers.

Significance. If the performance and scaling claims are substantiated, the work would be significant for production-scale repeated LP solving in distributed systems, as it directly targets memory limits of current GPU solvers, adds explicit stability control absent from prior GPU methods, and decouples formulation from fixed schemas.

major comments (2)
  1. [Abstract] Abstract: concrete performance claims (order-of-magnitude speedup over DuaLip-Scala; 3.86x on 4 GPUs) are stated without any reference to experimental setup, problem sizes, baselines, number of runs, error bars, or verification steps. Because these numbers are load-bearing for the central contribution, their unsupported presentation in the abstract undermines assessment of the scaling and speedup results.
  2. [Abstract] The manuscript states that production instances 'match' the sparse block-diagonal structure enabling column-sharded parallelism with communication limited to item-level dual variables, yet provides no quantitative characterization or real-data validation of this structure (e.g., sparsity patterns, block sizes, or communication volume measurements). This assumption is load-bearing for the near-linear scaling claim.
minor comments (1)
  1. [Abstract] The abstract is dense and interleaves system description, algorithmic choices, and performance claims; separating the contributions more clearly would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive comments. We address each major comment below and indicate planned revisions to strengthen the manuscript.

read point-by-point responses

  1. Referee: [Abstract] Abstract: concrete performance claims (order-of-magnitude speedup over DuaLip-Scala; 3.86x on 4 GPUs) are stated without any reference to experimental setup, problem sizes, baselines, number of runs, error bars, or verification steps. Because these numbers are load-bearing for the central contribution, their unsupported presentation in the abstract undermines assessment of the scaling and speedup results.

    Authors: We agree that the abstract would benefit from additional context on the experimental conditions supporting the reported numbers. In the revised manuscript we will expand the final sentence of the abstract to note that the speedups and scaling results are obtained on synthetic instances with up to 10^7 users and 10^4 items, using DuaLip-Scala as the baseline, and averaged over multiple runs; we will also add an explicit pointer to Section 5 for the full experimental setup, problem sizes, and observed variability. revision: yes

  2. Referee: [Abstract] The manuscript states that production instances 'match' the sparse block-diagonal structure enabling column-sharded parallelism with communication limited to item-level dual variables, yet provides no quantitative characterization or real-data validation of this structure (e.g., sparsity patterns, block sizes, or communication volume measurements). This assumption is load-bearing for the near-linear scaling claim.

    Authors: The evaluation is performed on synthetic workloads explicitly constructed to exhibit the target sparse block-diagonal structure. Section 4.1 details the instance generator, including block sizes, sparsity patterns, and user-item distributions chosen to match production characteristics; Section 5.3 and Figure 7 quantify communication volume, which remains bounded by item count independent of user scale. We acknowledge that proprietary production data precludes direct real-world validation. We will revise the abstract to state that the structure and scaling behavior are characterized on synthetic instances matching the assumed production pattern. revision: partial

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper is a systems description of a multi-GPU LP solver for block-diagonal problems. All central claims are empirical (wall-clock speedup, 3.86x scaling on 4 GPUs) measured on synthetic workloads that explicitly exhibit the stated sparse block-diagonal structure. No equations, parameter fits presented as predictions, uniqueness theorems, or self-citations appear in the text. The argument is self-contained: the solver is engineered for the given structure, the structure is assumed to match production instances, and performance is reported directly on matching synthetic data. No load-bearing step reduces to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract supplies no equations, parameters, or modeling assumptions beyond the high-level problem structure; therefore the ledger is empty.

pith-pipeline@v0.9.1-grok · 5858 in / 1102 out tokens · 23648 ms · 2026-06-27T20:45:09.987800+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 4 canonical work pages · 1 internal anchor

  1. [1]

    Ayan Acharya, Siyuan Gao, Borja Ocejo, Kinjal Basu, Ankan Saha, Keerthi Selvaraj, Rahul Mazumdar, Parag Agrawal, and Aman Gupta. 2023. Promoting inactive members in edge-building marketplace. In Companion Proceedings of the ACM Web Conference 2023. 945–949

    2023

  2. [2]

    David Applegate, Mateo Díaz, Oliver Hinder, Haihao Lu, Miles Lubin, Brendan O’Donoghue, and Warren Schudy. 2021. Practical large-scale linear programming using primal-dual hybrid gradient.Advances in Neural Information Processing Systems34 (2021), 20243–20257

    2021

  3. [3]

    Kinjal Basu, Amol Ghoting, Rahul Mazumder, and Yao Pan. 2020. ECLIPSE: An extreme-scale linear program solver for web-applications. InInternational Conference on Machine Learning. PMLR, 704–714

    2020

  4. [4]

    Niv Buchbinder, Moran Feldman, Arpita Ghosh, and Joseph Naor. 2014. Frequency capping in online advertising.Journal of Scheduling17, 4 (2014), 385–398

    2014

  5. [5]

    John Duchi, Shai Shalev-Shwartz, Yoram Singer, and Tushar Chandra. 2008. Efficient projections onto the l 1-ball for learning in high dimensions. InProceedings of the 25th international conference on Machine learning. 272–279

    2008

  6. [6]

    Lisa Fleischer, Michel X Goemans, Vahab S Mirrokni, and Maxim Sviridenko. 2006. Tight approximation algorithms for maximum general assignment problems. InSODA, Vol. 6. 611–620

    2006

  7. [7]

    Hongpei Li, Yicheng Huang, Huikang Liu, Dongdong Ge, and Yinyu Ye. 2026. D-PDLP: Scaling PDLP to Distributed Multi-GPU Systems. arXiv:2601.07628 [math.OC]https://arxiv.org/abs/2601.07628

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  8. [8]

    Elita Lobo, Justin Payan, Cyrus Cousins, and Yair Zick. 2024. Fair and welfare-efficient constrained multi-matchings under uncertainty.Advances in Neural Information Processing Systems37 (2024), 74579–74616

    2024

  9. [9]

    cuPDLPx: A further enhanced GPU-based first-order solver for linear programming.arXiv preprint arXiv:2507.14051, 2025

    HaihaoLu, ZedongPeng, andJinwenYang.2025. cuPDLPx: AFurtherEnhancedGPU-BasedFirst-Order Solver for Linear Programming. arXiv:2507.14051 [math.OC]https://arxiv.org/abs/2507.14051

    work page arXiv 2025

  10. [10]

    Haihao Lu and Jinwen Yang. 2024. cuPDLP.jl: A GPU Implementation of Restarted Primal-Dual Hybrid Gradient for Linear Programming in Julia. arXiv:2311.12180 [math.OC]https://arxiv.org/ abs/2311.12180

    work page arXiv 2024

  11. [11]

    Haihao Lu and Jinwen Yang. 2025. cuPDLP.jl: A GPU Implementation of Restarted Primal–Dual Hybrid Gradient for Linear Programming in Julia.Operations Research73, 6 (2025), 3440–3452

    2025

  12. [12]

    Joseph Naor and David Wajc. 2018. Near-optimum online ad allocation for targeted advertising.ACM Transactions on Economics and Computation (TEAC)6, 3-4 (2018), 1–20

    2018

  13. [13]

    Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019. Pytorch: An imperative style, high-performance deep learning library.Advances in neural information processing systems32 (2019)

    2019

  14. [14]

    Rohan Ramanath, S Sathiya Keerthi, Yao Pan, Konstantin Salomatin, and Kinjal Basu. 2021. Efficient algorithms for global inference in internet marketplaces.arXiv preprint arXiv:2103.05277(2021)

    work page arXiv 2021

  15. [15]

    Philippe Tillet. 2025. Introducing Triton: Open-source GPU programming for neural networks

    2025

  16. [16]

    Panagiotis Tsiakis and Lazaros G Papageorgiou. 2008. Optimal production allocation and distribution supply chain networks.International Journal of Production Economics111, 2 (2008), 468–483

    2008

  17. [17]

    2001.Approximation algorithms

    Vijay V Vazirani. 2001.Approximation algorithms. Vol. 1. Springer. 18

    2001