The Computational Intractability of Marginal MAP Inference

277 concepts215 papers1 proposal

In probabilistic reasoning, we often want to find the most likely state of the world given some evidence. Depending on what we are trying to predict, this goal manifests as one of two tasks: Most Probable Explanation (MPE), where we find the most likely assignment for all unobserved variables, or Maximum A Posteriori (MAP) inference, where we look for the most likely assignment for a specific subset of query variables.

While they sound nearly identical, MAP inference (often called Marginal MAP or MMAP) is fundamentally more difficult than MPE. As Shimony et al. noted, optimizing a joint distribution over a subset of variables introduces severe computational bottlenecks that do not exist when optimizing over the full set of variables. Understanding why this happens requires looking at how mathematical operations interact with graph structures.

The Core Bottleneck: Non-Commutativity

To understand why Marginal MAP is so challenging, consider a network with three types of variables: query variables $Q$ (the ones we care about), nuisance or hidden variables $H$ (the ones we do not care about but must account for), and observed evidence $E$.

To find the most likely configuration of $Q$, we must first sum out (marginalize) the hidden variables $H$, and then maximize over $Q$:

$$\arg\max_Q \sum_H P(Q, H, E)$$

If we were solving an MPE problem, there would be no hidden variables to sum out; we would simply compute $\max_Q \max_H P(Q, H, E)$. Because the maximization operator commutes with itself ($\max_Q \max_H = \max_H \max_Q$), a solver can optimize variables in whatever order is most computationally convenient. This allows us to push the maximization operators deep into the graph's factorization, solving the problem via local dynamic programming.

However, as Marinescu et al. and Sharma et al. emphasize, summation and maximization do not commute:

$$\max_Q \sum_H P(Q, H, E) \neq \sum_H \max_Q P(Q, H, E)$$

Because these operations cannot be reordered, we lose the freedom to choose an optimal elimination order. We are strictly forced to eliminate all hidden variables $H$ via summation before we can begin maximizing over the query variables $Q$.

The Destruction of Graph Topology

This restriction on the elimination order has devastating consequences for the underlying graph structure. In standard probabilistic inference, algorithms exploit topological features—like low treewidth or tree-like structures—to break down global calculations into cheap, local operations.

The forced elimination order of Marginal MAP completely destroys this structural advantage. As Park et al. demonstrated, MAP inference remains NP-complete even on polytrees (directed graphs with no undirected cycles), where standard marginalization takes linear time. When we are forced to sum out the nuisance variables first, it creates dense, artificial dependencies among the remaining query variables. This process moralizes and connects previously independent branches of the network, blowing up the effective treewidth of the problem.

As a result, the complexity of Marginal MAP frequently escalates to the $NP^{PP}$ complexity class, as detailed by Mauá. This makes it significantly harder than standard NP-complete optimization problems. Even in deep architectures explicitly designed to guarantee linear-time marginal inference, such as Sum-Product Networks, Mei proved that exact MAP inference remains NP-hard and exceptionally difficult to approximate within any reasonable factor.

Algorithmic Strategies for Coping with Intractability

Because exact global optimization is generally unfeasible, researchers have developed specialized paradigms to bypass the elimination bottleneck.

Heuristic Search Space Exploration

Instead of evaluating the entire state space, solvers can frame Marginal MAP as a heuristic search problem. Marinescu et al. designed anytime best-first search algorithms over AND/OR search spaces. By computing incremental upper and lower bounds, these methods avoid evaluating the expensive likelihood of every path, allowing the solver to find high-quality solutions within strict memory limits. Similarly, Sun utilized dynamic weighting A* search to navigate the massive combinatorial space of variable assignments efficiently.

Continuous Relaxations

Another prominent strategy is to transform the discrete optimization problem into a continuous one. Sontag et al. leveraged dual Linear Programming (LP) relaxations to approximate MAP configurations, optimizing over continuous blocks of variables using coordinate descent.

While relaxations are technically approximations, they perform remarkably well in practice. Meshi et al. provided a theoretical explanation for this success, demonstrating that the objective functions we use to train structured prediction models naturally encourage these LP relaxations to be "tight" (exact) when evaluated on real-world data.

Key Foundational Work

A new algorithm for finding MAP assignments to belief networks (1990) — contributed 4 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 226 papers
  2. Version 1 · 2026-10-04 · 292 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_map_inference_complexity_8599092d,
  title = {MAP inference complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/map-inference-complexity/rdr_8599092d082a47fe981198f731561d83},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_map_inference_complexity_8599092d_v2,
  title = {MAP inference complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/map-inference-complexity/rdr_8599092d082a47fe981198f731561d83/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake