6 ms·

The illusion of state in state-space models

60 points by canjobear 2y ago

deleted 2y ago
[deleted]
optimalsolver 2y ago
>Figure 1: We prove that SSMs, like transformers, cannot solve inherently sequential problems like permutation com- position (S5), which lies at the heart of state-tracking prob- lems like tracking chess moves in source-target notation (see Section 3.2), evaluating Python code, or entity tracking. Thus, SSMs cannot, in general, solve these problems either Do Microsoft & friends who are about to build trillion dollar AI data centers know about these proven limitations of transformer-based architectures?
- mjburgess 2y ago
  Yes. The solution is to hoover up all the queries people are currently putting to ChatGPT, save how people have "prompt engineer"ed the solution (ie., answered the question themselves); and then hope that you can just feed this back to people without them noticing. The only open question is whether people have common-enough queries for this charade to work out. It seems there's quite a lot at least. But this number will decrease over time for various reasons. So it's a game of building a system that can be retrained on the answers people are giving it fast enough that people don't notice where the answers are coming from.
  - FeepingCreature 2y ago
    Counterpoint: the more networks internalize the patterns behind engineered prompts, the closer they get to being general reasoners.
    - mjburgess 2y ago
      Statistical patterns in text tokens have nothing to do with reasoning. They lack such a property to learn in the first place. This would be more obvious, I guess, if the tokens were in an alien language. Consider a translation to 1,000 different alien languages of any given novel.. there is no distributional property they would share. Statistical AI is just a way of sampling from a historical dataset with a similarity metric. It only works to answer questions if you're sampling from a (Q, A) database in the same language the user already understands. The question was answered by a reasoner, it is now answered by a system which replays answers.
      - FeepingCreature 2y ago
        This is just chinese room. But also, I disagree that the languages would not share properties. A novel is too small. Consider a network trained on GPT-3 scale datasets in 1000 alien languages. The shared structures behind the sentences will be the same, even if the grammar is completely different. Stars will be stars, moons will be moons. I'd bet you that the model would be able to translate shared concepts between those languages even if it had not been trained on the same novels, same as GPT can translate terms that it has not seen in dictionary pairs. (I have no idea if it can! But I'm confident enough that I'm willing to just say it can, at risk of being proven wrong. If GPT can't do that, I'm fundamentally misunderstanding how it works - that is, I don't have a paper offhand showing that GPT shares concept neurons between languages, but I'm willing to bet I could find one if I went looking.) In other words, if you co-trained GPT-4 on Earth Internet and Alien Internet, there's a good chance it'd end up able to translate English to Alienese, purely as an emergent ability, if it had the concept of translation at all. Intelligence is compression. With sufficient abstraction (layers) and sufficient volume (dataset), any description of the same reality will assume the same structure. And no learning algo worth its salt will keep two identical structures around.
        mjburgess 2y ago
        Almost every predicate in natural languages is an arbitrary association of properties in the world. There isn't any property a person has "bald", nor are there "tree"s in the world. What bundles of properties the vast majority of language names are a product of historical and contingent associations we've made for practical reasons. Likewise, languages do not have the same distributional structure. There is no reason an alien language would use discrete tokens to name properties, nor co-locate tokens by linear position in a 'sentence'. Historical human languages did not; using, eg., the full 2D structure of the clay tablet. To suppose that it is the glyphs and their colocation which somehow bare meaning is a nonesensical superstition. The world is what our words mean, and it is we, in that world, who provide them their meaning. We can do so with arbitrary linguistic structures.
        FeepingCreature 2y ago
- empath75 2y ago
  Not being able to solve a problem "in general" does not mean that it can't solve specific and useful instances of the problem. There are lots of SAT solvers that can't solve SAT problems in general (in any reasonable amount of time), but nevertheless can solve many useful categories of SAT problems.
- canjobear 2y ago
  People at Microsoft Research certainly do. But the bet is that, with scale, these limitations won't matter in practice. For example Transformers can't recognize well-nested brackets (like {[()]}) to infinite depth; the depth that Transformers can recognize is limited by how many self-attention layers they have. But in practice, you rarely need much depth.
  - toxik 2y ago
    Notably, humans also cannot track this to infinite depth. Somehow we know this and reach for algorithmic solutions (like pen and paper).
    - logicchains 2y ago
      Interestingly LLMs also do better with pen and paper reasoning: https://arxiv.org/abs/2310.07923 https://arxiv.org/abs/2310.07923 .
gaudat 2y ago
Another name hijacked by AI/ML... I was hoping to see some control thoery...
- throwaway42668 2y ago
  This is what they actually mean by AI will be in everything. Just a relentless campaign of appropriating names that used to have meanings.
  - nico 2y ago
    Interesting. This is how I sometimes feel about physics The field completely appropriated and redefined so many terms of common language, that now it’s hard to talk in plain language with someone formally trained in physics about physical phenomena For example, everyone has some sort of intuitive idea about what Energy is. But if you use that word with a physicist, watch out, for them it means something super specific within the context of assumptions and mathematical models and they will assume you don’t know what you are talking about because you are not using their definitions from their models Same thing happens with infinite in math
- aerospace_guy 2y ago
  This has been happening for years now. Just adding "AI" or "LLM" gets the views and $$ these days.
- szvsw 2y ago
  I mean, if you like state space models, then you should read the paper on Mamba if you haven’t already! Because it quite literally uses state spaces… and you will probably think it’s a really cool application of state spaces! Apologies if you know the following already, but maybe others reading your comment feeling similarly will not be familiar and might be interested. At least intuitively, I like to motivate it this way- pick your favorite simple state space problem. Say a coupled spring system of two masses, maybe with some driving forces. Set it up. Perturb it. Make a bunch of observations at various points in time. Now use your observations to figure out the state space matrices. There’s fundamentally not really anything different (in my opinion) with using Mamba (or another state space model) as a function approximation of whatever phenomenon you are interested in. Okay Mamba has more moving parts, but the core idea is the same: you are saying that on some level, a state space is an appropriate prior for approximation of the dynamics of the quantities of interest. It turns out being pretty remarkable the number of things this can work out quite well for. For instance, I use it to model the 15-min interval data for heating, cooling, and electricity usage of a whole building given 15 min weather data, occupancy schedules, and descriptions of the building characteristics (eg building envelope construction, equipment types, number of occupants, etc).
briandw 2y ago
The early research in neural networks was hampered by proofs that perceptrons could never solve certain functions, like XOR. DNNs could have been developed much sooner otherwise. I view these proof papers with some skepticism, since they can be unnecessarily dismissive of good ideas.
- nickpsecurity 2y ago
  I’ve only read the abstract. It says that they have experiments to back their claims. So, that’s a proof claim with experimental data. It’s in a field where most learning happens by experimental exploration, too. I don’t think it will hold us back. If anything, it’s very exciting to see how many people in the ML field are challenging the status quo from many, different angles.
- logicchains 2y ago
  >The early research in neural networks was hampered by proofs that perceptrons could never solve certain functions, like XOR. DNNs could have been developed much sooner otherwise. These proofs still hold; pure MLPs (without a modern activation function) aren't very useful, both in theory and practice. What made them useful was the realisation that combining them with a proper activation function makes them much more useful, both theoretically and practically; this discovery took time.
- nyrikki 2y ago
  How did papers that demonstrated single layer neural networks can't do XOR, but multi layer neural networks can, hamper development? XOR is simply not linearly serperatable, requiring an MLP or kernel trick still holds. It is a similar reason that attention works for majority gates but not parity gates in the general case. Acknowledging that reality resulted in new developments, but is still a limitation. Perceptrons are binary classifiers.
empath75 2y ago
There's nothing wrong with this paper and it's important to understand exactly what LLMs (and related technologies) are capable of and what they aren't, but I do have a problem with the general argument that <ai technology> can't do <some task> and so that means it's useless and won't lead to AGI. I feel like a lot of people think that if a single neural network architecture can't achieve something on it's own that building a system that supplements the AI with other tools is somehow _cheating_. General AI if it ever happens is going to very likely be a system of specialized components working together, and there's not going to be a single piece of it that you can point to and say "that is where the intelligence lives" -- it's sort of liking digging through the brain looking for the homunculus that's piloting the ship. If an LLM can't track state, hook it up to something that can. If it doesn't have long term memory and retrieval, hook it up to something that does.
- andoando 2y ago
  I think a way to connect these different systems as a homogenous system is the difficult part.
- szvsw 2y ago
  Very well said. It absolutely drives me crazy - the focus on the model architecture for autoregressive text generation as the “key” (or blocker) to AGI seems so misguided as a debate. It seems clear to me (and maybe I’m wrong!) that a much larger system of modules interacting is essential (actuators, sensors, short term and long term memory, working memory, etc), and I completely fail to understand why it feels like the debate revolves around neural network architectures as opposed to the larger system architecture for agency. The language and decision making component is obviously extremely important and necessary, but it feels to me like it will always just be a necessary but not sufficient component for AGI. The fact that we have already obviously developed a technology which has an excellent grasp of language, can select between tools, perform knowledge retrieval from external databases, perform some form of simplistic reasoning and planning… it really feels (again, only intuitively!) like everything outside the perimeter of LLMs is where the actual frontier of AGI will be. It feels like with enough sensorimotor affordances and mechanisms for saving and accessing memory, all that is left is the (obviously complex) framework for connecting all of these together, with potentially many instances of each module working together… especially when you consider that one such system can potentially use human actors as tools (eg “hello fellow human, please complete this captcha for me, as I am low-vision”). I guess more succinctly - I do not believe that GPT-4 et al are remotely close to AGI on their own, but I do feel (again, this is just “vibes,” and obviously people smarter than me disagree!) that GPT-4 could be a component combined with lots of other tech we already have to essentially achieve AGI already. Perhaps what I am describing would just be a pale imitation of what others mean by AGI and be reductively called another mechanical Turk. I am probably the misguided one, but nonetheless, I can’t escape the feeling that “the one model to rule them all” is a red herring vis-a-vis a complex network (ha) of modules interacting together to achieve meaningful agency. Maybe it’s just that I am more interested in “meaningful agency” as a guiding principle over “AGI.”
Lerc 2y ago
Reading that abstract, I'm not sure what is being claimed here. They say "the “state” in common SSMs is an illusion:" Is this a claim that the activations within a state space model contain no state or that it cannot contain an arbitrary state. The former seems trivially false and the latter seems completely uncontroversial.
- logicchains 2y ago
  If you read the rest of the paper it's clear what they mean. SSMs are theoretically no more powerful than transformers, meaning without chain of thought they can't efficiently solve state-tracking problems, unlike RNNs: https://arxiv.org/abs/2207.00729 https://arxiv.org/abs/2207.00729 .
  - opprobium 2y ago
    Not just efficiently, can't solve.
    - logicchains 2y ago
      They can solve it if you keep adding layers to the transformer, it's just not efficient; you'd need exponentially more layers than a similarly sized RNN.
  - yobbo 2y ago
    The difference to RNNs is that the state in SSMs is a linear combination of previous inputs, which makes it possible to parallelise training in various ways. Gates and non-linearities in RNNs allow the state to be "any" function of previous inputs.
duped 2y ago
I disagree with the editorialized abstract. State is not an illusion. There is a limit to what stateful LTI systems are capable of modeling. It is very interesting that they've been able to prove what that limit is in the context of computation. From my reading, "non gated SSMs" are LTI systems. They're linear (the paper ignores the activation function) and the "does not depend on input" criteria is the controls way of saying "time invariant" (replace time with the domain of the input vector). It is not surprising that a system that cannot adapt to changing input conditions (by construction) is fundamentally limited to the problems it can model. This is why adaptive filters are studied - LTI systems are useful computationally, but limited because they cannot adapt. Relaxing the "TI" constraint greatly expands the domains of problems that can be solved. When the feedback matrix is diagonal you have an FIR system. While "finite impulse response" has as specific mathematical definition, conceptually it means the state at time n depends solely on past inputs and states n - N where N is the size of the state vector. So of course, if the feedback matrix is diagonal, the system is limited in the kinds of stateful problems it can handle. What this paper is missing is that connection to the limits of LTI and connection to TC0, which is very interesting indeed. In other words, the state of the network is still infinitely long and definitely not an illusion. However if the problem requires the network to adapt to its input then a non-gated SSM is not going to be sufficient. That's an interesting research space.

60 points by canjobear 2y ago

deleted 2y ago

[deleted]

>Figure 1: We prove that SSMs, like transformers, cannot solve inherently sequential problems like permutation com- position (S5), which lies at the heart of state-tracking prob- lems like tracking chess moves in source-target notation (see Section 3.2), evaluating Python code, or entity tracking. Thus, SSMs cannot, in general, solve these problems either Do Microsoft & friends who are about to build trillion dollar AI data centers know about these proven limitations of transformer-based architectures?

mjburgess 2y ago
Yes. The solution is to hoover up all the queries people are currently putting to ChatGPT, save how people have "prompt engineer"ed the solution (ie., answered the question themselves); and then hope that you can just feed this back to people without them noticing. The only open question is whether people have common-enough queries for this charade to work out. It seems there's quite a lot at least. But this number will decrease over time for various reasons. So it's a game of building a system that can be retrained on the answers people are giving it fast enough that people don't notice where the answers are coming from.
- FeepingCreature 2y ago
  Counterpoint: the more networks internalize the patterns behind engineered prompts, the closer they get to being general reasoners.
  - mjburgess 2y ago
    Statistical patterns in text tokens have nothing to do with reasoning. They lack such a property to learn in the first place. This would be more obvious, I guess, if the tokens were in an alien language. Consider a translation to 1,000 different alien languages of any given novel.. there is no distributional property they would share. Statistical AI is just a way of sampling from a historical dataset with a similarity metric. It only works to answer questions if you're sampling from a (Q, A) database in the same language the user already understands. The question was answered by a reasoner, it is now answered by a system which replays answers.
    - FeepingCreature 2y ago
      This is just chinese room. But also, I disagree that the languages would not share properties. A novel is too small. Consider a network trained on GPT-3 scale datasets in 1000 alien languages. The shared structures behind the sentences will be the same, even if the grammar is completely different. Stars will be stars, moons will be moons. I'd bet you that the model would be able to translate shared concepts between those languages even if it had not been trained on the same novels, same as GPT can translate terms that it has not seen in dictionary pairs. (I have no idea if it can! But I'm confident enough that I'm willing to just say it can, at risk of being proven wrong. If GPT can't do that, I'm fundamentally misunderstanding how it works - that is, I don't have a paper offhand showing that GPT shares concept neurons between languages, but I'm willing to bet I could find one if I went looking.) In other words, if you co-trained GPT-4 on Earth Internet and Alien Internet, there's a good chance it'd end up able to translate English to Alienese, purely as an emergent ability, if it had the concept of translation at all. Intelligence is compression. With sufficient abstraction (layers) and sufficient volume (dataset), any description of the same reality will assume the same structure. And no learning algo worth its salt will keep two identical structures around.
      - mjburgess 2y ago
        Almost every predicate in natural languages is an arbitrary association of properties in the world. There isn't any property a person has "bald", nor are there "tree"s in the world. What bundles of properties the vast majority of language names are a product of historical and contingent associations we've made for practical reasons. Likewise, languages do not have the same distributional structure. There is no reason an alien language would use discrete tokens to name properties, nor co-locate tokens by linear position in a 'sentence'. Historical human languages did not; using, eg., the full 2D structure of the clay tablet. To suppose that it is the glyphs and their colocation which somehow bare meaning is a nonesensical superstition. The world is what our words mean, and it is we, in that world, who provide them their meaning. We can do so with arbitrary linguistic structures.
        FeepingCreature 2y ago
empath75 2y ago
Not being able to solve a problem "in general" does not mean that it can't solve specific and useful instances of the problem. There are lots of SAT solvers that can't solve SAT problems in general (in any reasonable amount of time), but nevertheless can solve many useful categories of SAT problems.
canjobear 2y ago
People at Microsoft Research certainly do. But the bet is that, with scale, these limitations won't matter in practice. For example Transformers can't recognize well-nested brackets (like {[()]}) to infinite depth; the depth that Transformers can recognize is limited by how many self-attention layers they have. But in practice, you rarely need much depth.
- toxik 2y ago
  Notably, humans also cannot track this to infinite depth. Somehow we know this and reach for algorithmic solutions (like pen and paper).
  - logicchains 2y ago
    Interestingly LLMs also do better with pen and paper reasoning: https://arxiv.org/abs/2310.07923 https://arxiv.org/abs/2310.07923 .

gaudat 2y ago

Another name hijacked by AI/ML... I was hoping to see some control thoery...

throwaway42668 2y ago
This is what they actually mean by AI will be in everything. Just a relentless campaign of appropriating names that used to have meanings.
- nico 2y ago
  Interesting. This is how I sometimes feel about physics The field completely appropriated and redefined so many terms of common language, that now it’s hard to talk in plain language with someone formally trained in physics about physical phenomena For example, everyone has some sort of intuitive idea about what Energy is. But if you use that word with a physicist, watch out, for them it means something super specific within the context of assumptions and mathematical models and they will assume you don’t know what you are talking about because you are not using their definitions from their models Same thing happens with infinite in math
aerospace_guy 2y ago
This has been happening for years now. Just adding "AI" or "LLM" gets the views and $$ these days.
szvsw 2y ago
I mean, if you like state space models, then you should read the paper on Mamba if you haven’t already! Because it quite literally uses state spaces… and you will probably think it’s a really cool application of state spaces! Apologies if you know the following already, but maybe others reading your comment feeling similarly will not be familiar and might be interested. At least intuitively, I like to motivate it this way- pick your favorite simple state space problem. Say a coupled spring system of two masses, maybe with some driving forces. Set it up. Perturb it. Make a bunch of observations at various points in time. Now use your observations to figure out the state space matrices. There’s fundamentally not really anything different (in my opinion) with using Mamba (or another state space model) as a function approximation of whatever phenomenon you are interested in. Okay Mamba has more moving parts, but the core idea is the same: you are saying that on some level, a state space is an appropriate prior for approximation of the dynamics of the quantities of interest. It turns out being pretty remarkable the number of things this can work out quite well for. For instance, I use it to model the 15-min interval data for heating, cooling, and electricity usage of a whole building given 15 min weather data, occupancy schedules, and descriptions of the building characteristics (eg building envelope construction, equipment types, number of occupants, etc).

briandw 2y ago

The early research in neural networks was hampered by proofs that perceptrons could never solve certain functions, like XOR. DNNs could have been developed much sooner otherwise. I view these proof papers with some skepticism, since they can be unnecessarily dismissive of good ideas.

nickpsecurity 2y ago
I’ve only read the abstract. It says that they have experiments to back their claims. So, that’s a proof claim with experimental data. It’s in a field where most learning happens by experimental exploration, too. I don’t think it will hold us back. If anything, it’s very exciting to see how many people in the ML field are challenging the status quo from many, different angles.
logicchains 2y ago
>The early research in neural networks was hampered by proofs that perceptrons could never solve certain functions, like XOR. DNNs could have been developed much sooner otherwise. These proofs still hold; pure MLPs (without a modern activation function) aren't very useful, both in theory and practice. What made them useful was the realisation that combining them with a proper activation function makes them much more useful, both theoretically and practically; this discovery took time.
nyrikki 2y ago
How did papers that demonstrated single layer neural networks can't do XOR, but multi layer neural networks can, hamper development? XOR is simply not linearly serperatable, requiring an MLP or kernel trick still holds. It is a similar reason that attention works for majority gates but not parity gates in the general case. Acknowledging that reality resulted in new developments, but is still a limitation. Perceptrons are binary classifiers.

empath75 2y ago

There's nothing wrong with this paper and it's important to understand exactly what LLMs (and related technologies) are capable of and what they aren't, but I do have a problem with the general argument that <ai technology> can't do <some task> and so that means it's useless and won't lead to AGI. I feel like a lot of people think that if a single neural network architecture can't achieve something on it's own that building a system that supplements the AI with other tools is somehow _cheating_. General AI if it ever happens is going to very likely be a system of specialized components working together, and there's not going to be a single piece of it that you can point to and say "that is where the intelligence lives" -- it's sort of liking digging through the brain looking for the homunculus that's piloting the ship. If an LLM can't track state, hook it up to something that can. If it doesn't have long term memory and retrieval, hook it up to something that does.

andoando 2y ago
I think a way to connect these different systems as a homogenous system is the difficult part.
szvsw 2y ago
Very well said. It absolutely drives me crazy - the focus on the model architecture for autoregressive text generation as the “key” (or blocker) to AGI seems so misguided as a debate. It seems clear to me (and maybe I’m wrong!) that a much larger system of modules interacting is essential (actuators, sensors, short term and long term memory, working memory, etc), and I completely fail to understand why it feels like the debate revolves around neural network architectures as opposed to the larger system architecture for agency. The language and decision making component is obviously extremely important and necessary, but it feels to me like it will always just be a necessary but not sufficient component for AGI. The fact that we have already obviously developed a technology which has an excellent grasp of language, can select between tools, perform knowledge retrieval from external databases, perform some form of simplistic reasoning and planning… it really feels (again, only intuitively!) like everything outside the perimeter of LLMs is where the actual frontier of AGI will be. It feels like with enough sensorimotor affordances and mechanisms for saving and accessing memory, all that is left is the (obviously complex) framework for connecting all of these together, with potentially many instances of each module working together… especially when you consider that one such system can potentially use human actors as tools (eg “hello fellow human, please complete this captcha for me, as I am low-vision”). I guess more succinctly - I do not believe that GPT-4 et al are remotely close to AGI on their own, but I do feel (again, this is just “vibes,” and obviously people smarter than me disagree!) that GPT-4 could be a component combined with lots of other tech we already have to essentially achieve AGI already. Perhaps what I am describing would just be a pale imitation of what others mean by AGI and be reductively called another mechanical Turk. I am probably the misguided one, but nonetheless, I can’t escape the feeling that “the one model to rule them all” is a red herring vis-a-vis a complex network (ha) of modules interacting together to achieve meaningful agency. Maybe it’s just that I am more interested in “meaningful agency” as a guiding principle over “AGI.”

Lerc 2y ago

Reading that abstract, I'm not sure what is being claimed here. They say "the “state” in common SSMs is an illusion:" Is this a claim that the activations within a state space model contain no state or that it cannot contain an arbitrary state. The former seems trivially false and the latter seems completely uncontroversial.

logicchains 2y ago
If you read the rest of the paper it's clear what they mean. SSMs are theoretically no more powerful than transformers, meaning without chain of thought they can't efficiently solve state-tracking problems, unlike RNNs: https://arxiv.org/abs/2207.00729 https://arxiv.org/abs/2207.00729 .
- opprobium 2y ago
  Not just efficiently, can't solve.
  - logicchains 2y ago
    They can solve it if you keep adding layers to the transformer, it's just not efficient; you'd need exponentially more layers than a similarly sized RNN.
- yobbo 2y ago
  The difference to RNNs is that the state in SSMs is a linear combination of previous inputs, which makes it possible to parallelise training in various ways. Gates and non-linearities in RNNs allow the state to be "any" function of previous inputs.

duped 2y ago

I disagree with the editorialized abstract. State is not an illusion. There is a limit to what stateful LTI systems are capable of modeling. It is very interesting that they've been able to prove what that limit is in the context of computation. From my reading, "non gated SSMs" are LTI systems. They're linear (the paper ignores the activation function) and the "does not depend on input" criteria is the controls way of saying "time invariant" (replace time with the domain of the input vector). It is not surprising that a system that cannot adapt to changing input conditions (by construction) is fundamentally limited to the problems it can model. This is why adaptive filters are studied - LTI systems are useful computationally, but limited because they cannot adapt. Relaxing the "TI" constraint greatly expands the domains of problems that can be solved. When the feedback matrix is diagonal you have an FIR system. While "finite impulse response" has as specific mathematical definition, conceptually it means the state at time n depends solely on past inputs and states n - N where N is the size of the state vector. So of course, if the feedback matrix is diagonal, the system is limited in the kinds of stateful problems it can handle. What this paper is missing is that connection to the limits of LTI and connection to TC0, which is very interesting indeed. In other words, the state of the network is still infinitely long and definitely not an illusion. However if the problem requires the network to adapt to its input then a non-gated SSM is not going to be sufficient. That's an interesting research space.