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 change of coordinates, so the lifting preserves the infimum, critical points, local extrema (modulo the GNN-parameter fiber), and Hessian inertia of the free-logit problem. Joint gradient flow then induces the preconditioner $I+J{J}^{\top }$: the GNN cannot enlarge the feasible set, but it can add dissipation $\Vert J^{\top }\nabla \ell {\Vert }_2^2$. For a two-layer branch this extra coupling is four-hop local. We also show that every finite critical point of a nonconstant multilinear objective is a saddle, and that a unique MAP gap $\Gamma$ makes conditional-expectation rounding exact once the relaxed gap falls below $\Gamma$; residual gradient flow and joint gradient descent then obey explicit $O(1/t)$ and $O(1/k)$ rates in a small-gap region, with an improved bound under residual alignment. Experiments on synthetic MRFs, UAI 2022 benchmarks, and Physical Cell Identity (PCI) problems evaluate this residual geometry at scale.