By complete and utter coincidence, combined with a little bit of incompetence in leadership, the new players show up at an opportune time. As it happens, there were two groups assigned to do the current party's job, but nobody realized it until both groups had been sent out already.
The first group is the current party, and was assigned to this task by (the king? his spymaster? his top general? his other top general? the captain of the palace guard? a scheming duke?) The second group consists of the new players, who were assigned to this task by somebody entirely different. (If you want to be complicated, have the second group be there for a different reason. Make up another reason for them to be there. The players haven't explored the entire cave system yet, so you can still add something in an area they haven't seen.) If you think that "just the new players" is too small of an adventuring party to take on this cave system, then the new players' party was once larger, but some people got killed along the way.
As for how to dispose of the characters that left the game: adventuring is dangerous. People die, sometimes with no warning beyond "Hey, what's that funny soun---". Death doesn't respect character back-stories or plot arcs or convenience; if somebody suddenly has a gaping hole in their larynx, being in the center of a web of plot won't help them. Of course, if your players have easy access to resurrection, then that won't fly. So, if you truly need a way to remove the PCs without killing them, then the second group could have orders for the PCs who are leaving, that are more important than their current task. Or an offhand comment by one of the newcomers makes one or more of the PCs suddenly run off to rescue a loved one, who was living in a city that just got besieged by an invading army.
Edit: One late thought about killing off those extraneous PCs: if you kill the extras, and you make it a "deus ex machina" moment, make it clear to your remaining players that you're not going to kill them that way while they're still playing. Most players don't find it at all fun when the GM randomly kills off PCs; don't let your players pick up the idea that their PCs may suddenly be taken from them if they annoy you.