When erasing non-volatile storage, a verification process is used between erase operations to determine whether the non-volatile storage has been successfully erased. The verification process includes separately performing verification for different subsets of the non-volatile storage elements.