RECORD
Merge Hulls Without Copying Vertices: GPU Isotonic Regression
Distributed, Parallel, and Cluster Computing · Submitted 16 Oct 2026
abstract compiled · 2026-10-20 · no language-model review
The authors' main claim On dense hulls the merge phase is 17 to 276 times faster with segment lists and the whole operator 3.9 to 19 times; on noisy data, where few vertices survive, the difference is small.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Isotonic regression finds the monotone sequence closest to the data in weighted least squares. It is used to calibrate probabilities and inside differentiable ranking. Its standard algorithm, pool adjacent violators, is sequential within a sequence, and torchsort, the exact GPU solver of differentiable sorting libraries, runs it with one thread per sequence, which is slow on long ones. The fit is the slope sequence of the lower convex hull of cumulative sums, and hulls of sorted points can be merged in parallel. Merging partial hulls level by level, however, copies the surviving vertices at every level, which moves $\Theta(n \log n)$ data when most points survive. We store each chunk's hull once and represent a merged hull as a list of segments of these chunk hulls, at most one per chunk; a merge then updates the list. We prove the representation correct, bound the work and depth of the merge phase, and measure a CUDA implementation on four NVIDIA GPUs against a control that copies the surviving vertices with the whole GPU at every level. On dense hulls the merge phase is 17 to 276 times faster with segment lists and the whole operator 3.9 to 19 times; on noisy data, where few vertices survive, the difference is small. In a differentiable soft rank, replacing torchsort's isotonic solver makes forward and backward 2.3 to 230 times faster on a T4, and the training step of a compact model with a Spearman loss 1.6 to 9 times.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Isotonic regression finds the monotone sequence closest to the data in weighted least squares. | background 1.00 | 0.05 | 0.02 | asserted 1.00 |
| s1 | It is used to calibrate probabilities and inside differentiable ranking. | background 1.00 | 0.06 | 0.02 | asserted 1.00 |
| s2 | Its standard algorithm, pool adjacent violators, is sequential within a sequence, and torchsort, the exact GPU solver of differentiable sorting libraries, runs it with one thread per sequence, which is slow on long ones. | background 0.80 | 0.12 | 0.02 | asserted 1.00 |
| s3 | The fit is the slope sequence of the lower convex hull of cumulative sums, and hulls of sorted points can be merged in parallel. | background 0.76 | 0.13 | 0.07 | asserted 1.00 |
| s4 | Merging partial hulls level by level, however, copies the surviving vertices at every level, which moves $\Theta(n \log n)$ data when most points survive. | gap 0.56 | 0.29 | 0.06 | asserted 1.00 |
| s5 | We store each chunk's hull once and represent a merged hull as a list of segments of these chunk hulls, at most one per chunk; a merge then updates the list. | method 0.90 | 0.94 | 0.17 | asserted 1.00 |
| s6 | We prove the representation correct, bound the work and depth of the merge phase, and measure a CUDA implementation on four NVIDIA GPUs against a control that copies the surviving vertices with the whole GPU at every level. | contribution 0.68 | 0.97 | 0.10 | asserted 1.00 |
| s7 | On dense hulls the merge phase is 17 to 276 times faster with segment lists and the whole operator 3.9 to 19 times; on noisy data, where few vertices survive, the difference is small. | result 1.00 | 0.96 | 0.51 | asserted 1.00 |
| s8 | In a differentiable soft rank, replacing torchsort's isotonic solver makes forward and backward 2.3 to 230 times faster on a T4, and the training step of a compact model with a Spearman loss 1.6 to 9 times. | result 1.00 | 0.95 | 0.35 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Isotonic regression finds the monotone sequence closest to the data in weighted least squares. It is used to calibrate probabilities and inside differentiable ranking. Its standard algorithm, pool adjacent violators, is sequential within a sequence, and torchsort, the exact GPU solver of differentiable sorting libraries, runs it with one thread per sequence, which is slow on long ones. The fit is the slope sequence of the lower convex hull of cumulative sums, and hulls of sorted points can be merged in parallel. Merging partial hulls level by level, however, copies the surviving vertices at every level, which moves Theta(n log n) data when most points survive. We store each chunk's hull once and represent a merged hull as a list of segments of these chunk hulls, at most one per chunk; a merge then updates the list. We prove the representation correct, bound the work and depth of the merge phase, and measure a CUDA implementation on four NVIDIA GPUs against a control that copies the surviving vertices with the whole GPU at every level. On dense hulls the merge phase is 17 to 276 times faster with segment lists and the whole operator 3.9 to 19 times; on noisy data, where few vertices survive, the difference is small. In a differentiable soft rank, replacing torchsort's isotonic solver makes forward and backward 1.8 to 820 times faster, and the training step of a compact model with a Spearman loss 1.5 to 40 times. Code: https://github.com/LenaBarretta/torchisotonic
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.