A storage device updates optimal parameters associated with a Thermal Region Tag (TRT). A controller on the storage device assigns a TRT to blocks programmed at a given temperature range and updates an optimal TRT parameters by obtaining a set of representative wordlines and a set of indicative wordlines for a block assigned to the TRT. The controller performs a bit error rate (BER) estimation on indicative wordlines in the set until a valid indicative wordline is found. The controller determines whether a BER Estimation Scan (BES) check is to be performed when the valid indicative wordline is found. In performing the BES check, the controller performs the BER estimation on representative wordlines in the set until a valid representative wordline is found. When a valid representative wordline is found, the controller obtains the optimal TRT parameter and updates the optimal TRT parameter.