Abstract: The Bethe approximation provides an effective way for relaxing NP-hard problems of probabilistic inference. However, its accuracy depends on the model parameters and particularly degrades if the model undergoes a phase transition. In this work, we analyze when the Bethe approximation is reliable and how this can be verified. We show that it is mostly accurate if it is convex on a submanifold of its domain, the 'Bethe box'. For proving its convexity, we derive two sufficient conditions that use the definiteness properties of the Bethe Hessian. We further propose $\texttt{BETHE-MIN}$, a projected quasi-Newton method to efficiently find a minimum of the Bethe free energy.