A method includes storing data that is encoded with an Error Correction Code (ECC) in a group of analog memory cells. The memory cells in the group are read using multiple sets of read thresholds. The memory cells in the group are divided into two or more subsets. N partial syndromes of the ECC are computed, each partial syndrome computed over readout results that were read using a respective set of the read thresholds from a respective subset of the memory cells. For each possible N-bit combination of N bit values at corresponding bit positions in the N partial syndromes, a respective count of the bit positions in which the combination occurs is determined, so as to produce a plurality of counts. An optimal set of read thresholds is calculated based on the counts, and data recovery is performed using the optimal read thresholds.