Two families of scale-free exponentiality tests based on the recent characterization of exponentiality by Arnold and Villasenor are proposed. The test statistics are constructed using suitable functionals of U-empirical distribution functions. The family of integral statistics can be reduced to V- or U-statistics with relatively simple non-degenerate kernels. They are asymptotically normal and have reasonably high local Bahadur efficiency under common alternatives. This efficiency is compared with simulated powers of new tests. On the other hand, the Kolmogorov type tests demonstrate very low local Bahadur efficiency and rather moderate power for common alternatives, and can hardly be recommended to practitioners.The conditions of local asymptotic optimality of new tests are also explored and for both families special ‘‘most favourable’’ alternatives for which the tests are fully efficient are described.