LLCs of Compiled Neural Networks

This project aims to study the Local Learning Coefficient (LLC) in neural networks that are compiled from known programs. By using tools like Tracr or other techniques for compiling programs into neural networks, we can create a controlled environment to study the relationship between algorithmic structure and the LLC.

Key research questions:

1. How does the LLC of a compiled neural network correlate with known measures of program complexity?
2. How does the LLC vary with model size for compiled networks implementing the same algorithm?
3. Can we use LLC analysis to detect the presence of specific algorithmic structures in neural networks?
4. How does the complexity vary between compiled networks and the same networks trained on the relevant task?

Methodology:

1. Implement a system for compiling a variety of algorithms into neural networks of different sizes.
2. Estimate LLCs for these compiled networks.
3. Compare LLC estimates to established measures of program complexity (e.g., Kolmogorov complexity & time/space complexity when available).
4. Investigate how LLCs change as we vary the size of the compiled network while keeping the underlying algorithm constant.
5. Attempt to use LLC analysis to detect the presence of specific algorithmic structures in more general neural networks.

Expected outcomes:

1. Empirical data on the relationship between LLCs and algorithmic complexity.
2. Insights into how LLCs reflect the underlying structure of compiled neural networks.
3. Potential development of LLC-based techniques for detecting algorithmic structure in neural networks.

This research could provide a bridge between the abstract notion of the LLC and more concrete measures of algorithmic complexity, potentially enhancing our ability to interpret the internal structure of neural networks.