Augmenting Transformers with Recursively Composed Multi-grained Representations

Thank you for the time you spent reviewing our paper and for your valuable feedback.

W.1: The paper is poorly written, with many notations without explanation. Figure 2 is a copy from Figures in Fast-R2D2, with an unclear caption.

Thank you for reminding us of the clarity issues. We have gone through the paper again and explained some symbols that were not clarified before. To provide a better explanation of the entire pre-training process, we provided a pseudo-code in Algorithm 1. We will keep improving the paper in terms of clarity.

W.2: Lack of important details, e.g. the computational cost of the proposed layers, how to choose the number of layers, and the hidden dimension of the stacked CIO layers.

Thanks for pointing out. The overall time complexity of CIO is $\mathcal{O}(m^2n)$, where n refers to sequence length and m refers to the pruning threshold(set to 2 as default). We also give a detailed analysis of computational cost in Appendix A.6.
Moreover, we reduced the number of steps required to go through the entire CKY chart-table from $2n$ to $2\textrm{log}(n)$ and thus further reduced the training time on GPUs. Under the fast encoding mode, the overall computational cost is $2\sim3$ times vanilla Transformers. For a fair comparison, we choose $3$ as the number of the CIO layers and $768$ as the hidden dimension to make the size of the stacked CIO structure comparable to that of Fast-R2D2.

W.3: It would be helpful to explain the main differences and advantages of the proposed method compared with related works, e.g. Fast-R2D2.

Thanks for the suggestion. We have elaborated on the differences and the advantages in the general response to all reviewers. We also briefly explain the main differences and advantages of the proposed method in related works in the updated draft.

Q.1. What are the advantages of the proposed method compared with Fast-R2D2?

Please refer to the general response to all reviewers for details. In short, the major difference lies in the contextual outside pass which is not possessed by Fast-R2D2. Such a mechanism determines that the span representations in ReCAT are contextualized, i.e., with relative positional information and contextual information, and thus can be combined with Transformers. On the other hand, the span representations in Fast-R2D2 are span-local, lacking relative positional information and contextual information. Moreover, we also reduce the number of steps required to go through the entire CKY chart-table from $2n$ to $2\textrm{log}(n)$ which is detailed in Appendix A.5.

Q.2. What is the computational cost and complexity of the proposed layers? Q.3 How to choose the hyperparameters and the model configurations of the ReCAT models?

Please refer to our response regarding to W.2 above.

Q.4. Can the proposed method be incorporated and augmented to pre-trained models like BERT?

Yes, it can. A simple approach is to load the BERT parameters into the Transformer layers, and then jointly post-train the whole model. In practice, one may reduce the dimension of the CIO layers to reduce the computational cost but keep the feature of providing disentangled span

Sorry for the unclearness. The clarity of notations can be further improved by:

(1) separating scalars and vectors, e.g. using bold to refer to vectors like representations $\hat{\mathbf{e}}\_{i,j}$ and using normal characters for scalars like scores.

(2) Using different notations for different variables, e.g. the representations $\hat{\mathbf{e}}\_{i,j}$ and $\hat{\mathbf{e}}\_{i,j}[k]$ are not same, and $\hat{\mathbf{e}}\_{i,j}$ is the calculated from $\hat{\mathbf{e}}\_{i,j}[k]$ in Equation 1.

(3) multiple equations can be split in lines, e.g. Equation 1,2,3.

Thank you for the time you spent reviewing our paper and for your valuable feedback.

W.1: Contribution is not significant: the proposed method is an effective way of combining ideas of ..

Yes, your understanding of our work is right. But beyond combining them, we further enable it to be jointly pre-trained with Transformers. The key weaknesses along the line of composition-based models are:

(1) bad scalability

(2) difficulty in combining with Transformers.

We largely improve the scalability and demonstrate the key to combining with Transformers is joint pre-training. Meanwhile, joint pre-training is non-trivial for previous work like Fast-R2D2/DIORA. We explain the details in the general response.

Combining composition-based models with Transformers is a meaningful direction as it allows for the integration of constituent-level symbolic interfaces. Currently, Language Models (LLMs) can engage in natural language conversations with humans. However, researchers face a limitation wherein they can only interact with Transformer models using tokens without a rich symbolic interface. Recent studies have demonstrated that utilizing spans as symbolic interfaces can yield fascinating outcomes. For instance, it enables alignment with visual information[1] and facilitates grounded lexicon learning[2]. Offering constituent-level interfaces for Transformers holds great potential. These interfaces can be combined with retrieval, graphs, and more, leading to the development of intriguing features for Transformers. The span-level task is also a good example. In ReCAT, each span has an explicit symbol interface to obtain its representation, and the results significantly outperform Transformers. However, it's still underexplored on how to integrate constituent-level symbolic interfaces with Transformers in an end-to-end approach, which is the key topic we discuss in this work.

[1] Bo Wan, Wenjuan Han, Zilong Zheng, Tinne Tuytelaars. Unsupervised Vision-Language Grammar Induction with Shared Structure Modeling. ICLR 2022.

[2] Jiayuan Mao, Haoyue Shi, Jiajun Wu, Roger P. Levy and Joshua B. Tenenbaum. Grammar-Based Grounded Lexicon Learning. NeurIPS 2021

W.2: Efficiency is low.

(1) ReCAT is indeed slower than vanilla Transformer, but the CIO layer has been $5$ times faster than previous works like Fast-R2D2. We update the efficiency analysis in Appendix A.6. Moreover, we can control the cost via the fast encoding technique.

(2) there might be misunderstanding regarding to ``if we need a pre-trained top-down parser''. In fact, the pre-trained top-down parser in fast encoding refers to the parser used in the CIO layers, which is pre-trained along with the CIO layers. Therefore, no extra pre-trained top-down parser is required. We improve the clarity by the pseudo-code (i.e., Algorithm 1) in the update of the draft.

W.3: About performance on sentence-level tasks compared with a vanilla transformer with similar size. On the structure-prediction task, ReCAT achieves similar performance compared with the previous method TN-PCFG.

Yes, but we argue when the total layer numbers are the same, our results are still competitive on GLUE. We additionally add $ReCAT_{noshare}$[3,1,6] whose total layer number is 9. Its performance is competitive with Transformer 9. Regarding grammar induction, TN-PCFG is close to ReCAT in terms of performance, but considering its $O(n^3)$ time complexity while ReCAT is just $O(n)$, we think the advantage of ReCAT over TN-PCFG is huge in practice. Meanwhile, we can further improve via pre-training on the larger corpus.

Q.1. How do you deal with sub-word tokens: if a word is broken into multiple tokens, how do you handle them in the CIO layer?

Handling the sub-word tokens does not need any special operations. We just take them as ordinary input tokens. The CIO layers can learn how to compose them properly during pre-training.

Q.2. In 3.3, you mentioned “Specifically, we directly use the pre-trained top-down parser to predict a parse tree for a given sentence and apply the trained Compose functions”, does this mean that your method requires a pre-trained top-down parser?

No and we have clarified this point in response to W.2.

Q.3. Is it necessary to train the Transformer from scratch?

We suppose it's necessary for a research paper. As there is no previous work about whether span representations are helpful to augment Transformers, we need to compare ReCAT and vanilla Transformers as fairly as possible. Meanwhile, since the pre-trained Transformer has never seen span representations, we still need to post-train ReCAT to adopt those new span representations from CIO layers. It costs more computational resources to post-train on a corpus like OpenWebText than from scratch on wiki-103. Moreover, it would be hard to tell if the gain is from extra training steps or CIO layers.

There might be a misunderstanding regarding "It’s interesting to see that the Vanilla MLM can be used to replace the training objective of DIORA and the model can effectively learn the syntactic structure with the simple MLM objective."

Simply replacing the training objective of DIORA with the MLM objective $**doesn't work well**$. In Table 3 and Table 4. $ReCAT_{noshare}[1,3,3]$ can be viewed as an extended version of DIORA (run inside-outside algorithm only once, with 3-layered Transformers as encoder, but replacing the outside pass with our contextual outside pass, pretrained via MLM), but it does not perform well on grammar induction and glue tasks. The original version is supposed to perform worse if pretrained via MLM.

Fast-R2D2+DIORA+MLM doens't work well. Fast-R2D2+DIORA+ iterative up-and-down mechanism + contextual outside + MLM makes it work. The iterative up-and-down mechanism(stackable CIO layers) and contextual outside is our key innovation, enabling the CIO layer to be pre-trained through Masked Language Modeling, thereby making it possible to achieve joint pre-training with Transformer through MLM.

Please note that the original inside-outside algorithm is not stackable, as the outside algorithm was originally designed to construct language modeling objectives, thus there is no interaction between information inside and outside of a span. However, our contextual outside pass is designed to contextualize span representations, allowing for stacking and adapting to Masked Language Modeling.

Thank you for the time you spent reviewing our paper and for your valuable feedback.

W.1: about compositional generalization.

in addition to the span-level tasks, we also observed significant gains on the grammar induction task (i.e., Table 4 in the paper). This could be another piece of evidence that indicates the compositional generalization of the model. As compositional generalization refers to the ability to recognize or generate novel combinations of observed elementary concepts, our model has never seen sentences in the test set in the grammar induction task but induces their structures well. Besides, we also show a few parsing results from ReCAT in Appendix A.7, through which we aim to show what the syntax augmented Transformer really learned. Indeed, the showcases exhibit high consistency with human-annotated structures (i.e., the gold trees), meaning that the superior performance of ReCAT on the span-level tasks may stem from the recovery of the underlying syntactic structures of texts.

W.2: ..., maybe a self-contained step-by-step summary of the algorithm at the end of the section would be helpful.

We appreciate your suggestion and add pseudo code (i.e., Algorithm 1) in the updated draft to show how the model is pre-trained step-by-step.

W.3: ...,the takeaway is a bit unclear

We have discussed in detail about the advantages of ReCAT and the innovation we made in the work in the general response. The takeaway is

(1) the key advantages of ReCAT over DIORA and Fast-R2D2 are the capability of joint pre-training with Transformer and scalability;

(2) to achieve the advantages, we develop the iterative up-and-down mechanism (via stacking multiple CIO layers) and the contextual outside pass, which represent the key difference we made in the work comparing to DIORA and Fast-R2D2.

Please note that the original inside-outside algorithm is not stackable, as the outside algorithm was originally designed to construct language modeling objectives while ours is designed to contextualize span representations, allowing for stacking and adapting to Masked Language Modeling.

W.4: Related to (3), the paper would benefit from ablations to support the claims of why certain design decisions were effective.

Thanks for the suggestion. Since the iterative up-and-down mechanism and the contextual outside pass are key technical contributions, it is better for us to ablate the model so as to inspect the effect of each design. In fact, we have done the ablation in the experiments:

(1) ablation of iterative up-and-down. This is done by the comparison between $ReCAT_{share}$[1,3,3] and $ReCAT_{share}[3,1,3]$ in Table 3. The two models have similar parameter sizes, but $ReCAT_{share}[3,1,3]$ contains 3 layers of CIO while $ReCAT_{share}[1,3,3]$ only has one, i.e, no iterative up-and-down. The results in Table 3 indicate that when the total numbers of parameters are close, stacking CIO layers can bring consistent improvement. Additionally, we update Table 4 by including $ReCAT_{share}[1,3,3]$. Again, the big gap between the two models indicates the value of the proposed mechanism. We additional added an explanation for them in the updated draft.

(2) ablation of joint pre-training. This can be checked by comparing ReCAT$_{share}[3,1,3]$ with Fast-R2D2+Transformer and DIORA+Transformer in Table 3. Transformers used in these baselines are randomly initialized. From the results, we can conclude that the joint pre-training is important.

Response to Q1:

We were surprised too when we first observed the results. Appending Transformers is helpful for QQP but leads to no gain for MNLI. And to find out ``why'' motivates the work. As we analyze in Section 4.2, composition-based models are good at tasks that only need literal text information while Transformers are good at tasks requiring information beyond literal texts, i.e., knowledge. We realized the importance of joint pretraining. Knowledge entailed in corpora is compressed into Transformers during the pretraining. Just appending Transformers without joint pre-training, the two are incompatible. However, as we have elaborated in the general response, one cannot perform joint pre-training by simply appending Transformers after Fast-R2D2 or DIORA. Thus we propose CIO layers to address a series of issues even including scalability.

Response to Q2:

We update Table 3 in the draft by adding a baseline ReCAT$_{share}[3,1,0]$ (i.e., no transformer layers). As expected, it is worse than Fast-R2D2 and DIORA. The comparison indicates that MLM itself is not so efficient as the original objective used by R2D2 and DIORA (15% vs 100%). The advantage of MLM lies in its ability to make pre-training with Transformer feasible.

Response to Q3:

Sorry for the abuse of notations. They are $ReCAT_{share}[3,1,3]$ and $ReCAT_{noshare}[3,1,3]$ respectively whose parameter sizes are shown in Table 1. We have updated the draft to improve clarity.

Thanks for your insightful comments. But part of them seem incomplete, especially strengths and weaknesses. So could you kindly paste full of them once you have time? Many Thanks.

We are still preparing the rest part of the authors' response. But the question about character-level parsing we can respond first. We did try applying the inside-outside algorithm on character-level vocabulary to see if it could induce underlying structures of characters. Unfortunately, it doesn't work well in languages based on spelling like English. A key reason we guess is the information entropy is too low as there are only 26 characters in English. Thus feedback is so weak for the inside-outside algorithm. However, it could work well in languages with large basic character-level vocabulary like Chinese.

Thank you for the time you spent reviewing our paper and for your valuable feedback.

W.1: As the authors pointed out, the CIO layer can be expensive. I'm also wondering how is the effect.

As we have explained in the general response, with all the effort (contextual inside-outside with $\mathcal{O}(n)$ time complexity and $2\textrm{log}(n)$ steps), the CIO layer has been $5$ times faster than using the original pruning algorithm proposed in Fast-R2D2. We update the efficiency analysis in Appendix A.6 in the draft. On the other hand, training a ReCAT model is indeed more expensive than training a vanilla Transformer with a similar parameter size ($88M$) due to the dynamic programming in stacked CIO layers. We can control the running time of ReCAT to be about 2 to 3 times that of the vanilla Transformer during inference and fine-tuning using the fast encoding technique described in Appendix A.3. Considering the outstanding performance of ReCAT on span-level tasks and the grammar induction task, we think the cost is worthwhile.

Q.1. It would be interested to see if the gains still holds when we scale to larger models.

We train a larger ReCAT with 3 CIO layers and 6 Transformer layers (namely ReCAT$_{noshare}[3,1,6]$), and update the results in Table 3 in the draft. We can see that the performance of ReCAT continuously gets improved with the increase in model size ($[1,1,3] \rightarrow [3,1,3] \rightarrow [3,1,6]$).

Q.2. I'm wondering if the CIO layer can be trained at the finetuning stage so that we can still utilize a powerful pre-trained model and augment it with the CIO layer only at the finetuning stage.

Though we are not able to finish the extra experiments in such a short rebuttal period, we believe that joint post-training is still necessary to adapt to span-level representations, as the pre-trained model has never seen those span-level representations during its pre-training period.

Q.3. this might be diverging or outside the scope of the paper, but I'm curious how tokenization would be affecting the effectiveness of the proposed method. For example, if it's byte or character-level vocabulary, do we observe a similar gain.

Please refer to the previous reply.