3 ms·

> It performs no reasoning, and instead predicts the next token in language. Let A_i be a set of functions that transform sequents in a truth-preserving manner

by ke88y 4y ago

> It performs no reasoning, and instead predicts the next token in language. Let A_i be a set of functions that transform sequents in a truth-preserving manner (https://en.wikipedia.org/wiki/Sequent https://en.wikipedia.org/wiki/Sequent). Do you have a reason for believing that a transformer couldn't out-perform existing techniques for choosing, given a sequence A_n(...A_1(Prop)...), what token comes next? There are certain types of arguments that you could make, eg complexity theory does give us some bounds, but these models are large enough that (a) you can trade off enormous amounts of time for space, and (b) even time is questionable since forward passes result in truly enormous amounts of (CPU-indexed) computation. And of course you can say hand-wavy things like "these models can only at best interpolate", but how many mathematics papers get rejected every year due to lack of novelty? And how much actually useful reasoning is novel, either in its particulars or especially in its generalized schematic form? The true answer to the question of whether GPT-4 is a decent reasoning engine is, I think, close to your intuition: probably not. But in general, I don't see any good reason to believe that transformers can't do reasoning. In fact, quite the opposite.

kaba0 4y ago
As a foreword: I am absolutely not an expert on the topic. If theory of computation has taught us anything, is that complexity very quickly outgrows everything that is even in the grasp of mathematics (e.g. busy beaver). I just don’t think that a model that fundamentally can only take a fixed number of steps will ever make the jump. A human in theory can “go into a loop” and let’s say apply the same rules ad infinity, which is simply a must to most interesting problems. So - I guess GPT-4 can reason on the “trivial” degree simply by “caching” the output of the real algorithm, but that doesn’t scale at all.
- ke88y 4y ago
  > If theory of computation has taught us anything, is that complexity very quickly outgrows everything that is even in the grasp of mathematics (e.g. busy beaver). True. But if the science/practice of computation has taught us anything, it is that many problems can be solved for all practical purposes even if they are undecidable or intractable for all theoretical purposes. E.g., the halting problem is undecidable but software verification/static analysis tools that check for termination exist and are even widely used in some industries. > A human in theory can “go into a loop” A computer can as well, by identifying loop invariants. And even the discovery of loop invariants can be thought of as a next-token-prediction problem, if characterized in as a sequence of states followed by the question "if x_1=t_1, ..., x_n=t_n, then what are these variables equal to at state N+1?" > So - I guess GPT-4 can reason on the “trivial” degree simply by “caching” the output of the real algorithm, but that doesn’t scale at all. I am more-or-less in agreement about GPT-4, but I think claims about the limitations of the architecture/problem statement are over-stated.

by ke88y 4y ago

kaba0 4y ago

As a foreword: I am absolutely not an expert on the topic. If theory of computation has taught us anything, is that complexity very quickly outgrows everything that is even in the grasp of mathematics (e.g. busy beaver). I just don’t think that a model that fundamentally can only take a fixed number of steps will ever make the jump. A human in theory can “go into a loop” and let’s say apply the same rules ad infinity, which is simply a must to most interesting problems. So - I guess GPT-4 can reason on the “trivial” degree simply by “caching” the output of the real algorithm, but that doesn’t scale at all.

ke88y 4y ago
> If theory of computation has taught us anything, is that complexity very quickly outgrows everything that is even in the grasp of mathematics (e.g. busy beaver). True. But if the science/practice of computation has taught us anything, it is that many problems can be solved for all practical purposes even if they are undecidable or intractable for all theoretical purposes. E.g., the halting problem is undecidable but software verification/static analysis tools that check for termination exist and are even widely used in some industries. > A human in theory can “go into a loop” A computer can as well, by identifying loop invariants. And even the discovery of loop invariants can be thought of as a next-token-prediction problem, if characterized in as a sequence of states followed by the question "if x_1=t_1, ..., x_n=t_n, then what are these variables equal to at state N+1?" > So - I guess GPT-4 can reason on the “trivial” degree simply by “caching” the output of the real algorithm, but that doesn’t scale at all. I am more-or-less in agreement about GPT-4, but I think claims about the limitations of the architecture/problem statement are over-stated.