S ← S ∪ C complete 10: until |S| = K s or t = L 11: Output: y = argmax y∈S∪C log P (y|x) In the decoding step of Seq2Seq, its time complexity is dominated by the vocabulary size |V |, because of the large-scale computation in the operation of probability distribution projection; while the time complexity of implementing PPN is much smaller than that of decoding, with the help of the simple structure of PPN.
the time complexity of incorporating PPN in K s -width beam search is on the same scale as that of the vanilla K s -width beam search, which means incorporating PPN into beam search preserves the inference efficiency.