ElliCE generates counterfactual explanations with theoretical guarantees that remain valid across Rashomon set by approximating it with an ellipsoid. The method is faster than existing robust baselines and ensures meaningful explanations.