By showing that there is an equivalent graph in the rank space on which message passing is equivalent to message passing in the original joint state and rank space, this work exposes the fact that these large structured prediction models with fully decomposable clique potentials (Chiu et al 2021 being an exception) are equivalent to a smaller structured prediction model (albeit with over-parameterized clique potentials). For example, looking at Figure 5 (c), the original HMM is equivalent to a smaller MRF with state size being the rank size (which is the reason why inference complexity does not depend on the original number of states at all after calculating the equivalent transition and emission matrices). One naturally wonders why not simply train a smaller HMM, and where does the performance gain of this paper come from in Table 3.
As another example, looking at Figure 4 (a), the original PCFG is equivalent to a smaller PCFG (with fully decomposable potentials) with state size being the rank size. This smaller PCFG is over-parameterized though, e.g., its potential $H\in \mathcal{R}^{r \times r}$ is parameterized as $V U^T$ where $U,V\in \mathcal{R}^{r \times m}$ and $r < m$, instead of directly being parameterized as a learned matrix of $\mathcal{R}^{r \times r}$. That being said, I don't consider this a problem introduced by this paper since this should be a problem of many previous works as well, and it seems an intriguing question why large state spaces help despite the existence of these equivalent small models. Is it similar to why overparameterizing in neural models help? Is there an equivalent form of the lottery ticket hypothesis here?
In regard to weakness #1, I think this work would be strengthened by adding the following baselines: 1. For each PCFG with rank r, add a baseline smaller PCFG with state size being r, but where $H, I, J, K, L$ are directly parameterized as learned matrices of $\mathcal{R}^{r \times r}$, $\mathcal{R}^{r \times o}$, $\mathcal{R}^{r}$, etc. Under this setting, parsing F-1 might not be directly comparable, but perplexity can still be compared.
2. For each HMM with rank r, add a baseline smaller HMM with state size being r.
1. For each PCFG with rank r, add a baseline smaller PCFG with state size being r, but where $H, I, J, K, L$ are directly parameterized as learned matrices of $\mathcal{R}^{r \times r}$, $\mathcal{R}^{r \times o}$, $\mathcal{R}^{r}$, etc. Under this setting, parsing F-1 might not be directly comparable, but perplexity can still be compared.