In this paper, we present efficient HMM-based techniques for estimating missing features. By assuming speech features to be observations of hidden Markov processes, we derive a minimum mean-square error (MMSE) solution. We increase the computational efficiency of HMM-based methods by downsampling underlying Markov models, and by enforcing symmetry in transitional probability matrices. When applied to features generally utilized in parametric speech coding, namely line spectral frequencies (LSFs), the proposed methods provide significant improvement over the baseline repetition scheme, in terms of weighted spectral distortion and peak SNR.