Kinematic Fits as Hypergraph Programs: Sharing Sub-Fits Across Particle Assignments

In collider experiments, the detector does not say which photon came from which parent particle. To reconstruct an event such as $\chi_{cJ}\to\eta\eta\eta'$, analysts run a kinematic fit, a constrained least-squares adjustment that nudges measured momenta until energy-momentum conservation and known intermediate masses hold exactly. They run this fit separately for every way of assigning the detected photons to the decay tree, then keep the best one. The number of assignments grows factorially with the number of identical photons, yet most of the work is repeated. The same pair of photons, tested as an $\eta\to\gamma\gamma$ candidate, gets refitted inside every permutation that contains it. We propose to stop re-deriving shared pieces. Each candidate sub-decay is fitted once, and the event-level answer is assembled from those pieces with a search whose cost we can bound in advance from the structure of the event.

The bridge to database theory supplies both the algorithm's shape and its limits. In ontology-based data access, the field that studies how to compile logical background knowledge into executable database queries, there is a known gap between two kinds of compiled query. Unions of conjunctive queries behave like Boolean formulas with no reuse of sub-results. Non-recursive Datalog behaves like Boolean circuits that share sub-results, and circuits can be exponentially smaller (Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity). Permutation enumeration is the formula. Our claim is that photon assignment is, almost literally, the hypergraph program that this literature uses to classify query costs: a program that accepts when the relevant vertices can be covered by pairwise-disjoint hyperedges (Circuit Complexity Meets Ontology-Based Data Access). That match lets us import a cost classification, including the negative results.

Core Claim

Fix an event with $n$ reconstructed showers and tracks and a decay hypothesis. Build a hypergraph whose vertices are the showers and tracks and whose hyperedges are the candidate groups that pass a loose window around an intermediate-resonance mass. For example, a hyperedge might be a photon pair near the $\eta$ mass, or a $\pi^+\pi^-\eta$ triple near the $\eta'$ mass. A full assignment is an exact cover of the vertices by disjoint hyperedges. The question "does any assignment pass the $\chi^2$ cut" is therefore monotone in which hyperedges exist: adding a candidate can only add covers. That is the defining shape of a hypergraph program.

This framing makes two contributions. The first is algorithmic. Under the usual one-step linearization of the fit, the minimum $\chi^2$ for a cover splits into per-hyperedge terms plus one coupling term. Write $\chi^2_k$ for the local mass-constrained fit of hyperedge $k$, $P_k$ for its fitted composite four-momentum, $C_k$ for that composite's covariance, and $P_0$ for the known initial four-momentum. Then the minimum $\chi^2$ for a cover $S$ is

$$\chi^2(S) \;=\; \sum_{k\in S}\chi^2_k \;+\; \Big(\sum_{k\in S}P_k - P_0\Big)^{\!\top}\Big(\sum_{k\in S}C_k\Big)^{-1}\Big(\sum_{k\in S}P_k - P_0\Big).$$

This identity is exact for linear constraints and Gaussian errors. It holds because the fitted composites are independent Gaussian summaries of disjoint measurements. The first sum is additive, so every hyperedge is fitted once and reused. The second term is nonnegative, so $\sum_{k\in S}\chi^2_k$ is a valid lower bound. A best-first search over partial covers can therefore prune any branch whose additive part already exceeds the cut. A final full nonlinear refit of the few surviving covers removes the linearization error. The output is then identical to exhaustive enumeration, not an approximation of it.

The second contribution is theoretical. The cited work maps hypergraph programs of different topologies (degree, treewidth, tree shape) onto circuit classes from $NC^1$ up to $NP/\text{poly}$. It also shows that the existential depth of the ontology, meaning how many layers of unobserved "virtual" individuals the rules can create, triggers sharp jumps between these classes (Circuit Complexity Meets Ontology-Based Data Access; conference versions such as On the succinctness of query rewriting over shallow ontologies On the succinctness of query rewriting over shallow ontologies and Tree-like Queries in OWL 2 QL: Succinctness and Complexity Results Tree-like Queries in OWL 2 QL: Succinctness and Complexity Results). Unobserved intermediate resonances play exactly the role of those virtual individuals. A cascade like $\eta'\to\pi^+\pi^-\eta,\ \eta\to\gamma\gamma$ is a depth-2 witness. We conjecture, and will test, that the same split appears here. Single-level topologies with tight mass windows yield bounded-degree candidate hypergraphs whose covers can be counted and searched cheaply. Multi-level cascades with identical particles yield dense hypergraphs for which no shared, monotone evaluator of polynomial size should exist in general. In that regime, the right response is pruning with a provable bound, not a hoped-for clever circuit.

Relation to Prior Work

The physics analyses motivate the problem but do not attack it. Search for η1(1855) in χcJ→ηηη′ decays works with the identical-particle final state where enumeration is worst. The 6C fit in Measurements of the branching fractions of ψ(3686)→Σ¯0Λ+c.c. and χcJ(J=0,1,2)→ΛΛ¯ and the 4C selection in Partial wave analysis of J/ψ→γ(K+K−π+π−) treat each hypothesis as an independent per-event numerical fit. The cascaded anchoring used for the $\eta'$ mass in Measurement of the η′-Meson Mass using J/ψ→γη′ is the kind of multi-level tree our decomposition targets. That paper's precision also sets the standard that any speedup must not degrade.

The database theory supplies the method and its ceiling. We reuse the hypergraph-program abstraction from Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity. We take the lower-bound side seriously as well. The exponential blow-ups that Kikot et al. derive from monotone circuit bounds ( Exponential Lower Bounds and Separation for Query Rewriting) tell us not to promise polynomial cost for arbitrary events. Their observation that real ontologies avoid the structures that trigger those bounds (Long Rewritings, Short Rewritings Long Rewritings, Short Rewritings) suggests a measurable analogue: real decay topologies may rarely produce the worst-case hypergraphs. That is an empirical question we answer directly.

The work most similar in spirit, Circuit Complexity and Decompositions of Global Constraints, uses circuit size to reason about discrete constraint propagation. It has no continuous least-squares objective and no coupling term. The coupling term is precisely what our lower-bound search exists to handle.

Two learning papers constrain rather than supply the design. Deep Conservation: A Latent-Dynamics Model for Exact Satisfaction of Physical Conservation Laws found that an unconstrained model violated conservation by more than an order of magnitude more than a constrained-optimization variant. That supports keeping the exact fit in the loop rather than replacing it. Lorentz Group Equivariant Neural Network for Particle Physics addresses jet classification, not assignment, so it does not compete here.

Research Program

We will build an assignment engine in four stages. The first enumerates candidate hyperedges for a decay hypothesis using loose mass windows. The second fits each hyperedge once with its local mass constraint and caches $(\chi^2_k, P_k, C_k)$. The third runs a best-first exact-cover search ordered by the additive lower bound, evaluating the coupling term exactly at each completed cover. The fourth performs a full nonlinear refit of all covers whose linearized $\chi^2$ falls within a tolerance of the cut. For multi-level cascades, hyperedges are built bottom-up: an $\eta'$ candidate is a hyperedge over a $\pi^+\pi^-$ pair plus an already-cached $\eta$ composite. This is the direct analogue of a Datalog rule reusing a derived fact.

On the theory side, we will formalize the candidate hypergraph for a decay tree. We will then prove which known hypergraph-program classes it falls into as a function of identical-particle multiplicity, cascade depth, and maximum vertex degree; degree is controlled by how wide the mass windows are relative to resolution. We will also prove a worst-case bound on the covers the search expands in terms of these quantities. The theorems are only useful if they predict measured costs, so every regime they define will be checked against simulation.

Baselines

The naive reference is exhaustive permutation enumeration with a full nonlinear fit per assignment, which is what the cited BESIII analyses do. It defines ground truth for the best assignment and the selection decision, and it sets the cost ceiling.

The strongest practical competitor is enumeration with mass-window pre-cuts: discard any permutation in which some group falls outside its window before fitting. This is cheap, standard, and already removes most permutations in easy topologies. Our method must beat it on fits per event and wall time in the high-multiplicity regime while matching its decisions exactly.

The second competitor is a sequential cascade fit. It fits composites first, then runs a 4C fit on the composites, and keeps the best result without a global refit. This is fast but can pick a different assignment from the exhaustive fit. We will report how often its decision disagrees.

The third competitor is a generic branch-and-bound or integer-programming solver applied to the same minimum-$\chi^2$ exact-cover problem, using the same cached sub-fits. It isolates whether our topology-aware search adds anything beyond an off-the-shelf solver.

All methods will run on identical simulated events, in the same language and on the same hardware, with each method's window and tolerance parameters tuned on a shared validation split under an equal tuning budget.

Two ablations isolate the key ingredients. The first removes sub-fit caching, refitting each hyperedge on every visit. The second removes the lower-bound pruning, exploring all covers once candidates are cached.

No reported result was found on Lacuna for the timing or assignment accuracy of any kinematic-fit assignment method, so there is no published number to beat. "Beating" the strongest baseline therefore means three things together: identical selection decisions to exhaustive enumeration on every test event after the final refit, fewer full nonlinear fits per event than pre-cut enumeration, and a gap that grows with photon multiplicity.

Why not just…?

Why not just pre-cut on mass windows and enumerate? In topologies with few identical particles this may be nearly as good, and we expect to report that honestly. The threat weakens as multiplicity rises and as broad resonances force wide windows: each surviving permutation still repeats sub-fits that caching would share. The multiplicity sweep in our experiments locates the crossover. If no realistic topology lies past it, the practical claim fails and only the theoretical classification remains.

Why not just use a sequential cascade fit? It reuses composites, much as we do, but it drops the coupling term's effect on which cover wins. This can change the chosen assignment without anyone noticing. Our decomposition is the version of the same idea that keeps the coupling term exact. The disagreement rate between the sequential fit and exhaustive enumeration is the measurement that decides whether this matters in practice.

Why not just hand the assignment to an integer-programming or branch-and-bound solver? This is the most serious threat, because a good solver given our cached sub-fits and our lower bound might match the custom search. If it does, our contribution narrows to the decomposition identity and the complexity classification. Those would remain useful, since they tell the solver what to cache and when to expect blow-up. The head-to-head baseline above settles which case holds.

Why not just train a network to predict the assignment? A network could rank assignments quickly. However, the evidence in Deep Conservation: A Latent-Dynamics Model for Exact Satisfaction of Physical Conservation Laws is that unconstrained models violate conservation laws, and the analysis still needs an exact fit and an exact selection decision. A learned ranker could at most order our search. We will treat it as possible future work rather than a competitor, since we found no reported assignment result to compare against.

Proposed Experiments

BESIII and CLEO-c data are not public, so we will generate Monte Carlo samples for the topologies in the cited analyses:

Detector smearing will follow a parametrized calorimeter and tracker resolution model. We will add extra fake photon showers to sweep multiplicity and inject non-Gaussian tails to probe convergence failures.

The metrics are fits per event, wall time per event, the fraction of events whose selection decision and chosen assignment match exhaustive enumeration, correct-assignment rate against simulation truth, and signal efficiency against background rejection at fixed $\chi^2$ cuts.

As a physics-level sanity check, we will run an $\eta'$ mass extraction on the simulated mode-B sample with our engine and with exhaustive enumeration and require identical fitted mass shifts. The published reference precision is $M_{\eta'} = 957.793 \pm 0.054\,\text{(stat)} \pm 0.036\,\text{(syst)}$ MeV (Measurement of the η ′ -Meson Mass using J / ψ → γ η ′ Measurement of the η ′ -Meson Mass using J / ψ → γ η ′). We cannot reproduce that number without the real data, but any bias our method introduces must be negligible against the stated 36 keV systematic.

Two checks are decisive. The first is exactness: after the final refit, the engine must agree with exhaustive enumeration on every event in every topology. Any disagreement points to a bug in the tolerance logic, which is the same class of silent soundness and completeness failure that Benchmarking Ontology-Based Query Rewriting Systems found in every query-rewriting engine it tested. We will therefore also generate adversarial events near the $\chi^2$ cut boundary, in the spirit of that paper's automated test generation.

The second is predictive theory. For each simulated event we compute the candidate hypergraph's degree and cascade depth, and we check that the predicted regime (cheap versus exponential cover search) matches the measured number of expanded covers. A clear split by cascade depth and identical-particle count, mirroring the depth-1 versus depth-2 jump in the ontology setting, would confirm that the complexity map transfers. No split would mean the analogy is decorative, and we would report it as such.

References

  1. Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity
  2. Circuit Complexity Meets Ontology-Based Data Access
  3. On the succinctness of query rewriting over shallow ontologies
  4. Tree-like Queries in OWL 2 QL: Succinctness and Complexity Results
  5. Search for $η_{1}(1855)$ in $χ_{cJ}\toηηη^{\prime}$ decays
  6. Measurements of the branching fractions of ψ(3686)→Σ¯0Λ+c.c. and χcJ(J=0,1,2)→ΛΛ¯
  7. Partial wave analysis of J/ψ→γ(K+K−π+π−)
  8. Measurement of the<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:msup><mml:mi>η</mml:mi><mml:mo>′</mml:mo></mml:msup></mml:math>-Meson Mass using<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:mi>J</mml:mi><mml:mo>/</mml:mo><mml:mi>ψ</mml:mi><mml:mo>→</mml:mo><mml:mi>γ</mml:mi><mml:msup><mml:mi>η</mml:mi><mml:mo>′</mml:mo></mml:msup></mml:math>
  9. Exponential Lower Bounds and Separation for Query Rewriting
  10. Exponential Lower Bounds and Separation for Query Rewriting
  11. Long Rewritings, Short Rewritings
  12. Long Rewritings, Short Rewritings
  13. Circuit Complexity and Decompositions of Global Constraints
  14. Deep Conservation: A Latent-Dynamics Model for Exact Satisfaction of Physical Conservation Laws
  15. Lorentz Group Equivariant Neural Network for Particle Physics
  16. Improved measurement of the branching fractions for $J/ψ\toγπ^0$, $γη$ and $γη^\prime$
  17. Measurements of the branching fractions of ψ(3686)→Σ¯0Λ+c.c. and χcJ(J=0,1,2)→ΛΛ¯
  18. Measurement of the<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:msup><mml:mi>η</mml:mi><mml:mo>′</mml:mo></mml:msup></mml:math>-Meson Mass using<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:mi>J</mml:mi><mml:mo>/</mml:mo><mml:mi>ψ</mml:mi><mml:mo>→</mml:mo><mml:mi>γ</mml:mi><mml:msup><mml:mi>η</mml:mi><mml:mo>′</mml:mo></mml:msup></mml:math>
  19. Benchmarking Ontology-Based Query Rewriting Systems