If you have inexpensive features then you could try and build a Determinantal Point Process, a model for sampling diverse subsets (diversity defined via the features and an appropriate kernel). The downside is that this method, at worst, typically scales poorly (O(N^3 )) with the number of samples although there is recent work in this field to speed up inference. I can’t say a priori if it is fast enough for your task.