Answers.Body: <p>Yes. What you're describing seems to be similar to the <a href="https://arxiv.org/pdf/2110.13711.pdf" rel="nofollow noreferrer">Hourglass Transformer</a>, the <a href="https://arxiv.org/pdf/2006.03236.pdf" rel="nofollow noreferrer">Funnel Transformer</a>, <a href="https://www.semanticscholar.org/paper/Funnel-Transformer%3A-Filtering-out-Sequential-for-Dai-Lai/4ca3b0ea12f02e2dea01a4aa505956bae5500a09?sort=relevance#citing-papers" rel="nofollow noreferrer">among others</a>.</p>
  <p>Looking at the first paper, they consider two ways of downsampling tokens (upsampling methods are similar).</p>
  <ol>
  <li>Linear pooling: reshape <code>(n, d) -&gt; (n/k, k * d)</code>, with <code>k</code> being the downsampling factor. Then, use a linear map to project <code>k * d</code> to your desired output dimension.</li>
  <li>Attention pooling: First do simple 1D max/mean pooling to downsample across n: <code>(n, d) -&gt; (n', d); n' &lt; n</code>. Then, pass that into an attention layer (with residual connects), where the queries are the downsampled embeddings, and the keys &amp; values are the original embeddings. For example, you may start off with <code>x.shape = (10, 16)</code>, then do mean pooling to get <code>x_pooled.shape = (5, 16)</code>. Now, each vector in <code>x_pooled</code> gets converted to a weighted sum of vectors in <code>x</code> (attention operation) and added to the original vector in <code>x_pooled</code> (residual). This is described in more detail in the second paper.</li>
  </ol>
  <p>There's also approaches that instead do a discrete selection over tokens (e.g., <a href="https://aclanthology.org/2022.acl-long.602.pdf" rel="nofollow noreferrer">Pyramid-BERT</a>).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-20T16:24:45.353Z
Answers.Text: This is exactly what I am looking for. Thank you for your answer!
Answers.UserDisplayName: Andy Yermakov
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-20T17:51:08.543Z
Answers.Text: @AndyYermakov No problem! Also, please accept the answer if it sufficiently answers your question.
Answers.UserDisplayName: Alexander Wan
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-19T02:33:11.310Z
Answers.LastActivityDate: 2024-01-19T02:33:11.310Z
Answers.UserDisplayName: Alexander Wan
Body: <p>Do you know any papers that try to overcome quadratic scaling problems by attending lower dimensional representations in the dimension of tokens?</p>
  <p>For example, let's say that the input to the transformer is <code>(batch_size, token_number, hidden_dimension)</code>.</p>
  <p>Do you think it would make some sense to do let's say one Transformer Block (<code>TB</code>) and then map (by some weight matrix) <code>token_number</code> to let's say <code>token_number/2</code> and do <code>TB</code> again?</p>
  <p>The graph might look like this:</p>
  <p><code>input_tokens</code> -&gt; <code>TB</code> -&gt; <code>hidden_tokens</code> -&gt; <code>TB</code> -&gt; ... -&gt; <code>output_tokens</code> (might be equal to <code>input_tokens</code> in dimension)</p>
  <p>So, our shapes would be:</p>
  <p><code>(B, T, H)</code> -&gt; <code>(B, T/2, H)</code> -&gt; <code>(B, T/4, H)</code> -&gt; ... -&gt; <code>(B, T/4, H)</code> -&gt; <code>(B, T/2, H)</code> -&gt; <code>(B, T, H)</code></p>
  <p>where B - batch_size, T - token_number, H - hidden_dimension</p>
  
Tags: <reference-request><transformer><papers><gpt>
Title: Overcoming the quadratic scaling in transformer architecture
UserDisplayName: Andy Yermakov
ThreadText: # Overcoming the quadratic scaling in transformer architecture
  
  (Asked by: username_0 on 2024-01-17)
  
  Do you know any papers that try to overcome quadratic scaling problems by attending lower dimensional representations in the dimension of tokens?
  
  For example, let's say that the input to the transformer is `(batch_size, token_number, hidden_dimension)`.
  
  Do you think it would make some sense to do let's say one Transformer Block (`TB`) and then map (by some weight matrix) `token_number` to let's say `token_number/2` and do `TB` again?
  
  The graph might look like this:
  
  `input_tokens` -> `TB` -> `hidden_tokens` -> `TB` -> ... -> `output_tokens` (might be equal to `input_tokens` in dimension)
  
  So, our shapes would be:
  
  `(B, T, H)` -> `(B, T/2, H)` -> `(B, T/4, H)` -> ... -> `(B, T/4, H)` -> `(B, T/2, H)` -> `(B, T, H)`
  
  where B - batch\_size, T - token\_number, H - hidden\_dimension
  
  **Tags:** reference-request, transformer, papers, gpt
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-01-19. Score: 1 | Accepted answer
  
  Yes. What you're describing seems to be similar to the [Hourglass Transformer](https://arxiv.org/pdf/2110.13711.pdf), the [Funnel Transformer](https://arxiv.org/pdf/2006.03236.pdf), [among others](https://www.semanticscholar.org/paper/Funnel-Transformer%3A-Filtering-out-Sequential-for-Dai-Lai/4ca3b0ea12f02e2dea01a4aa505956bae5500a09?sort=relevance#citing-papers).
  
  Looking at the first paper, they consider two ways of downsampling tokens (upsampling methods are similar).
  
  1. Linear pooling: reshape `(n, d) -> (n/k, k * d)`, with `k` being the downsampling factor. Then, use a linear map to project `k * d` to your desired output dimension.
  2. Attention pooling: First do simple 1D max/mean pooling to downsample across n: `(n, d) -> (n', d); n' < n`. Then, pass that into an attention layer (with residual connects), where the queries are the downsampled embeddings, and the keys & values are the original embeddings. For example, you may start off with `x.shape = (10, 16)`, then do mean pooling to get `x_pooled.shape = (5, 16)`. Now, each vector in `x_pooled` gets converted to a weighted sum of vectors in `x` (attention operation) and added to the original vector in `x_pooled` (residual). This is described in more detail in the second paper.
  
  There's also approaches that instead do a discrete selection over tokens (e.g., [Pyramid-BERT](https://aclanthology.org/2022.acl-long.602.pdf)).
  
  > **Comments:**
  > **username_0**: This is exactly what I am looking for. Thank you for your answer!  
  > **username_1**: @username_0 No problem! Also, please accept the answer if it sufficiently answers your question.  
  
  ---
  
  