The reliable prediction of phase stability is a challenging computational problem in chemical process simulation, optimization, and design. The phase stability problem can be formulated either as a minimization problem or as an equivalent nonlinear equation-solving problem. Conventional solution methods are initialization dependent and may fail by converging to trivial or nonphysical solutions or to a point that is a local but not a global minimum. Thus, there has been considerable recent interest in developing more reliable techniques for stability analysis. Recently, we have demonstrated, using cubic equation of state models, a technique that can solve the phase stability problem with complete reliability. The technique, which is based on interval analysis, is initialization independent and, if properly implemented, provides a mathematical guarantee that the correct solution to the phase stability problem has been found. However, there is much room for improvement in the computational efficiency of the technique. In this paper we consider two means of enhancing the efficiency of the method, both based on sharpening the range of interval function evaluations. Results indicate that, by using the enhanced method, computation times can be reduced by nearly an order of magnitude in some cases.