Track Finding as an Acyclic Join: Exact Dead-End Removal and Marginal Hit Scores for Dense Trackers

In a particle tracker, a charged particle leaves one hit on each detector layer it crosses. At the High-Luminosity LHC, each event contains around a hundred thousand hits from thousands of overlapping collisions, and track finding has to assemble those hits into particle trajectories while rejecting combinations that are random noise. This proposal treats that assembly as a database query. Each candidate track is a row in the result of a chain of joins: hit on layer 1, joined with a compatible hit on layer 2, joined with a compatible hit on layer 3, and so on. Compatibility is a small geometric or learned relation over consecutive hit triplets. Because the chain has the shape of a tree, a classical database algorithm due to Yannakakis can run one backward and one forward filtering pass. Those passes delete every hit and segment that cannot belong to any complete track, at a cost linear in the size of the compatibility tables. The same tree also lets us count, and weight, every complete track before enumerating any of them.

Physics tracking today mostly lives at two extremes. One is combinatorial search, typified by the Combinatorial Kalman Filter, which branches on every compatible next hit and can cost about 12 seconds of CPU per event. The other is learned clustering, such as transformers or Object Condensation, which gives up explicit structure and its guarantees. The structural view sits between the two. The core claim is that "can this hit or segment be completed into a full track, and in how many weighted ways?" can be answered exactly and cheaply. It is computed as a sum over the join tree, and it is a strong signal-versus-background discriminant in its own right: noise hits and fake segments are the ones with zero or low completion weight. The guarantee holds only while the constraint structure stays acyclic. The research question is how much tracking accuracy survives under that restriction, including across detector gaps, compared with the best clustering and combinatorial methods.

Core Claim

Fix a map of which detector layers can follow which, derived from simulation. It forms a directed acyclic graph over layers and covers barrel-to-endcap transitions. Each path through it defines a conjunctive query: a join whose variables are the hits $h_1,\dots,h_L$, one per layer along the path, and whose atoms are triplet relations $T_i(h_{i-1},h_i,h_{i+1})$ listing hit triples consistent with a helix locally. Consecutive atoms share two variables, so the query hypergraph is acyclic. Yannakakis-style full semi-join reduction therefore leaves exactly the hits and triplets that appear in at least one complete track, in time $O(\sum_i |T_i|)$. If each triplet carries a nonnegative quality weight $w_i$, for example the exponential of a negative local fit $\chi^2$, the same two passes compute for every hit $h$ on layer $j$

$$ s(h) = \sum_{\text{complete tracks } t \ni h} \;\prod_{i} w_i(t), $$

which is the total weight of all complete candidate tracks passing through $h$. Normalizing $s(h)$ gives an exact marginal "probability of belonging to a good track." The same passes also give the total number of candidates, so the system knows before enumerating anything whether the output will explode, and can tighten tolerances only where it would.

To handle detector gaps and dead modules, the proposal adds skip atoms that allow layer $i$ to connect to layer $i+2$. This keeps every per-path query acyclic, so the guarantees survive. That design choice responds directly to the main objection to discrete graph tracking, discussed below.

Position Relative to Prior Work

Two papers motivate the gap. The Tracking Machine Learning Challenge: Throughput Phase ran a throughput competition on TrackML. Its winner was a carefully tuned combinatorial algorithm with fixed search windows, reaching "execution times as low as 0.56 seconds per event" with "top solutions reaching over 94% accuracy." That suggests structured combinatorics is not obsolete, but those methods carry no guarantee against dead-end branching. Efficient ML-Assisted Particle Track Reconstruction Designs cites the combinatorial cost of Kalman-filter search and replaces it with flash-attention transformers. Those were validated only on simplified data (REDVID, and TrackML subsets of 10 to 500 tracks), and they depend on binning or on HDBSCAN post-clustering.

One paper constrains the design. An Object Condensation Pipeline for Charged Particle Tracking at the High Luminosity LHC shows that graph trackers based on classifying individual edges fracture tracks whenever a single edge is missed. In the barrel-endcap gap near $\eta\approx 2.5$, edge classification drops to near-zero perfect-match efficiency while Object Condensation keeps about 60%. That paper argues for continuous latent clustering. We take this negative result seriously. Our pipeline has no per-edge accept/reject decision before global reasoning, because semi-join reduction only removes segments with no complete extension anywhere, and skip atoms supply redundancy across gaps. Whether that is enough is an empirical question the experiments settle.

Three papers supply the method. Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees rewrites acyclic queries into SQL operator graphs with linear-in-input-plus-output guarantees and reports speedups up to 47,059× on graph queries. We reuse its reduction and aggregation-pushdown ideas but apply them to geometric hit relations instead of business or web data. Selective Use of Yannakakis' Algorithm to Improve Query Performance: Machine Learning to the Rescue shows that applying Yannakakis everywhere causes regressions in 60% of queries when the data is already clean, and fixes this with a learned selector. This warns us that full reduction may be wasted effort in sparse detector regions, so we measure that per region. A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries classifies when counting query answers is tractable. It tells us what not to do. If we projected away intermediate hits, for example counting distinct (seed, endpoint) pairs, or added a single global helix constraint over all hits, the structure would leave the tractable class. We therefore keep all hit variables in the output and restrict constraints to overlapping local windows. The weighted marginal is sum-product message passing on a chain, in the same family as the lineage-circuit evaluation that Challenges for Efficient Query Evaluation on Structured Probabilistic Data uses for probabilistic databases of bounded treewidth. That paper works on static road graphs, not detector hits.

What is new here is not the message-passing algebra. It is three things together. First, a formulation of track finding in which the constraint hypergraph is provably acyclic, including gap-crossing skips. Second, exact global dead-end removal as a preprocessing guarantee. Third, the use of exact completion marginals as a background discriminant, tested against the strongest learned and combinatorial trackers on the same data.

Research Program

The first component builds the relations. From TrackML training events we derive the layer-transition map and per-transition triplet tolerances in curvature and longitudinal slope. We build the tolerances in two variants: purely geometric windows, and windows from a small learned triplet scorer. Because the learned variant only changes the tables, not the query shape, the guarantee holds either way.

The second component is the reduction engine. It runs the backward and forward semi-join passes per path query in the layer map and computes candidate counts and marginals $s(h)$ and $s(\text{triplet})$. It then enumerates surviving tracks in descending weight and resolves hit sharing between tracks greedily by marginal.

The third component measures structure empirically. For each event we record the sizes of the triplet tables, the fraction removed by reduction, and the candidate count. We also record how these scale with pileup when TrackML events are overlaid or subsampled. This is where the approach could fail: if the triplet tables themselves grow superlinearly with pileup, the linear guarantee is linear in a quantity that is already too large. We will report that honestly.

The fourth component is a per-region switch, the analogue of SMASH. It is a small classifier over table-size statistics that decides whether full reduction is worth running or whether a forward-only pass suffices.

Baselines

The naive reference point is greedy forward-only extension: start from seeds and follow the best compatible next triplet. It uses the same triplet tables and has no global pass or marginals. It shows what the tables alone deliver.

The strongest learned competitor is the Object Condensation pipeline of An Object Condensation Pipeline for Charged Particle Tracking at the High Luminosity LHC. On TrackML it reports a Double Majority match efficiency of 95% for $p_T>0.9$ GeV and a fake rate of 1.7%, and it keeps about 60% perfect-match efficiency in the $\eta\approx 2.5$ gap region where edge classification falls to near zero. It is the strongest competitor because it was designed to fix exactly the brittleness a discrete join could inherit. We run it on the same TrackML split with the authors' configuration, report our own reproduction alongside the published numbers, and give it the same GPU budget for any learned components. Beating it means matching its 95% efficiency at $p_T>0.9$ GeV while lowering the fake rate below 1.7%, or exceeding 60% perfect-match efficiency in the gap region. Matching it on both while running on CPU at lower latency would also count.

The strongest combinatorial competitor is the throughput-phase winner reported in The Tracking Machine Learning Challenge: Throughput Phase, at 0.56 s per event and above 94% accuracy. We compare on the challenge's own score and on wall-clock time on matched CPU hardware. Beating it means equal or higher TrackML score at no greater time per event.

An edge-classification graph neural network with connected-components track building is included to reproduce the gap failure, so that our gap-region numbers have a direct contrast.

Three ablations isolate the key ingredients. The first removes the backward semi-join pass, which yields a cellular-automaton-like forward pass. The second replaces the exact marginals $s(h)$ with local triplet weights. The third removes the skip atoms. If the forward-only ablation matches the full system, the structural contribution is nil.

All methods use identical events, identical truth matching, and an equal hyperparameter-search budget for tolerances or thresholds, measured in validation-set evaluations.

Why not just…?

Why not just use Object Condensation, which already handles gaps? It is the real threat, and it may win on raw efficiency. Its remaining weaknesses are a 1.7% fake rate and about 60% gap efficiency, and it offers no statement that every reported track is geometrically complete or that no viable track was discarded. The decisive comparison is fake rate at fixed efficiency and gap-region efficiency, measured on identical data. If Object Condensation dominates on both, the honest conclusion is that exact marginals do not add discrimination, and the method's remaining value is cheap preprocessing. We would then test it as a hit filter in front of Object Condensation.

Why not just tune a combinatorial search with fixed windows, as the challenge winner did? Tuned windows clearly work: 0.56 s per event at above 94% accuracy. But nothing in that approach prevents branching into dead ends when occupancy rises. Our pileup-scaling experiment shows directly whether candidate counts and time per event grow more slowly with full reduction than with forward search on the same tables. If they do not, that alternative wins.

Why not just load hits into DuckDB and write the join in SQL? That would be the cheapest route. Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees reports native engines stalling on graph-shaped joins where rewriting gave up to 47,059× speedups, which suggests intermediate results blow up. We test this concretely by running the identical triplet-chain query natively in DuckDB, with Yannakakis+ rewriting, and in our engine. A general engine still does not produce the weighted marginals without custom aggregation, which is the part that matters for discrimination.

Isn't this just forward-backward message passing on a chain? Algebraically, yes, and we say so. The contribution is showing which tracking constraints keep the structure in the tractable class, how gap skips preserve that, and whether the resulting exact marginals beat learned scores. The marginal-versus-local-weight ablation answers the last point.

Proposed Experiments

All experiments use the TrackML dataset of about 10,000 simulated events with about 100,000 hits each, with the standard train/test split. Metrics are the TrackML score, Double Majority efficiency at $p_T>0.9$ GeV, fake rate, perfect-match efficiency binned in $\eta$ with focus on the $\eta\approx2.5$ gap, CPU time per event, and the fraction of hits and triplets removed by reduction.

Three checks decide the proposal. The first is fake rate at matched 95% efficiency against Object Condensation's reported 1.7%. The second is gap-region perfect-match efficiency against its reported roughly 60%, with and without skip atoms. The third is the growth of candidate count and time per event under pileup overlays, comparing full reduction with forward-only search on identical tables. We also report the per-region selector's regression rate against always-on reduction, mirroring the 60%-to-2–3% result of Selective Use of Yannakakis' Algorithm to Improve Query Performance: Machine Learning to the Rescue.

The proposal fails cleanly in either of two cases: the forward-only ablation equals the full system, or Object Condensation dominates on both fake rate and gap efficiency.