Abstract In this article, we present a new numerical algorithm to detect the kernel shape parameter and the subdomain radius size within a partition of unity method for scattered data interpolation. Since an adaptive search of such hyperparameters is quite expensive from the computational point of view, we propose the use of a leave-one-out cross-validation (LOOCV) technique combined with univariate global optimization tools from the class of Lipschitz derivative-free methods. Conventional LOOCV methods often suffer from ill-conditioning, particularly in high-dimensional settings, leading to computational inefficiencies. To address these issues, we consider efficient global optimization strategies characterized by optimistic and pessimistic improvements. The resulting algorithm allows us to improve the performance of the standard approach in terms of both accuracy and efficiency. Numerical results deriving from the study of some test cases and an application to real-world data support our analysis.