Multipass coarse-to-fine decoding is another popular idea (Venugopal et al., 2007;Zhang and Gildea, 2008;Dyer and Resnik, 2010).
dyer and Resnik (2010) uses a two-pass approach, where their first-pass, −LM decoding is also incremental and polynomial-time (in the style of Earley (1970) algorithm), but their second-pass, +LM decoding is still bottom-up CKY with cube pruning.