Working Notes: a commonplace notebook for recording & exploring ideas.
Home. Site Map. Subscribe. More at expLog.

Thinking Like Transformers

2025-08-05

I'm realizing I should just read everything written by Sasha Rush and I'll be much better of as an ml systems engineer.
While looking for some cuda projects I ran into Thinking Like Transformers, with the corresponding paper.

Abstract
- computational model for transformers
- map the basic components of the transformer-encoder
  - attention
  - feed forward computation
- into a programming language
  - Restricted ACcess Sequence Processing
  - model solutions that could be learned by a transformer
- simulate transformer computations using a discrete computation
- relate difficultly to heads and layers needed to encode a task
overview
- the transformer iterates not along length of input sequences
- but along depth of the computation == layers it applies to its input
- a computation over length-n input involves sequences of length-n and matrices of size n x n
- input = tokens + indices
  - user proveded input
  - range 0 -> n-1
  - output is a sequence, and consumer can choose to look at only specific locations
- possible transforms
  - element wise operations to transform sequences
  - select, aggregate operations
    - select takes k, q and a boolean over pairs; returns a selection matrx S where S = p(k, q)
    - aggregate operations take S and a sequence v, returns a sequence s which combies vaulues in v according to row i in S
rasp programs are lazy functional -- operate on functions instead of sequences
double histograms
- count for each token how many unique input tokens in the sequence have the same input frequency
- eg. hist(aabcd) [ 1, 1, 3, 3, 3 ]