The Nonlinear Library LW - Coherence of Caches and Agents by johnswentworth
Apr 2, 2024
18:29
Welcome to The Nonlinear Library, where we use Text-to-Speech software to convert the best writing from the Rationalist and EA communities into audio. This is: Coherence of Caches and Agents, published by johnswentworth on April 2, 2024 on LessWrong.
There's a lot of confusion about what coherence means for agents, and what "coherence theorems" do and don't say about agents. In this post, I'll talk about some particularly simple notions of coherence in a particularly simple setting. We'll see what nontrivial things coherence has to say, at least in a simple kind of environment, starting with an analogous notion of coherence for caches.
What Kind Of "Coherence" We're Talking About Here
Let's start with a standard CS-101-style example. We write a recursive python function to compute fibonacci numbers:
We pass in n = 0, then n = 1, then 2, then 3, etc. It spits out 1, 1, 2, 3, 5, 8, .... Great. Buuuuut it gets very slow very quickly as n increases; the runtime is exponential in n.
So, standard simple improvement: memoize. The first time
fib(n) is computed for each value of n, cache it (i.e. "make a memo" of the result).
Now the recursive calculation will only happen once for each value of n, so runtime is linear in n.
Ok, that's the CS 101 part. Now on to coherence.
Imagine that the cache in our fibonacci program gets corrupted somehow. Maybe I mess around in the debugger and stick a few wrong numbers into it, maybe some other thread writes into it, whatever. Somehow, incorrect values end up in that cache.
Key point: we can notice the cache corruption "locally", i.e. by only looking at a small subset of the cache. Say, for instance, that cache[6] is corrupted - it should be 8 (the sixth fibonacci number), but instead let's say it's 11, and let's assume for now that the rest of the cache is fine. So we're looking in the cache, and we see:
cache[4] = 3
cache[5] = 5
cache[6] = 11
Well, just from those three entries we can tell that something's wrong, because 3 + 5 is not 11. It's supposed to be the case that cache[n] = cache[n-1] + cache[n-2] for any n bigger than 1, but that equation is not satisfied by these three cache entries. Our cache must be corrupt. And notice that we did not need to look at the rest of the cache in order to tell; we just needed to look at these three entries. That's what I mean when I say we can notice the cache corruption "locally".
We'll want a word for when that sort of thing isn't happening, i.e. a word which says that cache[n] is equal to cache[n-1] + cache[n-2] (in this particular example). For that, we'll use the word "coherence".
More generally: we'll say that a cache is coherent when small parts of the cache (like cache[n], cache[n-1], and cache[n-2] in this case) all locally satisfy some relationship (like cache[n] = cache[n-1] + cache[n-2]) which they're supposed to satisfy if everything is working correctly.
(Note that our usage here is a lot more general than the most common usage of "coherence" in CS; it's most similar to the use of "coherence" in formal logic. "Coherence" in CS is usually about the more specific case where different threads/processes/servers each have their own caches of the same information which might not match. That's a special case of the more general notion of "coherence" we'll use in this post.)
In the fibonacci example, if the whole cache is coherent, i.e. cache[n] = cache[n-1] + cache[n-2] for every n greater than 1, and cache[0] = cache[1] = 1, then the whole cache contains the values it's supposed to. In that case, the final cache entry, say e.g. cache[100], contains the result of fib(100).
More generally, we're typically interested in "coherence" in cases where all the local constraints together yield some useful property "at the large scale". In logic, that might be a property like truth-preservation: put true assumptions in, get true conclusions out. In our fibonacci example, the useful "large scale" property is that the cache in fact contains the fibonacci se...
There's a lot of confusion about what coherence means for agents, and what "coherence theorems" do and don't say about agents. In this post, I'll talk about some particularly simple notions of coherence in a particularly simple setting. We'll see what nontrivial things coherence has to say, at least in a simple kind of environment, starting with an analogous notion of coherence for caches.
What Kind Of "Coherence" We're Talking About Here
Let's start with a standard CS-101-style example. We write a recursive python function to compute fibonacci numbers:
We pass in n = 0, then n = 1, then 2, then 3, etc. It spits out 1, 1, 2, 3, 5, 8, .... Great. Buuuuut it gets very slow very quickly as n increases; the runtime is exponential in n.
So, standard simple improvement: memoize. The first time
fib(n) is computed for each value of n, cache it (i.e. "make a memo" of the result).
Now the recursive calculation will only happen once for each value of n, so runtime is linear in n.
Ok, that's the CS 101 part. Now on to coherence.
Imagine that the cache in our fibonacci program gets corrupted somehow. Maybe I mess around in the debugger and stick a few wrong numbers into it, maybe some other thread writes into it, whatever. Somehow, incorrect values end up in that cache.
Key point: we can notice the cache corruption "locally", i.e. by only looking at a small subset of the cache. Say, for instance, that cache[6] is corrupted - it should be 8 (the sixth fibonacci number), but instead let's say it's 11, and let's assume for now that the rest of the cache is fine. So we're looking in the cache, and we see:
cache[4] = 3
cache[5] = 5
cache[6] = 11
Well, just from those three entries we can tell that something's wrong, because 3 + 5 is not 11. It's supposed to be the case that cache[n] = cache[n-1] + cache[n-2] for any n bigger than 1, but that equation is not satisfied by these three cache entries. Our cache must be corrupt. And notice that we did not need to look at the rest of the cache in order to tell; we just needed to look at these three entries. That's what I mean when I say we can notice the cache corruption "locally".
We'll want a word for when that sort of thing isn't happening, i.e. a word which says that cache[n] is equal to cache[n-1] + cache[n-2] (in this particular example). For that, we'll use the word "coherence".
More generally: we'll say that a cache is coherent when small parts of the cache (like cache[n], cache[n-1], and cache[n-2] in this case) all locally satisfy some relationship (like cache[n] = cache[n-1] + cache[n-2]) which they're supposed to satisfy if everything is working correctly.
(Note that our usage here is a lot more general than the most common usage of "coherence" in CS; it's most similar to the use of "coherence" in formal logic. "Coherence" in CS is usually about the more specific case where different threads/processes/servers each have their own caches of the same information which might not match. That's a special case of the more general notion of "coherence" we'll use in this post.)
In the fibonacci example, if the whole cache is coherent, i.e. cache[n] = cache[n-1] + cache[n-2] for every n greater than 1, and cache[0] = cache[1] = 1, then the whole cache contains the values it's supposed to. In that case, the final cache entry, say e.g. cache[100], contains the result of fib(100).
More generally, we're typically interested in "coherence" in cases where all the local constraints together yield some useful property "at the large scale". In logic, that might be a property like truth-preservation: put true assumptions in, get true conclusions out. In our fibonacci example, the useful "large scale" property is that the cache in fact contains the fibonacci se...