Read reference levels are used to distinguish different data states for information stored in non-volatile memory. A storage system recalibrates its read reference levels, to maintain accuracy of the read process, by sensing samples of data for different test read reference levels and using those samples to determine an improved set of read reference levels. At least a subset of the test read reference levels used for the samples are dynamically and adaptively chosen based on indications of error for previous samples.