There are cleverer ways to reduce the complexity (e.g., see (Huang and Chiang, 2005) for three such ways).
since the efficiency of the algorithm did not limit us to produce k-best parses for larger k, it was not a priority in this work.