Hypergraph cycle enumeration for efficient inference of planted $k$-XOR with smooth trade-off

We introduce hypergraph cycle enumeration (HCE), a simple spectral framework for detecting and recovering planted signals in noisy hypergraph inference problems. In this work, we focus on planted noisy $k$-XOR, a canonical average-case constraint satisfaction problem (CSP) closely connected to tensor PCA, refutation of random CSPs, and computational-statistical gaps in high-dimensional inference. However, our algorithm can be applied to a broader category of tensor PCA problems. We show that HCE yields recovery with a hierachical threshold (determined by a parameter $l$), matching the Kikuchi spectral threshold up to $k$-dependent constants while giving a direct cycle-counting interpretation of the mechanism. Both theoretically and empirically, HCE achieves comparable recovery behavior to Kikuchi methods while using a substantially smaller matrix representation, leading to significant runtime and memory improvements in the sparse regimes we test.