Techniques are disclosed to refresh data in a non-volatile storage device often enough to combat erroneous or corrupted data bits, but not so often as to interfere with memory access or to cause excessive stress on the memory cells. One embodiment includes determining to perform a refresh of data stored in a first group of non-volatile storage elements in a device based on a condition of data in the first group, determining that a second group of non-volatile storage elements in the device should undergo a refresh procedure based on when the second group of non-volatile storage elements were last programmed relative to when the first group of non-volatile storage elements were last programmed, and performing the refresh procedure on the second group of non-volatile storage element.