A hallmark of many of these models is that they can be implemented very efficiently.
transition-based parsers normally run in linear or quadratic time, using greedy deterministic search or fixed-width beam search Attardi, 2006;Johansson and Nugues, 2007;Titov and Henderson, 2007), and graph-based models support exact inference in at most cubic time, which is efficient enough to make global discriminative training practically feasible (McDonald et al., 2005a;McDonald et al., 2005b).