# Exact inference in structured prediction

arXiv: https://arxiv.org/abs/1906.00451 · HTML: https://mlsanity.com/paper/1906.00451/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jun 2019.

## Built on by (most cited first, 6 of 6)

- [Exact Inference in High-order Structured Prediction](https://mlsanity.com/paper/2302.03236/) (2023)
- [Partial Inference in Structured Prediction](https://mlsanity.com/paper/2306.03949/) (2023)
- [A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy](https://mlsanity.com/paper/2102.08019/) (2021)
- [On the Fundamental Limits of Exact Inference in Structured Prediction](https://mlsanity.com/paper/2102.08895/) (2021)
- [Though Language Models Err While They Strive: Conformal Prediction for Self-Correcting Scientific Generation](https://mlsanity.com/paper/2607.16704/) (2026)
- [Provable Guarantees for Spectral Structured Prediction](https://mlsanity.com/paper/2609.18527/) (2026)

## Abstract (arXiv)

Structured prediction can be thought of as a simultaneous prediction of multiple labels. This is often done by maximizing a score function on the space of labels, which decomposes as a sum of pairwise and unary potentials. The above is naturally modeled with a graph, where edges and vertices are related to pairwise and unary potentials, respectively. We consider the generative process proposed by Globerson et al. and apply it to general connected graphs. We analyze the structural conditions of the graph that allow for the exact recovery of the labels. Our results show that exact recovery is possible and achievable in polynomial time for a large class of graphs. In particular, we show that graphs that are bad expanders can be exactly recovered by adding small edge perturbations coming from the ErdHos-R'enyi model. Finally, as a byproduct of our analysis, we provide an extension of Cheeger's inequality.