A method in a computing device for decoding a weighted finite state transducer (WFST) for automatic speech recognition is described. The method includes sorting a set of one or more WFST arcs based on their arc weight in ascending order. The method further includes iterating through each arc in the sorted set of arcs according to the ascending order until the score of the generated token corresponding to an arc exceeds a score threshold. The method further includes discarding any remaining arcs in the set of arcs that have yet to be considered.