We present a complete solution to the problem of Formal Higher Spin Gravities --- formally consistent field equations that gauge a given higher spin algebra and describe free higher spin fields upon linearization. The problem is shown to be equivalent to constructing a certain deformation of the higher spin algebra as an associative algebra. Given this deformation, all interaction vertices are explicitly constructed. All formal solutions of the equations are explicitly described in terms of an auxiliary Lax pair, the deformation parameter playing the role of the spectral one. We also discuss a natural set of observables associated to such theories, including the holographic correlation functions. As an application, we give another form of the Type-B formal Higher Spin Gravity and discuss a number of systems in five dimensions.

30 pages; typos fixed, ref added