Physicists who fit a model directly to individual collision events avoid the information loss of histograms. They then face an awkward question: does the fitted model actually describe the data? In an unbinned fit, the likelihood value at its maximum says almost nothing about goodness of fit. So analysts usually fall back on histograms to check the model, which reintroduces the binning they had avoided. A natural binning-free check is to draw a large sample from the fitted model and pair every real event with a simulated event so that the total distance between partners is as small as possible. This pairing is a minimum-cost bipartite matching, and its cost is a Wasserstein, or "earth mover's," distance. The matching also shows where the model fails, because each real event that lands far from its partner points to a mismodeled region.
This note proposes making that test certified and bit-for-bit reproducible. It borrows the core insight of a recent result in deterministic parallel complexity. Parallel Complexity of Geometric Bipartite Matching proves two things for planar point sets. Finding the exact minimum Euclidean matching needs $\Omega(n \log n)$ bits of arithmetic precision. Getting within an additive $\delta = 1/\text{poly}(n)$ of the optimum is achievable deterministically in NC, the class of problems solvable in polylogarithmic parallel time on polynomially many processors. It does so by rounding points to a polynomial grid and breaking ties with a fixed, seed-free weighting that makes the optimal matching unique. Our central claim is that this precision barrier does not matter for inference. The rounding error on the test statistic can be made far smaller than the statistic's own sampling noise using only $O(\log n)$ bits per coordinate. The practical consequence is concrete. Using exact integer costs and a fixed tie-breaking rule, one can compute a goodness-of-fit statistic, its bootstrap p-value, and a per-event residual map that are provably within a stated tolerance of the exact answer. These outputs are also identical across GPUs, thread counts and collaborations.
Core Claim
Take $n$ data events $x_i$ in a two-dimensional observable space, such as a Dalitz plane rescaled to the unit square, and $n$ events $y_k$ sampled from the fitted density. The statistic is
$$T = \min_{\sigma} \frac{1}{n}\sum_{i=1}^{n} \lVert x_i - y_{\sigma(i)} \rVert,$$
where $\sigma$ ranges over one-to-one pairings of data events with model events.
Rounding every coordinate to a grid of spacing $h$ moves each point by at most $h/\sqrt{2}$. Each pair distance therefore changes by at most $\sqrt{2}h$, so the statistic computed on the rounded points, $T_h$, satisfies
$$|T - T_h| \le \sqrt{2}\, h .$$
If $s_n$ is the standard deviation of $T$ when the model is correct, then choosing $h \ll s_n$ makes rounding statistically invisible. We expect $s_n$ to shrink only polynomially in $n$, which is the part to verify. If so, $h = 1/\text{poly}(n)$ suffices, which means $O(\log n)$ bits, in contrast to the $\Omega(n\log n)$ bits Bhore et al. show are needed for exactness.
On the rounded instance all costs are integers, so the optimal value is exact and does not depend on the order in which parallel threads add numbers. We add a small deterministic tie-breaking weight, in the spirit of the planar isolating weights Bhore et al. use. Their proof shows that near-optimal matchings of planar point sets combine into a planar graph, which is why a planar weighting suffices. With this weight the optimal matching itself is unique, so the residual map is canonical as well as the number.
Current practice falls short on each of these guarantees. Double-precision parallel solvers can return different optimal pairings from run to run whenever ties occur. Entropy-smoothed and neural approximations carry no worst-case error bound.
Research Program
The work has three parts.
Theory. We will derive $s_n$, or tight bounds on it, for the Euclidean matching statistic under the null hypothesis in dimensions one to three. This yields an explicit bit budget $b(n, \epsilon)$: the number of bits per coordinate that guarantees the rounding error contributes at most a fraction $\epsilon$ of the null spread. We will also bound how that error propagates into bootstrap p-values.
Algorithm. We will not implement the determinant-based NC algorithm literally. Its processor counts are theoretical. Instead we take its two ingredients, grid rounding and seed-free tie-breaking, and plug them into a practical exact integer solver: cost-scaling auction or network simplex, parallelized on GPU. This split is deliberate. The complexity result supplies the guarantee that the approximation regime is sound. The engineering supplies speed.
Extensions. We will extend the analysis to the settings Bhore et al. leave open that physics actually needs. The first is three-dimensional observables, where the planarity-based tie-breaking fails and we test lexicographic integer perturbations instead. The second is weighted events, which cover signal and background yields in an extended fit and turn the problem into transportation rather than perfect matching. The third is angular coordinates of the form (rapidity, azimuth), which require periodic boundary handling.
Baselines
Naive reference. This is what analysts do today: a binned Pearson chi-square on the Dalitz plane or dijet mass plane after the unbinned fit, with bin sizes chosen by the usual rule of thumb. Beating it means higher power against localized mismodeling at the same false-positive rate. Unbinned fits exist because binning loses information. Dalitz plot analysis of D_s+ → K+K−π+ needed unbinned fitting to resolve interfering resonances, which is exactly the regime where a binned check should be weakest. No reported goodness-of-fit power result was found on Lacuna for this dataset.
Strongest competitor: energy distance. We regard the energy-distance, or kernel two-sample, permutation test as the strongest competitor. It is unbinned, and it is embarrassingly parallel with $O(n^2)$ work. With care over summation order it can also be made reproducible. Both tests will receive the same data and model samples, the same number of bootstrap replicas, and the same GPU budget. The kernel bandwidth will be tuned on a held-out null simulation. The matching test beats it only if it shows higher power at equal size on at least one realistic class of mismodeling. The candidate class is a narrow resonance with a shifted mass or a wrong interference phase. A second way to win would be if the matching residual map localizes the defect measurably better than the kernel witness function.
Approximate optimal-transport solvers. The first is entropy-regularized Sinkhorn matching at several regularization strengths. The second is the learned approximation of Particle Graph Autoencoders and Differentiable, Learned Energy Mover's Distance. That paper trains a graph network to predict earth mover's distance between jets and reports "relative difference of only -0.003% on average and a standard deviation of 1.6%" against exact values. Our certified statistic should have worst-case error below $\sqrt{2}h$ by construction. The comparison is whether a 1.6% spread in the statistic measurably distorts p-values near the rejection threshold.
Exact reference. A double-precision exact solver serves as ground truth for accuracy, run-to-run reproducibility, and wall-clock time.
Ablations. Two ablations isolate our ingredients. Removing the tie-breaking weight measures how often residual maps differ across runs. Removing grid rounding, keeping floating-point costs, measures nondeterminism in both value and pairing.
Why not just…?
Why not just use GPU map-reduce, as unbinned fits already do? The likelihood sum parallelizes event by event, and the 36-million-event fit in Direct neutrino-mass measurement based on 259 days of KATRIN data shows this works for fitting. A matching couples every event to every other, so it cannot be split into independent per-event terms. In one dimension, however, optimal matching reduces to sorting. There our method adds nothing beyond reproducible sorting, and we will say so for KATRIN-like spectra.
Why not just use a seeded random perturbation instead of deterministic tie-breaking? This is a genuine threat. Bipartite Perfect Matching in Pseudo-Deterministic NC shows that randomized algorithms can already return a canonical output with high probability, and a fixed seed gives reproducibility in practice. The only advantage of seed-free weights is that they need no agreed seed and fail on no input. We will measure the cost of both. If they cost the same, the choice is cosmetic. The core contribution is then the precision certificate, not the derandomization.
Why not just use Sinkhorn or a neural surrogate? Both are fast and differentiable. Finding NEEMo fits a neural transport potential by minimax optimization, and its authors note the method is slow and hard to run in real time. More importantly, neither kind of method bounds its error on anomalous inputs. The p-value distortion experiment above decides whether this matters in practice.
Why not just use energy distance and skip matching entirely? This may win on power. The proposal is structured so that a loss here is informative: if energy distance is uniformly more powerful, the matching test survives only as a localization tool, and we report it that way.
Proposed Experiments
Dalitz simulation. We generate $D_s^+ \to K^+K^-\pi^+$ Dalitz samples of 14,400 events from the isobar model with the fit fractions reported by CLEO-c. We then fit deliberately wrong models, for example one with the $f_0(1370)$ component dropped, which carries a 4.3% fit fraction in the published fit, or one with a shifted phase. We compare the power of every test against the size of the defect.
LHC Olympics. On The LHC Olympics 2020 datasets, we fit smooth background models to the two-dimensional distributions of the R&D and Black Box samples. The question is whether residual maps flag the injected resonance. The only reported number available here is the resonance found in Black Box 1 at 3.7 TeV with 2.8σ global significance by Particle Graph Autoencoders, which serves as context rather than a like-for-like baseline. Black Box 2, which contains pure background, checks the false-positive rate.
Decisive checks. Five checks decide the outcome. First, the empirical null spread of the statistic must match the derived bit budget. Second, the certified statistic must be bitwise identical across hardware configurations. Third, bootstrap p-values must be unchanged, within Monte Carlo error, relative to the exact double-precision reference. Fourth, the matching test must beat binned chi-square on power, and its standing against energy distance determines how strong the paper's claim is. Fifth, we record the wall-clock time for 1,000 bootstrap replicas at $n = 10^4$ and $10^5$.
References
- Parallel Complexity of Geometric Bipartite Matching
- Dalitz plot analysis of<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:msubsup><mml:mi>D</mml:mi><mml:mi>s</mml:mi><mml:mo>+</mml:mo></mml:msubsup><mml:mo>→</mml:mo><mml:msup><mml:mi>K</mml:mi><mml:mo>+</mml:mo></mml:msup><mml:msup><mml:mi>K</mml:mi><mml:mo>−</mml:mo></mml:msup><mml:msup><mml:mi>π</mml:mi><mml:mo>+</mml:mo></mml:msup></mml:math>
- Particle Graph Autoencoders and Differentiable, Learned Energy Mover's Distance
- Direct neutrino-mass measurement based on 259 days of KATRIN data
- Bipartite Perfect Matching in Pseudo-Deterministic NC
- Finding NEEMo: Geometric Fitting using Neural Estimation of the Energy Mover's Distance
- The LHC Olympics 2020 a community challenge for anomaly detection in high energy physics