Going the other way from mkl, I wonder if you don't really need beam search. Approximate as a finite state space, use https://en.wikipedia.org/wiki/Viterbi_algorithm