On The Efficient Marginalization Of Probabilistic Sequence Models