# Faster Exact MPE and Constrained Optimization with Deterministic Finite State Automata

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 40 references that are in the map.
- First posted on arXiv 9 Aug 2021.

## Builds on (most cited first, 4 of 4)

- [Bucket Elimination: A Unifying Framework for Several Probabilistic Inference](https://mlsanity.com/paper/1302.3572/) (2013)
- [AND/OR Multi-Valued Decision Diagrams (AOMDDs) for Graphical Models](https://mlsanity.com/paper/1401.3448/) (2014)
- [Compact-Table: Efficiently Filtering Table Constraints with Reversible Sparse Bit-Sets](https://mlsanity.com/paper/1604.06641/) (2016)
- [Structured Message Passing](https://mlsanity.com/paper/1309.6832/) (2013)

## Abstract (arXiv)

We propose a concise function representation based on deterministic finite state automata for exact most probable explanation and constrained optimization tasks in graphical models. We then exploit our concise representation within Bucket Elimination (BE). We denote our version of BE as FABE. FABE significantly improves the performance of BE in terms of runtime and memory requirements by minimizing redundancy. Results on most probable explanation and weighted constraint satisfaction benchmarks show that FABE often outperforms the state of the art, leading to significant runtime improvements (up to 5 orders of magnitude in our tests).