Techniques are disclosed for tuning external invocations utilizing weight-based parameter resampling. In one example, a computer system determines a plurality of samples, each sample being associated with a parameter value of a plurality of potential parameter values of a particular parameter. The computer system assigns weights to each of the parameter values, and then selects a first sample for processing via a first external invocation based on a weight of the parameter value of the first sample. The computer system then determines feedback data associated with a level of performance of the first external invocation. The computer system adjusts the weights of the parameter values of the particular parameter based on the feedback data. The computer system then selects a second sample of the plurality of samples to be processed via execution of a second external invocation based on the adjustment of weights of the parameter values.