WorksPhysics and Astronomy
Deployment of a Graph-Based Track Seeder for the ATLAS Phase-II Tracking Upgrade
Abstract
The ATLAS experiment is undergoing significant detector, computing and software upgrades for the High-Luminosity LHC (HL-LHC). The ongoing software modernisation is essential to leverage future processing technologies and ensure maintainability throughout the operation of the experiment, while meeting the tracking performance requirements for physics and reducing the compute needs for event reconstruction. To meet these goals, the ATLAS Collaboration is adopting the ACTS (A Common Tracking Software) toolkit, an experiment-independent software for charged-particle track reconstruction. Using ACTS in the ATLAS reconstruction software at the HL-LHC facilitates the development and integration of new algorithms while promoting thread safety, high performance, and code maintainability. This document describes the development and recent deployment of a Graph-Based Track Seeder (GBTS), its underlying methodology, and its expected tracking performance at the HL-LHC.
© 2026 CERN for the benefit of the ATLAS Collaboration. Reproduction of this article or parts of it is allowed as specified in the CC-BY-4.0 license.
Introduction
In recent years, the ATLAS Collaboration has worked on an extensive detector [1, 2] and software upgrade programme [3, 4] to cope with the high instantaneous luminosity and the number of simultaneous proton-proton interactions per bunch crossing () expected at the High-Luminosity LHC (HL-LHC) [5], which are expected to be significantly higher than in LHC Run 3. An entirely new all-silicon Inner Tracker (ITk) [6, 7] will be installed during Long Shutdown 3, which started in 2026. It is composed of Pixel and Strip subsystems extending the tracking coverage to from the Run 1–3 coverage of . Together with the detector upgrade, a software modernisation is also taking place. One of the areas of major activity is track reconstruction, where components from the ACTS (A Common Tracking Software) toolkit [8] are being integrated and deployed in the ATLAS reconstruction software [9, 10]. The main goal is meeting the tracking performance requirements for physics while reducing the compute requirements for event reconstruction and improving code maintainability.
The reconstruction of tracks from charged particles traversing the ITk is an essential part of event reconstruction at the ATLAS experiment [11]. This is achieved through a sequence of algorithms. First, a clustering algorithm groups signals from individual channels within the ITk Pixel and Strip subdetectors that are likely to originate from the same particle. These groups of signals are referred to as clusters. The clusters are then converted into three-dimensional space points, which are used by the track seeding algorithm to form track seeds and provide initial estimates of the track parameters. These seeds serve as the initial state for the track-finding algorithm, which is based on a Combinatorial Kalman Filter [12, 13]. The algorithm extends the seeds into track candidates by incorporating all clusters compatible with the predicted trajectory. In the track reconstruction chain considered so far, the resulting track candidates are subsequently processed by an ambiguity-solving algorithm to resolve cases where tracks share multiple clusters, reject low-quality candidates, and perform the final track fit. This dedicated step is no longer required in the ACTS-based reconstruction chain, which makes use of precise material modelling, accurate magnetic-field maps and refined calibrations during track finding, so that high-precision track parameters are obtained without the separate, computationally demanding refit previously required.
Since Run 1, track seeds produced with seeding algorithms have consisted of triplets of space points from the silicon parts of the Inner Detector. To study the expected tracking performance of ATLAS at the HL-LHC and validate the new track reconstruction algorithms ahead of Run 4 data taking, the triplet seeding algorithm has been adapted to account for the expected HL-LHC conditions and the specific geometry of the ITk. In the higher pile-up environment, the combinatorial complexity increases substantially, leading to a low seed purity, i.e. a large fraction of seeds that lead to duplicate or fake track candidates. The track finding has to reject these candidates, which increases the compute requirements for track reconstruction. While further developments and optimisation were carried out in the most recent years, the seeding algorithm remained among the most computationally expensive components of the tracking chain, at the same level as the track-finding algorithm [14].
The Graph-Based Track Seeder (GBTS) is a seeding algorithm designed for high pile-up conditions such as those expected during ATLAS Run 4 data taking. This algorithm was originally developed as fastrack as part of the TrackML challenge [15], and then implemented in the ATLAS software. Subsequently, it was reimplemented directly in ACTS to ensure seamless integration with the toolkit and consistency with the ATLAS software’s broader adoption of ACTS for track reconstruction.
The algorithm addresses the issue of high combinatorics through two complementary approaches. First, it reduces the seeding runtime by applying computationally inexpensive selection criteria, exploiting the assumption that prompt tracks originate from the beam spot. Second, it constructs a graph connecting compatible space points, enabling the production of high-purity seeds. Through these two improvements, GBTS reduces the computing time substantially without compromising track reconstruction efficiency and quality and has been deployed as part of the ATLAS offline track reconstruction.
The note is structured as follows: § 2 provides a description of the GBTS seeding strategy for prompt tracks, its implementation in ACTS and deployment in the ATLAS reconstruction software; § 3 summarises the obtained track reconstruction performance using GBTS; finally § 4 concludes the note.
The Graph-Based Track Seeder algorithm
The GBTS algorithm operates on nodes and edges aiming at constructing chains of nodes likely corresponding to true particle tracks. Nodes are objects created from space points: they hold the positions of the original clusters in the ATLAS global reference frame coordinates1, their -width2 and a layer index. A layer in GBTS is a grouping of modules corresponding to a geometrical structure in the detector geometry. Edges are connections between two compatible nodes. Nodes and edges are used in the different stages of the GBTS algorithm, corresponding to graph construction, seed finding and seed filtering.
Graph construction
The GBTS algorithm aims to create high-purity seeds. To achieve this, connections are first restricted to pairs of space points belonging to physically compatible detector layers, thereby preventing the formation of invalid edges. A layer connection table is created using Monte Carlo simulated samples of 100 000 single-muon events with GeV. This momentum gives the largest multiple scattering expected for valid tracks, so the table also covers all layer pairs of tracks at higher . Figure 1 shows this table for the ITk geometry, with a zoom on the inner Pixel region. The algorithm described in this note uses only Pixel space points and hence restricts the layer connection table to the Pixel subdetector.
Figure 1. The layer connection table for GBTS of the ITk detector, with a subset of the ITk Pixel subdetector highlighted. The geometrical layers, which correspond to the grouping of detector modules, are represented in grey. The direct connections between layers are illustrated as blue lines, while the connections that skip a layer are shown with orange lines. Only nodes on valid layer pairs are checked for compatibility to form an edge.
The width of the cluster in the -direction provides an additional criterion for edge selection. Under the assumption that particles originate within a given -window around the interaction point, the cluster width defines a valid -interval for each node. Only edges connecting nodes with overlapping -intervals are retained.
At this point, for each layer, nodes are placed into fixed-width bins and sorted in ascending order. The algorithm then makes use of the valid layer connections and creates pairs of bins that are compatible with a straight line from the interaction point.
A window in is defined by the maximum curvature (i.e. minimum ) allowed by a track traversing from the inner to outer bin. This window is then centred at each inner node such that only a small subset of connections to outer nodes need to be checked. Edges are constructed from nodes within the window, imposing additional constraints based on the allowed range for track parameters (mainly transverse and longitudinal impact parameters and transverse momentum) and cluster -widths. Figure 2 illustrates a window derived from a node on the innermost layer. This process continues for all windows and -bin pairs, between connected layers. With all the edges created, any that share common nodes are linked into connected components. Those with fewer nodes than a configured minimum are discarded.
Figure 2. Illustration of the sliding window projected from an inner node to reduce the region for valid connections to outer nodes.
Seed finding and filtering
The seed extraction from the graph follows two steps.
First, a Cellular Automaton (CA)-based seed finding [16] is used to extract longer chains of connected edges from the graph. This works as follows: the CA starts by assigning an integer value of 1, called the level, to every edge in the graph. Then, starting from the outermost edges, it looks at the connected neighbouring edges towards the interaction point and updates its edge level. If at least one of those neighbours has the same level, the level of the outer edge is increased by 1. This update is repeated until no more updates occur. The level of an edge corresponds to the number of edges in the longest chain that extends inward from that edge, including the edge itself. The outermost edges are used as the starting points to construct seed candidates by connecting only edges that have a level of exactly 1 below the previous one. This approach is very effective at removing dead-end branches from the seed candidates. An example of the edge level update procedure and edge tracing is illustrated in Figure 3.
Figure 3. The Cellular Automaton (CA) updates the levels of the edges by 1 for each iteration if a neighbouring edge closer to the interaction point has the same level. After three iterations, the levels are updated to the values marked with the yellow circles. This is used to reject branches that are unlikely to be produced by a true particle trajectory.
The seed candidates produced by the CA are then passed to a Kalman Filter (KF) [12]. The KF follows the seed candidates and scores each node according to its compatibility with an approximate helix trajectory. Early rejection is performed on seed candidates for which the value of at least one node exceeds a predefined threshold. The remaining seed candidates are scored based on the number of nodes in the seed and their value. Seed candidates for which the majority of nodes are shared with a higher-scoring candidate are removed. Finally, a seed splitting step is used for seed candidates with four or five space points within . This samples three space points from these chains and checks their compatibility; if there is a discrepancy larger than a set value, the seed is split. In the case of candidates with four space points, this can result in seeds of three space points. The number of seeds that go through this process is small in general but can help with regaining a small amount of efficiency. The final collection of seed candidates is used to estimate the initial track parameters for the track-finding algorithm. This estimate relies on the first, middle and last space points of each seed, thereby using the full radial extent of the seeds.
Results
All components of the GBTS algorithm have been implemented in ACTS and then deployed in the ATLAS ACTS-based track reconstruction chain [10]. This section summarises the expected seeding and tracking performance and compares it with that obtained using the Run 3-based tracking chain, hereafter referred to as Legacy [11]. The results are obtained using a event sample at TeV with pile-up ranging from 190 to 210, labelled as . The number of pile-up interactions is randomly sampled from a Poisson distribution with a mean corresponding to the average pile-up. The production of the sample is modelled using the Powheg Box v2 [17, 18, 19, 20] generator at NLO with the NNPDF3.0nlo [21] PDF set and the parameter3 fixed to [22], with GeV used for the top-quark mass. The events were interfaced to Pythia 8.307 [23] to model the parton shower, hadronisation, and underlying event, with parameters following the A14 tune [24] and using the NNPDF2.3lo set of PDFs [25]. The decays of bottom and charm hadrons were performed by EvtGen 2.1.1 [26]. Only events with a single leptonic -boson decay have been considered.
The performance of the seeding algorithm is assessed using different figures of merit that rely on associating seeds with stable charged particles produced by the Monte Carlo simulation. A seed is considered matched to a particle if more than half of its measurements originate from this particle, and the fraction of particles matched to at least one seed is defined as the seeding efficiency. Only particles with GeV within the detector acceptance (), stemming from the hard-scatter interaction, are considered.
Figure 4(a) and Figure 4(b) show the seeding efficiency of GBTS in the ACTS-based track reconstruction chain and of the Legacy triplet seeder. While the Legacy seeding algorithm produces triplet seeds both in the ITk Pixel and Strip subdetectors, the GBTS algorithm is currently configured to find seeds only using Pixel space points. In both configurations, Pixel seed candidates are required to contain at least four space points. The Legacy seeding algorithm achieves this by requiring a fourth space point to confirm the trajectory of an initial triplet seed. The Strip seeds of the Legacy configuration help to recover seeding efficiency within when too few measurements are available in the Pixel detector to form a valid seed. This can occur, for example, when a particle traverses a gap between Pixel modules or when the charge deposited in the active detector area is insufficient to activate a readout channel. GBTS allows for a higher seeding efficiency at , as a result of looser requirements in the edge construction compared to the ones for triplet formation in the Legacy seeder. As a function of , the GBTS seeding efficiency is about 1% to 1.5% below that of the Legacy seeder over the entire range.
Figure 4. Comparison of the expected seeding efficiencies as a function of (a) and (b) for events at for hard-scatter particles with GeV for the GBTS algorithm and the Legacy triplet seeding algorithm.
The average number of matched seeds per particle obtained with GBTS and the Legacy triplet seeding algorithm is shown in Figure 5, highlighting the difference between the two strategies: while the Legacy seeding algorithm by construction produces multiple triplet seeds per particle (from both Pixel and Strip subdetectors), GBTS allows for one long seed per track, where the connected space points are likely to be associated with the same particle. Reconstructing multiple seeds per particle can be beneficial to robustness against detector inefficiencies and misalignment. The impact of these effects using the GBTS algorithm is under evaluation.
Figure 5. Comparison of the average number of matched seeds per particle as a function of for events at for hard-scatter particles with GeV for the GBTS algorithm and the Legacy triplet seeding algorithm. For the latter, the numbers are shown separately for Pixel-only (PPP), Strip-only (SSS) and both combined.
Analogously to the seeding efficiency, the tracking efficiency is defined as the fraction of charged particles associated with a reconstructed track. The differences in seeding efficiency are also reflected in the tracking efficiency, as shown in Figure 7(a) and Figure 7(b).
Figure 7. Comparison of the expected tracking efficiencies as a function of (a) and (b) for events at for hard-scatter particles with GeV for the ACTS-based and Legacy tracking chains.
Figure 6 shows the rate of fake tracks as a function of . The fake rate for the ACTS-based tracking chain is compatible with the one of the Legacy tracking, and well under control; the fake rate obtained with GBTS is larger than the Legacy one for , corresponding to the region of higher seeding and tracking efficiency.
Figure 6. The rate of fake tracks as a function of for events at for the ACTS-based and Legacy tracking chains.
The resolution on track parameters is estimated from reconstructed tracks associated with charged particles. Figure 8(a) and Figure 8(b) show the expected resolution of the transverse () and longitudinal () impact parameters for tracks in events at . The ACTS-based tracking chain exhibits a slightly worse resolution compared to the Legacy chain. The ACTS-based tracking chain is still under active development. At the time of writing, several important features aimed at improving impact parameter resolution were still being developed, including optimal calibration of measurement positions and covariances. Further investigations are ongoing to improve the parameter estimation for long seeds, which are more common at . In this region, the seed parameters, estimated using the first, middle and last space points, are subject to biases arising from larger multiple-scattering contributions and the non-zero radial component of the magnetic field towards the endcaps.
Figure 8. Comparison of the transverse (a) and longitudinal (b) impact parameter resolutions as a function of for events at for hard-scatter particles with GeV for the ACTS-based and Legacy tracking chains.
Finally, Table 1 summarises the timing results for the Legacy tracking chain and for two ACTS-based configurations that differ only in the seeding algorithm. For the Legacy chain, the time is split into the combined seeding and track finding step, and the ambiguity solving step. These are defined by an ACTS implementation of a Legacy-like triplet seeder [27] and the GBTS algorithm described in this note. Both ACTS-based workflows achieve a substantial speed-up compared with the Legacy reconstruction chain. The ACTS-based strategy requires no dedicated ambiguity-solving step, because the track finding already resolves cluster–track ambiguities and suppresses duplicates. It also requires no dedicated track-fitting step, historically part of ambiguity solving, because the track finding already outputs fitted tracks. In addition, GBTS reduces the seeding time by approximately a factor of five compared with the Legacy-like triplet seeder, while maintaining physics performance close to that of the Legacy configuration, as demonstrated in the previous sections. In total, the ACTS-based chain with GBTS is faster than the Legacy chain by a factor of about 13, and faster than the ACTS-based chain with the triplet seeder by a factor of about 2. Furthermore, owing to the increased seed purity and reduced amount of seeds, the track finding time decreases slightly, within the uncertainty of the measurement.
| Workflow | Seed method | Seeding | Track finding | Ambiguity solving | Sum |
| Legacy | Triplet Pixel + Strip | 5100 | 3500 | 8600 | |
| ACTS-based | Triplet Pixel | 860 | 530 | – | 1390 |
| ACTS-based | GBTS Pixel | 180 | 490 | – | 670 |
Table 1. Per-event timings for seeding, track finding and ambiguity solving. Measured on events with , single-threaded, on an Intel Xeon Gold 6326 at 2.90 GHz. The uncertainty on the measurements is 5%, corresponding to the observed timing variations on the machine.
Conclusion
This note summarises the deployment of the Graph-Based Track Seeder (GBTS) for ATLAS track reconstruction at the HL-LHC. It describes the algorithm implemented within the ACTS toolkit and demonstrates its performance following integration into the ATLAS track reconstruction software. Both tracking and computational performance are presented, demonstrating a substantial reduction in computing time while maintaining high tracking efficiency, good track-parameter resolutions and a low fake rate. Since GBTS significantly improves computational performance while maintaining broadly comparable physics performance to the ACTS-based implementation of the Legacy-like triplet seeder, it has been selected as the default seeding algorithm for ATLAS offline track reconstruction. The improved computational performance provides greater flexibility for further optimisation of the ACTS-based tracking chain. Ongoing work focuses on addressing the remaining differences with respect to the Legacy tracking chain, in particular by reducing the fake rate, improving the impact parameter resolutions and better understanding the observed performance differences. Overall, GBTS has demonstrated strong computational performance while achieving broadly comparable physics performance, making it a promising candidate for track reconstruction in the HL-LHC era.
References
- [1]ATLAS Collaboration, Letter of Intent for the Phase-II Upgrade of the ATLAS Experiment, CERN-LHCC-2012-022, LHCC-I-023, 2012, URL: https://cds.cern.ch/record/1502664 (cit. on p. 2).
- [2]ATLAS Collaboration, ATLAS Phase-II Upgrade Scoping Document, CERN-LHCC-2015-020, LHCC-G-166, 2015, URL: https://cds.cern.ch/record/2055248 (cit. on p. 2).
- [3]ATLAS Collaboration, ATLAS HL-LHC Computing Conceptual Design Report, CERN-LHCC-2020-015, LHCC-G-178, 2020, URL: https://cds.cern.ch/record/2729668 (cit. on p. 2).
- [4]ATLAS Collaboration, ATLAS Software and Computing HL-LHC Roadmap, CERN-LHCC-2022-005, LHCC-G-182, 2022, URL: https://cds.cern.ch/record/2802918 (cit. on p. 2).
- [5]O. Aberle et al., High-Luminosity Large Hadron Collider (HL-LHC): Technical design report, CERN-2020-010, 2020, url: https://cds.cern.ch/record/2749422 (cit. on p. 2).
- [6]ATLAS Collaboration, ATLAS Inner Tracker Pixel Detector: Technical Design Report, ATLAS-TDR-030; CERN-LHCC-2017-021, 2017, URL: https://cds.cern.ch/record/2285585 (cit. on p. 2).
- [7]ATLAS Collaboration, ATLAS Inner Tracker Strip Detector: Technical Design Report, ATLAS-TDR-025; CERN-LHCC-2017-005, 2017, URL: https://cds.cern.ch/record/2257755 (cit. on p. 2).
- [8]X. Ai et al., A Common Tracking Software Project, Comput. Softw. Big Sci. 6 (2022) 8, arXiv: 2106.13593 [physics.ins-det] (cit. on p. 2).DOI
- [9]ATLAS Collaboration, Software and computing for Run 3 of the ATLAS experiment at the LHC, Eur. Phys. J. C 85 (2025) 234, arXiv: 2404.06335 [hep-ex] (cit. on p. 2), Erratum: Eur. Phys. J. C 85 (2025) 907.DOI
- [10]ATLAS Collaboration, Initial improvements to the CPU performance for the ACTS-based track reconstruction software for ATLAS during the HL-LHC, ATL-PHYS-PUB-2024-017, 2024, URL: https://cds.cern.ch/record/2912217 (cit. on pp. 2, 5).
- [11]ATLAS Collaboration, Expected tracking performance of the ATLAS Inner Tracker at the High-Luminosity LHC, JINST 20 (2025) P02018, arXiv: 2412.15090 [hep-ex] (cit. on pp. 2, 5).DOI
- [12]R. Frühwirth, Application of Kalman filtering to track and vertex fitting, Nucl. Instrum. Meth. A 262 (1987) 444 (cit. on pp. 2, 5).DOI
- [13]R. Mankel, A Concurrent track evolution algorithm for pattern recognition in the HERA-B main tracking system, Nucl. Instrum. Meth. A 395 (1997) 169 (cit. on p. 2).DOI
- [14]ATLAS Collaboration, Software Performance of the ATLAS Track Reconstruction for LHC Run 3, Comput. Softw. Big Sci. 8 (2024) 9, arXiv: 2308.09471 [hep-ex] (cit. on p. 2).DOI
- [15]S. Amrouche et al., The Tracking Machine Learning Challenge: Throughput Phase, Comput. Softw. Big Sci. 7 (2023) 1, arXiv: 2105.01160 [cs.LG] (cit. on p. 2).DOI
- [16]I. Abt, D. Emelianov, I. Kisel and S. Masciocchi, CATS: a cellular automaton for tracking in silicon for the HERA-B vertex detector, Nucl. Instrum. Meth. A 489 (2002) 389 (cit. on p. 4).DOI
- [17]S. Frixione, G. Ridolfi and P. Nason, A positive-weight next-to-leading-order Monte Carlo for heavy flavour hadroproduction, JHEP 09 (2007) 126, arXiv: 0707.3088 [hep-ph] (cit. on p. 6).DOI
- [18]P. Nason, A new method for combining NLO QCD with shower Monte Carlo algorithms, JHEP 11 (2004) 040, arXiv: hep-ph/0409146 (cit. on p. 6).DOI
- [19]S. Frixione, P. Nason and C. Oleari, Matching NLO QCD computations with parton shower simulations: the POWHEG method, JHEP 11 (2007) 070, arXiv: 0709.2092 [hep-ph] (cit. on p. 6).DOI
- [20]S. Alioli, P. Nason, C. Oleari and E. Re, A general framework for implementing NLO calculations in shower Monte Carlo programs: the POWHEG BOX, JHEP 06 (2010) 043, arXiv: 1002.2581 [hep-ph] (cit. on p. 6).DOI
- [21]NNPDF Collaboration, R. D. Ball et al., Parton distributions for the LHC run II, JHEP 04 (2015) 040, arXiv: 1410.8849 [hep-ph] (cit. on p. 6).
- [22]ATLAS Collaboration, Studies on top-quark Monte Carlo modelling for Top2016, ATL-PHYS-PUB-2016-020, 2016, url: https://cds.cern.ch/record/2216168 (cit. on p. 6).
- [23]T. Sjöstrand et al., An introduction to PYTHIA 8.2, Comput. Phys. Commun. 191 (2015) 159, arXiv: 1410.3012 [hep-ph] (cit. on p. 6).DOI
- [24]ATLAS Collaboration, ATLAS Pythia 8 tunes to 7 TeV data, ATL-PHYS-PUB-2014-021, 2014, URL: https://cds.cern.ch/record/1966419 (cit. on p. 6).
- [25]NNPDF Collaboration, R. D. Ball et al., Parton distributions with LHC data, Nucl. Phys. B 867 (2013) 244, arXiv: 1207.1303 [hep-ph] (cit. on p. 6).
- [26]D. J. Lange, The EvtGen particle decay simulation package, Nucl. Instrum. Meth. A 462 (2001) 152 (cit. on p. 6).DOI
- [27]C. Allaire et al., Seed Finding in the Acts Software Package: Algorithms and Optimizations, tech. rep., 2024, URL: https://cds.cern.ch/record/2943308 (cit. on p. 9).







