We sincerely thank the reviewer for their insightful comments on our submission.

1. As for the organization of the paper, we agree with the reviewer that our manuscript is somewhat dense as we have tried to cover many different bases and angles, leading to an additional 25 pages of appendix materials. In order to make the final manuscript more clear, we will move the notion of block attention higher to the beginning of the paper as the reviewer suggested. If possible, we will also try to move some of the background materials to the appendix to find more room for the Dynamic Programming section in the main text. As for the section on the KL-optimality of HSA (i.e. Theorem 3.2), we would like to note that this result is a crucial theoretical contribution of our work as it establishes the optimality of HSA approximation among other block approximations of the attention matrix. But why is this result important? Because it opens the door for another equally important application of HSA in practice: the zero-shot plug-n-play capability of HSA in integrating into the pretrained models, as it was empirically validated in Section 4.3 and Appendices J and L. Such plug-n-play capability effectively enables us to avoid building large-scale HSA models from scratch but from already pre-trained transformers. Our theoretical result guarantees the optimality of such zero-shot procedure.

2. As for comparison to some other hierarchy-based models such as Swin-Transformer, we are planning to add such baselines to some of our experiments. However, making a fair comparison of HSA to these frameworks is somewhat tricky. In particular, most of such models including Swin-Transformer encode a fixed hierarchical structure within their architecture by assigning different sets of $Q$, $K$ and $V$ projection parameters to different levels of the hierarchy. While this restricts these models' capability in handling arbitrarily-shaped hierarchies (unlike HSA), it also introduces a completely different parameter structure than that of the HSA. In other words, any potential gain or loss cannot be properly attributed to the hierarchical attention mechanism only, which is the main focus of the current work. Please note that in all of our current experiments, the baselines as well as their rival HSA model have exactly the same parameter structure and count but different attention calculation procedures, which makes the comparison fair and the results meaningful. Nonetheless, we are currently trying to come up with a variation of some of these hierarchical baselines that have more similar parameter structure to HSA, but that would require training such baselines from scratch.

We truly appreciate the reviewer's constructive feedback and comments.

1. Regarding lack of experimentation for multi-step gradient-descent interpretation, we'd like to note that the main angle and focus of this work is the theoretical derivation of hierarchical attention from the entropy minimization interpretation of self-attention. In that sense, the gradient-descent interpretation is a secondary byproduct of our theoretical framework which is, of course, worth exploring on its own in a separate work. At the same time, we'd like to mention that performing $n$-step gradient descent on conditional entropy using the attention operator is mathematically similar to having $n$ sequential self-attention layers that share weights. But weight sharing in transformers has been already studied in the literature and shown to improve the performance (e.g. see [A, B, C]).

[A] Xiao, Tong, et al. "Sharing attention weights for fast transformer." arXiv preprint arXiv:1906.11024 (2019).

[B] Reid, Machel, Edison Marrese-Taylor, and Yutaka Matsuo. "Subformer: Exploring weight sharing for parameter efficiency in generative transformers." arXiv preprint arXiv:2101.00234 (2021).

[C] Kowsher, Md, et al. "Does Self-Attention Need Separate Weights in Transformers?." arXiv preprint arXiv:2412.00359 (2024).

2. Re: "a mathematical approach for creating the hierarchy", as we stated in the paper, the HSA framework by itself doesn't provide any systematic approach to infer the hierarchy from data. Instead, the hierarchical structure is seen as domain knowledge which can act as inductive bias and subsequently encoded via the HSA framework. This leaves the door open for HSA to integrate with any manual or machine-learned hierarchy extraction method. Nevertheless, as shown by the results in Section 4.3 and Appendices J and L, in the absence of the hierarchical knowledge, one may still impose an "artificial" hierarchy on the input signal and still benefit from the regularization and speedup characteristics of HSA. Also, to further understand the sensitivity of HSA to the choice of the hierarchical structure (as the reviewer suggested), we have conducted ablation studies in Appendix L using four different imposed hierarchies across multiple datasets (please see Figures 7-13 in the appendix). As these experiments show, certain tasks can be more sensitive to the choice of the imposed hierarchy, while others are more robust. This further shows the strong correlation between the data geometry and the nature of the classification task and highlights the importance of cross-validation for picking a suitable hierarchical structure when prior domain knowledge is limited.

We are sincerely grateful to the reviewer for their insightful feedback and bringing up some important points that'd require our further explanation.

1. Re: "predefined depths", we would like to emphasize that our proposed HSA framework does NOT require the input hierarchies to have any pre-defined depth, size or shape. In fact, within a minibatch, each nested signal example can have its own different depth, size and shape, and this is already supported via an efficient implementation using the breath-wise tree concatenation technique in our codebase, as explained in Appendix E.4. In other words, the same way that the classical transformer architecture is invariant to the length of the input (flat) sequence, the HSA-based transformer architecture is invariant to the depth, size and shape of the input nested signal. In that sense, HSA-based transformer can very well handle "evolving" hierarchies. Now, if one wants to define a separate $Q$, $K$ and $V$ projection for each different modality in each layer of transformer (as proposed in Appendix F), these modalities need to be predefined, so one can know how many of such projections are needed in each layer. However, once these modalities (e.g. language and vision) are known, one may compose arbitrarily-shaped hierarchies using these predefined modalities and feed them to the same HSA transformer model. That said, as we explicitly stated in the paper, the HSA framework cannot "infer" the hierarchy; instead, the hierarchy and its implicit geometry are seen as external domain knowledge acting as a form of inductive bias. In that sense, hierarchy inference is completely tangential to the HSA framework, enabling us to use HSA in combination with any hierarchy extraction method. It should also be noted that, depending on the scenario, even when the hierarchical structure of the input isn't given or learned, we may still benefit from HSA by imposing "artificial" hierarchies on the input signal, and effectively using it as a form of regularization. In fact, all the results reported in Section 4.3 and Appendices J and L are obtained by incorporating imposed hierarchies.

2. Re: the multi-modal empirical study, we understand that the reported results are somewhat limited to one task. However, we would like to note that most interesting multi-modal tasks such as VQA, visual-language reasoning, etc. almost always require auto-regressive generation (ARG) as a key component of the model. But in this work, we have deliberately tried to stay away from ARG because incorporating HSA with ARG capabilities is not trivial and merits its own dedicated, follow-up work. Nonetheless, we have laid the foundation for hierarchical ARG in Appendix G to be elaborated upon in future work. In the meantime, for the purpose of this work, we will make this point clear in the final version of the draft to avoid any empirically unsubstantiated claim or confusion.

3. Re: integrating with large-scale vision-language transformers: The HSA framework can be in principle integrated with any multi-modal transformer architecture including large-scale vision-language transformers. Currently, many of such models naively put signals from various modalities on a simple, flat sequential geometry and instead rely on massive-scale pretraining to learn the underlying geometry of cross-modal interactions from data. However, if such geometrical information is partially available as domain knowledge, HSA can incorporate it within the proposed nested signal data structure to potentially reduce the statistical complexity of pretraining and finetuning large-scale transformers. For instance, assume that the input data consist of images with their corresponding scene graphs (where the scene graph's nodes are detected object bounding boxes with some textual descriptions while its edges model various relationships between the objects). Feeding such rich data structure to classical vision-language transforms often involves losing most of such rich geometrical and semantical information in the process of "flattening" the signal, and instead relying upon massive-scale pretraining to recover part of that knowledge. Whereas, it's quite seamless to encode such prior knowledge using the nested signal construct and perform self-attention operation on it using the HSA formalism.

4. Re: the computational overhead of HSA, first please note that the main overhead of HSA is building the hierarchy for the input signal. But that can be seen as part of the tokenization process, and similar to tokenization, it can be done only once on the CPU before training. As for the rest of computational analysis, we have provided GFLOP metric on various tasks with different context lengths in Table 3. As shown in the table, HSA has significantly decreased the required GFLOPs compared to the baseline. Furthermore, the reduction is way more dramatic for larger context lengths, as shown in Table 3. As for the exact time comparisons of HSA and the baselines, we'd like to note that such comparisons are heavily implementation dependent and rely on various CUDA optimization tricks. However, efficient CUDA implementation of HSA is beyond the scope of our current paper, which is primarily meant to lay the theoretical foundations of the proposed framework.

We appreciate the reviewer's insightful feedback and recognition of our fundamental derivation of hierarchical attention.

1. Re: the scope of our empirical study, we agree with the reviewer that our empirical study is somewhat limited to classification tasks and has not covered generative tasks which are key to modern LLMs. However, as we also stated in the main paper, addressing token generation is beyond the scope of the current work which is already somewhat dense presenting the theoretical foundations of the HSA framework. Nevertheless, in Appendix G, we have laid the theoretical foundations for hierarchical generation by proposing techniques to perform efficient causal masking and key-value caching under the hierarchical setting (which are both crucial to any realistic transformer-based LLM). Further empirical exploration of hierarchical generation has been deferred to future work.

2. As for VQA and Image Description tasks, we agree that both of these tasks involve more complex modality cross-interactions; however, those tasks are generative and, as mentioned above, outside the scope of our empirical study for this work, which is mainly focused on introducing the theoretical foundations for HSA and nested signals. Our goal is to address generative tasks in a follow up work dedicated to hierarchical generation.

3. Re: learning the hierarchy, as we have stated in our Limitations section, our HSA framework does not provide any mechanism to learn the hierarchal structure from data. In that sense, hierarchy is seen as a form of domain knowledge which injects strong inductive biases into the model and potentially reduces the statistical complexity of learning on top of improving the computational complexity. Nevertheless, depending on the scenario, one may be able to impose an artificial hierarchy in the absence of such domain knowledge or a parser. In fact, in Section 4.3 and Appendices J and L, we have not used any parser or domain knowledge for any of the experiments and all the reported results are based on purely imposed hierarchies (using various (fixed) branching factors at each level). As the results show, even with blindly imposed hierarchies for these problems, the HSA framework outperforms the baselines in terms of both accuracy and speed, highlighting the role of HSA as a form of regularization.