This thesis focuses on Hierarchical Machine Translation (HMT). HMT allows to model long distance phenomena and reordering at a cost of higher complexity of the decoder. With this thesis we reduce the complexity of HMT. In the first part we propose a series of alternative Cube Pruning (CP) algorithms that leverage on more aggressive pruning and less memory usage. Then we propose a linear time CP that solves exactly a relaxation of the decoding problem. All these algorithms can substitute the standard CP algorithm in any of its applications. In the second part of the thesis we present a novel Structured Prediction approach to HMT. The proposed model builds the structures incrementally, by choosing a single action at each step, and pruning all incompatible alternatives to that action. This approach allows translations to be constructed in an undirectional manner, thus not being constrained by the bottomup ordering of CKYlike algorithms.