Task: Question Generation
Input (English): Parallel Scan Inference
The commutative properties of semiring algorithms allow flexibility in the order in which we compute $A(\ell )$. Typical implementations of dynamic programming algorithms are serial in the length of the sequence. Vectorized Parsing
Computational complexity is even more of an issue for parsing algorithms, which cannot be as easily parallelized. Semiring Matrix Operations
The two previous optimizations reduce most of the cost to semiring matrix multiplication. In the specific case of the $(\sum , \times )$ semiring these can be computed very efficiently using matrix multiplication, which is highly-tuned on GPU hardware. Unfortunately for other semirings, such as log and max, these operations are either slow or very memory inefficient. For instance, for matrices $T$ and $U$ of sized $N \times M$ and $M \times O$, we can broadcast with $\otimes $ to a tensor of size $N \times M \times O$ and then reduce dim $M$ by $\bigoplus $ at a huge memory cost.
Output (English): What baselines are used in experiments?