Any thoughts on procedural cave generation?

Say I have a planet, starting off with a low poly sphere or plane, and then subdivide the mesh and add a bit of randomness and repeat. You can end up with some nice mountains etc. But it won’t have any caves. i.e. it will always have the same topology. It will just be a bumpy sphere.

Any ideas how people usually make procedural caves (at runtime)? It seems to be easier in voxel type games than if everything is made of triangles.

One way I thought would be to remove two of the triangles in the mesh and then link them. But then you have all the problems of what if tunnels cross each other etc? (if its all done randomly)

(Do you think caves are important? Would you be really disappointed in an environment with no caves?)

Edit: Actually I had quite a good idea. You could take one triangle from a torus mesh and one triangle from your world mesh and stitch them together. That would add a hole to your geometry. But kind of a strange cave. More like a hoop sticking out the ground

Most voxel type games are also made of triangles - the world data is stored as voxels but the voxel data is then used to compute a triangle mesh just like any other mesh for rendering.

I found this guide to be quite good back when I was doing procedural cave generation: Accidental Noise Library

Thanks. I think the problem is I’m storing all my geometry as surface mesh data rather than volume data. Maybe I have to rethink it. Or find someway to convert between the two.