On Bitrates of Very Sparse Superposition Codes

Thanks for taking the time to write your review. We took care to make this work reasonably accessible to readers without background in compressive sensing. (See our response to Reviewer VkuK.) We're happy to see that, despite your unfamiliarity with the literature, our claims and evidence were convincing.

Your question about how this work relates to training SAEs is natural. Indeed, in this work we suppose that the underlying dictionary is known and focus on the problem known as sparse reconstruction. On the other hand, an SAE also needs to learn the dictionary.

The most obvious significance of our results is that the encoder layer of an SAE may not be able to reconstruct the sparse latent code with reasonable accuracy, whether or not the correct dictionary is used. In particular, it is likely that some dimensions of the latent code can never be correctly inferred, and it would follow that their associated codewords can never be learned by the SAE. So, as you guessed, this suggests that we need to change our overall strategy for dictionary learning.

However, we hope that our analysis—and the information-theoretic point of view in particular—can inform interpretability research beyond SAEs. We would include the main points of our response to reviewer PjJn in the conclusion of the camera-ready version.

We're less sure whether the structure of our work should be adjusted. The sub-sections of Section 3 could potentially be re-numbered. However, our work doesn't follow the "methods/results" restructure common in empirical papers, and the overall sequence should remain the same.

Thank you for your thoughtful feedback and for bringing up the connection with compressive sensing (CS). Our decision to not reference many tools from this world—like restricted nullspace properties, proximal gradient methods, etc.—may be surprising, but it was made deliberately.

During this work, we did our best to inform ourselves in CS and were impressed by the variety of tools and perspectives. For example, besides the RIP, the restricted nullspace property also guarantees recovery of a sparse vector from the $L_1$ minimization problem but has been found to hold under weaker conditions [1]. On the side of numerical methods, many iterative algorithms (like ISTA and FISTA) can be motivated using proximal gradient descent, but Dono, Maleki, and Montanari showed that belief propagation motivates a proximal-type iteration with an additional "correction," sometimes called the Onsager correction, that significantly decreases the required undersampling ratio compared to ISTA [2]. It's hard to do this field justice! We appreciate your suggestion to reference another work of Candès'—are you referring to [3]?

However, we believe that the main content of this work wouldn't be improved by more tools from CS. This is for two reasons:

1. Our main message can be stated and defended without relying on tools like the RIP or reconstruction algorithms beyond simple matching pursuit.
2. As far as we know, the findings of this paper—in particular, the empirical performance of matching pursuit in Section 3.5—cannot be easily explained by existing theory of compressive sensing.

To begin, let us address your concern with our use of $\epsilon$-orthogonality/incoherence in Section 3.3. You suggest that it would be better to rely e.g. on the RIP. In fact, this section does not deal with the standard framework of compressive sensing: its goal is only to understand the reliability of what we call one-step estimates. (Such an estimate is like the first iteration of an iterative method.) As we explain, what determines the success of a one-step estimate is the scale of the crosstalk between different code words. Our proof of Proposition 3 (the main result of the section) relies on a uniform bound over sums of crosstalks. In usual regimes of compressive sensing, where the undersampling and sparsity ratios are bounded below by positive constants, these sums become very large and it becomes easy to show that one-step estimates do not work. Therefore, the results of Section 3.3 and the "rules of thumb" shown in Figure 3 have little to do with compressive sensing and would not benefit from a discussion of the RIP or the RNP.

You also suggested that it would be more natural to use a proximal gradient method. In fact, we previously considered using ISTA as our sparse reconstruction method. In Appendix G, we show some results obtained using coordinate gradient descent for the $L_1$ objective, which is a common alternative to ISTA that turned out to work better in our experiments. (We will mention this appendix in the main text of the camera-ready version.) ISTA performs slightly better than matching pursuit, but not enough to contribute to our conclusions substantially. Indeed, the role of Section 3.5 is only to show that some simple iterative method can significantly outperform one-step methods in our chosen regime, and our observation that one of the simplest imaginable methods already performs well strengthens this conclusion. The problem of benchmarking different compressive sensing methods is out of scope.

Finally, even if we had introduced more compressive sensing theory, we would not have been able to provide significantly more insight about the empirical results of Section 3.5. A lot of classical CS theory, like [4], focuses on the "linear regime" where $k/d \to \rho$ and $d/N \to \delta$ for some moderate constants $(\rho, \delta)$ bounded strictly between $0$ and $1,$ and applying bounds from this theory (like bounds derived from the RIP) give very weak guarantees in our setting. We searched the literature for more information on sublinear regimes where $\ln k / \ln N \to \epsilon < 1,$ including works like [5], but were ultimately not able to find a practical guarantee that explained Figure 5, and decided that further inquiry was out of the scope of this work.

Overall, we hope that this work encourages some readers to learn more about CS and are happy to include some more pointers and references in Section 3.5. (Certainly, it was our own inspiration.) However, including more CS theory in the body of the work would not make our findings significantly easier to explain or to understand. Given the choice, we prioritized making this work as accessible as possible.

[1] https://doi.org/10.1016/j.laa.2016.03.022 [2] https://doi.org/10.1073/pnas.0909892106 [3] https://doi.org/10.1016/j.crma.2008.03.014 [4] https://doi.org/10.1109/TIT.2005.858979 [5] https://proceedings.mlr.press/v99/reeves19a.html

Thanks for taking the time to write your review.

Sparse autoencoders are indeed "efficient" in the sense they are computationally inexpensive, at least relative to other dictionary learning methods. In this work, we explain that they are inefficient in an information-theoretic sense. For example, we argue that, as the sparsity $k$ and latent dimension $N$ grow to infinity within a certain regime, a SAE encoder requires the dimension $d$ of a superposition code to grow faster than the entropy of the underlying sparse latent. I hope that this resolves the main weakness you perceived in this work!

Your suggestion to conduct experiments using real LLM activations is natural. However, this work is occupied with providing theory to inform future methods. In our interactions with researchers doing empirical work on SAE, we realized that ideas from compressive sensing are frequently underappreciated. On the other hand, we were unable to find references characterizing the "inefficiency" of one-step methods in a regime meaningful to SAE applications. Before these insights can be used practically, we believe it's important to make the findings of the present work better known. We discuss the relevance of our work to interpretability in more depth in our response to Reviewer PjJn.

Thanks for raising the question of how our findings relate to real applications of SAEs in interpretability. In fact, we hope this work will help interpretability researchers become more aware of ideas from compressive sensing. However, after reading your review, we realize it may be useful to clarify the broader significance of these ideas.

Let's begin by addressing your main concern. It's true that attempts to apply iterative reconstruction at inference time, as in Engels' work, have not had much success. However, the dictionaries used by these inference-time optimization methods are still learned using non-iterative ("one-step") encoders at training time. If some latent variable cannot be reliably inferred during training, its codeword will almost certainly not become an element of the dictionary, and no amount of optimization at inference time will be able to read the latent. So, the failure of inference-time optimization (ITO) does not rule out the possibility that SAE error could be modeled by an iterative encoder provided with the right dictionary. Indeed, when its bitrate exceeds the capabilities of a top-$k$ encoder, a superposition code from our own toy example will look like SAE dark matter in the language of Olah/Engels.

In our own work, however, we are explicitly holding off on proposing an improvement over SAEs. Our message is not that SAEs need to be modified to use specific compressive sensing algorithms, or that real experiments with residual vectors will resemble our own toy experiment. Our message is simply that, in general, reading latent variables from a superposition code through "one-step estimates" is very inefficient from a coding-theoretic point of view and that even surprisingly naive methods (like matching pursuit) can do much better. This is true for generic reasons and is a well-known phenomenon in the field of compressive sensing. However, before this work, we weren't able to find a comparative analysis of SAE-type encoders in a regime that makes sense to interpretability researchers.

How can this message inform work on SAEs? As we see it, one huge challenge in mechanistic interpretability is that we don't know the true structure of the (hypothetical) interpretable latent representation. For example, it's possible that some "features" have special relationships, should be viewed as elements of a continuous space, etc.. However, we can still talk about the entropy of the latent representations and consider the bitrate at which it is encoded by an activation vector.

Even beyond the toy model of this paper, it is very natural that linear estimates for properties of the latent representation would suffer from significant crosstalk. As we explain in this work, this limits one-step methods to reading a small amount of information—for example, a fractional bit—from each dimension of the residual vector. (In practice, it's possible that only a limited selection of "large magnitude" properties will be recovered, while latent variables represented with smaller magnitude are impossible to read due to crosstalk.) The compressive sensing point of view, as introduced in this paper using a simple toy example, raises at least two routes for future inquiry:

1. First, the existence of compressive sensing algorithms means that significantly more information can be stored in a residual vector through linear superposition. Although neural networks do not explicitly decode the latent representation—let alone run a method like OMP, ISTA, etc.—there is no reason in principle why they cannot learn to use this extra information, especially if the latent signal has some special structure. This raises the question of estimating the bitrates of neural representations in practice and determining whether they exceed the low bitrates that limit one-step decoders.
2. The structure of existing compressive sensing algorithms gives us some clues on how this "extra information" can be decoded, should it exist. Roughly, the idea is to use our dictionary to model the noise term $Z$ of Equation 1 (line 216), which previously we treated as a Gaussian. In practice, this means letting our estimates for the different components of the latent vector communicate.

Overall, the hypothesis that extra information can be stored in linear superposition is not ruled out by the apparent failure of ITO, and we believe the point of view of compressive sensing can help us reason about future approaches in interpretability.

If this resolved your skepticism regarding the failures of ITO, please consider reevaluating our work. If you found this explanation helpful, we would be happy to include some similar discussion in the conclusion of the camera-ready version.