[Paper] A General Algorithm for Detecting Higher-Order Interactions via Random Sequential Additions

Source: arXiv - 2512.11793v1

Overview

Shamail and McWhite introduce a surprisingly simple geometric technique for uncovering how variables in a system interact—whether they amplify each other (synergy), duplicate each other’s information (redundancy), or act independently. By repeatedly adding features in random order and plotting their incremental contributions, characteristic L‑shaped patterns emerge that let practitioners quantify interaction strength on a single, intuitive scale.

Key Contributions

• L‑score metric: A continuous measure ranging from ‑1 (perfect synergy) through 0 (independence) to +1 (perfect redundancy).
• Random Sequential Additions (RSA) framework: A domain‑agnostic protocol that turns any performance‑oriented model into a source of interaction data by simply re‑ordering its inputs.
• Geometric visualisation: Pairwise contributions appear as 2‑D point clouds; L‑shaped clusters directly reveal the underlying interaction type and dominance of one feature over another.
• Higher‑order inference from pairwise data: Consistency across AB, AC, and BC pair clouds automatically surfaces three‑way (or higher) interaction structures without extra computation.
• Metric‑agnostic design: Works with any additive performance metric (accuracy, loss, reward, latency, etc.), making it applicable across ML, recommender systems, A/B testing, and even non‑ML pipelines.

Methodology

1. Define a contribution metric – e.g., change in validation accuracy, reduction in loss, or increase in click‑through rate when a feature is added.
2. Generate random permutations of the set of elements (features, actions, sensors, etc.) and evaluate the model incrementally along each permutation.
3. Record the marginal contribution of each element at the moment it is introduced. Over many permutations this yields a distribution of contributions for every element, conditioned on the elements that preceded it.
4. Plot pairwise contributions (element i on the x‑axis, element j on the y‑axis) across all trials.
   • Redundancy → points cluster along the x‑axis (first element carries the information, second adds nothing).
   • Synergy → points cluster along the diagonal or y‑axis (both elements need to be present to see any gain).
   • Independence → points spread uniformly, showing no order dependence.
5. Compute the L‑score by measuring the asymmetry of the L‑shape: the length of the “horizontal arm” versus the “vertical arm” yields a value in ([-1, 1]).
6. Infer higher‑order interactions by checking whether the pairwise L‑scores are mutually consistent (e.g., if AB and AC are synergistic but BC is redundant, this suggests a three‑way interaction pattern).

Results & Findings

• Synthetic benchmarks (e.g., (Y = X_1 X_2) for perfect synergy, (Y = X_1 + X_2) for independence, (Y = X_1) with (X_2 \approx X_1) for redundancy) produced clean L‑shapes and L‑scores of (-1), (0), and (+1) respectively, validating the metric.
• Real‑world datasets (image classification with overlapping visual cues, recommendation engines with correlated item features, and sensor fusion for autonomous driving) showed a spectrum of L‑scores, uncovering hidden redundancies (e.g., two color histograms that convey the same texture information) and synergistic triples (e.g., GPS + IMU + camera data).
• Dominance detection: The longer arm of the L indicated which feature consistently contributed more information, helping prioritize feature engineering or sensor placement.
• Scalability: Because only pairwise contributions are stored, memory grows quadratically with the number of elements, while the number of random sequences needed for stable estimates scales modestly (≈ 10 × |features| permutations sufficed in experiments).

Practical Implications

• Feature selection & pruning: Quickly spot redundant features that can be dropped without hurting performance, reducing model size and inference latency.
• Model debugging: Identify synergistic groups that may be under‑exploited by current architectures, suggesting new interaction layers or attention mechanisms.
• A/B testing optimisation: Apply RSA to incremental UI changes or rollout strategies to see whether two changes are truly independent or interfere with each other.
• Sensor suite design: For robotics or IoT, the L‑score can guide hardware budgets by revealing which sensors add unique value versus those that merely duplicate existing data.
• Explainability dashboards: The geometric L‑plots are intuitive visual tools for non‑technical stakeholders to understand why certain inputs matter more in combination than alone.

Limitations & Future Work

• Metric dependence: The method assumes an additive, monotonic contribution metric; non‑additive objectives (e.g., adversarial loss) may distort the L‑shape.
• Quadratic storage: Pairwise analysis becomes costly for thousands of features; future work could explore sketching or sampling strategies to keep the approach tractable at scale.
• Noise sensitivity: In highly stochastic environments (e.g., reinforcement learning with high variance rewards), many more permutations are needed to converge to stable L‑scores.
• Extension to continuous ordering: Current RSA works with discrete, non‑repeating sequences; adapting it to streaming or overlapping feature updates remains an open challenge.

Overall, the paper offers a refreshingly visual and metric‑agnostic toolkit for developers who need to untangle complex interaction webs without diving deep into information‑theoretic calculations. By turning random ordering into a diagnostic lens, it opens up new, low‑overhead pathways for feature engineering, system design, and interpretability across a wide range of tech domains.

Authors

• Ahmad Shamail
• Claire McWhite

Paper Information

• arXiv ID: 2512.11793v1
• Categories: cs.LG
• Published: December 12, 2025
• PDF: Download PDF