It's 1000x compared to a very naive baseline, exhaustive traversal of the matching subtree. Nobody in practice would do that, storing the maximum score for each

It's 1000x compared to a very naive baseline, exhaustive traversal of the matching subtree. Nobody in practice would do that, storing the maximum score for each subtree so you can prune is a very common technique, definitely not novel here. Even doing a Levenshtein-bounded beam search along the trie is pretty much common practice, see for example this paper [1] from 2011. There are more sophisticated ways of doing this in space-efficient ways, for example this paper [2] I co-authored in 2013. [1] https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/WWW11-OnlineSpellingCorrection.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... [2] https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/TopKCompletion.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...