High-energy cosmic rays are observed indirectly by detecting the extensive air showers initiated in Earth's atmosphere. The interpretation of these observations relies on accurate models of air shower physics, which is a challenge and an opportunity to test QCD under extreme conditions. Air showers are hadronic cascades, which eventually decay into muons. The muon number is a key observable to infer the mass composition of cosmic rays. Air shower simulations with state-of-the-art QCD models underpredict the observed muon content; this is called the Muon Puzzle. The origin of this discrepancy has been traced to the composition of secondary particles in hadronic interactions. The muon discrepancy starts at the TeV scale, which suggests that this change in hadron composition is observable at the Large Hadron Collider. An effect that can potentially explain the puzzle has been observed at the LHC, but more experimental data in the forward region and with future oxygen beams at the LHC is needed to fully understand the impact. I will review what we currently know about the Muon Puzzle and which measurements at the LHC may point to a solution.