You might be able to use a cellular automaton to simulate cave formation, not in the simple Conway's Game of Life sense, but by programming the automaton to simulate earth of varying densities which are randomly placed in a 2D or 3D grid, fluid, which might be water or magma, and air.
By setting the rules correctly, water would come from above at random intervals and areas and erode the earth, weakening each cell until it disappeared, or it could cause rock deposition in empty spaces (stalactites and stalagmites). If you had a 3D simulation, you could also add gravity, requiring that water always move horizontally or downhill unless the rate of flow was restricted at some point (at which point it could rise upstream of the blockage), or unless it got sufficiently hot.
Gravity could also be used to determine collapses - if insufficiently strong earth is asked to span too great a distance without support, it would collapse.
Magma would come from beneath, originating from a hot spot, whose intensity and position of maximum heat may vary over time, and magma might solidify to form hard rock, or subside again to leave cavities (depending on the type of the hot spot and/or random factors), and it would also heat water, making it rise.
This wouldn't necessarily be quick to program, and wouldn't be particularly quick to run, but done properly, could produce very realistic results.