The model of (Che et al., 2008) decided one label for each arc before decoding according to unigram features, which caused lower labeled attachment score (LAS).
keeping all possible labels for each arc made the decoding inefficient.