Techniques are described for programming memory cells with reduced widening of the threshold voltage distributions. Bit line voltages are adjusted during verify tests for memory cells assigned to the upper data state in a pair of adjacent data states which are concurrently verified. An elevated bit line voltage is applied and then stepped up in successive program loops. A lower, fixed bit line voltage is used for verifying the lower data state in the pair of adjacent data states. In one option, the step size increases progressively over the program loops. In another option, the minimum level of the elevated bit line voltage is lower for higher data states. In another option, the minimum level of the elevated bit line voltage is set as a function of data states, program-erase cycles and/or temperature.