A method of performing an erase operation on non-volatile storage is disclosed. The method comprises: applying, in a first erase loop of a plurality of erase loops of the erase operation, a first erase voltage pulse to a set of non-volatile storage elements; determining an upper tail of a threshold voltage distribution of the set of non-volatile storage elements after applying the first erase voltage pulse; determining a second erase voltage pulse based on the upper tail of the threshold voltage distribution of the set of non-volatile storage elements; and applying, in a second erase loop of the plurality of erase loops, the second erase voltage pulse to the set of non-volatile storage elements.