- Ben Brubaker wrote a long piece for Quanta magazine about meta-complexity. The first three-quarters are a giant refresher on the story of computability and complexity theory in the 20th century—including Turing, Gödel, Shannon, Cook, Karp, Levin, Baker-Gill-Solovay, Sipser, Razborov, Rudich, and more. But then the last quarter gets into actually new (well, within the last couple years) developments, including the NP-completeness of “Partial-MCSP” and other progress on the Minimum Circuit Size Problem, and progress toward basing cryptography on the sole assumption P≠NP, and ruling out Impagliazzo’s “Heuristica” and “Pessiland” worlds. I’m quoted (and helped proofread the piece) despite playing no role in the new developments. Worth a read if you don’t already know this stuff.
- Duane Rich created a Part II of his YouTube video series on the Busy Beaver function. It features some of the core ideas from my Busy Beaver survey, clearly narrated and beautifully animated. If reading my survey is too much for you, now you can just watch the movie!
- Aznaur Midov recorded a podcast with me about quantum computing and AI—just in case you haven’t got enough of either of those lately.
- Oded Regev put an exciting paper on the arXiv, showing how to factor an n-digit integer using quantum circuits of size ~O(n3/2) (multiple such circuits, whose results are combined classically), assuming a smoothness conjecture from number theory. This compares to ~O(n2) for Shor’s algorithm. Regev’s algorithm uses classical algorithms for lattice problems, thereby connecting that subject to quantum factoring. This might or might not bring nearer in time the day when we can break (say) 2048-bit RSA keys using a quantum computer—that mostly depends, apparently, on whether Regev’s algorithm can also be made highly efficient in its use of qubits.
- A team from IBM, consisting of Sergey Bravyi, Andrew Cross, Jay Gambetta, Dmitri Maslov, Ted Yoder, and my former student Patrick Rall, put another exciting paper on the arXiv, which reports an apparent breakthrough in quantum error-correction—building a quantum memory based on LDPC (Low Density Parity Check) codes rather than the Kitaev surface code, and which (they say) with an 0.1% physical error rate, can preserve 12 logical qubits for ten million syndrome cycles using 288 physical qubits, rather than more than 4000 physical qubits with the surface code. Anyone who understands in more detail is welcome to comment!
- Boaz Barak wrote a blog post about the history of the atomic bomb, and possible lessons for AI development today. I’d been planning to write a blog post about the history of the atomic bomb and possible lessons for AI development today. Maybe I’ll still write that blog post.
- Last week I attended the excellent Berkeley Simons Workshop on Large Language Models and Transformers, hosted by my former adviser Umesh Vazirani. While there, I gave a talk on watermarking of LLMs, which you can watch on YouTube (see also here for the PowerPoint slides). Shtetl-Optimized readers might also enjoy the talk by OpenAI cofounder Ilya Sutskever, An Observation on Generalization, as well as many other talks on all aspects of LLMs, from theoretical to empirical to philosophical to legal.
- Right now I’m excited to be at Crypto’2023 in Santa Barbara, learning a lot about post-quantum crypto and more, while dodging both earthquakes and hurricanes. On Wednesday, I’ll give an invited plenary talk about “Neurocryptography”: my vision for what cryptography can contribute to AI safety, including via watermarking and backdoors. Who better to enunciate such a vision than someone who’s neither a cryptographer nor an AI person? If you’re at Crypto and see me, feel free to come say hi.
This entry was posted
on Monday, August 21st, 2023 at 5:38 pm and is filed under Complexity, Procrastination, Quantum.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.
You can use rich HTML in comments! You can also use basic TeX, by enclosing it within $$ $$ for displayed equations or \( \) for inline equations.
Follow
Comment #1 August 21st, 2023 at 7:46 pm
Since I guess this is something of an open thread — my friend Beren came up with a nifty tree of numbers with some surprising properties. Since I don’t have time to go writing a proper paper about it at the moment[0], I just wrote up this quick webpage about it. (I left out one of the proofs because it was too annoying, but maybe I’ll go back and include it later? Or maybe it’s already known?)
Anyway it’s a nifty tree, maybe you don’t want to read my explanation of what’s going on with it, maybe you just want to look at it and try to find patterns for yourself, but it’s a nifty tree. 🙂
(Also psst hey Scott you mean “palate cleanser”, not “palette cleanser”)
[0]Really, the real difficulty with doing this is doing a literature search! Normally if I write a math paper it’s in an area not many people are working in and where I have a pretty good idea of what’s known and what isn’t. This is the sort of really simple number theory / combinatorics that, who knows, there could easily be some obscure paper out there that already did this that I’d have no way of knowing about. A lot of this isn’t on OEIS — and that’s really the reason I made this page, so I could have something to cite for adding this info to OEIS — but it could still be known by someone…
(Although, geez, adding all this to OEIS seemed way more appealing when I thought it was just going to be, like, 2 or 3 sequences. Now that I’ve expanded it it looks like I might have a whopping 14 sequences to add… even adding one can be fairly bureaucratic… and then there’s dealing with all the cross-references I’d be wanting to add…)
Comment #2 August 21st, 2023 at 7:52 pm
Scott,
This may be somewhat incidental to much of your post, but I know that you have been promoting a program to find more and better tests for quantumness, especially ones that are efficiently verifiable. Indeed, you’ve introduced (among other things) the concept of “peakedness” as roughly a circuit that, when acting on a fiducial state such as the all-zeros ket, returns another computational basis state with high probability; you’ve asked questions about how hard (or easy) it is to find peaked circuits.
To that end, can we not just obfuscate the identity? For example, can we not have our classical skeptic generate a secret random circuit (U), and either (1) an obfuscation of (U^dagger), or (2) another random circuit (V), who then provides a description of either (U^dagger U) or (VU) to our alleged quantum computer, who must then decide which circuit she’s been provided? (We could spice it up a bit by inserting a circuit exponentially close to the identity, and running our circuit through the Solovay-Kitaev machinery…)
Most of the time quantum computer engineers use circuit equivalences to shrink the size of a circuit but perhaps we could use those same equivalences to (slightly) increase the size of our circuit and then obfuscate (U^dagger U). Or, is there no sure-fired way to guarantee obfuscation to fool every conceivable classical compiler? After all, identity check is QMA-complete.
Comment #3 August 21st, 2023 at 8:05 pm
Sniffnoy #1: Thanks, changed to “palate cleanser.”
Comment #4 August 21st, 2023 at 8:08 pm
Mark Spinelli #2: Things like “obfuscating the identity” are precisely what I’ve advocated doing in my recent talks—have you seen them? The challenge is how to do this so that the circuit is actually obfuscated, and also implementable on a NISQ device.
Comment #5 August 21st, 2023 at 8:16 pm
Those are some good links, and in fact I had seen some of them a few days ago — e.g. the Quanta Magazine piece and some of the Simons Institute conference videos. I liked the panel discussions. The one with Ilya Sutskever, Sanjeev Arora, Christopher Manning, Yejin Choi, Yin Tat Lee:
https://www.youtube.com/watch?v=unotid_qTbw
It was funny seeing Sutskever having to avoid saying much (when addressing questions like “Are we running out of data?” and Choi’s question of “Might you use synthetic data?”) becasue of his work with OpenAI. I also thought his reaction to the question of whether Transformers are n-gram models was funny — “Absolutely and emphatically no. Absolutely not.”
Regarding Boaz Barak’s post, which I had not read before until now, I wonder if AI will get more predictable using certain flexible, light-weight (not a lot deep and heavy math) approaches with few assumptions, like what Sanjeev Arora talked about at the Simons conference.
I was trying to tease out from his paper something that occurred to me a few years ago about “sharp threshold” phase transitions in AI which maybe also appear in runaway nuclear chain reactions (and also random graphs, states of matter, etc.). Here was my thinking: let’s suppose you have some kind of AI model with “n sites”, which can be artifical neurons, collections of neurons, whatever you want; and say the training data is proportional to n when measured in characters, words, tokens, whatever. Now, let’s say that you have some task you want the AI to learn to solve, and the “algorithm” that it learns involves “k algorithmic components” (similar to what Sanjeev calls “skills”), where any site has a probability of p of learning each one of these components. Depending on p and k, as you vary n you might see behavior like this: if n 1.1 N then the probability jumps to more than 90%. Whether or not the model can combine these learned components together to produce the complete algorithm is another question entirely; but let’s assume that it can.
So, you could get a very sudden jump in capability, which might not be what you were expecting based on a previous model’s performance, even if that earlier model was just a tiny bit smaller.
Making various independence assumptions, my back-of-the-envelope calculations (reference to Barak’s post) are as follows: the probability that component i (where i = 1,…, k) is learned at one or more of the n sites ought to be
1 – (1-p)^n
And (assuming independence for simplicity; to be rigorous one could attempt to show it’s approximately true in certain cases), the probability that all k are learned is
(1 – (1-p)^n)^k.
Say we take n ~ log(k)/p. Then, (1-p)^n is roughly exp(-np) ~ 1/k. And then
(1- (1-p)^n)^k is roughly (1-1/k)^k ~ exp(-1) = 1/e = 0.37… (for k large)
But what if you just double n? Take n ~ 2 log(k)/p. Then, (1-p)^n is about 1/k^2; and
(1 – (1-p)^n)^k is then about (1 – 1/k^2)^k which is about 1 – O(1/k), very close to 1.
You should be able to get similar conclusions even if p is allowed to vary with n in not too forceful a manner.
Gradually, then suddenly…
Comment #6 August 21st, 2023 at 8:59 pm
Seems like something got clipped off when I copy-pasted. “if n 1.1 N…” should be (written in words) “If n is less than N then there is at most a 10 percent chance that all k components are learned; but when n is more than 1.1 N then with more than 90 percent chance all k components are learned”.
Comment #7 August 21st, 2023 at 11:20 pm
> that mostly depends, apparently, on whether Regev’s algorithm can also be made highly efficient in its use of qubits
That’s correct.
In a superconducting quantum computer using the surface code (and some other architectures), idling is just as expensive as doing operations. The underlying expensive thing is pumping out noise, and noise leaks into the system regardless of whether you’re idling or not at the logical level. Also, because you’re building operations out of programmable microwave pulses that can be changed from moment to moment, anything you’re not currently using for memory could instead be used for magic state factories (accelerating the computation). These two factors mean that the thing that determines your dollar cost isn’t gate count (number of non-idling operations), it’s hardware time (amount of stuff allocated to a task * duration of the allocation). A consequence is that memory isn’t cheap; it’s actually one of the most expensive things you can do.
The main place where Regev’s paper gains an advantage is that it mostly multiplies small integers instead of big integers. Since you’d be using schoolbook multiplication at these sizes, the average size of the factors directly multiplies onto the runtime. Achieving that small-multiplications-only effect involves periodically squaring the accumulator. Regev emailed me and Martin Ekerå an early version of the paper, and we caught the issue that there’s actually not a known inplace reversible modular squaring circuit. In fact, it seems unlikely for something like that to exist since (1) squaring has a small bit of irreversibility and (2) running it backwards could conceivably factor the number. As a fallback, you can use an out of place squaring circuit and uncompute the intermediate values at the end of the computation, or play more complicated pebble games. But ultimately this fallback requires multiple additional registers of storage, which eats the advantage when you’re thinking in terms of hardware*time or in terms of amount of hardware needed.
That said, assuming the rest of the paper checks out, I think this is promising. Not necessarily as the final form of a more efficient construction, but as a key building block of that construction. An idea to keep in mind.
Comment #8 August 22nd, 2023 at 8:52 am
Scott,
It would be helpful if you could write a blog post on the Simons workshop. You have been a very active participant, including your quips making those sessions lively. Your insights would provide a good perspective on the state of affairs in this very dynamic field
Thanks
Comment #9 August 22nd, 2023 at 9:15 am
Here’s a fun paper that came out:
“Consciousness in Artificial Intelligence: Insights from the Science of Consciousness” (https://arxiv.org/abs/2308.08708)
It looks pretty good imo, probably a consequence of it having actual ML scientists *and* philosophers as authors.
This table is their main result:
Recurrent processing theory
RPT-1: Input modules using algorithmic recurrence
RPT-2: Input modules generating organised, integrated perceptual representations
Global workspace theory
GWT-1: Multiple specialised systems capable of operating in parallel (modules) GWT-2: Limited capacity workspace, entailing a bottleneck in information flow and a selective attention mechanism
GWT-3: Global broadcast: availability of information in the workspace to all modules
GWT-4: State-dependent attention, giving rise to the capacity to use the workspace to query modules in succession to perform complex tasks
Computational higher-order theories
HOT-1: Generative, top-down or noisy perception modules
HOT-2: Metacognitive monitoring distinguishing reliable perceptual representations from noise
HOT-3: Agency guided by a general belief-formation and action selection system, and a strong disposition to update beliefs in accordance with the outputs of metacognitive monitoring
HOT-4: Sparse and smooth coding generating a “quality space”
Attention schema theory
AST-1: A predictive model representing and enabling control over the current state of attention
Predictive processing
PP-1: Input modules using predictive coding
Agency and embodiment
AE-1: Agency: Learning from feedback and selecting outputs so as to pursue goals, especially where this involves flexible responsiveness to competing goals
AE-2: Embodiment: Modeling output-input contingencies, including some systematic effects, and using this model in perception or control
Table 1: Indicator Properties
(I also like thought it was funny when they explicitly mentioned and then excluded integrated information theory, lol.)
Comment #10 August 22nd, 2023 at 12:48 pm
Dr. Bob Carpenter summarized the meeting in this post: https://statmodeling.stat.columbia.edu/2023/08/20/report-on-the-large-language-model-meeting-at-berkeley/
It includes the following:
“Scott Aaronson (UT Austin, on sabbatical at OpenAI) gave a really interesting talk,
Scott Aaronson. Watermarking of large language models
The talk was a masterclass in distilling a problem to math, explaining why it’s difficult, and considering several solutions and their implications. I felt smarter after watching this one.”
Comment #11 August 22nd, 2023 at 1:05 pm
Scott #4:
Indeed I have seen some of your recent talks on test for quantumness! In particular I like the birthday-attack idea of running a quantum computer continuously on a fixed random circuit for a month or so, to look for collisions much faster than achievable classically.
As for obfuscations, does not the QMA-completeness of identity check, under standard complexity-theoretic assumptions such as BPP not containing QMA, *necessarily* imply that there must be an obfuscation of the identity, or of two equivalent circuits having the same depth?
For example, if we consider a classical random walk along a graph of circuit diagrams generated by a nice set of rewrite rules (where two circuit diagrams are connected iff there’s a rewrite relating the two), we might have to walk a very long time but could we not eventually have an obfuscated circuit of roughly the same size as where we started from?
Or is circuit obfuscation more akin to trying to tie up the unknot – no matter how long you scramble your unknot it’s just not that difficult to recognize as such?
Comment #12 August 22nd, 2023 at 1:23 pm
Mark #11: No, the QMA-completeness of identity check does not give what we need. That only shows that it’s hard to decide whether there’s some input state on which our circuit behaves very differently from the identity. We care about whether our circuit behaves very differently from the identity on a fixed input state, such as the all-0 state. This problem is clearly no harder than BQP (or else a quantum computer couldn’t solve it!); the question is whether it’s outside BPP. Even here, there are already plausible constructions (even based, for example, on Shor’s factoring algorithm), but none that we know how to implement on a NISQ device.
Comment #13 August 22nd, 2023 at 3:15 pm
Scott 12:
I think you might be missing his point, Scott. He’s not directly saying that QMA-completeness implies that we can obfuscate the identity for any circuit. Instead, he’s drawing a potential link between the hard problem of identity check being QMA-complete and the possibility of obfuscation for certain scenarios. By invoking a random walk on a graph of circuit diagrams, he’s suggesting that there might be a route to obfuscate, albeit not directly.
The heart of the matter is whether we can construct quantum circuits that are functionally equivalent yet structurally obfuscated to the extent that a classical system finds it hard to determine their equivalency. The randomness and complexity introduced by walking through a graph of rewrite rules can provide the obfuscation we seek. If this random walk has to be performed for an exceedingly long time to get to an obfuscated version of our starting circuit, isn’t that an indication of the inherent difficulty for classical systems to recognize it? This indirectly leverages the hardness of the QMA-complete problem.
Comment #14 August 22nd, 2023 at 4:41 pm
Adam Hornburg #13: Ok, maybe! But then there would remain the questions of
(1) does the walk ever get you back to an equivalent circuit that’s tiny, yet unrecognizably different from the one you started with?, and
(2) if so, how do we simulate the process efficiently in order to generate the hard circuit?
This directly relates to my open problems about peaked random circuits. Happy to look at a more detailed proposal.
Comment #15 August 22nd, 2023 at 5:30 pm
Scott, the random walk through a graph of rewrite rules would aim not to get back to an “equivalent circuit that’s tiny,” but rather one that is functionally equivalent and yet structurally obfuscated. The size isn’t the primary concern; it’s the structural dissimilarity while maintaining functional equivalence that we’re aiming for. This could help us bypass the obstacle of implementing the circuit on a NISQ device, because size and complexity don’t necessarily correlate in a straightforward manner.
Concerning your second question, simulating the process efficiently to generate a hard circuit is not trivial. But the goal isn’t necessarily efficiency; it’s effective obfuscation that stymies classical systems. Suppose this process isn’t in BPP but is in a higher complexity class, like TreeBQP, which means it’s solvable by a quantum computer making bounded error probabilistic queries to a quantum oracle. In this case, generating the circuit might be complex, but that’s precisely what lends the circuit its obfuscating properties.
So, even though the problem of peakedness might still be open, this method could offer a path toward generating circuits that would be difficult for classical systems to de-obfuscate, thus making the tests for quantumness more stringent. Would you consider that a valid approach to addressing your open problems?
Comment #16 August 22nd, 2023 at 5:37 pm
Adam Hornburg #15: I’ll take any progress on these problems that anyone can offer! 🙂
With my peaked random circuits proposal, I also don’t know how to generate the circuits efficiently (even assuming that suitable circuits exist), so it’s not like I can claim an advantage there. But of course, if we want doable NISQ experiments, ultimately we do want a fast enough way to find the circuits, either with my proposal or with the walk-on-the-rewrites-graph proposal (which I also thought about years ago, but I wasn’t able to prove anything quantitative).
Comment #17 August 22nd, 2023 at 6:07 pm
Adam Hornburg #13 and Scott #14,
Indeed I could imagine peakedness when applied to a fiducial state such as the all-zeroes ket to be in BQP\BPP and satisfying Scott #14’s first requirement, but to not even be in NP and hence not satisfying Scott #14’s second requirement!
But alas, the only “concrete” idea I have is to start with a given peaked circuit such as one (exponentially close to) the identity, and fixing a generating set of rewrite rules while randomly walking along the complexity-circuit graph so generated. The longer you walk, presumably the more obfuscated it would be, but the circuit could blow up in size, and no longer be in BQP, much less in NISQ.
Analogously, I don’t know how tests for TAUTOLOGY are created – clearly assuming NP and coNP are distinct then one must apply rules of inference to a tautological statement a superpolynomial amount of time, to have a tautological statement that is not easily identified as such (otherwise, your NP certificate would just be the rules of inference so-applied).
Comment #18 August 23rd, 2023 at 9:15 am
Scott,
could an AI ever be able to sidestep/overwrite/evade its own internal watermarking scheme?
Comment #19 August 23rd, 2023 at 9:26 am
fred #18: If it knew the key for the watermarking scheme (for example, because it had hacked the code of the computer it was running on?) and had the situational awareness and the motivation, then sure, why not?
As Eliezer constantly reminds us, there’s virtually nothing that we can confidently say a sufficiently powerful AI couldn’t do, other than violate the laws of physics or logic. But “sufficiently powerful” is doing a lot of work there. 🙂
Comment #20 August 23rd, 2023 at 9:43 am
Scott #19
yea, thinking about the sort of reasoning in “Reflections on Trusting Trust” (the famous Ken Thompson paper), I wonder whether there isn’t a way to make it much harder for an AI to self modify, e.g. using methods like encryption, blockchain, control at the hardware level, etc
This seems like an “AI safety” prerequisite even before thinking about alignment (because there’s no point of putting in place some aligning mechanism if the AI can easily work around it at some point).
Comment #21 August 23rd, 2023 at 12:19 pm
I found the talk on “Large Language Models Meet Copyright Law” to be very informative and well done: https://simons.berkeley.edu/talks/pamela-samuelson-uc-berkeley-2023-08-16
One thing I noticed is that no one broached the topic of whether the weights files themselves (the actual AI) is subject to copyright law. Would have been nice to hear her opinion on this.
Comment #22 August 23rd, 2023 at 3:17 pm
It seems that one of the key ideas (among many) from Bravyi et al’s error correction paper is relaxing the requirement that the tanner graph of the code be planar (as is the case with the surface code and related topological codes). Rather, they look for codes such that the tanner graph can be partitioned into 2 sets of edges, each of which is planar. The physical motivation for this is that when building a quantum computer on a flat 2D surface (like how superconducting quantum computers are built), you could put one planar set of edges connecting qubits on the top surface of the chip and another planar set of edges connecting qubits on the bottom surface of the chip.
I find this idea very interesting. I suspect we will see lots more of these almost-planar codes in the future.
Comment #23 August 23rd, 2023 at 4:09 pm
Regarding the LDPC code. In the paper “High-threshold and low-overhead fault-tolerant quantum memory,” it is written that several groups have demonstrated the principles of surface code error correction with small numbers of physical qubits. The challenge of scaling surface codes lies in the low encoding efficiency. We will need thousands of physical qubits to encode a single logical qubit with a reasonable error rate. This makes scaling to many logical qubits very resource-intensive.
As to the LDPC codes, which are the central issue of the paper: the IBM group writes that they present LDPC codes that are high-rate and high-distance, potentially offering a more efficient encoding with fewer physical qubits per logical qubit than surface codes. Thus, one can achieve the same level of error protection using fewer qubits, which is significant in terms of resource savings. The paper offers to replace surface code with a high-distance LDPC code. The LDPC code is an alternative to the surface code, not an encoding layered on top of the surface code. It seems that such a code can provide better error correction for a given resource overhead, making it attractive for quantum devices that are limited in qubits and coherence times.
If the group has indeed demonstrated a high-rate LDPC code with efficient decoding, then it is a significant advancement in the field. The challenge has always been in finding efficient decoding algorithms that work well with realistic noise models. I read in the paper that they measure the syndromes, and the decoding algorithm then processes the syndrome data and determines the errors that have occurred; based on the decoding algorithm’s output, are the gates applied? Am I right? LDPC codes can pave the way for more efficient quantum error correction if decoding challenges are overcome. But I read that there are many more challenges to overcome.
Comment #24 August 24th, 2023 at 4:16 pm
@Scott19 It sounds like you have the solution – if powerful AI can’t violate the laws of physics, just put it in a simulation, and it can’t violate the laws of physics of the simulation. Also make sure the AI is unaware of the nature of its reality. (Otherwise it might try to manipulate people in the real world to do stuff for it).
Take regular snapshots, and if the AI figures it out somehow just revert to earlier snapshot.
Comment #25 August 25th, 2023 at 12:22 pm
Your title slide for the watermarking talk is hilariously appropriate. Well done.
Comment #26 August 27th, 2023 at 11:26 am
“In less than a year, ChatGPT has gone from being mistaken for AGI to being the butt of a joke, and an insulting shorthand for robotic, incoherent, unreliable, and untrustworthy. ”
“The only areas where AI is flourishing are shamming, spamming & scamming”
The latest from Gary “I told you so” Marcus: https://garymarcus.substack.com/p/the-rise-and-fall-of-chatgpt
Comment #27 August 27th, 2023 at 10:06 pm
Scott, re #3 (your podcast): Your comment at 13:52 caused me to realize that I know very little about the history of the no-communication theorem. Do you happen to know who proved it and when? Was there a significant window of time between the publication of the EPR paper and the proof of the NCT during which experts in quantum physics thought that quantum entanglement might plausibly allow FTL communication?
Comment #28 August 28th, 2023 at 9:32 am
Hans Holander #26: But that’s just empirically wrong. Do you have any idea how many millions of people have come to rely on GPT as a coding assistant? Or for generating formulaic prose (eg grant progress reports)? I was just at Crypto and it was a large fraction of everyone I talked to there—by and large, people whose research has nothing to do with AI. I’m using it for writing LaTeX and generating transcripts of talks.
I’m old enough to remember, in 1994, the people who sneered at the idea that real commerce was going to happen via the World Wide Web. They got to bask in their victory—their shortsighted, stupid victory—for maybe 3 or 4 years, before history steamrolled them.
Comment #29 August 28th, 2023 at 9:37 am
Ted #27: I’ve generally seen the No Communication Theorem (and, extremely closely related, the concept of a density matrix) credited to von Neumann, from his 1932 book Mathematical Foundations of Quantum Mechanics. Note that this was three years before EPR. I’m not sure whether experts were confused about the signaling issue in the years between 1925 and 1932–does anyone else?
Comment #30 August 28th, 2023 at 10:11 am
Scott #29:
wikipedia says:
The formalism of density operators and matrices was introduced in 1927 by John von Neumann[26] and independently, but less systematically, by Lev Landau[27]
[26] von Neumann, John (1927), “Wahrscheinlichkeitstheoretischer Aufbau der Quantenmechanik”, Göttinger Nachrichten, 1: 245–272
[27] “The Damping Problem in Wave Mechanics (1927)”. Collected Papers of L.D. Landau. 1965. pp. 8–18.
Comment #31 August 28th, 2023 at 10:43 am
@Scott 26: Yes, coding is the one major exception (ironically, one may add), though LLMs are still mostly assisting humans, and are still poor at solving totally novel tasks beyond their training data (the CodeForce example).
But even in coding, the widespread use of LLMs could backfire in several ways in the long run: 1) easy malware and virus programming, 2) dissemination of unreliable code, 3) loss of skills by actual programmers. The first one is similar to 3D-printing guns or assembling bioweapons.
Paul Krugman underestimated the internet as late as 1998. But then again many internet applications and other tech application of that era did in fact fail.
By the way Krugman recently had a follow-up on the impact of the internet: The Internet Was an Economic Disappointment: https://www.nytimes.com/2023/04/04/opinion/internet-economy.html
This is something I mentioned previously: the internet didn’t increase economic productivity. Surprising but true. But of course life is more than just economic productivity 🙂
Comment #32 August 28th, 2023 at 11:54 am
Hans Holander #31:
I think just because LLMs are extremely good at small-scale help, doesn’t necessarily make them any less impactful or cool. I think some people overly praise LLM’s, but some people also do the opposite. If you use LLM’s for what they’re good at, they’re super useful. The average person gains a lot from ChatGPT. Even with all of its downsides. If you look at LLM’s as just assisting the average person to make life easier, rather than solving a novel problem, then you will really see the benefit.
If you improve the ease of a general task for a human. Then yeah, whatever made the improvement is probably going to make ~ALL humans better at what they’re doing (good or bad). I don’t think that’s a surprise or a concern for any technology.
Loss of skill in programmers is irrelevant. If they choose to use a tool that makes them MORE productive, then who cares if that somehow makes them less skilled, although I’m not even sure how one can be more impactful but less skilled? If you put them in an environment without a tool they rely on, they will be less skilled because they’re optimized for use with that tool. But in the real world, they aren’t in that environment. It makes sense that people use LSP’s and IDE’s instead of just writing code in plain text, even though it probably makes them “less skilled” when programming without them. But they aren’t ever programming without them, so why limit yourself.
Comment #33 August 28th, 2023 at 1:25 pm
The back-and-forths with Hans Holander remind me of some of the audience questions & answers at some of the recent Simons Institute lectures. e.g. See this talk with Sanjeev Arora beginning around 8 minutes 5 seconds in
https://www.youtube.com/watch?v=0D23NeBjCeQ&t=485s
where he talks about his experiment with taking 5 random skills from a list of 1,000 and seeing if an LLM can solve a task requiring combining them together — the point being that the number of combinations is large enough that it’s impossible the LLM just memorized all the possible combinations to complete the task (this is similar to an earlier comment I made on one of the posts about how using math like this can put an end to claims “it’s just memorizing”). But then someone from the audience (Alexi Efros?) wasn’t satisfied and mentions how text on the internet doesn’t necessarily follow that kind of distribution, missing Arora’s point that *he* picked the 5 random skills to combine, that he didn’t just get that specific combination from the internet. Then they have two or three more back-and-forths with the audience member left unsatisfied with using math in such a definitive way. Arora says a few times things like, “it doesn’t matter!… Why does it matter?” to various objections. Someone points out there is a difference between choosing 5 skills and excluding the rest and choosing the 5 skills and possibly including others. Arora says that that case doesn’t matter, that the numbers would still be too large (as long as you exclude using too many other skills at once, which is going to be the case if the text is not too long); and, besides, Arora chose the skills and got to exclude others. I think there were also a few more “But it doesn’t matter!” and maybe a “let’s move on” or two.
(If that talk by Arora doesn’t convince, there is recent work from Anthropic using “influence functions” to trace the “influence” of training examples to model outputs. They showed that a lot of the time the influence of text on larger models’ outputs was more at an “abstract thematic level” and often very far for anything even close to memorization.)
I think the same guy was moderator of this panel discussion with Ilya Sutskever and others:
https://www.youtube.com/watch?v=unotid_qTbw
He (Alexi Efros?) asked the panel about whether LLM-builders were running out of data to train models, and got mixed answers. He asked about whether models were “just interpolating (and not actually doing anything complicated)”, and Arora questioned what that even means. Manning mentioned how Yann Lecun has said “it’s just interpolating” is bullshit, and in general the panel seems to think LLMs are not some kind of Clever Hans. Soon after that the moderator gets into a discussion about whether Transformers are “just n-gram models” (or simple look-up tables). Sutskever tells him “no” and that Transformers are *computers* that can execute algorithms within. Then the guy insists that, “but maybe they are if n is variable”. Sutskever tells him “I don’t think so”, and mentions how you need an exponentially-large table as a function of n in order to emulate a Transformer with an n-gram model. And he says that the difference between “exponential” and “polynomial” seems to be something people have forgotten in their computer science education.
Comment #34 August 28th, 2023 at 6:08 pm
@jacob #32: “Loss of skill in programmers is irrelevant.” Only in the short term. In the long-term this may well turn out to be catastrophic, especially since LLM rely on harvesting already existing work, which in the future will be work produced by other LLMs. In fact this is *already* a problem: LLMs taking as input false information produced by other LLMs. Right now smart programmers can still catch such mistakes, but future dumb programmers will no longer be able to do so.
@starspawn0 #33: it has long been clear that it isn’t about “memorizing”. what the codeforces example showed was that during the last week of its training data, gpt was able to solve 100% of the challenges, and one week later, it was less than 10% at the easiest level.
But to come back to my initial post: Gary’s point wasn’t that LLMs aren’t useful at all. Zeppelins were also useful (to use his favorite example). His point is that LLMs may turn out to be a commercial (and technological) failure.
Comment #35 August 29th, 2023 at 2:09 am
Hans Hollander, #34:
No. Future programmers will be better at judging the quality of AI-written code, because they have more experience at doing so. (Of course, this might not make up for the increasing amount of low-quality code being used in AI-training.)
Comment #36 August 29th, 2023 at 9:20 am
@Hans Holdander #34: You mention the Codeforces problems earlier in this thread as examples where the model is poor at solving “totally novel tasks”. It’s hard to quantify what one means by “totally novel tasks”. e.g. One could take a very bright high school student who is “good at math”, and then give them the IMO exam (or the Putnam exam), and maybe they totally fail, maybe even getting not a single problem correct. Would we then conclude that the student must not be able to solve totally novel problems at all? I mean here we gave them tests that didn’t even require any advanced math!
My initial reaction to hearing about the Codeforces flap where the model did well on one set then did much worse on the next year’s set was, “That’s not surprising. The first year’s problems were probably in the training set. And because these are competition problems, it did poorly on the next year’s ones it hadn’t seen.” (At the upper levels some of these coding competition problems require knowing some mathematical tricks, so can be like IMO problems.
e.g. that if p is a prime number and x is an integer in [1,p-1], then the mapping f(y) : {0,…,p-1} –> {0,…,p-1} sending y to xy mod p is a permutation of {0,…,p-1}; and some problem might even require leveraging the fact that for p large enough not every permutation of {0,…,p-1} is of this form.)
However, that’s a just-so story that I haven’t seen corroborated by OpenAI (maybe it has been and I just didn’t see it). Here’s another just-so story that might explain it: maybe the test-makers got lazy and decided to modify some already-solved problems they found on the internet that the model had seen. Maybe they took a problem about Alice and Bob and made it about Mary and John; maybe the problem was about widgets and they made it about pigeons; maybe it had numbers like 15, 25, and 75 and they made them 201, 11, -947; maybe the description was 2 paragraphs and they embellished it to 5. But the model “noticed” that the core logic in the problem was very similar to the one about Alice and Bob that it had seen, so it merely “translated” that old solution into one to solve the Mary and John problem.
One more comment about “novel problems”: you may recall Francois Chollet has hyped his ARC problems to test for the generalization capability of AI models, claiming that, “They just do interpolation. Think of LLMs as like a noisy database,” or something like that. Well, there have been several recent papers testing GPT4 on easier variants of ARC problems formatted as text-completion (one by the Santa Fe Institute with Melanie Mitchell as a coauthor, on by Google, and one by the Vector Institute). GPT4 is still far below human performance, but gets a surprising number of them right. As I recall, one of the papers found that some of what made the model struggle was that it didn’t have a strong sense of “objectness” that could be learned if it had some visual training (instead of just text). And the Google one, in order to ensure it wasn’t just relying on problems it had seen before, tweaked their problems by changing the tokens around. e.g. if the completion problem involved the symbols A, B, C, D, they make it about W, X, Y, Z (there are probably billions of choices of symbol combinations); and performance didn’t drop to zero as maybe Chollet had surmised — the model seemed to learn general principles to solve ARC problems, even though it was still far below human performance. Perhaps a multi-modal LLM will do a lot better…
As to whether LLMs will be a “commercial success”, LM’s (language models without the “large”) have been around a long time, and have their uses (e.g. as a component in speech recognition systems); and LLMs, besides being used as coding assistants, will likely also continue to be used for machine translation. So I don’t see them going away anytime soon. They might fail to live up to the wildest hype expectations, but will probably exceed the expectations of more sober observers (which are not the contrarian ones who think they are in a nose-dive into the ground).
I think Marcus is hoping LLMs will be a commercial failure so he can say, “See, I told you that if you ignore neurosymbolic / hybrid / Algebraic Mind approaches then the whole LLM / deep learning / blank-slate approaches are going to go to pot.” And if they continue to succeed the message will be, “See, I told you that neurosymbolic approaches are the key to success. All the latest successful models are really `hybrid’ models.”
Comment #37 August 29th, 2023 at 12:18 pm
I just thought I would add one more thing related to “it’s just interpolation” mentioned in my last comment: Arora correctly asks “what does it mean?” in the panel discussion he was in. I would go further and say that even if you pin down a definition, the dynamics might not be what one would guess. One imagines “interpolation” as meaning something like “collage”, that by “interpolating” a model is just “collaging-together” fragments of text from different parts of the internet. However, when you iterate this several times, the logic inherent in the word patterns can drag you into a direction you weren’t expecting, like how the law can have unintended consequences that lawmakers never imagined.
Here is a simple example just at the level of math, and not even words: suppose you define the two quadratic functions
f(x) = 4 x (1-x), and g(x) = x^2.
Both map [0,1] –> [0,1]. And if you iterate starting at x = 1/2 you get the sequences
f(x), f(f(x)), f(f(f(x))), … = 1, 0, 0, 0, …
g(x), g(g(x)), g(g(g(x)))) = 1/4, 1/16, 1/256, …
Both are taking you to 0 — the first one gets there by the second step; and the second gets you there “quadratically fast”.
Now let’s see what happens if we “interpolate”. Let
h(x) = the average of f(x) and g(x) = (1/2)*(f(x) + g(x)) = 2x – 1.5 x^2.
For x = 1/2 what would you expect the sequence
h(x), h(h(x)), …
to look like? Would you expect it to converge to 0 like for f and g?
Let’s find out:
h(x), h(h(x)), h(h(h(x))), … = 0.625, 0.664063…, 0.666656…
is converging to 2/3, not 0 as one might expect.
So you’re getting completely novel behavior, even though your function h interpolates between f and g. I think when you collage-together words from two sources and try to stay logically consistent, you can quickly find yourself in a whole other “universe” just like with this numerical interpolation example.
Comment #38 August 29th, 2023 at 1:34 pm
How do you keep up with so much? Are you on steroids or something to get extra energy?
Comment #39 August 29th, 2023 at 4:23 pm
Since this is something of a grab bag, Scott, you once mentioned that you read Yudkowsky’s Harry Potter stuff to your kids. You obviously think it’s good stuff. Could you say a word or two about that. (I haven’t read that stuff and, given what I’m up to, probably won’t).
I’m not a EY fan, by any means. To the extent that I’ve looked at it, his technical stuff seems rather scattershot. For example, I’ve taken several tries on his long paper on Levels of Organization in General Intelligence, but have never been able to finish it (high opportunity cost). He’d obviously read a lot and thought a lot, but comes across as a really bright sophomore who’s decided to write a magnum opus and just couldn’t pull it off. Didn’t have the discipline and experience. Since he’s an autodidact he never got the discipline. And yet he inspired LessWrong, which is a crazy place, but… He’s obviously been very influential in Silicon Valley,
I’ve never read the general Sequences or the Harry Potter stuff, but based on a remark or two, I’m guessing that that material has been very important in attracting people to his ideas. Without it, LessWrong would be a much poorer place.
Comment #40 August 29th, 2023 at 6:54 pm
Scott, a broad philosophical question re your podcast comments at 40:14-40:48 (about the need to regain clear quantum supremacy): Have your ultimate motivations for achieving quantum supremacy shifted at all since the 2019 Google demonstration?
Across the whole QC community, there were several ultimate motivations for the original quantum supremacy target:
(1) Refute those (like Gil Kalai) who doubted that we could in practice entangle together any nontrivial number of qubits;
(2) prove that textbook QM is in principle scalable up into the high-entanglement regime, with no fundamentally new physics kicking in, and so it (probably) describes our actual universe at a fundamental level;
(3) demonstrate that the simple uncorrelated noise model remains realistic in the many-qubit regime, with no weird correlated errors cropping up;
(4) give experimentalists and engineers a concrete goal to shoot for in order to motivate them to continue improving their hardware; and
(5) encourage the broader community to care about QC via a flashy milestone.
The way I see it:
(1)-(3) were pretty definitively and permanently settled by Sycamore’s “perhaps-temporary quantum supremacy” in 2019, and will effectively remain settled even if classical computers soon regain the lead;
(4) has been effectively replaced by the quest for quantum error correction and is no longer necessary; and
(5) may have worked too well, given all the subsequent popular hype around QC!
So I admit that I’m no longer really clear about the ultimate philosophical motivation for regaining quantum supremacy, and I’m inclined to agree with the experimentalists that we should now be focusing our efforts on QEC and the search for practical NISQ applications.
I do see the inherent theoretical interest in questions like “Are any classically intractable but efficiently checkable problems currently NISQ-able?”. But it seems to me that those are narrower problems than the broad goal of regaining quantum supremacy. Are you mainly thinking of “regaining quantum supremacy” as a proxy for those more specific theoretical problems, or do you think that the direct goal itself still retains fundamental interest?
Comment #41 August 29th, 2023 at 9:01 pm
Bill Benzon #39: My daughter actually loved HPMOR—although that probably had more to do with its being “more Harry Potter,” and with its asking countless questions that push the boundaries of the Potterverse in entertaining ways, than with the underlying rationalist messages. I enjoyed HPMOR too, having enormous context for everything from having just read the original Harry Potter series, and from having known the rationalist community for 15 years. Certainly, there are parts of HPMOR that drag on too long with no action, and Eliezer’s Harry Potter must be one of the most annoying protagonists ever written, but no one could ever accuse HPMOR of failure to attempt something genuinely new. Much like with Ayn Rand’s novels, you have only to read HPMOR to understand why its message might resonate with tens of thousands of people, even if you hate the message.
Arguably, dialogues and didactic fiction are the genres where Eliezer are at his best, precisely because he doesn’t have to try to pretend to be an academic scientist or a philosopher, and can just be what he is and always has been: a prophet.
Comment #42 August 29th, 2023 at 9:03 pm
Ted #40: I agree with you that (1)-(3) are more prominent than (4) and (5) as reasons to continue doing quantum supremacy experiments.
Comment #43 August 30th, 2023 at 9:03 am
starspawn0
“is converging to 2/3, not 0 as one might expect.”
That’s very interesting, but I’m not sure what anyone would expect a priory.
I think the expectation is more a result of missing some fine point in the formulation of the problem.
But it doesn’t seem too hard to get convinced that one really shouldn’t expect anything obvious, no?
E.g. we have three different sequences, and the “average” is only true for the first terms:
f(x), f(f(x)), …
g(x), g(g(x)), …
1/2 [f(x)+g(x)], 1/2 [f(1/2[f(x)+g(x)]) + g(1/2[f(x)+g(x)])] ,…
and it’s pretty obvious (?) that
f(1/2[f(x) + g(x)]) + g(1/2[f(x) + g(x)]) != f(f(x)) + g(g(x))
so it’s unlikely that the two sequences would converge to the same value.
And even if the functions were linear, don’t we get
f(f(x)) + f(g(x)) + g(f(x)) + g(g(x)) != f(f(x)) + g(g(x))
(unless I screwed up the math, which is very likely, haha)
Comment #44 August 31st, 2023 at 10:47 am
Scott #41: Yes, a prophet, I’ll buy that. He certainly seems to be the first to emphasize the potential dangers of AI in the real freakin’ world, as opposed to fiction, and (what I think of as) his essential insight, that you can’t inject values into (an autonomous) AI from the outside, seems valid to me.
But a systematic thinker, no.
And that’s a subject that does come up now at then at LessWrong, such as this recent post, Eliezer Yudkowsky Is Frequently, Confidently, Egregiously Wrong. It’s currently at -24 karma, meaning lots of people do not like it at all, and 71 comments, meaning that lots of people find it interesting. Given that many people at LessWrong seem to have an uncritical regard for him however they may think of him – prophet, profound thinker, potential Nobel laureate, whatever – the fact that such a conversation can take place there speaks well for the community, and indirectly for EY as well.
FWIW, I recently posted this (Why I hang out at LessWrong and why you should check-in there every now and then) at my New Savanna blog and cross-posted it at LessWrong. Haven’t gotten many comments (and nothing negative), but I’ve racked up 15 karma points, which is fine.
Comment #45 September 3rd, 2023 at 7:09 pm
@fred #43: I’m glad you liked that problem and saw how it worked. When people say things like “the LLM is the average of the internet, so that’s why it’s behavior is `average’ ” (or suggest it), it makes me think they are making an error similar to confusing these two sequences:
(f(x)+g(x))/2, (f(f(x)) + g(g(x))/2, (f(f(f(x))) + g(g(g(x))/2, …
and
h(x), h(h(x)), h(h(h(x)), … where h(x) = (f(x) + g(x))/2.
The second one is more analogous to what you would see in a language model. If you think of each term in the sequence as corresponding to a token being outputted, in the first sequence above, the f and g are not getting to “see” the previous token (or sequence of previous tokens). They’re seeing their own separate sequences only. Imagine doing that for the “average of the internet” — the model would have to keep track of the all the possible sequences (based on individual models of types of text), separately, and then average them together, with no mixing between the sequences. e.g. in the case of 3 sequences it would look like:
(f(x) + g(x) + h(x))/3, (f(f(x)) + g(g(x)) + h(h(x))/3, …
You need to keep track of 3 sequences to compute these averages — f(x), f(f(x)), … and
g(x), g(g(x)), … and h(x), h(h(x)), … Do this for millions of functions, and to compute an “average of the internet” model of text this way you’d have to run millions of separate models for each step.
Comment #46 September 4th, 2023 at 11:33 am
Why thank you Scott for this delicious palate cleanser! Recently I found myself digging up old shtetl blogposts to cleanse my palates. Most recently I seriously enjoyed (re?)reading your reply to Penrose from 2016 (https://scottaaronson.blog/?p=2756). I can’t remember if I read this back then, but it felt like I was reading it for the first time. Maybe I’ve developed an appreciation for the topic that I didn’t have back then.
The breakthrough in quantum LDPC codes seems significant indeed, though there seems to be serious hurdles to implementing these codes in practice, as discussed in the conclusion section of the paper.
At the moment, I would say that the two big questions are:
1) Can chip designers/manufacturers make high quality chips with the required connectivity?
2) Can we generalize these constructions to include logical gates (and not just memory) and still get similar advantages? As I understood, the problem there is the lack of good decoders.
The open problems at the end of the paper look very interesting.
Comment #47 September 6th, 2023 at 6:44 pm
(This is related to efforts to reduce the running time of Shor’s algorithm, mainly being a question about improving on a paper using hash functions to reduce the number of qubits needed in Shor’s algorithm and related algorithms.)
This is an attempt to generalize and strengthen the results in https://arxiv.org/abs/1905.10074 to general quantum circuits and to prove the BPP=BQP (below just covers decision problems with no intermediate measurements.)
The paper is about using hash functions to reduce the number of qubits required for Simon’s algorithm, Shor’s algorithm etc. There is some speculation that this could be used to prove BPP=BQP, if an appropriate homomorphic hash function could be found.
Consider the following setup.
For a quantum circuit with n qubits, g gates, no intermediate measurements, and 1 decision qubit, create a new circuit with a 2-qubits window for applying unitary gates and one $O(log n)$ qudit formed by hashing the bases of the remaining qubits with a universal hash function. For each gate in the original circuit, perform an operation which amounts to unhashing the state, rotating the state so as to expose a different two qubit window and rehashing. Then apply the unitary gate to the new 2 qubit window. At the end of the circuit, compute the probability of the answer qubit measuring to 0 or 1. The 2-qubit window is chosen for convenience so arbitrary gates will be universal for quantum computation.
The universal hash function is
$$
h_{a,b} = (ax + b \mod 2^{w+M}) \div 2^w
$$
The reason for choosing this universal hash function is that it is well adapted to working with qubits (it would be less suited to qutrits) and that “inverting” it is easy. The hash function is applied by treating the qubits’ bases as integers $x$ and taking each basis vector $x$ to its hashed basis $h(x)$.
Rotating to a new qubit window means adding and subtracting powers of 2 to $x$ like $x \to x + 2^k – 2^l$. Then, when we rotate the 2-qubit window the result is to shift the hashed state left or right. It’s not an exact permutation, since basis vectors in the same bin can wind up in different, yet neighboring bins with a calculable probabilities, $p$ and $q$, such that $p+q=1$. As such, we can approximate the results of unhashing, rotating, and rehashing the state.
Not being a true permutation, means that the matrix fails to be unitary. (As a sub-question what is the probability distribution of the determinant of this matrix?) However, if we coarse-grain the result of $UU^\dagger$ by merging neighboring bins, the result will, with a linear factor of mergers, quickly approximate unitarity.
Now, the question is whether the circuit described above can approximate quantum circuits in polynomial time. The argument consist of two steps: 1) the error introduced by each layer, that is, a unhash-rotate-rehash step and a unitary gate is bounded and 2) these errors accumulate over the course of the circuit slowly enough that the circuit can approximate the quantum circuit in polynomial time.
For 1), May and Schlieper provide an argument for specific circuits that the error in probability for a universal hash function is $O(1/m)$ (so the probability amplitude error would be expected to be around $O(1/\sqrt m)$). Their proofs requires that certain probability amplitudes sum to 0 which can’t be assumed for general quantum circuits.
The error \emph{introduced} by each layer can be estimated calculating the variance and standard deviation of the probability and probability amplitude errors. For $m$ bins, rotations have variances about $O(1/m)$ and standard deviations around $O(1/\sqrt{m}$. ( $O(\frac{1}{m^2})$ probability error per bin for $O(\frac{1}{m}$ probability error overall and $O(\frac{1}{m})$ probability amplitude error per bin and $O(\frac{1}{\sqrt{m}}$ probability amplitude error overall. So, errors are small enough per layer.
For 2) the main concern is that since the unhash-rotate-rehash matrices are not unitary they could magnify already existing errors (unitary matrices would keep them the same magnitude). The idea is that we can show that the circuit just consists of quantum operations — unitary gates and measurements — which can’t stretch the errors out, so that errors add up at most linearly. That is that hashed state is described as a reduced density matrix of the true quantum circuit.
For the hashed circuit’s density matrix, the unhash-rotate-rehash steps are formed from the sum of unhashed rotations, so it should be described as quantum operation (further mixing the a quantum state).
Otherwise, we can think of hashing as changing the basis of the unhashed qubits to one with the hashed qubits (assuming $m$ is a power of 2) and the remaining qubits and then summing out the “environment” leaving only the 2-qubit window and the hashed qubits. Then, the quantum operation argument applies and neither unhash-rotate-rehash steps nor 2-qubit unitary gates should be able to stretch out errors, so the error should accumulate at most linearly across gates. (Otherwise entangling a state with the environment would allow quantum cloning.)
Looking at probability amplitudes, if the errors grow linearly, the running time will be around $O(\frac{g^3}{\epsilon})$, where $\epsilon$ is the allowed error in the decision qubit, and if the probability amplitudes grow like a square root, the running time should be around $O(\frac{g^2}{\epsilon})$, which is what we would expect if the randomizations of layers are independent of each other and variances add up.
Comment #48 September 9th, 2023 at 6:05 pm
Because you mentioned AI, I wanted to link this hilarious video.
https://www.youtube.com/watch?v=02kbWY5mahQ&ab_channel=AlexTurner
Scott, what do you think? Anyway, I think this is the best place to post it.
Comment #49 September 11th, 2023 at 8:11 am
Scott and others: I have now posted a longish article rationalist culture and AI x-risk at 3 Quarks Daily. Here’s the title and the introduction:
A New Counter Culture: From the Reification of IQ to the AI Apocalypse
I have been thinking about the culture of AI existential risk (AI Doom) for some time now. I have already written about it as a cult phenomenon, nor am I the only one. But I believe that’s rather thin. While I still believe it to be true, it explains nothing. It’s just a matter of slapping on a label and letting it go at that.
While I am still unable to explain the phenomenon – culture and society are enormously complex: Just what would it take to explain AI Doom culture? – I now believe that “counter culture” is a much more accurate label than “cult.” In using that label I am deliberately evoking the counter culture of the 1960s and 1970s: LSD, Timothy Leary, rock and roll (The Beatles, Jimi Hendrix, The Jefferson Airplane, The Grateful Dead, and on and on), happenings and be-ins, bell bottoms and love beads, the Maharishi, patchouli, communes…all of it, the whole glorious, confused gaggle of humanity. I was an eager observer and fellow traveler. While I did tune in and turn on, I never dropped out. I became a ronin scholar with broad interests in the human mind and culture.
I suppose that “Rationalist” is the closest thing this community has as a name for itself. Where psychedelic experience was at the heart of the old counter culture, Bayesian reasoning seems to be at the heart of this counter culture. Where the old counter culture dreamed of a coming Aquarian Age of peace, love, and happiness, this one fears the destruction of humanity by a super-intelligent AI and seeks to prevent it by figuring out how to align AIs with human values.
I’ll leave Bayesian reasoning to others. I’m interested in AI Doom. But to begin understanding that we must investigate what a post-structuralist culture critic would call the discourse or perhaps the ideology of intelligence. To that end I begin with a look at Adrian Monk, a fictional detective who exemplifies a certain trope through which our culture struggles with extreme brilliance. Then I take up the emergence of intelligence testing in the late 19th century and the reification of intelligence in a number, one’s IQ. In the middle of the 20th century the discourse of intelligence moved to the quest for artificial intelligence. With that we are at last ready to think about artificial x-risk (as it is called, “x” for “existential”).
This is going to take a while. Pull up a comfortable chair, turn on a reading light, perhaps get a plate of nachos and some tea, or scotch – heck, maybe roll a joint, it’s legal these days, at least in some places – and read.
Comment #50 September 12th, 2023 at 4:05 pm
It seems that LLM detectors still do not work. Has OpenAI deployed the watermarking? Or is it a scam, so that they can claim that they tried by hiring you, and that it is not their fault then?
Comment #51 September 13th, 2023 at 9:21 pm
bystander #50: Watermarking (as opposed to discriminator models) has not been deployed yet. You can listen to my talk at the Berkeley LLM workshop if you want to understand some of the technical, social, and logistical challenges.
In the future, all comments with needlessly hostile embedded premises will be deleted without explanation.
Comment #52 September 14th, 2023 at 9:29 am
It seems that many just don’t get that Scott is currently an employee of OpenAI, and, like every employees, he just can’t/won’t/shouldn’t comment on what’s going on inside the company and the details of its products.
Comment #53 September 14th, 2023 at 12:54 pm
Hey Scott,
How’s life treating you in general, outside of computational complexity and deep learning that is 🙂 You mentioned on a recent post (can’t remember exactly which one) that the kids / family obligations and whatnot have been soaking up a lot of your time. I mean — how do you deal with raising two kids while at the same time being a professor, working at OpenAI, and running the top complexity blog on the internet—is there a secret 🙂
Comment #54 September 15th, 2023 at 9:29 am
Alec #53: The secret is to just drop stuff, which is exactly what I’ve been doing 🙁
Comment #55 September 17th, 2023 at 8:46 pm
I think this is a very nice-looking and interesting new paper worth mentioning by Eran Malach:
https://arxiv.org/abs/2309.06979
One of his theorems, in informal language (page 2):
“Theorem 1 (informal). For any function f that can be efficiently computed
using a Turing machine, there exists a dataset D such that training a (linear)
auto-regressive next-token predictor on D results in a predictor that approximates f.”
(One of several related posts of mine back in March: https://scottaaronson.blog/?p=7094#comment-1947372 )
I think some people wrote comments on some posts on this blog doubting something like this could be true, thinking that, yes, LLMs can compute very general things, if you get to precisely change the weights; but actually *training* them on data to do this is another matter — and in fact you won’t succeed in every case.
….
I think Malach’s examples with very simple linear neural nets using the TinyStories dataset (with a final non-linear output when a token is chosen) and MLPs using an arithmetic dataset with chain-of-thought, are also very interesting. It makes me wonder if it’s possible to create a synthetic dataset with liberal use of chain-of-thought and inner-monologues (written in invisible tokens) so that if you train one of these ridiculously simple models with it, you get a language model that is as good as Transformer-based ones, but using dramatically less computation and maybe even number of parameters. Maybe a pretty good one would even fit on a smartwatch.
And with the right data you might even make the model smarter than the “teacher” in many ways. e.g. using something like what I described here to @nole a few months back:
https://scottaaronson.blog/?p=7188#comment-1949227
I chose that one because I know it works! — turns out some researchers at Meta very recently did something similar (and added a filtering step, that also was automated):
https://arxiv.org/abs/2308.06259
Comment #56 September 20th, 2023 at 2:48 pm
A recent-but-not-so-recent paper surprised me (because I only now noticed it and have heard nothing about it), arguing that Google Quantum AI team has presented a new RCS experiment beyond the “computational capabilities of existing classical supercomputers”.
There’s been a lot of work on reducing the classical cost, but mostly before April. Is advantage back?
the paper: https://arxiv.org/abs/2304.11119