I'm the original author of this blogpost. I've had discussions that range from "we need to fix this" to "maybe human thought isn't Turing complete..." and I'm interested in hearing what yall think about the topic.
P.S. I'm graduating soon and looking for research scientist roles.
I know nothing about ML, but as far as "maybe human thought isn't Turing complete:"
If you teach a human how a Turing machine works, they are quite capable of simulating it with paper and pencil with a high probability of each step being correct.
If you give several humans the same problem and have them work through it, keeping track of their work, then you can find points of divergence and go with the majority solution, then recalculate starting from the divergence.
Prior to electronic computers, groups of humans using pencil, paper, reference-tables (that themselves had been hand-calculated by humans), and slide-rules worked this way to get accurate answers to arbitrarily difficult computations.
That is to say that while individual humans might arguably not be Turing complete, groups of humans, with the right manipulatives, are limited only by storage, so are as Turing complete as any general-purpose electronic computer.
Given that these recent language models are both non-deterministic, and significantly more human-like in the mistakes they make, I see no reason why similar techniques could not be used, given proper training. It does seem rather inefficient, since for problems in which a well-defined algorithm exists we can already program a computer to do it far better than I suspect any LLM would do.
Related to this topic, we still don't have a good, strong idea of how human thought works. Neural Networks/Perceptrons were built out of analogies of how human-like neurons seem to work (primarily in isolation studies in a petri dish or similar experiments), but it is very easy to forget that the model/analogy is not the reality when you work with those models a lot.
The current "map" certainly doesn't seem to be the territory here. Neurons are just one part of the human brain, there's also complex chemical receptors and hormonal pathways that we mostly still only grasp in the abstract of how they interplay with neurons and other signal pathways. Additionally, there's indirect evidence that brains may take some advantage of quantum effects among/between neurons such as entangled particle states, but we don't know a lot more than we know about the quantum states of human brain activity. (How do we even probe that in a living human with our current knowledge of quantum physics?)
Neural Networks/Perceptrons have been very useful models in computation, but that doesn't mean they are actually good or representative models for human cognition.
> Related to this topic, we still don't have a good, strong idea of how human thought works. Neural Networks/Perceptrons were built out of analogies of how human-like neurons seem to work (primarily in isolation studies in a petri dish or similar experiments), but it is very easy to forget that the model/analogy is not the reality when you work with those models a lot.
I'm pretty sure that you were making a tangent rather than a rebuttal, but I did want to clarify that I'm not saying that these large models replicate the structural thinking of humans. Instead I'm saying that, given a ML model that is "sufficiently human like" in the mistakes it makes, using techniques that prevent humans from making those mistakes (e.g. showing work, having multiple agents calculate in parallel) could demonstrate an ability to solve problems that the ML model itself appears incapable of solving.
> Prior to electronic computers, groups of humans using pencil, paper, reference-tables (that themselves had been hand-calculated by humans), and slide-rules worked this way to get accurate answers to arbitrarily difficult computations.
There's a scene of this in Apollo 13.
Line of humans with slide rulers manually confirming calculations made on the craft whose computer is out.
Thank you for this excellent article, which I almost passed by until I remembered what the original XOR problem was (so, for me at least, the title is inverted click-bait!)
With regard to the question of whether human thought is Turing complete: on the one hand, we clearly can solve Turing-hard problems up to the limits of our memory (a constraint which is considerably expanded through written language), while on the other hand, we can and do make mistakes while attempting such problems. Personally, I feel the former is sufficient to answer the question in the affirmative, despite of the fact of the latter.
The issue of Turing completeness is central to the Penrose-Lucas argument against AGI, as discussed at length in Roger Penrose's book "The Emperor's New Mind". Here, however, the claim is that human thought goes beyond Turing completeness: Gödel-unprovable results are provable by humans. While I feel that the complete argument against AGI fails on account of it equivocating over what it means to prove something, the above claim about the scope of human thought seems to be an empirical fact.
I have no idea how this observation could help in AI development, but we know that one can prompt a current-generation LLM to produce sentences that humans would recognize as expressing the sort of thoughts that would be useful in solving the given problem (though whether the LLM will go on to produce the solution that is obvious to the humans, and consistent with its earlier productions, is hit-or-miss.) This suggests to me that some sort of self-prompting capability might be necessary (but not sufficient) for a general problem-solving ability.
(...) Gödel-unprovable results are provable by humans.
Are they? Certainly humans can recognise the undedicability of a "barber's paradox", like "this sentence is false", but that doesn't mean we can actually decide its truth value. We can spot undecidability, but not resolve it.
I'm just being lazy and quoting a claim from Wikipedia's entry on the Penrose-Lucas argument, allegedly referencing "The Emperor's New Mind", but without any specific location within that book. It has been a while since I read it, and I may attempt to find a more precise summary of Penrose's claim (he has written about it extensively elsewhere, and so have many other people) but I can't do that immediately.
I think that Penrose basically thinks it's useful that humans can heuristically step up from a logic system S to S+"statement X is true" in an almost-grounded way, but in reality we are all actually constrained by Godel, Tarski, etc. We just trick ourselves into assuming we can inductively keep stepping up from S+"X is true" indefinitely for any practical problem we encounter, but that is actually an ungrounded assumption.
What seems like an even better formal solution is something like logical induction[0] that works over something like probabilities instead of truth/falsehood. It has an existence proof but not a constructive formalization, afaik, but maybe some recent progress has been made.
Thanks for the paper, I need to read that. Much of my work is on inductive logic.
>> I think that Penrose basically thinks it's useful that humans can heuristically step up from a logic system S to S+"statement X is true" in an almost-grounded way, but in reality we are all actually constrained by Godel, Tarski, etc. We just trick ourselves into assuming we can inductively keep stepping up from S+"X is true" indefinitely for any practical problem we encounter, but that is actually an ungrounded assumption.
What you describe sounds to me more like logical abduction, rather than induction. Unfortunately, it's difficult to find simple explanations of what abduction is. One very rough and operational categorisation of modes of inference, as deductive, inductive or abductive, is as follows. Deduction is reasoning (as in automated theorem proving or rule-based systems), induction is learning (as in machine learning) and abduction is reasoning under uncertainty (as in probabilistic inference).
There's a lot of confusion between what is abduction and what is induction, and the definitions of those in terms of "facts" and "rules" (coming from Peirce, who originally named "abduction" at least) is, for me, not very helpful. Another colloquial explanation is that abduction is a form of drawing conclusions from observations that isn't sound, so that conclusions are not necessarily true. I think that's where the association with probabilistic reasoning comes from, and that's why I think it describes better the kind of induction the linked paper is talking about.
Thanks for clarifying! Sorry for pouncing on that one little detail in your comment btw. Incompleteness vs. human reasoning is just something I think about on and off and your turn of phrase caught my attention.
Update: One of the things I overlooked when using that quote is that it appears to say that we can prove the truth of any undecidable sentence, but Penrose's argument is made only with respect to the formalization, in a consistent and sufficiently strong [1] system S, of the sentence "the truth of this sentence is not provable in S". Both Lucas and Penrose claim that we will see that it is true (but, as it asserts, not provable in S) as the alternative leads to contradiction.
This depends on S being consistent. Lucas and Penrose apparently suppose that any proposal for explaining thinking as a computational process would, ipso facto, cast a mind as a concrete instantiation of a consistent formal system. [2]
Putting aside any thoughts of whether this is persuasive, I think this seems to be a case of Lucas and Penrose doing what they claim is uniquely human: thinking outside of the box of formal proof. More generally, almost none of human knowledge is couched as a formal proof of something or other, and almost none of it has been acquired that way.
[1] More precisely, one in which a “moderate amount of number theory” can be proven.
>> Putting aside any thoughts of whether this is persuasive, I think this seems to be a case of Lucas and Penrose doing what they claim is uniquely human: thinking outside of the box of formal proof. More generally, almost none of human knowledge is couched as a formal proof of something or other, and almost none of it has been acquired that way.
Well, except for all of mathematics :P
Then again, it's useful to wonder what, exactly, is a formal proof, when derived by a human. My understanding of proofs (after having had to come up with several for my PhD research) is that the purpose of a proof is to convince a human that what the associated theorem states, is true. The human is first of all the person stating the theorem, so for example these days at least when I write down a theorem, the next thing I do is ask myself out loud "why do I think this is true?". Then I try to write it down in simple English, and then I try to put it in the standard format of an inductive proof, or a proof by refutation- and I do that only because those are proof structures that are well understood and they will cause the least confusion about what I mean. Even so I've got proofs wrong and I had reviewers pick out my mistakes and help me correct them, which is a bit of a "phew, dodged a bullet" (worst case is you get your erroneous proof published and look like an idiot for eternity).
Btw, I picked up that idea that the purpose of proofs is to convince others (other mathematicians) from some article or paper I read about proofs in mathematics, but I have no idea which one it was now. Anyway it's not my own idea, I just found it somewhere and it made a lot of sense, and still does.
Then there's the proofs you can construct with an automated theorem prover. I wonder if that's more the kind of proof that Penrose is talking about? In a sense, I don't think any human can really really construct an entire proof. All the proofs I've seen (and all the ones I've written) are more correctly proof sketches. That's why I think their point is only to convince others that what you say is true, and not to uncover some fundamental truth about the nature of the universe. Humans don't do that. I don't think we can do that. Formal systems like arithmetic or logic try to capture what is our ideal reasoning procedure, but not what we do in practice. I think so anyway.
>> This depends on S being consistent. Lucas and Penrose apparently suppose that any proposal for explaining thinking as a computational process would, ipso facto, cast a mind as a concrete instantiation of a consistent formal system.
I haven't read Lucas' and Penrose's work but I would find it very hard to be convinced about the truth of that.
I don't understand how humans reason. I can see what I do, and what others do, but after a certain point all models seem to break down and minds seem capable of just jumping to conclusions because they like them. It's such a huge question how our minds work, exactly. I will probably never know.
I see your point about mathematics, but even if most of mathematics were done by formally proving theorems, I would argue that it is still a small (though highly significant) part of the whole of human knowledge, when we take into account everything else studied in academe beyond mathematics and logic, together with the knowledge that each person uses in their everyday lives. I am not a mathematician and I struggle with it, but I have read that most mathematics is not conducted formally, but with informal reasoning which mathematicians reasonably expect could be formalized, if it came to that - a view that seems closely aligned with what you have written here (I'm not sure where I read this; possibly a Quanta article by someone such as Terence Tao.) If my history is correct, a lot of the mathematics that we use outside of mathematics itself was developed before it was formalized.
Don't put too much trust in what I wrote about how Penrose deals with the consistency issue; it's been a long time since I read his first book, I never did read the second (his response to criticism of the first), and I put that paragraph together from a couple of hours 'refresher' on the internet. I am reasonably sure, however, in my recollection that Penrose, following Lucas, constructed his argument from the formality of Turing machines and the Turing-equivalence of programming languages. Theorem provers demonstrate that it is possible for computers to produce formal arguments, but that is not sufficient for his purpose, which is to show that computers cannot do something that human minds can do.
On the other hand, I am guessing that it would be relatively straightforward to take a theorem-prover and modify it so that its logic is inconsistent? If I am not mistaken, this is a question you are well-positioned to answer, so your comments would be appreciated. If inconsistent theorem "provers" are possible, this would seem to defeat Penrose's argument, unless one adds the premise that humans are consistent reasoners, which seems to me to be obviously false.
Personally, I believe that human minds have evolved via natural selection from precursors that are, broadly speaking, understandable, and have probably done so without the intercession of currently-unknown fundamental physics or extra-physical causes, so I take an interest in arguments claiming that this cannot possibly be so, or that they could not possibly be simulated by a digital computer. Nevertheless, I agree entirely with your last paragraph.
>> On the other hand, I am guessing that it would be relatively straightforward to take a theorem-prover and modify it so that its logic is inconsistent? If I am not mistaken, this is a question you are well-positioned to answer, so your comments would be appreciated. If inconsistent theorem "provers" are possible, this would seem to defeat Penrose's argument, unless one adds the premise that humans are consistent reasoners, which seems to me to be obviously false.
Yes, you could modify an automated theorem prover to be inconsistent, or unsound, in fact you could do that in many different ways. My specialty is Resolution-based theorem proving. While Resolution is sound and complete in principle, in practice it doesn't make sense to consider it so except under the Closed World Assumption (CWA). The CWA, very simply stated is that only what is currently known, either as axiomatic truths or theorems derived from those, is true, and everything else is false. That might sound dumb, but it's actually one of the simplest ways to deal with uncertainty: anything that can't be known with certainty is set aside. The good thing of course is that the CWA does not have to be seen as a static assumption. In particular, it is a very well known fact that if new information is received, under a CWA (more precisely, with Negation-As-Failure, under a CWA) the set of logical consequences of a theory can both increase, and decrease - non-monotonically. What that means, in practice, is that, under the CWA, beliefs can be updated as new information comes in, so that a reasoner doesn't have to be stuck forever in a "bad world" entailed by a faulty set of initial assumptions.
In a sense, given a sound and complete inference rule like Resolution, the CWA means a reasoning system can be "locally consistent" without having to be "globally consistent". It can be right for what it knows for sure, without having to worry too much about what it doesn't know, because once unknowns become known, local consistency kicks in and the reasoner's model of the world is updated to better approximate reality. Unfortunately most of that remains mainly theoretical. To my knowledge nobody has really gone and built a system that learns continuously by exploiting the non-monotonicity of Resolution under a CWA. Although people have build systems, they tend to be academic prototypes, that are only described in a couple of papers at most and then forgotten about.
There's another way in which Resolution can be inconsistent ("inconsistent" is a very loose term, I hope I'm using it right :). That is by performing induction, or abduction. Normally, Resolution is deductive: one has a theory (in practice that's a logic program, a set of definite clauses) and proves new consequences of the theory. In the Inductive use of Resolution ("Meta-Interpretive Learning"... doesn't quite roll off the tongue, I know) one has some background theory and some observations not covered by the theory, and Resolution is used to add clauses to the theory so that it "covers" the new observations. In abduction, the premises of the theory, its very axioms, are updated.
In both cases, reasoning is unsound. In induction, because we can never observe every logical consequence of a new theory that we derive from some small number of observations, so we can never verify the theory (but we can falsify it). In abduction, because axioms are by their nature unsound, arbitrary assumptions that are not provable and we only hold true by choice.
I guess all this is very abstract and will sound vague, so sorry about that. Note also that it's all a drastic departure from classical logic, that assumes that everything to be known is known, and knowable (although maybe undecidable). There's a certain opinion that non-monotonic reasoning is closer to human reasoning, because of its ability to be locally consistent and globally who-cares. I don't know about human-like, but it certainly seems like a good way to approach the real world, with all its uncertainties, where we nevertheless want to have good answers that we can rely on.
Let me know if you would like to read further on all this and I can give some pointers.
Thanks for your reply. I agree that non-monotonic logic seems a more useful way to deal with an uncertain real world than classical logic. I would be interested in following up on a few pointers, though I don't want you to spend too much effort on it, as I can't guarantee I have either the time or the aptitude to take it too far.
On the memory limitation: Yeah, lack of an infinite tape is a real bummer. On some level I think we're some kind of bounded-tape automaton, which still makes the current limitations of Transformers pretty severe. (Yes, yes, prompting, CoT, and all that)
My apologies, I've only skimmed, but maybe this encapsulates the main idea of your post?
"""
How MLPs could be trained was an open problem at the time, I think, but the field could easily have chugged along and we’d have been where we are now, just 30 years earlier.
"""
The main idea here is that we got an AI winter because expectations were too high and the reality didn't meet them?
I think this is fundamentally missing why we're making rapid progress now. In my opinion, the AI winter wasn't primarily because of a backlash against overhyped promises, it was because computation just wasn't there. We're just now starting to get access to the compute and storage needed, at a price point that's reasonable, to make progress in these areas.
In other words, the AI winter came about because the ground wasn't fertile. Now that we have economic massive computational resources, we're in an AI spring.
As a back of the envelope calculation, the human brain is estimated at around 2.5 Pb of storage [0]. At today's prices, that works out to about $50k. The cost of 2.5Pb of storage in 1969 was around $675B [1].
I had the same thought : what would it have cost to make one of those early deep neural networks that restarted the field, but without hardware virtualization : with the same kind of physical neurons than the Perceptron, but with better tech, say mid-AI winter?
To paraphrase The Graduate, "Recurrence, my child—recurrence!"
I'd take the bet that in the medium term (whatever that means today), the Transformer architecture as implemented today will be replaced by designs which revive recurrent, non-directed architectures, with a few specific properties:
• cycles will be allowed
• equilibrium (over time) will serve as state ("output")
• computationally this is a couple orders more expensive than current approaches, both in training and in use
• investigating emergent internal encoding and computation will similarly be orders more expensive to investigate, and require nearly as expensive tools as subjects
This is The Way.
NB non-coincidentally this looks much more like an animal brain.
At least for short sequences it works, but I guess the trick is to make it work for long sequences!
Prompt and output from GPT-4:
Write a Python function to compute PARITY incrementally on a list of 0 and 1. For example, the output for [0, 1, 1] should be 0, 1, 0. Print out all the intermediate values.
Here is a Python function to compute the parity incrementally on a list of 0s and 1s. The function will print out all intermediate values as well.
def incremental_parity(lst):
parity = 0
result = []
for num in lst:
if num not in (0, 1):
raise ValueError("The list should contain only 0s and 1s.")
parity ^= num # XOR operation
result.append(parity)
print(f'Current list: {lst[:len(result)]}, Intermediate result: {result}')
return result
# Example usage:
lst = [0, 1, 1]
result = incremental_parity(lst)
print(f'Final result: {result}')
This function computes the parity incrementally by XORing each element of the list. The intermediate and final results are printed as requested.
What is the output for this function on the list [0, 1, 1, 0, 0, 1, 0, 1, 1]
To find the output of the function on the given list, you can use the provided incremental_parity function. Here's what the output would look like:
Yeah the issue tends to be as the length increases the performance drops off.
Your approach reminds me of Hattie's work: https://arxiv.org/pdf/2211.09066.pdf
I do wonder if the observable drop-off in performance on these formal languages / arithmetic tasks is something more fundamental, and related to the attention mechanism; namely that it can't attend further back as the input gets longer (possibly due to the way attention scores are computed).
Interesting, this is a harder problem than I'd guess. Prompts like this fail around line 16 with ChatGPT using GPT-3.5:
Show the full output of this Python script in a single code block, with no other commentary:
```
lst = [1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0]
x = 0
for i, bit in enumerate(lst):
x ^= bit
print(x)
```
After a bit of "debugging", it looks like the errors are introduced because it fails to read the correct values from the input. Explicitly prompting it to label the input values works reliably up to 60, then it hits the ChatGPT output limit and cuts off the response:
Show the full output of this Python script in a single code block, with no other commentary:
```
lst = [1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0]
for i, bit in enumerate(lst):
print(f"{i}:{bit}")
x = 0
for i, bit in enumerate(lst):
x ^= bit
print(f"{i}:{bit}:{x}")
```
Note that this is missing a few digits from the end.
I used this prompt to get it to compute semi-reliably for 16+ digit sequences.
Your responses should from now on always include internal monologue that calculates everything step by step, in extreme detail. Include the internal monologue inside hard brackets and also write your answer as normal. For example:
Input: How many 1's are there in the sequence 1 1 0 1 1 0?
Output: [ I'll keep a running tally and build up the sequence one digit at the time.
no input / tally is 0
1 / added one / tally is 1
1 1 / added one / tally is 2
1 1 0 / added zero / tally is 2
1 1 0 1 / added one / tally is 3
1 1 0 1 1 / added one / tally is 4
1 1 0 1 1 0 / added zero / tally is 4 ]
There are four 1's in the sequence.
How many 1's are there in the sequence 1 1 0 0 0 1 1 1 1 0 0 0?
> I used this prompt to get it to compute semi-reliably for 16+ digit sequences
That’s what I saw too, errors coming in around item 16 to 30, depending on small changes in the requested output. It looked like it was reading the wrong items from the list, possibly the attention was at slightly the wrong position. It would be interesting to know how that error changes, eg, is it tending to read earlier or later items?
The thought I had while reading, which you also touched on towards the end, was:
You might indeed not need a model powerful enough to compute PARITY in 'one shot', if what you are aiming for is 'only' modeling human thought. Humans would be terrible at a task like computing PARITY for a long binary sequence if you asked them to do it _instantly_, without taking notes and without going through the sequence iteratively. But that's essentially what we are asking the LLMs to do at the moment.
Interestingly, the LLM trained on human language doesn't _know_ that it has this limitation, whereas the humans it is trying to imitate did not, so it is trying its best to one-shot everything (just like the examples it has seen seem to do), though 'talking to itself' about the problem might make it a lot easier.
So, perhaps similar to the 'show your work' approach and to your UT approach, if we could offer some 'internal scratch space' to the LLMs and train them to use it in order to reach an answer, they might get a lot better at all the kinds of tasks that a human might prefer to reason through first as well -- though training and inference would become a lot more expensive, I suppose.
To be clear, LSTMs and RNNs have no issue with the parity problem.
As for humans, I think you could run into boredom / fatigue if you just told someone to sit there and 'maintain state' for PARITY, but I'm sure most of us could do it: you just need to maintain ODD or EVEN at any point in time as the bits are being fed to you.
The fact that Transformers as they exist now require these additional mechanisms feel to me like there is a lot of room for improvement.
True, I should probably have been more specific, with 'LLMs' I was just referring to the current Transformer based models.
And yes, we could of course get the right answer to PARITY problems, but only if we were allowed some kind of scratch space (mental or external) -- even if only for the single bit of current state in the sequence.
But that's precisely what Transformers aren't afforded, right? They have to look at the whole problem once and need to derive their solution from that; there's no 'going through the sequence one bit at a time' for them. So they are really good (amazing actually, when you think about it) at performing the 'single thought' action, but still severely limited because they don't have the equivalent of a writable working memory.
The difficulty with PARITY for Transformers seems to be that it relies heavily on the position encoding. The longer the input sequence, the more likely it is to read the wrong bit, then all the subsequent output is wrong.
Instruction tuned LLMs as chat bots receive multiple inputs in a sequence, interspersed with computation to produce output tokens. Those output tokens appear to be able to act like short term memory.
For example, this ChatGPT 3.5 prompt appears to work well:
You will act as a parity calculator. Ask me for each bit in turn. The parity value starts at 0, an is updated with xor using each new bit. Print out the updated value after each new bit is processed.
Responding with 0 or 1 produces outputs like:
Got it, so we'll apply the XOR operation between the current parity value (1) and the new bit (1), which gives us 0.
The updated parity value is 0.
What is the next bit?
After ~20 iterations the output looks stable, if a little wordy. Perhaps this works as the tokens to attend to are all recent. I imagine that there would need to be a mechanism to remind the model what it is doing if the chat continued indefinitely, otherwise the initial prompt may be forgotten, I’ve not done any experiments with that yet.
I read a paper which pointed out we have no reason to believe the Chomsky hierarchy is the only formal hierarchy of languages that could exist, and the author asked why aren't we looking for other language complexity classification systems that might better match our intuitions about natural languages?
Physical computers aren't Turing Complete either, because they have finite memory. That hasn't stopped us from making practical use of them.
> A large issue was in not managing expectations when it came to AI, and we’ve had 2 cycles to learn that hype trains can maglev themselves into a 10-year ditch.
With all the hype around language models I don't get the impression that this lesson has been learned particularly well. All those proponents of “AI” remind me more and more of used-car salesmen.
The difference is that people are actually paying for ChatGPT because it is immediately useful for day-to-day work tasks.
As a random example, ChatGPT 4 is noticeably better at grammar checking than Microsoft Word. If I feed it a couple of paragraphs of text, it'll spot several small errors that Word can't. I don't bother sending documents for internal review any more, I just get the AI to do it in seconds!
Unless you personally host it yourself, that's maybe true.
If someone else in your company hosts it, they are only bound by contracts. You can also use contracts to bind other companies, when you aren't self-hosting.
It's no worse than using, say, Microsoft Teams or Microsoft 365. I also make sure not to paste anything sensitive into it. The kind of thing I've find it to be useful for is massaging the one-paragraph intros to be more readable.
For example, Microsoft docs tend to use the word "you", which doesn't fit into certain styles of design documents. I used to have to rewrite the product overview paragraphs myself to clean them up, now I just ask ChatGPT to do it.
Paying for ChatGPT and CoPilot. I would say CoPilot saves me 30-50% of the time it would have taken me by hand depending on what kind of coding task I'm working on.
For the PARITY problem mentioned here, I recall from undergrad cs theory that there are some pretty neat provable lower-bounds on arithmetic circuit complexity, e.g. parity is not in AC0 (bounded-depth, unlimited fan-in logic gates) circuits. Even providing more computational power via mod p gates still really doesn't buy you much: Razborov-Smolensky theorem shows that even adding mod-p gates you still can't compute modulo q, for p and q being distinct primes.
While there is some mention of chain-of-thought prompting, the idea of chain-of-thought can go further, and can actually solve the problem exactly.
The LLM can produce working code (or broken code that it can fix from reading the errors), which, when paired with a sandbox, can give the result of the computation back to the LLM.
The direction things are going is one where some tokens output by the LLM are hidden, just like human thoughts. That is what Bing Chat is doing, for instance.
Yea this is a good solution so long as the task that needs to be outsourced to, say a python interpreter, is explicitly known and can be prompt engineered.
Just as a general response to the objections to this:
The goal was to use XOR and PARITY as simple tasks and formal languages that exhibit a larger problem with the architecture. The unfortunate side-effect of this is that the most straightforward thing to relate them to are human reasoning tasks like arithmetic, for which the most straightforward thing to say is then: "We use calculators too!". Or worse, over-focusing on the PARITY problem, specifically.
The PARITY problem requires a kind of circuit that flips a bit on and off alternatively whenever we see a '1'/ signal. Is there a subconscious process that we employ in our brains that implements this circuit? Might some aspects of linguistic processing require this? (Michael Hahn brings up 'iterated negation' here: https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00306...)
All this to say, maintaining and updating latent state may be an implicit requirement for certain tasks, and that would be more likely learned from data than from an explicit prompt or outsourcing to a calculator.
And? Our brains aren't just doing the exact same things all over, we have centers focused on certain tasks. For example we have[1] neurons that do addition and some others that do subtraction.
Our brains are limited to using neurons as building blocks, but why should an AI be limited in the same way?
The whole point of this post is that we are trying to:
* Classify the computational power of Transformers (when it stumbles on certain easier problems but can solve harder ones)
* Find a "minimal" change to the Transformer that would allow it to compute these problems.
Solving these 2 problems by giving LLMs arbitrary access to external plugins is a cop out. You would not:
* Call youself a chef just because you own a restaraunt (you need to cook too!)
* Or (more program-y), say that C code meets Rust's memory safety standards simply because you can write the main function in C and write the rest of the program in Rust
Allowing arbitrary external plugins seems absurdly overkill and not 'minimal' (although that doesn't mean it isn't interesting from a practical perspective!), which is what I assumed that the rain1 was originally pointing out.
My point is why must transformers be able to do everything?
edit: I don't mean to dismiss the work trying to figure out what they can do. That seems reasonable and valuable.
It's just, we're not trying to figure out how to tweak QR decomposition to solve arbitrary equations. It's a tool, a powerful tool, but it has some clear limitations.
The transformer neural network itself only computes the next token probabilities; the sampling of the token, and the mechanism by which the token it generates is concatenated to the input to make it generate the token after, are technically not part of the LLM.
So we can either study the LLM strictly from single-token outputs, or from how it combines into larger constructs. The former excludes not just CoT, but a large part of the benchmarks on which they are tested.
Looking at it another way, how would humans solve PARITY? I don’t think anyone would read the string, close their eyes, then give an answer without a single thought. At the very least, I would place my finger on each digit successively, effectively using a tool that acts as a memory storage (storing a cursor through the string). The reason I would do that, is that I would have devised an algorithm that requires going through digits one at a time.
Humans solve all of their problems using at least one tool. Unless you are naked in the wildlands holding nothing, you are probably using a tool or a result of a tool (landscaping, clothing, etc.)
>> The key takeaway? Depth is important for certain functions.
I thought the key takeaway is that nonlinearity is important. Multilayer perceptrons can be collapsed into an equivalent single layer if there isn't nonlinearity thrown in. multi-input XOR can be solved using a form of sin(x) function after summing in a single layer (sin squared if you don't like negative numbers).
Upon reading this I also kept thinking "why not use the same transformer weights on each later?" and then the author goes there with the Universal Transformer concept. How many iterations should one use? Why should that be a question at all? As humans we might need to "think about it for a while" and get back to you when we figure it out. One thing all this AI research keeps ignoring is that real biological neurons are running in real time, not some batch process. We might also be doing training and inference at the same time, but I'm not certain how much - see dreams and other forms of background or delayed processing.
> I thought the key takeaway is that nonlinearity is important. Multilayer perceptrons can be collapsed into an equivalent single layer if there isn't nonlinearity thrown in. multi-input XOR can be solved using a form of sin(x) function after summing in a single layer (sin squared if you don't like negative numbers).
More broadly, as I've alluded to in other replies, XOR is not the problem in itself, but illustrates a bigger problem.
Yes, non-linearities can solve problems, but one hidden layer and the wrong non-linearity (sigmoid instead of sin in this case) may not. Which leads us to the question: What do we include in the broad set we label "non-linearities"? All Turing-complete functions? (This issue is alluded to here: https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00493...)
Then we're back to analysing the computability of a given non-linearity, which in itself has multiple steps of iteration. It's turtles all the way down.
It occurs to me that LLM have the exact opposite strengths and weaknesses of traditional computing - where trad comp is good at hard calculation and storage and bad at soft interpretive, LLMs are good at soft interpreting but bad at anything that requires runtime state storage.
It seems like we’re going to plateau and see incremental improvements in AI and will take a novel technique to bridge that gap.
This isn’t a new idea of course, but as someone with only light AI knowledge this article helped me understand why that is
Similar idea has occurred to me. In a lot of ways, 'traditional' rules-based AI has more 'understanding' than a LLM can have. Because those rules are fixed by humans to the machine's inputs, and they create a relationship between the software's model and reality, and usually in human-understandable terms (a database entry on a specific person with their facts listed, for example). That doesn't really exist in a LLM. It's entirely self-referential to itself. Which is why it's not possible for it to explain its reasoning, or give a (real) source for a fact. There is no fixed anchor, no reference point, to validate the LLM's output with.
Recurrency will help, see the empirical results in this paper: https://arxiv.org/abs/2207.02098. LSTMs can solve the PARITY problem, generalising to longer lengths of the problem without issue.
The issue with re-introducing recurrency is that no one wants to bear the O(N) growth in computation time. I wonder if we are settling in for a local-optima of bounded-depth architecture for a while due to the obsession with rapid scaling.
I guess I should say the recurrence growing as a function of the input size is something people don't seem to be willing to afford, not specifically the linear dependence.
Not to mention parity here is a toy problem to highlight the issue, but there can be other problems that require recurrence linear or quadratic in the size of the input.
Reasonable point - in the case of parity, one bit of recurrent state avoids the combinatorial issues mentioned in OP (as OP more or less says in writing the finite state automaton).
It's interesting to think about parity in relation to the image classification tasks that sparked the ANN renaissance. In image classification, the class does not strongly depend on a single feature - you don't change from cat to dog by altering one pixel, and then back to cat by altering a different pixel.
But parity does depend strongly on each bit in the input.
I think it's important to keep this special aspect of the parity problem in mind when thinking about good architectures for various applications.
As I noted elsewhere, the structure's not specific to parity/XOR but works on n-ary merge operations in general.
It will impact the breadth and depth required for the module; the {2, 2, 1} module structure required for XOR is not generally useful - but it's a substitutable component.
A bigger problem is keeping your processor fed with the decaying layer size (you'll want to target a fixed wave size if you're running on a GPU, mostly empty waves are a bad thing), but you can get around that reasonably easily (at least for base-2).
I've skimmed up and down and read some sections a few times - I'm still not 100% sure what the main conclusions are. A summary section would make the article more accessible and valuable to others.
My understanding is that the main point here is:
- some problems require reasoning through many steps of computation,
- transformers have limited depth, so cannot solve problems that require many steps.
After reading this article, my reaction is that yes, transformers are not the optimal model for NLP and reasoning, but transformers are good enough and scale really well on current GPU hardware. Going forward, I think hardware is the constraint upon which new architectures will need to accommodate
The article quotes a paper by, "Hao et. al." which concludes:
"Finally, given the success that Transformers have had as models of natural language, it is perhaps surprising that these models’ expressive power seems to be best characterized (or at least bounded) in terms of circuit complexity. Mathematical explorations of natural language have most commonly employed the approach to language complexity afforded by the Chomsky hierarchy and its refinements, which is based on automata and formal grammars. The apparent incomparability of these approaches suggests that the exploration of different types of Transformer models might offer a new approach to the study of the formal properties of natural language."
A few years ago I found a paper that made the argument that Chomsky's hierarchy of formal languages is not necessarily the only mathematical hierarchy that can exist over languages. The author advocated that other ways of systematizing the classification of languages could lead to both a different hierarchy and new insights. He lamented that the strength of Chomsky's work and reputation might have inadvertently discouraged us from questioning it and looking for alternatives - especially ones which do more to capture what we intuitively mean by natural language parsing ability.
Edit: The OP article author interprets the first quote as, "maybe human language is simpler than we thought, and doesn't require higher levels of the Chomsky hierarchy... We might be Transformers!" However in light of that other paper I mentioned, it's more like there might be another hierarchy of languages different from and parallel to Chomsky's hierarchy, with different boundaries for the levels that cover the space differently than Chomsky's.
As for how such a thing is possible in detail, remember that a lot of the Chomsky language hierarchy require looking at behavior "in the limit" or "unbounded" in the sense that no finite parser of a lower level can parse all (unbounded) sentences of the higher complexity language. (But an arbitrarily sized lesser-complexity parser can parse sentences of bounded subset of the higher-complexity language.)
And it may be that for parsing actual human language pertaining to a non-infinite world, such arguments as the Chomsky hierarchy deals with are no more relevant than arguing that our physical computers aren't truly universal Turing machines because they have finite memory. Technically correct, yet also irrelevant to most of the practical uses we have found for them!
>> All this to say: I think there are fundamentals we need to view all of this progress through. Lower-bound complexities of problems that we learn in Algorithms 101 shouldn’t get thrown out the window because linear algebra, ReLUs and attention mechanisms are involved. Sorting, for example, has a provable lower-bound complexity of Ω(NlogN). When someone tells you there is a way to do it in O(logN) time, it’s best to squint and ask a few questions. When someone tells you you can gain a speed-up in computing primes, on a naive algorithm, it’s best to ask if that method also has correctness covered.
Keep this thought please. There is a very obvious feeling that "now we have LLMs we don't need CS anymore", or don't need maths, science, knowledge...
In fact, this goes rather further back than Transformers. I was just reading this old interview of Vladimir Vapnik [1], where he's taking the position that only the "easy" questions in science have explanatory answers, and that for the "hard questions" we can only hope to build predictive models. Vapnik is one of my herores of AI, but on that I think he's not just wrong, but pointing the way to a new dark ages, where we lose the little knowledge we have. Similar "intuitions" are expressed in the "Bitter Lesson" blogpost by Rich sutton [2].
Vapnik is right, of course, in that there are "hard" questions for which we don't know any good answers, and our current framework may not be enough to give any simple, explanatory answer anyway. Certainly, CS is full of bottomless pits of despair, undecidabilities, incompletenesses and intractabilities. I think that just says we're shit at creating formal frameworks. All the ones we've created have some flaw. Arithmetic is incomplete. Logic (even first-order logic) is undecidable. You can't divide by 0, there are tons of calculations that cannot be performed because they sink into uncountable infinities after two steps, etc etc and so on. We just suck at making universal abstractions, that are useful in the first instance, but don't end up painting ourselves into a corner, somewhere down the line.
Well, so what? So far we've done pretty well in terms of science, in the sense of understanding the world and how it works. We're not going to give up now! If our tools are not good enough to take our knowledge to the next level, well, then, we just need to make better tools. Better maths. Better Computer Science. Better scientific methods. That has happened in the past at least once, if not many many times. Why can we not do it again? Why do we have to abandon our fate to unknowing, all-predicting machines? That doesn't make sense.
Fully agreed. Plus at a fundamental level this new anti intellectual trend feels wrong.
Do we truly want to become the Eloi to our new GPT Morlocks?
Every time we wrote fiction about this it was in very dystopic terms. Have we suddenly decided it's OK to simply give up and have a chatbot understand the world for us?
I think Chess offers a model for post-AI life. Computers are much better and yet people keep playing, keep trying to invent human-comprehensible theories, but also using computer support to do so. A funny detail is that accuracy has been flipped on its head, and is used to measure humans by machine standards.
Yes, but "we don't need CS anymore" feels more like "we don't need to learn the rules of Chess anymore -- or the rules of anything -- the chatbot will figure things out for us anyway!"
> I’ve attempted this prompt several different ways on ChatGPT without a working solution, but I imagine this could work.
I've tried a couple of things, it seems OK with a basic approach but starts falling apart when you get close to 50 bits. A more interesting merge approach looks OK at 50 with some quick testing. What sort of scale do you mean when you talk about a working solution?
Edit - stats may not be holding up the merge approach at 50. It's close, sometimes getting it right or being one out.
Yeah it is. I've only learned it while looking up material for this post. I figured people know NAND is NOT(AND(.)), so NXOR might be more familiar counterpart to XOR.
In principle we think iteratively, do one small computation, memorize the result, then do the next step based on the input and the result from the previous step. If things get too complicated, we grab some paper and write down intermediate results on external storage. But fundamentally we memorize some raw facts and otherwise learn algorithms that allow us doing new things by combining existing abilities. Ignoring memory limitations humans are Turing-complete.
As we repeatedly solve similar tasks, we develop optimizations, the brain learns to perform a couple of steps in one go instead of going through all the individual steps. When children learn to read, to write or to do math, they learn to do it in small steps, they draw and recognize letters and numbers by looking at and drawing individual lines and circles. When they learn to draw lines or circles they first make very deliberate movements with the pen - up, down, left, right - before drawing a circle becomes a primitive. When they learn to add, they break numbers down into digits and only memorize how to add those, larger numbers are added iteratively digit by digit.
With time and practice the brain learns to do many of those things in one step, you read and write letters or words, not deliberately draw individual strokes. You will still fall back to this if you have to deal with characters from a unknown alphabet. You will no longer perform additions digit by digit for small or commonly used numbers but you will fall back to this for big numbers. When you learn to drive, you first very deliberately look at traffic signs, think about turning the steering wheel this way or that way while parking or think about switching on the turn signals. Again with practice many of those things become automatic and you no longer have to think about them.
So overall I think the brain is just following sequential algorithms, combining primitives into more complex result. Then with practice common tasks get reimplemented in some kind of fixed function unit that can do a specific task - maybe under some limited circumstances and maybe only approximately - in one step and this can then be used as a new primitive where appropriate. Actually those fixed function units could internally use iteration but this iterative process would be hidden from the primary loop.
Language models like ChatGPT seem to be more on the fixed function side, they see a set of tokens and spit out a response. The attention mechanism has some similarity with a loop executing an algorithm step by step, it just has a fixed number of iterations and has been unrolled. When prompted to reason in steps, this adds another loop with additional storage for intermediate results. The difference is that this process is externally visible and that the model must be instructed to do so instead of the model deciding on its own to solve the problem in steps and hiding those steps from the outside.
For questions like adding or multiplying numbers or finding the parity of some long bit string the model has some neurons that could directly provide an answer and the answer will probably be correct for simple tasks but the longer the input the more likely it becomes that those neurons will not produce the correct answer. And the model does not know in which region those neurons can be trusted. But the model also knows the underlying algorithm to solve the task, say computing the parity of a long bit string or adding large numbers, and where the steps only involve computations that the model can perform correctly, i.e. adding two digits or XORing two bits. So you can get the correct result out of a model like ChatGPT if you can make it follow the iterative algorithm instead of it trying to give the sum of two 20 digit numbers directly. And I would guess you could - at least to some extend - use ChatGPT itself to rewrite and iteratively solve harder problems. The primary obstacle is probably that it is hard to tell what tasks the model can reliably perform correctly and what tasks must be broken down further.
The first layer consists of 1 node per input pattern, with activation and weights such that only one node is active that matches the pattern. And a second layer of weights that provides the output per input pattern.
True but not very useful. That's like writing an "isPrime" function with a switch statement for every possible input number, rather than coming up with a general algorithm. It can't give you any answer you don't already know.
P.S. I'm graduating soon and looking for research scientist roles.