This paper proposes an approach to improve graph-based dependency parsing by using decision history. We introduce a mechanism that considers short dependencies computed in the earlier stages of parsing to improve the accuracy of long dependencies in the later stages. This relies on the fact that short dependencies are generally more accurate than long dependencies in graph-based models and may be used as features to help parse long dependencies. The mechanism can easily be implemented by modifying a graphbased parsing model and introducing a set of new features. The experimental results show that our system achieves state-ofthe-art accuracy on the standard PTB test set for English and the standard Penn Chinese Treebank (CTB) test set for Chinese. 1