ReMAP: Lossless Residual Neural Lifting for Scalable MAP Inference in Arbitrary-Order Markov Random Fields

Maximum a posteriori inference in a finite Markov random field is generally NP-hard. We study an instance-wise optimizer that minimizes the exact multilinear energy under product marginals. The canonical parameterization adds a GNN output to free per-node logits. This residual bypass is a global cha