Dealing with pruning issues

I spent a holiday looking on the issues in poketsphinx decoding in fwdflat mode. Initially I thought it's a bug but it appeared that it's just a pruning issue. The result looked like this:

INFO: ngram_search.c(1045): bestpath 0.00 wall 0.000 xRT
INFO: <s> 0 5 1.000 -94208 0 1
INFO: par..grafo 6 63 1.000 -472064 -467 2
INFO: terceiro 64 153 1.000 -1245184 -115 3
INFO: as 154 176 0.934 -307200 -172 3
INFO: emendas 177 218 1.000 -452608 -292 3
INFO: ao 219 226 1.000 -208896 -181 3
INFO: projeto 227 273 1.000 -342016 -152 3
INFO: de 274 283 1.000 -115712 -75 3
INFO: lei 284 3059 1.000 -115712 -79 3


Speech recognition is essentially a search for a globally best path in a graph. Beam pruning is used to drop the nodes during the search if node score is worse then the best node like in this picture


If beam is too narrow, the result might not be the globally best one despite its locally the best. In practice it could lead to complex issues like desribed above. See the word "lei" spans about 2k frames which means about 20 seconds. Another sign of overpruning is number of words scored per frame