for each state in extended frontier do if state is complete do complete paths ← APPEND(complete paths, state) extended frontier ← REMOVE(extended frontier, state) beam width ← beam width -1 frontier ← extended frontier to apply some form of length normalization to each of the hypotheses, for example simply dividing the negative log probability by the number of words: