When processing states column-by-column, this means that all states that could have been skipped because of pruning have already been computed anyway. Run your favourite alignment algorithm (Edlib/WFA), but after each front (ie column or wavefront), shrink the ends of the front as long as \(f(u) > t\) for states at those ends. In this case we should split each front (column/wavefront) into two smaller intervals of states \(f\leq t\) that cover the good candidate states, and skip the states in the middle with \(f > t\).