Techniques are provided to adaptively determine when to begin verify tests for memory cells during a program operation. The memory cells are programmed using a normal programming speed until their threshold voltage exceeds an initial verify voltage. The memory cells are then programmed further using a reduced programming speed until their threshold voltage exceeds a final verify voltage. In one aspect, a count of memory cells which exceeds the initial verify voltage is used to determine when to begin verify tests for a higher data state. In another aspect, a count of the higher state memory cells which exceeds the initial or final verify voltage is used to determine when to begin verify tests for the higher data state. The counted memory cells are not subject to the reduced programming speed.