Many problems in computer vision can be modeled using conditional Markov random fields (CRF). Since finding the maximum a posteriori (MAP) solution in such models is NP-hard, much attention in recent years has been placed on finding good approximate solutions. In particular, graph-cut based algorithms, such as a-expansion, are tremendously successful at solving problems with regular potentials. However, for arbitrary energy functions, message passing algorithms, such as max-product belief propagation, are still the only resort. In this paper we describe a general framework for finding approximate MAP solutions of arbitrary energy functions. Our algorithm (called Alphabet SOUP for Sequential Optimization for Unrestricted Potentials) performs a search over variable assignments by iteratively solving subproblems over a reduced state-space. We provide a theoretical guarantee on the quality of the solution when the inner loop of our algorithm is solved exactly. We show that this approach greatly improves the efficiency of inference and achieves lower energy solutions for a broad range of vision problems.