The recent application of large deviations techniques to the cavity method allows a better characterization of the phase diagram of constraint satisfaction problems, opening to the investigation of the geometric properties of the space of solutions. We apply this method to the bicoloring of regular random hypergraphs, for which many results can be obtained analytically. Some interesting consequences on the computational hardness of single instance problems are also discussed.