A computer-implemented method is provided for estimating output confidence of a black box Application Programming Interface (API). The method includes generating paraphrases for an input text. The method further includes calculating a distance between the input text and each respective one of the paraphrases. The method also includes sorting the paraphrases in ascending order of the distance. The method additionally includes selecting a top predetermined number of the paraphrases. The method further includes inputting the input text and the selected paraphrases into the API to obtain an output confidence score for each of the input text and the selected paraphrases. The method also includes estimating, by a hardware processor, the output confidence of the input text from a robustness of output scores of the input text and the selected paraphrases.