Probably Approximately Correct Maximum A Posteriori Inference

About

Computing the conditional mode of a distribution, better known as the $\mathit{maximum\ a\ posteriori}$ (MAP) assignment, is a fundamental task in probabilistic inference. However, MAP estimation is generally intractable, and remains hard even under many common structural constraints and approximation schemes. We introduce $\mathit{probably\ approximately\ correct}$ (PAC) algorithms for MAP inference that provide provably optimal solutions under variable and fixed computational budgets. We characterize tractability conditions for PAC-MAP using information theoretic measures that can be estimated from finite samples. Our PAC-MAP solvers are efficiently implemented using probabilistic circuits with appropriate architectures. The randomization strategies we develop can be used either as standalone MAP inference techniques or to improve on popular heuristics, fortifying their solutions with rigorous guarantees. Experiments confirm the benefits of our method in a range of benchmarks.

Matthew Shorvon, Frederik Mallmann-Trenn, David S. Watson · 2026

Related benchmarks

Task	Dataset	Result
MAP Inference	Twenty Datasets	accidents1.7	15
MAP Inference	accidents 50% query size	Runtime (seconds)1060	5
MAP Inference	adult 50% query size	Runtime (s)6.75	5
MAP Inference	baudio 50% query size	Runtime (s)1980	5
MAP Inference	bnetflix 50% query size	Runtime (s)1390	5
MAP Inference	book 50% query size	Runtime (s)2230	5
MAP Inference	connect4 50% query size	Runtime (s)105	5
MAP Inference	dna 50% query size	Runtime (s)501	5
MAP Inference	jester 50% query size	Runtime (seconds)707	5
MAP Inference	kdd 50% query size	Runtime (s)60.3	5