jsenn

Has there been any serious study of exactly how LLMs store and retrieve memorized sequences? There are so many interesting basic questions here.

Does verbatim completion of a bible passage look different from generation of a novel sequence in interesting ways? How many sequences of this length do they memorize? Do the memorized ones roughly correspond to things humans would find important enough to memorize, or do LLMs memorize just as much SEO garbage as they do bible passages?

> Those layers have different representation space.

Do they? Interpretability techniques like the Logit Lens [1] wouldn't work if this were the case. That author found that at least for GPT-2, the network almost immediately transforms its hidden state into a "logitable" form: you can unproject the hidden state of any layer to see how that layer incrementally refines the next token prediction.

[1]: https://www.lesswrong.com/posts/AcKRB8wDpdaN6v6ru/interpreti...

On the contrary, examples like yours are the entire point of approaches like this one. If you read the HippoRAG paper cited by OP, their motivating example is almost identical to yours, and their evaluations are largely on multi-hop question answering of this kind.

The "embarrassingly simple inference technique" is to put a bunch of [MASK] tokens at the end of the prompt.

I'm having trouble understanding whether this paper is saying anything new. The original BERT paper already compared it favourably to causal models including GPT. Was there any doubt that BERT-style models could be in-context learners?

From what I gather as a non-expert, the problem with BERT is scaling/training efficiency: GPT gets C-1 training examples out of a training input of length C, but BERT only gets 0.15*C examples. Indeed, the author points out that DeBERTa required 3x more compute than GPT-3 to achieve the level of performance reported, which makes sense.

This is discussed in the "Watermarking with Synth-ID Text" section right after they define the Score function:

> There are two primary factors that affect the detection performance of the scoring function. The first is the length of the text x: longer texts contain more watermarking evidence, and so we have more statistical certainty when making a decision. The second is the amount of entropy in the LLM distribution when it generates the watermarked text x. For example, if the LLM distribution is very low entropy, meaning it almost always returns the exact same response to the given prompt, then Tournament sampling cannot choose tokens that score more highly under the g functions. In short, like other generative watermarks, Tournament sampling performs better when there is more entropy in the LLM distribution, and is less effective when there is less entropy.

I don't think this is right. If you're worried about units you can calculate the (generalized) surface area to volume ratio, which turns out to be exactly D/r. In other words, as D increases, the ratio goes to infinity.

I think this fact can fairly be interpreted to mean that a high-dimensional unit sphere encloses almost no volume. The 2D cartoon drawing of a hypersphere also helps capture this: you can imagine the "spikes" stretching out and squeezing the interior portion, until it's all outside and no inside.

EDIT: another argument I've seen involves calculating the ratio of the volume of a thin shell surrounding the n-sphere's surface to its total volume. You can prove that the limit of the ratio as the dimension goes to infinity is 1. In other words, in high dimensions almost all of the volume of the sphere is concentrated near its surface.

Deborah Gordon (ant biologist) makes this argument in her book Ant Encounters. Because the ants in a colony are all sisters, the unit of reproduction is actually the colony rather than the individual ant. Great book!

Very cool to see an article that discusses Crutchfield's Epsilon machine formalism. It's one of those rare theories that is conceptually powerful but also simple and concrete enough that it can be implemented in a couple hundred lines of code.

For those interested, [1] is a readable (if quirky) introduction to the theory. The paper discussed in this article seems to discuss a way of "stacking" epsilon machines, so that you have a machine that describes the state transitions of a machine that describes a data set. I wonder if this gets around the main weakness of the e-machine formalism, namely that for a process with non-finite memory, there's no obvious next class of automata to try after finite state machines. In a sense FSMs are the only non-arbitrary model of computation; everything else basically boils down to augmenting a finite-state control with a gadget for storing data, like a stack (pushdown automata), register (counter/register machines), random-access tape (Turing machines), random-access tape but you're only allowed a tape the size of the input (linear-bounded automata) etc. You can constrain that gadget in pretty much arbitrary ways, which makes it difficult to choose a computational model for a non-finite process.

[1]: https://csc.ucdavis.edu/~cmg/papers/CalcEmerg.pdf

Yes, that's a good way of thinking about it.

Another useful representation is as a point in spherical coordinates. The polar+azimuth angles encode the normal, and the radius encodes the distance from the origin.

This is handy because it puts similar planes nearby in space. For example, it allows you to efficiently cluster objects by coplanarity using a spatial index.

When you do the merge step on insert do you allocate scratch space or do a fancy in-place merge?

Some spec based systems allow you to refine a high-level spec until it’s detailed enough to generate code from, where each refinement can be proved correct [1]. I doubt this is done much, but it is possible.

[1] eg https://en.m.wikipedia.org/wiki/B-Method

As you can tell from the diversity of responses here it really depends on what you're doing. In my work I use C++, and "optimization" typically involves making a heavy computation run faster (measured in wall clock time) or making a particular subsystem use less memory.

The number one most important thing you can do is dive in and start profiling real-world code. Find a part of your software that is too slow or uses too many resources, and use whatever the standard profiler is for your development environment to figure out why. Performance optimization is a very empirical discipline. Yes there are general principles, but if you don't measure your baseline or your changes you won't know how good your optimization was. In my experience, the first attempt at a fix is often flat-out wrong! Doing this first will also help motivate your reading.

Once you know how to measure the performance of your software, I recommend learning the basics of modern computer architecture. At a minimum, learn about CPU caches, how they work, and how to design your code to use them effectively. I find Algorithms for Modern Hardware to be a good resource for this [1], but there are many others. Relatedly, you should have a rough idea of how long it takes for your computer to do various basic things (fetch something from memory, fetch something from cache, etc.). There's a table at [2] that gives a good idea. Don't worry too much about the absolute values--the order of magnitude is what's important.

You should also study fundamental data structures, but understand that for low-level programming 95% of the time the correct answer will be to shove everything into a simple flat array (e.g. std::vector in C++), maybe with some sort of index on top. Fancy data structures are more important in higher-level languages that are structurally unable to make effective use of modern hardware.

[1] https://en.algorithmica.org/hpc/

[2] https://gist.github.com/jboner/2841832

This was really helpful, but only discusses linear operations, which obviously can’t be the whole story. From the paper it seems like the discretization is the only nonlinear step—in particular the selection mechanism is just a linear transformation. Is that right? How important is the particular form of the nonlinearity?

EDIT: from looking at the paper, it seems like even though the core state space model/selection mechanism is linear (except for discretization?), they incorporate a nonlinearity in the full “mamba block”, which is stacked up with residual connections and layer norm just like in a transformer. They describe this as combining a linear attention and an MLP into a single step, rather than alternating attention and MLP as in a transformer.

Check the article. They have a learned preprocessing step that translates time slices containing multiple data points into tokens, so the transformer is actually predicting larger chunks of time rather than individual time points.

I also find this stuff fascinating, but I'm not sure Kolmogorov complexity (and therefore Solomonoff Induction) are useful models of any form of intelligence that matters in the real world. The main issue I see is that Komogorov Complexity is dominated by noise. The majority of bits in the smallest program that generates a given sequence will be devoted to reproducing arbitrary/accidental features of the sequence, rather than its computational structure. For example, if a Solomonoff Induction machine sees a data stream produced by someone flipping a coin, its model of that process will be... the data stream itself. To me, that's not intelligent behaviour. I would like an intelligent agent to "average out" the noise and say "this data stream is produced by sampling from a Bernoulli process with p = 0.5".

This is why I like Crutchfield's Epsilon Machine formalism[1]. He factorizes Kolmogorov Complexity into a noise part (Shannon Entropy) and a "computational part", which measures the structural complexity of the smallest probabilistic finite state machine that is an optimal predictor of the data sequence, under some coarse-graining. If the size of the optimal machine gets bigger and bigger the more fine-grained your measurement, then there's no finite representation of the sequence as a FSM, so you "jump up one level" to a stack machine and try again.

In the coin-flipping example above, the epsilon machine will correctly factor out all of the noise in the sequence, leaving you with a simple probabilistic model of a coin-flip process.

This procedure is also computable, and even practical: you can implement the FSM-only algorithm in a couple hundred lines of code.

[1]: https://csc.ucdavis.edu/~cmg/compmech/pubs/CalcEmergTitlePag...

A critical book I enjoyed when I read it (before starting my career) was The Real World of Technology: https://www.goodreads.com/en/book/show/1291973. Worth it just for the first chapter where she defines technology as practice, which helps clarify why the classic “technology X is a neutral tool that can be used for good or ill” argument isn’t very satisfying.

That said, I haven’t read it in a long time so not sure how well it holds up.

The methods section of the paper describes the training data generation as well as the model settings: https://www.nature.com/articles/s41586-023-06747-5#Sec16

Though not for the same purpose, some of the tricks described remind me of the “compact slot map” described here: https://gamedev.stackexchange.com/a/33905, including the “swap and pop” for deleting from the middle of the array.

I wonder if there’s a way to physically encrypt the DNA before sending it off for sequencing—e.g. randomly permute the base pairs, send jumbled DNA to sequencing company, get digital results back, then decrypt them. Of course generating the physical “private key” and then turning it into something usable to decrypt the results would have to be much simpler/cheaper than the sequencing itself, otherwise you’re back at square one…

There's an episode of BBC In Our Time about Automata: https://www.bbc.co.uk/programmes/b0bk1c4d

It’s hard to imagine this particular use case being practical, but it’s a cool idea, and it raises some interesting questions: would it be a good idea if you had a faster JIT? Why is it only 30% faster ignoring overhead? Would it work better on a more realistic benchmark (e.g. with a less uniform distribution of queries)?

This is a useful insight, but I think that many automations really are based on solid, honest-to-goodness abstractions of the same type you would find in math. Furthermore, that's good and important!

It's true that a compiler is merely translating a high-level language into the actual machine code, but it's simultaneously true that you can (generally) talk sensibly about the high-level language, and maybe even prove theorems about it, without making any reference to how it will be realized on the machine. That's a good abstraction.

The better your abstractions, the more your automations make sense, and the more you can reason about them. Automation without abstraction gives you biology, which is a gnarly mess of accidental complexity that's very difficult to reason about and control.

That said, I'm going to start thinking of my code more in terms of creating efficient and low-risk automation, and less about creating nice abstractions.

The books Tuning, Timbre, Spectrum, Scale [1] and Rhythm and Transforms [2] by Sethares have a lot of detail about the perception of higher level phenomena like pitch and rhythm. Plus he's an electrical engineer, so you get some code out of the deal. He doesn't dwell too much on the neuroscience aspect though--in both cases he's after a more functional explanation.

[1] https://sethares.engr.wisc.edu/ttss.html [2] https://sethares.engr.wisc.edu/RT.html

This was also where my mind went, and it's cited in the open letter, but it's worth noting that the premise of his critique is that IIT is not pseudoscience. In fact, he praises the theory for being clear enough to be proven wrong!

This might give a decent estimate of the entropy of the file, but it is a poor approximation of the Kolmogorov complexity in general.

All major compression libraries that I know of essentially work by "factoring out" statistical regularities in the input string--i.e. repeating patterns. But many strings have regularity that can't be captured statistically. For example, the sequence 1, 2, 3, 4, ... has an entropy rate of 1, because all digits and all subsequences of digits occur with equal frequency, so most modern compression libraries are going to be unable to compress it to any significant degree [1]. However, it obviously has a very compact representation as a program in your favourite language.

If you want to go down a bit of a rabbit hole, this video from a researcher in this field gives an overview, as well as some proposed methods for approximating Kolmogorov Complexity in a reasonable way (even though in a technical sense approximating it with known, fixed bounds is I believe impossible): https://www.youtube.com/watch?v=HXM3BUXsY4g. This paper also discusses a theory that decomposes KC into a statistical part (Shannon entropy) and a "computational part": https://csc.ucdavis.edu/~cmg/compmech/pubs/CalcEmergTitlePag....

[1]: Note that if you encode it as ASCII or even N-bit integers there will be significant redundancy in the encoding. To properly test it you'd have to encode the numbers in a packed binary encoding with no padding.

That makes sense. So ChatGPT has to use some cleverness to present the relevant previous text in the current prompt, but the language model is still responsible for pulling out the meaning of that context and responding appropriately. I remain mind-blown :)

> that the context-awareness is just a very well done illusion

Could you expand on this? The context awareness is the part that blows my mind. I would be disappointed/fascinated to find out that it’s “just” a simple set of tricks!

A fun post I wrote last year about an unexpected acoustic feature of those brick labyrinths you see in public parks.

The software is called MassMotion: https://www.oasys-software.com/solutions/pedestrian-simulati....

> Given that formation is the (density * speed * wiggleness) I assume boundary variability will have a logistic relationship with density right?

I'm not sure what you mean by this--boundary variability meaning the variance of velocity? I'm also not 100% sure what I mean about my own concern :D--really I'm just confused. I would feel like I understood the significance of the simulations more if, instead of having the same agents pop up at the bottom as just exited the top (i.e. periodic boundaries), agents simply left the simulation entirely at the top and new ones entered at the bottom (with correspondingly new velocities). Left-right boundaries are trickier I guess, not sure what would be reasonable there. Maybe just no boundaries.

There are good reasons why periodic boundaries are used (ensures density is well-defined and consistent, makes analytical calculations easier, etc.). It just strikes me as a obviously non-physical model, and one that could make emergent structures easier to form.