Top all-time · #9743
when trees fall...
Personal blog · blog.wtf.sgaiprogramming
when trees fall... is a personal blog at blog.wtf.sg about ai and programming. Since 2010, 8 different Hacker News readers have linked it 14 times, most often “The New XOR Problem”. It is still writing: the last post was on 2026-02-28, and you can follow it by feed.
Too few sampled comments (1) to say how often HN recommends it.?
Why HN links it
Blog posts on the expressiveness and limits of Transformer neural networks, including "the new XOR problem", which links them to the Chomsky Hierarchy and formal languages.
Summarised by Claude from a sample of 1 HN comments that link here. Each comment is marked recommending, critical or neutral (citing without judging); how this works.
Most-linked posts?
- The New XOR Problem3 people · 8 mentions · first linked 2023-02-27
- Yes it's just doing compression. No it's not the diss you think it is2 people · 2 mentions · first linked 2025-09-20
What Hacker News says?
For the research focused, there are some references in my blogpost here on what kinds of computational problems minimally require how much CoT to solve: https://blog.wtf.sg/posts/2023-02-03-the-new-xor-problem/ Notably Will Merrill's work: https://arxiv.org/abs/2310.07923 As for how universal transformers (looping transformers, but everyone has since forgotten prior work) will affect this, Will Merrill (again) has a…
Comment linking /posts/2023-02-03-the-new-xor-problem/
on “GPT-6 Astra, looped transformers, and hidden reasoning”Submitted When trees fall: Programming, machine learning, and artificial intelligence as a story · 42 points
HN discussionYou're both kinda right. The type of computation that happens for that attention step that you refer to is parallel. I would say the thing that is "constant" is the computation graph depth (the number of sequential computations) which is actually important in computing certain functions. https://blog.wtf.sg/posts/2023-02-03-the-new-xor-problem/
Comment linking /posts/2023-02-03-the-new-xor-problem/
on “How Chain-of-Thought Reasoning Helps Neural Networks Compute”Submitted Neural Turing Machines FAQ as a story · 17 points
HN discussionNot sure if you mean in general, but I'll answer both branches of the question. In general: Depending on the method of compression, you can have lossy or non-lossy compression. Using 7zip on a bunch of text files can lossless-ly compress that data. Briefly, you calculate the statistics of the data you want to compress (the dictionary), and then make the commonly re-occuring chunks describable with fewer bits (encodi…
Comment linking /posts/2023-06-05-yes-its-just-doing-compression.-no-its-not-the-diss-you-think-it-is./
on “LLM-Deflate: Extracting LLMs into Datasets”Submitted The New XOR Problem as a story · 4 points
HN discussionYou should check out the work referenced in the abstract, the most recent here: https://twitter.com/lambdaviking/status/1630581475425828864 There are limitations for what a Transformer can compute if we do not allow for Chain-of-Thought type of output. By allowing the model to "show its work" allows it to effectively use the output as an "infinite tape". I'm simplifying but that's the basic gist of it. I'll shameles…
Comment linking /posts/2023-02-03-the-new-xor-problem/
on “Tighter bounds on the expressivity of transformer encoders”Submitted Neural Turing Machines – A first look as a story · 4 points
HN discussionI recommend reading the theoretical work on the computational capabilities of Transformers: https://twitter.com/lambdaviking/status/1630581475425828864 References to other work can probably be found in that article. Shameless plug to my own blogpost about this: https://blog.wtf.sg/posts/2023-02-03-the-new-xor-problem/ TL;DR: The theoretical class of problems that Transformers can solve (without Chain-of-Thought styl…
Comment linking /posts/2023-02-03-the-new-xor-problem/
on “Will a prompt that enables GPT-4 to solve easy Sudoku puzzles be found?”Submitted Yes it's just doing compression. No it's not the diss you think it is as a story · 2 points
HN discussionBeing technically maybe turing complete doesn't mean we know how to program it usefully. https://blog.wtf.sg/posts/2023-02-03-the-new-xor-problem/ To be completely fair, the Transformer architecture does not map neatly into being analysed like automata and categorised in the Chomsky Hierarchy. Neural Networks and the Chomsky Hierarchy train different architectures on formal languages curated from different levels of…
Comment linking /posts/2023-02-03-the-new-xor-problem/
on “Thinking Like Transformers (pdf)”Submitted The New XOR Problem as a story · 1 points
HN discussionShort version of this without the caveats: It's not even Turing complete. I review a few papers on the topic here: https://blog.wtf.sg/posts/2023-02-03-the-new-xor-problem/
Comment linking /posts/2023-02-03-the-new-xor-problem/
on “I made a transformer by hand (no training)”Submitted How to stay awake in class as a story · 1 points
HN discussion