We explore the potential of anytime best-first search schemes for combinatorial optimization tasks over graphical models (e.g., MAP/MPE). We show that recent advances in extending best-first search into an anytime scheme have a potential for optimization for graphical models. Importantly, these schemes come with upper bound guarantees and are sometime competitive with known effective anytime branch-and-bound schemes.