Indeed the takeaway of the paper is roughly speaking that there is a negative relationship between the length of proof required to prove that a network achieves a fixed level of accuracy, and the degree of mechanistic understanding.
A brute force proof is incredibly long, because you have to give a computational trace of every possible input to the network (in the
The current shorter proofs we have trade off some accuracy, but they are significantly shorter. These require you to engage with the mechanisms of the network, doing “interpretability”.
Jason Gross has published a number of other papers in this vein. Relevant to the modular addition transformer mentioned above, attempting to find a non vacuous proof of performance of linear length in parameter count lead to Modular addition without black-boxes: Compressing explanations of MLPs that compute numerical integration, which gives a detailed mechanism for the MLP layer in the modular addition task.
In this strict adversarial sense then the answer is we’ve not interpreted any SGD trained neural networks I think.
Perhaps modular addition but only because the input space is sufficiently small we can just brute force every input to be sure it’s not running a different program.
Maybe it’d be possible to make progress if you specified some sufficiently high complexity level on the hidden program.