Paper: Cube Pruning as Heuristic Search

ACL ID D09-1007
Title Cube Pruning as Heuristic Search
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2009

Cube pruning is a fast inexact method for generating the items of a beam decoder. In this paper, we show that cube pruning is essentially equivalent to A* search on a specific search space with specific heuris- tics. We use this insight to develop faster and exact variants of cube pruning.