  Predictive business process monitoring increasingly leverages sophisticated
prediction models. Although sophisticated models achieve consistently higher
prediction accuracy than simple models, one major drawback is their lack of
interpretability, which limits their adoption in practice. We thus see growing
interest in explainable predictive business process monitoring, which aims to
increase the interpretability of prediction models. Existing solutions focus on
giving factual explanations.While factual explanations can be helpful, humans
typically do not ask why a particular prediction was made, but rather why it
was made instead of another prediction, i.e., humans are interested in
counterfactual explanations. While research in explainable AI produced several
promising techniques to generate counterfactual explanations, directly applying
them to predictive process monitoring may deliver unrealistic explanations,
because they ignore the underlying process constraints. We propose LORELEY, a
counterfactual explanation technique for predictive process monitoring, which
extends LORE, a recent explainable AI technique. We impose control flow
constraints to the explanation generation process to ensure realistic
counterfactual explanations. Moreover, we extend LORE to enable explaining
multi-class classification models. Experimental results using a real, public
dataset indicate that LORELEY can approximate the prediction models with an
average fidelity of 97.69\% and generate realistic counterfactual explanations.
