Given a quantum gate implementing a d-dimensional unitary operation U_{d}, without any specific description but d, and permitted to use k times, we present a universal probabilistic heralded quantum circuit that implements the exact inverse U_{d}^{-1}, whose failure probability decays exponentially in k. The protocol employs an adaptive strategy, proven necessary for the exponential performance. It requires that k≥d-1, proven necessary for the exact implementation of U_{d}^{-1} with quantum circuits. Moreover, even when quantum circuits with indefinite causal order are allowed, k≥d-1 uses are required. We then present a finite set of linear and positive semidefinite constraints characterizing universal unitary inversion protocols and formulate a convex optimization problem whose solution is the maximum success probability for given k and d. The optimal values are computed using semidefinite programing solvers for k≤3 when d=2 and k≤2 for d=3. With this numerical approach we show for the first time that indefinite causal order circuits provide an advantage over causally ordered ones in a task involving multiple uses of the same unitary operation.