Understanding Transformers via N-gram Statistics | Hacker News Reader

Understanding Transformers via N-gram Statistics

arxiv.org

139 pointspona-a16 comments

This paper was accepted as a poster to NeurIPS 2024, so it isn't just a pre-print. There is a presentation video and slides here:

https://neurips.cc/virtual/2024/poster/94849

The underlying data has been open sourced as discussed on his blog here https://timothynguyen.org/2024/11/07/open-sourced-my-work-on...

I wonder if these N-gram reduced models, augmented with confidence measures, can act as a very fast speculative decoder. Or maybe the sheer number of explicit rules unfolded from the compressed latent representation will make it impractical.

I'd also like to see a list of similarly-simple techniques for extracting rules where ML researchers could automatically try them all. In this case, the N-gram rules would be the starting point. For what predictions failed, they'd try to throw in the other techniques. Eventually most or all of the predictions should be captured by one or more simple rules. Some might be compound rules mixing techniques.

I think there will also be benefits to that both in interpretability and hardware acceleration. In time, maybe cheaper pretraining of useful models.

I don't have a list, but another popular one was this [0]. They trained a one layer attention-only transformer and could extract its weights as bigrams and skip-trigrams ("A… B C").

[0] https://transformer-circuits.pub/2021/framework/index.html

They literally can! The exact speculative method is supported on vLLM using `speculative_model="[ngram]"`[1]

1: https://docs.vllm.ai/en/latest/features/spec_decode.html#spe...

Not quite. The paper uses its own N-gram rules with positive/negative/invariant weights as a rudimentary attention, and these rules are distilled from the model itself.

This, as I found out from this repo [0] linked in the Twitter thread in the documentation (which for some reason they didn't just link to directly), seems to be a regular Markov chain of context, if it even builds a stochastic matrix. See algorithm below.

  Current prompt
  "Article: (CNN)French striker Bafetimbi Gomis, who has a history of [...]
  Summary: French stri"

  Prompt lookup algorithm
  1. Get last few tokens from prompt -"French stri"
  2. Search for "French stri" in prompt
  3. Match found - return next k tokens after match as candidate completion -"ker Bafetimbi Gomis, who has"

  Candidate tokens
  "ker Bafetimbi Gomis, who has"

[0] https://github.com/apoorvumang/prompt-lookup-decoding

> The results we obtained in Section 7 imply that, at least on simple datasets like TinyStories and Wikipedia, LLM predictions contain much quantifiable structure insofar that they often can be described in terms of our simple statistical rules

> we find that for 79% and 68% of LLM next-token distributions on TinyStories and Wikipedia, respectively, their top-1 predictions agree with those provided by our N-gram rulesets

Two prediction methods may have completely different mechanisms, but agree sometimes, because they are both predicting the same thing.

Seems a fairly large proportion of language can be predicted by a simpler model.. But it's the remaining percent that's the difficult part; which simple `n-gram` models are bad at, and transformers are really good at.

I've always thought that LLMs are still just statistical machines and that their output is very similar to the superpermutation problem, though not exactly.

I just like to think of it as a high dimensional view of the relationships between various words and that the output is the result of continuing the path taken through that high dimensional space, where each point's probability of selection changes with each token in the sequence.

Unfortunately there's no thought or logic really going on there in the simplest cases as far as I can understand it. Though for more complex models/different architectures anything that fundamentally changes the way that the model explores a path through space like that could be implementing thought/logic I suppose.

It's why they need to outsource mathematics for the most part.

How does this have 74 points and only one comment?

on topic: couldn't one in theory, re-publish this kind of paper for different kinds of LLMs, as the textual corpus upon which LLMs are built based off ultimately, at some level, human effort and human input whether it be writing, or typing?

"How does this have 74 points and only one comment?"

I think one cause is hobbyists upvoting submissions that might be valuable to people in a specific field. We understand just enough to think it could be important but defer to subject matter experts on the rest. That's why I upvoted it.

https://en.wikipedia.org/wiki/Warnock%27s_dilemma

Interesting! Makes me wonder if you could replace transformers with some sort of fancy Markov chain. Maybe with a meta chain that acts as attention.

Sounds regressive and feeds into the weird unintellectual narrative that llm is just like ngram models (lol, lmao even)

Thr author submitted like 10 papers this May alone. Is that weird?

These are different people:

https://arxiv.org/search/cs?searchtype=author&query=Nguyen,+...

Wikipedia mentions that up to ~40% of the Vietnamese population (~40,000,000 people) carries the name Nguyen:

https://en.wikipedia.org/wiki/Nguyen

For the paper itself, as someone working in the field, I find it interesting enough to consider reading at some point (I do not read that many analysis papers recently, but this one looks better than most). As for your accusation about it claiming that large language models are simply n-gram models, read the abstract until you realise that your accusation is very much unfair to the work.

> Thr author submitted like 10 papers this May alone. Is that weird?

Chances are, you just assumed all the search results for 'Nguyen, T' refer to the same author.

I did. My bad.

Reply on news.ycombinator.com