There have been a number of attempts to derive the set of quantum non-local correlations from reasonable physical principles. Here we introduce $tilde{Q}$, a set of multipartite supra-quantum correlations that has appeared under different names in fields as diverse as graph theory, quantum gravity and quantum information science. We argue that $tilde{Q}$ may correspond to the set of correlations of a reasonable physical theory, in which case the research program to reconstruct quantum theory from device-independent principles is met with strong obstacles. In support of this conjecture, we prove that $tilde{Q}$ is closed under classical operations and satisfies the physical principles of Non-Trivial Communication Complexity, No Advantage for Nonlocal Computation, Macroscopic Locality and Local Orthogonality. We also review numerical evidence that almost quantum correlations satisfy Information Causality.