We present a new approach to parameter inference targeted on generic situations where the evaluation of the likelihood $\mathcal{L}$ (i.e., the probability to observe the data given a fixed model configuration) is numerically expensive. Inspired by ideas underlying simulated annealing, the method first evaluates $χ^2=-2\ln\mathcal{L}$ on a sparse sequence of Latin hypercubes of increasing density in parameter (eigen)space. The semi-stochastic choice of sampling points accounts for anisotropic gradients of $χ^2$ and rapidly zooms in on the minimum of $χ^2$. The sampled $χ^2$ values are then used to train an interpolator which is further used in a standard Markov Chain Monte Carlo (MCMC) algorithm to inexpensively explore the parameter space with high density, similarly to emulator-based approaches now popular in cosmological studies. Comparisons with example linear and non-linear problems show gains in the number of likelihood evaluations of factors of 10 to 100 or more, as compared to standard MCMC algorithms. As a specific implementation, we publicly release the code PICASA: Parameter Inference using Cobaya with Anisotropic Simulated Annealing, which combines the minimizer (of a user-defined $χ^2$) with Gaussian Process Regression for training the interpolator and a subsequent MCMC implementation using the COBAYA framework. Being agnostic to the nature of the observable data and the theoretical model, our implementation is potentially useful for a number of emerging problems in cosmology, astrophysics and beyond.