Zoology: Measuring and Improving Recall in Efficient Language Models

arxiv:2312.04927

Original source · Paper JSON

LLMs: architectures, context, training · 2023-12-08

Cites (3) · Cited by (3)

Complete cleaned Markdown · Source Markdown including bibliography

Read in parts

1. Part 1
2. Part 2
3. Part 3
4. Part 4
5. Part 5
6. Part 6
7. Part 7
8. Part 8
9. Part 9
10. Part 10
11. Part 11
12. Part 12
13. Part 13
14. Part 14

Contents

• Zoology: Measuring and Improving Recall in Efficient Language Models
• Abstract
• 1 Introduction
• 2 Background and Preliminaries
• 3 Identifying the associative recall problem
• 3.1 Fine-grained analysis of downstream quality
• Perplexity Gap
• Associative Recall Perplexity
• 3.2 Formalizing the problem: Multi-Query Associative Recall
• Definition 3.1 (Multi-Query-AR ( Mqar ) \left(\textsc{Mqar}\right) ) .
• 4 Explaining the associative recall problem
• 4.1 BaseConv : a minimal gated convolution operator
• Definition 4.1 ( BaseConv Operator) .
• Theorem 4.2 (Equivalency to Arithmetic Circuits) .
• 4.2 Theoretical analysis of gated convolution capacity and associative recall
• Proposition 4.3 (Attention) .
• Theorem 4.4 (Data-Independent Filters 7 7 7 We note here that existing architectures also use data-independent convolution filters, meaning the filter is defined as a function of the model parameters, independent of the input. ) .
• Theorem 4.5 (Input-Dependent Filters) .
• 4.3 Empirical analysis of gated convolution capacity and associative recall
• Setup
• 5 Closing the Associative Recall Gap
• Sparse BaseConv -Attention Hybrids
• Downstream Evaluations
• 6 Discussion and Conclusion
• Acknowledgments
• Appendix
• Appendix A Extended Related Work
• A.1 Mechanistic Interpretability, Synthetic Languages, and Associative Recall
• A.2 Efficient Language Modeling Architectures
• A.3 Input-Dependence in Sequence Modeling Architectures
• Appendix B Code Listing
• Appendix C Downstream Experimental Details
• C.1 Measuring the Mqar Gap on Real Language Data
• C.2 Gated Convolution Downstream Architectures
• Hybrid Architectures
• Appendix D Extended Downstream Analysis of Mqar
• D.1 Additional Discussion of Mqar in the Pile
• D.1.1 Pile Examples
• D.1.2 Distribution of Mqar Hit Positions in Sequences
• Implications
• D.2 Analyzing Mqar across Varied Language Distributions
• Appendix E Synthetic Mqar Experimental Details
• E.1 Mqar Generation Procedure
• E.2 Training Details
• Appendix F Extended Results on Mqar Across Architectures
• F.1 Synthetic Experiments
• Experiment 1: Increasing the number of token-interaction distances per example.
• Experiment 2: Increasing the number of key-value pairs occurring per example.
• Experiment 3: Increasing the range of token-interaction distancs per example.
• F.2 Demonstrating Mqar as a Tool for Architecture Development
• Appendix G Mqar Perplexity Gap and Model Size
• Open-source 7B parameter models
• Measuring AR Gap with Scale
• Appendix H Details on Theoretical Analysis
• H.1 Preliminaries and Notation
• H.1.1 Notation
• Polynomial Notation.
• Arithmetic Circuit Notation.
• Definition H.1 .
• Model Notation.
• H.1.2 Summary of the Results
• H.2 Gated Attention-Free Models
• Definition H.2 .
• Definition H.3 .
• Remark H.4 .
• H.2.1 The Hyena Layer
• Remark H.5 .
• H.2.2 The RWKV Layer
• H.2.3 The Retnet Layer
• H.2.4 BaseConv
• Proposition H.6 .
• Proof.
• Lemma H.7 .
• Proof.
• H.3 Primitives
• Proposition H.8 (The Shift Primitive) .
• Proof.
• Proposition H.9 (The Running Sum Primitive) .
• Proof.
• Resetting for Next Phase.
• Proposition H.10 (The Remembering Primitive) .
• Proof.
• Lemma H.11 .
• Proof.
• H.3.1 BaseConv -Hyena Equivalence
• Proposition H.12 .
• Proof.
• H.4 Linear Arithmetic Circuits
• Definition H.13 (Linear Arithmetic Circuit [ Bürgisser et al., 1996 ] ) .
• Definition H.14 (Butterfly Matrices [ Dao et al., 2020 ] ) .
• Proposition H.15 .
• Lemma H.16 .
• Proof.
• Definition H.17 (The Kaleidoscope Hierarchy [ Dao et al., 2020 ] ) .
• Lemma H.18 .
• Proof.
• Theorem H.19 ( [ Dao et al., 2020 ] ) .
• Corollary H.20 .
• H.5 General Arithmetic Circuits
• Theorem H.21 .
• Proof Sketch of Theorem H.21 .
• Proof of Theorem H.21 .
• Addition Gates.
• Multiplication Gates.
• H.6 The Retnet Reduction and Space Complexity for AR
• Corollary H.22 .
• Proof.
• The Space Complexity of AR
• Theorem H.23 ( [ Jayram et al., 2008 ] ) .
• Corollary H.24 .
• Proof.
• H.7 The Multiple-Query Associative Recall Problem
• H.7.1 Introduction
• Setup.
• Remark H.25 .
• H.7.2 Mqar Solution via Attention
• Remark H.26 .
• Proposition H.27 .
• Proof.
• H.7.3 Initial Attempt: A Sequential Algorithm
• Proposition H.28 .
• Proof.
• H.7.4 Algorithm via Parallel Binary Search
• Remark H.29 .
• H.7.5 Correctness and Complexity
• Proposition H.30 .
• Proof.
• H.7.6 Conversion to Arithmetic Circuit
• Circuit for pbs-key-values .
• Definition H.31 (Comparators) .
• Lemma H.32 ( Cormen et al. [2022] ) .
• Proposition H.33 .
• Proof.
• Circuit for Parallel-MQAR .
• Definition H.34 (Informal) .
• Lemma H.35 ( Ajtai et al. [1983] ) .
• Proposition H.36 .
• Proof.
• H.7.7 The Resulting BaseConv Model
• Theorem H.37 .
• Proof.
• H.8 Data-Dependent Convolutions
• H.8.1 Introduction
• Setup.
• Autocorrelations
• H.8.2 BaseConv with kernels generated using Auto-Correlation
• The Input-Dependent Kernels.
• Projections.
• Theorem H.38 .
• Proof.
• Instructions for reporting errors