Techniques are disclosed herein for verifying that memory cells comply with a target threshold voltage that is negative. The technique can be used for an erase verify or a soft program verify. One or more erase pulses are applied to a group of non-volatile storage elements that are associated with bit lines and word lines. One or more non-negative compare voltages (e.g., zero volts) are applied to at least a portion of the word lines after applying the erase pulses. Conditions on the bit lines are sensed while holding differences between voltages on the bit lines substantially constant and while applying the one or more compare voltages. A determination is made whether the group is sufficiently erased based on the conditions. At least one additional erase pulse is applied to the group of non-volatile storage elements if the group of non-volatile storage elements are not sufficiently erased.