 |
ACTS
Experiment-independent tracking
|
|
ACTS
Experiment-independent tracking
|
Seeding by building and filtering a graph of hit doublets.
Classical ACTS seeding (Seeding) enumerates triplets of space points from a binned grid and cuts on the helix they describe. The combinatorics of that enumeration grow steeply with occupancy, and every triplet is judged in isolation.
GBTS inverts the order. It first builds a graph: nodes are space points, and a directed edge joins two space points on connected detector layers whenever the pair passes a set of cheap two-point cuts. Only then does it look for structure in that graph — long chains of mutually compatible edges — and turn the best chains into seeds. The expensive per-candidate work is therefore done once per edge rather than once per triplet, and the chain length itself becomes a quality signal.
The workflow has four stages, each documented below:
GBTS does not use the ACTS tracking geometry. It works on its own lightweight description: a flat list of GbtsLayer logical layers, each subdivided into eta bins.
Acts::Experimental::GbtsLayerDescription gives a layer its ID, its type (barrel or endcap), its sensor technology and its extent. For a barrel layer refCoord is the radius and the bounds are in \(z\); for an endcap it is the other way round. The ID is the caller's own numbering, and the algorithm never decodes it.
A ring of inclined modules is described by its slope in \(r\)- \(z\), along which its eta bins are cut. ActsExamples::GraphBasedSeedingAlgorithm takes the slope from the module planes of the tracking geometry when useLayerTilt is set.
A pixel barrel layer carries one more field, barrelOrder: the position of the layer in the inside-out ordering of the pixel barrel. Every other layer keeps the default -1, so the sign of the field also says whether a layer is a pixel barrel layer. If the caller leaves the field unset, Acts::Experimental::GbtsGeometry sorts the pixel barrel layers by refCoord and fills it in. Set it on every pixel barrel layer or on none of them, because the constructor rejects a partial ordering.
The cuts that were tuned on the pixel barrel read barrelOrder and nothing else: the two innermost-layer cuts of Building the graph ask how deep a layer sits. The \(\tau\) ratio tolerance comes from the layer pairs instead, see below. GBTS therefore runs on any layer numbering.
Which layer pairs may be joined by an edge is a list of Acts::Experimental::GbtsLayerConnection, each naming a source (outer) and a destination (inner) layer. Acts::Experimental::GbtsGeometry combines the layer descriptions with those connections and precomputes, for every pair of connected layers, which eta bin pairs are geometrically compatible with the allowed \(z_0\) range. The result is a bin group list — one inner bin together with all outer bins it may connect to — which serves as the graph builder's iteration schedule, ordered so that outer bins are processed before the inner bins that depend on them. The \(z_0\) range is widened on both ends by GbtsZ0Range::z0Tolerance.
The binning it worked out is readable back off the geometry, so a consumer that runs the same algorithm elsewhere does not have to recompute or pre-generate it: Acts::Experimental::GbtsGeometry::layerBinning gives a layer's Acts::Experimental::GbtsLayerBinning, the eta bins it owns in the global numbering, and Acts::Experimental::GbtsGeometry::binGroups the schedule itself. Eta bins are numbered globally and a layer's are contiguous, so the layers tile the numbering in order. This is what the GPU implementation is configured from.
Acts::Experimental::GbtsNodeStorage holds the graph nodes. Space points are fed in one at a time through insert, which takes plain scalars rather than an ACTS container:
As with Acts::CylindricalSpacePointGrid, an experiment can therefore fill the storage straight from its own space point EDM. Overloads exist for callers that already have \(r\) and \(\phi\), and for an Acts::ConstSpacePointProxy together with the columns carrying the layer index, cluster width and local \(y\) position.
Two different layer numbers meet here, and they are separate types:
| Type | What it is |
|---|---|
| GbtsExperimentLayerId | the layer id the experiment assign. Sparse and structured – the layer descriptions and connections are written in terms of it. The algorithm treats it as an opaque key. |
| GbtsLayerIndex | where that layer sits in one Acts::Experimental::GbtsGeometry, dense from zero. It indexes the geometry, and it is what a node carries. |
insert takes the index, because it is on the per-space-point path. Acts::Experimental::GbtsGeometry::layerIndex hands it out. It is the geometry's own numbering and is not derivable from the id.
insert assigns the node to an eta bin via GbtsLayer::getEtaBin and buffers it. finalize then sorts each bin by \(\phi\) and materialises the nodes into a space point container ordered by eta bin and then by \(\phi\), so that every eta bin is one contiguous range of node indices. A node index is therefore all that the rest of the algorithm needs to pass around.
The per-node data the graph builder reads lives in dynamic columns on that same container. It is packed rather than split into one array per field, because the innermost loop reads all of it together:
\(\tau = \cot\theta\). The infinite defaults disable the \(\tau\) cut entirely; only the optional machine-learning lookup table narrows them (see Machine-learning assisted acceptance). Alongside it sits the bookkeeping the graph builder writes:
Each eta bin carries its node range plus the \(\phi\) index used by the sliding window. The \(\phi\) index duplicates entries shifted by \(\pm 2\pi\) near the wrap-around, so the window never has to handle wrapping:
The builder walks the bin groups from Geometry and layer connections. For each inner bin it prepares one sliding window in \(\phi\) per connected outer bin, whose half-width grows with the radial separation of the two bins — the further apart they are, the more a low- \(p_T\) track can bend between them. It then loops over the inner nodes, and for each one scans only the outer nodes inside the window.
A candidate pair \((n_1, n_2)\) becomes an edge if it survives, in order:
| Cut | Meaning |
|---|---|
| \(\Delta r > \) minDeltaRadius | the two hits are radially separated enough for \(\tau\) to be meaningful |
| \(\lvert\tau\rvert < \) maxAbsTau | within the detector's angular acceptance |
| \(\tau\) inside both nodes' windows | per-node acceptance from the ML lookup table |
| \(z_0\) inside [minZ0, maxZ0], and \(z\) at the outer radius inside the ROI | the pair points back to the luminous region |
| \(\lvert\kappa\rvert\) below an \(\eta\)-dependent bound | consistent with the \(p_T\) threshold |
with \(\tau = \Delta z/\Delta r\), \(z_0 = z_1 - r_1\tau\) and the curvature proxy \(\kappa = (\phi_2-\phi_1)/\Delta r\).
Surviving pairs are appended to a flat edge array:
The three fit parameters p are \(\{\exp(-\eta),\ \kappa,\ \phi_1 + \kappa r_1\}\).
Because the inner node's edges are written contiguously, the edges incoming to a node form a contiguous range, recorded in that node's GbtsNodeEdgeInfo. Immediately after creating an edge \((n_1, n_2)\), the builder scans the edges incoming to \(n_2\) — that is, edges \((n_2, n_3)\) — and links the two whenever the implied triplet is consistent: the \(\tau\) ratio, the \(\phi\) continuation and the curvature difference must all agree within tolerance. The \(\tau\) ratio tolerance comes from the layer pairs: a triplet is held to the looser of tauRatioCutInner of its inner pair and tauRatioCutOuter of its outer pair, see Acts::Experimental::GbtsLayerConnection. Acts::Experimental::assignAdaptiveTauRatioCuts fills them from the layers: wider for a pair that skips a pixel barrel layer or, as the outer pair, leaves the pixel barrel, and wider again for a pair with a strip layer. With useSumRatioCut the three differences, each divided by its own cut, may not add up to more than sumRatioCutMax, which rejects a pair that is marginal in all three at once. For pixel-barrel triplets an optional validateTriplets step also fits a circle through the three points and cuts on \(d_0\) and \(p_T\). Each edge stores up to kGbtsMaxEdgeNeighbours (6) such neighbours.
Two further cuts apply on the innermost pixel barrel layers, where the combinatorics are worst. Each cut has its own depth limit on the barrelOrder of the inner layer, and a negative limit switches the cut off:
With the edge graph built, every edge gets a level: the length of the longest chain of linked edges going outwards from it, so an edge that nothing further out links to is at level 1. An edge only links to edges further in, which are always created after it, so a single pass over the edges in creation order settles every level. Chains longer than maxChainLength edges are left unsettled and take no part in the extraction.
An edge with no settled edge further in exactly one level up is a root, the innermost edge of a chain. An edge further in that is more than one level up belongs to a longer chain outwards elsewhere and does not continue the chain.
Every edge yields at most one seed candidate: the best fitted path from it inwards to a root, each step going to an edge one level up, i.e. along the longest chain outwards of that root. The paths are found by a depth first search from every edge, fitted on the way by Acts::Experimental::GbtsTrackingFilter, and edges and branches that cannot reach a root far enough in are skipped. Nothing depends on the order the edges are visited in. This is the seed extraction of the traccc GPU GBTS.
The filter is a small Kalman filter over the chain. It carries a state of two independent parts — a quadratic in the bending plane and a linear \(z\) versus \(r\) model — and at each step extrapolates to the next node, forms a \(\chi^2\) residual for each part and rejects the branch if either exceeds its threshold (maxDChi2X, maxDChi2Y).
Every accepted hit adds a fixed reward addHit to the branch score, minus its two \(\chi^2\) increments weighted by weightX and weightY. The score therefore counts the hits on the chain, discounted by how badly they fit the circle and the \(z\) versus \(r\) line. Of the complete paths from an edge, the one with the best score per space point wins, and a path that fails the filter is dropped.
The result is a set of seed candidates. These are reduced in two passes:
The surviving candidates are written to the output Acts::SeedContainer, with node indices translated back to the caller's own space point indices.
When useClusterWidthCuts is enabled, GBTS narrows the per-node \(\tau\) window using a pre-trained lookup table indexed by pixel cluster width. The cluster a track leaves in a pixel module grows with the incidence angle, so the width alone constrains \(\cot\theta\) before any pairing is attempted.
The table carries two sets of bounds per width bin: one for clusters comfortably inside the module, and one for clusters within moduleEdgeTolerance of the module edge, where the cluster may be truncated and the width therefore underestimates the angle. Wide clusters in the pixel endcap are dropped entirely (maxEndcapClusterWidth).
The cuts that build and link the doublets live on GbtsGraphBuilder::Config, which GraphBasedSeedingAlgorithm takes as graphConfig and exposes to Python as GbtsGraphBuilderConfig:
| Option | Stage | Effect |
|---|---|---|
| minPt | Building the graph | drives the curvature and \(\phi\)-window bounds |
| minDeltaRadius, maxAbsTau | Building the graph | doublet acceptance |
| minZ0, maxZ0, doubletFilterRZ | Building the graph | luminous-region cuts on the doublet |
| cutDPhiMax, cutDCurvMax | Building the graph | edge-to-edge linking tolerances |
| useSumRatioCut, sumRatioCutMax | Building the graph | bound on the summed linking tolerances, against pairs marginal in all three |
| tauRatioCut | Building the graph | \(\tau\) scale of the validateTriplets high-pT check. The linking cut comes from Acts::Experimental::GbtsLayerConnection |
| validateTriplets, d0Max | Building the graph | circle fit on pixel-barrel triplets |
| maxEdgesPerSP | Building the graph | cap on the edge array per space point (30 by default); exceeding it costs efficiency |
| matchBeforeCreate, tauRatioPrecut, matchBeforeCreateMaxBarrelOrder | Building the graph | require a compatible incoming edge before creating one, down to that depth in the pixel barrel |
| z0HistogramMaxBarrelOrder, z0Resolution | Building the graph | \(z_0\) histogram cut, down to that depth in the pixel barrel |
The rest are on GraphBasedTrackSeeder::Config:
| Option | Stage | Effect |
|---|---|---|
| nMaxPhiSlice | Graph nodes | sets the \(\phi\) slice width, and with it the base sliding-window width the graph uses |
| maxChainLength | Chain levels | longest chain of edges taken into account |
| minSeedLevel | Seed extraction | chain length a candidate must reach |
| postFitCurvatureFactor | Seed extraction | tighter curvature bound on the fitted chain, as a factor on the filter's maxCurvature; values below 1 does nothing |
| addTriplets, maxAbsEtaAddTriplets | Seed extraction | allow shorter chains within an \(\eta\) range |
| hitShareThreshold | Seed extraction | fraction of shared hits above which a candidate is a clone |
| maxSeedSplitEta, maxInvRadDiff | Seed extraction | seed splitting |
| useClusterWidthCuts, tauLookupTable | Machine-learning assisted acceptance | cluster-width based \(\tau\) windows |
| maxEndcapClusterWidth, moduleHalfLengthY, moduleEdgeTolerance | Machine-learning assisted acceptance | cluster-width acceptance and module-edge handling |
useStripConnections, which takes the strip layer connections from the connector file instead of the pixel ones, is read where the file is loaded and so sits on GraphBasedSeedingAlgorithm::Config itself.
GbtsTrackingFilter::Config separately controls the chain-following filter of seed extraction:
| Option | Effect |
|---|---|
| sigmaX, sigmaY | measurement resolution in the bending plane and along \(z\) |
| maxDChi2X, maxDChi2Y | per-step \(\chi^2\) ceilings; a branch exceeding either is dropped |
| addHit, weightX, weightY | the reward and the two \(\chi^2\) weights in the branch score |
| sigmaMS, radLen | multiple-scattering inflation added before each extrapolation |
| maxCurvature, maxZ0 | track-level bounds checked after each update |
A GPU implementation of the same algorithm, using an equivalent struct-of-arrays layout, lives in the traccc plugin under Traccc/device/common/include/traccc/gbts_seeding.
1.15.0