Tighter relaxations for MAP-MRF optimization via Singleton Arc Consistency
Asaf Lev-Ran, Pavel Arkhipov, Vladimir Kolmogorov · 2026
Read Tighter relaxations for MAP-MRF optimization via Singleton Arc Consistency by Asaf Lev-Ran, Pavel Arkhipov, Vladimir Kolmogorov (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-13392.txt.
Introduction
Asaf Lev-Ran, Pavel Arkhipov and Vladimir Kolmogorov propose a tighter way to solve MAP-MRF inference. That task chooses discrete variable values that minimise a sum of single-variable and pairwise costs. The usual approach solves a linear programming relaxation and then strengthens it by adding clusters of variables. Their technique finds such clusters by running singleton arc consistency, a constraint-propagation check, on a related constraint problem. Experiments indicate the new tightening beats the earlier frustrated-cycle search of Sontag and colleagues.
Catalog record
| CREATOR | Asaf Lev-Ran, Pavel Arkhipov, Vladimir Kolmogorov |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52471 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.13392
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Tighter relaxations for MAP-MRF optimization via Singleton Arc Consistency Asaf Lev-Ran, Pavel Arkhipov, Vladimir Kolmogorov Abstract We consider the MAP-MRF inference task, that is, minimizing a function of discrete variables represented as a sum of unary and pairwise terms. A prominent approach for tackling this NP-hard problem in practice is to solve its natural LP relaxation and then iteratively tighten the relaxation by adding clusters . Based on some theoretical observations, we propose a new technique for identifying such clusters. It works by running the Singleton Arc Consistency algorithm in a certain CSP instance. Experimental results indicate that the new tightening technique outperforms the previous approach by [ SCL12 ] that searches for frustrated cycles . Our code will be made available at https://github.com/vnk-ist/MAP-MRF/ . 1 Introduction This paper focuses on the problem of minimizing functions of discrete variables represented as a sum of unary and pairwise terms: \min_{x\in\mathcal{X}}f[\theta](x),\qquad\quad f[\theta](x)=\sum_{v\in V}\theta_{v}(x_{v})+\sum_{\{u,v\}\in E}\theta_{uv}(x_{u},x_{v}) (1) The problem is specified by a graph G=(V,E) , a discrete set of labels \mathcal{X}_{v} for each node v\in V , unary costs \theta_{v}:\mathcal{X}_{v}\rightarrow\mathbb{R} for each v\in V , and pairwise costs \theta_{uv}:\mathcal{X}_{u}\times\mathcal{X}_{v}\rightarrow\mathbb{R} for each (u,v)\in E . The set of labelings is defined as \mathcal{X}=\prod_{v\in V}\mathcal{X}_{v} . Under a probabilistic interpretation, this problem is known as MAP inference in MRFs or CRFs , i.e., maximum a posteriori inference in Markov random fields or conditional random fields, in the computer vision and machine learning communities [ BKR11 ] . In the constraint programming and constraint satisfaction communities, problem ( 1 ) is known as Weighted CSPs or Cost Function Networks [ CdGSF+10 ] . MAP-MRF optimization was a prominent approach in computer vision before the deep-learning era, especially for problems that could be formulated as discrete labelings with spatial smoothness, such as image segmentation, stereo, restoration, and object labeling [ SZS+08 , BKR11 ] . More recently, MRF/CRF ideas are often used as structured components coupled to learned representations rather than as standalone hand-engineered models. Examples include learned potentials and neural message passing for stereo matching [ GWL24 ] , learned MRF layers over discrete image tokens for efficient text-to-image generation [ JGR+24 ] , SAM-based area matching formulated as an MRF energy minimization problem solved by graph cuts [ ZZ24 ] , neuralized MRFs for interaction-aware human trajectory prediction [ FHL25 ] , and voxel-adaptive message passing for deformable CT registration [ ZZW+25 ] . Applications outside computer vision include sequence labeling tasks such as named entity recognition, part-of-speech tagging, and chunking [ MH16 , LBS+16 , WQHS21 ] , protein design [ TAA+13 , AAB+14 ] , and recent deep protein-design methods that incorporate MRF-style components [ RYBZ24 , RZZ24 ] . Related pairwise MAP formulations also arise in Markov-logic knowledge-base reasoning [ FLCS23 ] , while the binary case is widely studied in operations research as QUBO or UBQP [ KHG+14 , GKHD22 ] . LP relaxations and tightening Although problem ( 1 ) is NP-hard in general, it has been demonstrated that many practical instances can be solved to optimality. A prominent approach is cluster-based tightening [ SMG+12 ] which starts by solving an LP relaxation of ( 1 ) and then iteratively tightens the relaxation by adding clusters of nodes. The success of this approach depends crucially on which clusters are added. Early approaches chose clusters from a fixed dictionary, e.g. the set of all triplets (3-cycles in the graph) [ SMG+12 , KP08 , BNK11 ] . [ SCL12 ] showed how to avoid fixed dictionaries by proposing an algorithm for computing “frustrated cycles”, while showing that after adding these cycles the dual objective can be improved. The main contribution of this paper is a new algorithm for computing clusters. It is based on running a Singleton Arc Consistency (SAC) algorithm on a certain CSP instance. We prove several properties of this algorithm. Roughly speaking, they can be formulated as follows: (1) If SAC produces a cluster then after adding this cluster either the dual objective can be improved or some fractional vertices are cut off from the local polytope. (2) If the instance has at least one frustrated cycle then SAC will find a cluster. For more formal statements we refer to Sections 3 and 5 . Our experimental results show our SAC tightening procedure outperforms the method in [ SCL12 ] by consistently finding the same or better bounds. Other related work [ SJ07 ] proposed to tighten relaxations of MAP-MRF problems by adding cutting planes that generalize odd-cycle inequalities for MAX-CUT. Their separation algorithm works in the primal domain, and requires a (fractional) primal solution of the relaxation. In contrast, we focus on tightening techniques that use only dual solutions (“reparameterization”), since relaxations of large-scale problems are often solved via message-passing techniques that work only in the dual domain. Tightening techniques require introducing high-order terms, which can become expensive when the number of labels is large. [ SGJ08 ] address this issue by proposing to use coarse partitions on labels for high-order terms. Note that this approach is orthogonal to the question studied in this paper. [ Wer09 ] presented an approach based on the language of Constraint Satisfaction Problems (CSPs), by showing that all unsatisfiable CSP subproblems could potentially tighten the relaxation. However, no concrete algorithm for identifying such subproblems was proposed. In this work we use a particular CSP algorithm, namely Singleton Arc Consistency (SAC). This algorithm was recently used in [ DWdG23 ] for identifying superreparameterizations that improve the lower bound. At each iteration they replace current vector \theta with another vector {\overline{\theta}} that satisfies f[{\overline{\theta}}](x)\leq f[\theta](x) for all labelings x , and guarantees that {\overline{\theta}} gives a better lower bound than \theta . This approach is not comparable with the tightening techniques that we consider: it can be computationally less costly since it does not introduce any high-order terms, but it may also decrease the minimum \min_{x\in\mathcal{X}}f[\theta](x) (which would never be “undone” in later iterations). Note that a simpler Arc Consistency (AC) algorithm has been used for approximately solving the standard LP relaxation of ( 1 ) (without tightening). In particular, an AC-based algorithm for establishing the Virtual Arc Consistency has been given in [ CdGS+08 , CdGSF+10 ] , and is similar to the Augmenting DAG algorithm [ Sch76 , Wer09 ] . There are also alternative tightening approaches based on more expensive computational tools such as semidefinite programming relaxations, see e.g. [ DKS22 ] . We limit the scope of this work to LP relaxations, which arguably can scale to larger problems. A survey of tightening techniques for MAP-MRF optimization can be found in [ KKP19 ] . 2 Background The cluster-based tightening approach [ SMG+12 ] starts with the objective function in ( 1 ) and then repeats the following procedure: • Add some zero-valued higher-order terms to the current objective, leading to the following optimization problem: \min_{x\in\mathcal{X}}f[\theta](x),\qquad\quad f[\theta](x)=\sum_{\alpha\in\mathcal{F}}\theta_{\alpha}(x_{\alpha}) (2) Here \mathcal{F}\subset 2^{V} is a set of non-empty subsets of V , called factors . For a factor \alpha\in\mathcal{F} we denote \mathcal{X}_{\alpha}{\stackrel{{\scriptstyle\mbox{\tiny\tt~def~}}}{{=}}}\prod\limits_{v\in\alpha}\mathcal{X}_{v} , and for a labeling x\in\mathcal{X} we let x_{\alpha}\in\mathcal{X}_{\alpha} be the restriction of x to \alpha . By construction, \theta_{\alpha}(x_{\alpha})=0 for all \alpha\in\mathcal{F},x_{\alpha}\in\mathcal{X}_{\alpha} with |\alpha|\geq 3 . • Approximately