Developing Good Heuristics

Neural nets (and LLMs and modern AI agents) are very complicated. Even though we know the architecture and parameters completely, it is very hard to understand what they are doing and how they are accomplishing their tasks. Thus, there is a concern that if a powerful AI system is capable of affecting the world, it will cause catastrophic harm. How do we deal with this?

One approach is to try and develop good heuristics, in lieu of proofs, or even understanding. This happens in math all the time: we develop some sense of what “generic behaviour” should be, and in lieu of structural properties to think otherwise we conjecture it to hold in a particular instantiation. If we had a better understanding of heuristics, we could apply it to AI systems and the question of whether a particular system will cause catastrophe.

ARC has tried to formalize this. Two important ingredients are meant to formalize the notion of “structure” and to detect “generic behaviour.”

Detecting hidden structure: No-coincidence conjecture

To make precise the notion of hidden structure, ARC has attempted to formalize a “no-coincidence conjecture,” in the spirit of the heuristic that sufficiently unlikely coincidences should have structural explanations. A good example to keep in mind is the twin prime conjecture, which is heuristically justified by pretending primes are random with 1/log(n) density. Their attempt is as follows; see ARC's A computational no-coincidence principle.

Conjecture (ARC computational no-coincidence). Let C : {0,1}³ⁿ → {0,1}³ⁿ be a reversible circuit. Define P(C) to mean: there is no input x ending in n zeros such that C(x) also ends in n zeros.

There is a polynomial-time verifier program V which takes in a pair (C, π) as inputs, such that:

• Completeness: if P(C) holds, then some polynomial-length advice string π makes V(C, π) = 1.
• Random-circuit soundness: for 99% of random reversible circuits C, no advice string π makes V(C, π) = 1.

Some remarks:

1. As the toy AI-safety application, imagine C to be an AI system and P(C) to represent the property that catastrophe will not happen, where a catastrophe is represented by an input x ending in n zeroes such that C(x) also ends in n zeroes. The idea is that such a V lets us be reasonably confident that C will not lead to catastrophe, though not certain.
2. If 99% were replaced by 100%, then this conjecture is equivalent to NP = co-NP. The sketch is that P(C) is essentially a co-NP-complete problem, and π is a certificate which V checks in polynomial time.
3. One should think of V as a human trying to evaluate whether P(C) holds, and π as a heuristic argument. The conjecture says that every true statement has a short convincing argument for it, and most false statements do not.
4. There are at least two heuristic reasons this might fail: some true statements might not have short heuristic arguments, or every statement—even a false one—might have a short convincing heuristic argument. The second part might seem implausible, but consider the possibility that there is a short heuristic argument for Peano Arithmetic being inconsistent. That would easily give a convincing argument for any statement!

For earlier related work see Formalizing the presumption of independence. See also Wide Neural Networks as a Baseline for the Computational No-Coincidence Conjecture for a version directly about large neural nets.

Estimating generic behaviour: Matching Sampling Principle

What does it mean to understand the generic behaviour of an AI system? An easy proxy is to imagine the AI system M as a function mapping inputs x sampled from some distribution D to outputs y, and ask for the expected value of f(M(x)). One may imagine f as measuring risk of catastrophe, or the risk that a particular safety feature is not satisfied.

The most naive way to compute this is simply to sample randomly. The Matching Sampling Principle program by ARC strives to do better. They ask whether we can do at least as well as sampling for an arbitrary M. First we detect hidden structure in the style of the no-coincidence conjecture and record that as an advice string π; then an estimator evaluates E_x∼D[f(M_θ(x))].

For a readable explanation, see ARC's outperforming random sampling explained, which frames MSP as the attempt to use a structural explanation to estimate model behavior at least as well as direct random sampling.

Formalization. A trained model is written as M_θ, where M is the architecture and θ is the learned parameter vector. An explanation or advice string π describes useful structure in M_θ, and an estimator might be written as G_M(θ, π, ε), where ε is the desired error tolerance. The hope is for the estimator to approximate the expectation of f(M_θ) to within ε, and to run in time comparable to sampling.

There is an issue with this phrasing: π can simply record the answer. Thus, the formal version adds another context parameter c, parametrizing models M_c,θ, and asks for π to be independent of c, while only requiring the conclusion for a generic c. In other words, E_c[(G_M(θ,c,π,ε) − E_x∼D[f(M_c,θ(x))])²] should compete with sampling. The idea is for G_M to run mechanistically—an imprecise notion which nonetheless seems a useful guiding post. This should involve understanding something about the structure of the architecture.

A good example is Cumulant Propagation in Appendix D of Formalizing the presumption of independence. The basic idea is mean propagation: input nodes in a neural net or circuit are considered independent Gaussian distributions, and we record only their mean. At every step, when we sum two nodes the means add, and when we multiply they multiply. We can improve this by keeping track not only of the means but also the variance and covariance between every pair of nodes. Cumulants detect roughly the kth-order interaction between random variables, and one can propagate only the kth cumulants, assuming higher ones are zero. This empirically performs well in cases such as random wide neural networks.