We consider the problem of inference in higher order undirected graphical models with binary labels. We formulate this problem as a binary polynomial optimization problem and propose several linear programming relaxations for it. We compare the strength of the proposed linear programming relaxations theoretically. Finally, we demonstrate the effectiveness of these relaxations by performing a computational study for two important applications, namely, image restoration and decoding error-correcting codes. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This work was supported by the Air Force Office of Scientific Research [Grant FA9550-23-1-0123]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0776 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0776 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .