DragonGod's Shortform

DragonGod

This is a special post for quick takes by DragonGod. Only they can create top-level comments. Comments here also appear on the Quick Takes page and All Posts page.

"Is intelligence NP hard?" is a very important question with too little engagement from the LW/AI safety community. NP hardness:

Bounds attainable levels of intelligence (just how superhuman is superintelligence?)
Bounds physically and economically feasible takeoff speeds (i.e. exponentially growing resource investment is required for linear improvements in intelligence)

I'd operationalise "is intelligence NP hard?" as:

Does there exist some subset of computational problems underlying core cognitive tasks that have NP hard [expected] (time) complexity?

I want to write a LW question post on this sometime.

For now, I want to learn more about complexity theory and let my thoughts on the complexity of intelligence gestate further.

Gwern's "Complexity no Bar to AI" argues convincingly that complexity theory doesn't prohibit AGI/superhuman AI, but not that:

The attainable level of intelligence is as far above humans as humans are above ants (or other animal of choice)
Fast takeoff is feasible

As best as I can tell (I didn't finish it, but will reread it after I'm done with my current complexity paper) Gwern did not argue convincingly that intelligence is not NP hard.

3porby4y

Yes, if you modified the forward pass to output a million tokens at once, it would remain constant time so long as the forward pass's execution remained bounded by a constant. Likewise, you could change the output distribution to cover tokens of extreme length. Realistically, the architecture wouldn't be practical. It would be either enormous and slow or its predictions would suck. [...] No, a given GPT-like transformer always does exactly the same thing in the forward pass. GPT-3 does not have any kind of adaptive computation time within a forward pass. If a single token prediction requires more computation steps than fits in the (large) constant time available to the forward pass, the transformer cannot fully complete the prediction. This is near the core of the "wait what" response I had to GPT-3's performance. Note that when you prompt GPT-3 with something like "1401749 x 23170802 = ", it will tend to give you a prediction which matches the shape of the answer (it's a number, and a fairly big one), but beyond the rough approximation, it's pretty much always going to be wrong. Even if you fine-tuned GPT-3 on arithmetic, you would still be able to find two integers of sufficient size that they cannot be multiplied in one step because the number internal steps required exceeds the number of steps the forward pass can express. The output distribution will cover a wide smear of tokens corresponding to approximately-correct big numbers. It can't compute which one is right, so the probability distribution can't narrow any further. (Raw GPT-3 also isn't interested in being correct except to the extent that being correct corresponds to a good token prediction, so it won't bother with trying to output intermediate tokens that could let it perform a longer non-constant-time computation. The prompt makes it look like the next token should be an answer, not incremental reasoning, so it'll sample from its smear of answer-shaped tokens.) [...] It can feel that way a bit

5leogao4y

For all practical purposes, it takes O(N+M) compute to generate N tokens from an M token context (attention is superlinear, but takes up a negligible proportion of flops in current models at the context lengths that current models are trained for. also, while nobody has succeeded at it yet, linear attention does not seem implausible). No current SOTA model has adaptive compute. There has been some work in this direction (see Universal transformers), but it doesn't work well enough for people to use it in practice.

For all practical purposes, it takes O(N+M) compute to generate N tokens from an M token context

Yup. I suspect that's close to the root of the confusion/apparent disagreement earlier- when I say constant time, I mean constant with respect to input, given a particular model and bounded context window, for a single token.

I think doing the analysis at this level is often more revealing than doing the analysis across full trajectories or across arbitrary windows in an important way: a tight bound makes it easier to make claims about what's possible by existence proof (which turns out to be a lot).