The time complexity of the Eisner algorithm is O(N 3 ), while checking if a tree is projective can be done reasonably faster, with a O(N log N ) algorithm.
we only apply the Eisner algorithm to the non-projective output of our greedy inference strategy.