A method implements efficient counterfactual search. The method includes receiving a request corresponding to an input vector, processing the input vector with a model to generate an output vector that does not correspond to a selected class, and processing the input vector using a component, of a plurality of components, to generate a counterfactual vector to the selected class. The plurality of components includes a number of dimensions that is less than a number of features of the input vector. The method further includes processing the counterfactual vector to generate a recommendation and presenting the recommendation.