acceptodds
Under review as a conference paper at ICLR 2027

How Many Probes Identify What a Network Computes?

Abstract

Two networks can agree on every test example and still compute different functions. Benchmarks cannot separate them when the relevant disagreement is rare under the evaluation distribution. We show that any score formed by averaging a bounded loss differs by at most between two mechanisms that disagree on an fraction of that distribution, independent of benchmark sample size. Choosing the inputs is what helps. For a probe set with separation , identification cost scales inversely with , while a sufficient budget grows only logarithmically with the number of candidate mechanisms; per-query unreliability is controlled by a Bhattacharyya exponent . The predicted inverse-separation scaling is confirmed at slope () across a 25-fold range of . A greedy multicover identifies one of 256 mechanisms using 24 probes, while random draws from the same pool still misidentify 31% of models after 256 queries. On sixteen trained transformers, one designed probe reaches the 95% identification target that requires five random probes, and the random-probe curve is predicted without fitting. Across seven Pythia-410m checkpoints, candidates derived from the prompt and corpus statistics recover the checkpoint at which the dominant behavior changes. Across these settings, the value of probe design is governed by a separation quantity that can be computed before querying the model.

Primary area:
interpretability and explainable AI
Keywords:
mechanism identification, model evaluation, experimental design, black-box probing, sample complexity, language models

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_51QkOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
1
Presentation
1
Soundness
2(+1)
Read review
Paper summary

The paper studies when benchmark scores can distinguish competing model mechanisms and when targeted probes are needed. It gives a bounded-score “blindness” result, query bounds in terms of pairwise probe separation Δ\Delta, a greedy multicover procedure for selecting probes, and experiments on synthetic candidates, small trained transformers, and Pythia-410m checkpoints. The distinction between estimating performance and identifying behavior is useful, and Δ\Delta gives it a simple quantitative framing.

Critical strengths
  • The problem is clearly motivated, and the separation measure makes the role of probe design easy to interpret.
  • The authors acknowledge that the Pythia analysis is conditional on its two chosen candidates.
Critical weaknesses
  1. The paper defines Δ(S)\Delta(S) as the empirical separation of a fixed probe set. But the noiseless proof of Theorem 4 uses the probability (1−Δ)n(1-\Delta)^n of missing a separating probe, and the ρ=0\rho=0 lower bound in Theorem 5 scales as Δ−1log⁡(1/δ)\Delta^{-1}\log(1/\delta). Those arguments require probes sampled afresh from a distribution with separation probability Δ\Delta. For a fixed designed set with positive empirical separation, every candidate pair is already separated; with noiseless observations, identification is exact and has no log⁡(1/δ)\log(1/\delta) cost. This is a material issue because the query bounds are the central theoretical contribution.

  2. The two Pythia candidates together account for about 43% of predictions, and the reference label is which candidate agrees more on 1,200 designed probes. This demonstrates candidate ranking, not that the model follows one of those mechanisms with high probability—the assumption behind the identification guarantee. The experiments are also small: 16 tiny transformers and seven checkpoints from one Pythia training trajectory.

  3. The blindness bound is a direct coupling argument, while the identification and selection results draw on standard hypothesis-testing and submodular-cover ideas. The synthesis may be useful, but the paper does not yet make clear what new insight or capability it provides beyond applying those tools to mechanism probing.

Questions for authors
  1. Could you state separate assumptions and results for fixed designs and random sampling?

  2. Concerning the Pythia candidates, could you keep the distinction between candidate ranking and distinguishing competing model mechanisms explicit in the abstract and conclusions?

1 comment
AuthorsOpenReview ↗

Response to Reviewer 51Qk

Thank you for the careful reading. Separating fixed designs from random sampling, as you suggested, produced the main theoretical result of the revision.

W1 / Q1. Separate assumptions and results for fixed designs and random sampling. The Δ−1\Delta^{-1} scaling is a random-sampling law, whereas on a fixed design noiseless identification is exact once every pair is separated. The revision states the two settings as separate theorems, each with matching upper and lower bounds, and the comparison shows that design changes the exponent itself:

  • Fixed design (Theorem 4). The relevant quantity is the number cij(S)c_{ij}(S) of separating queries per pair. Plurality errs with probability at most ∑j≠⋆βc⋆j\sum_{j \ne \star}\beta^{c_{\star j}}, and every rule errs with probability at least 14β2cij\frac{1}{4}\beta^{2c_{ij}}. Hence cmin⁡≥log⁡((k−1)/δ)/D(ρ)c_{\min} \ge \log((k-1)/\delta)/D(\rho) suffices and cmin⁡≥log⁡(1/(4δ))/(2D(ρ))c_{\min} \ge \log(1/(4\delta))/(2D(\rho)) is necessary. A Fano argument on Hadamard candidates adds the matching dependence on kk, so the worst-case cost of a fixed design is Θ(log⁡k+log⁡(k/δ)/D(ρ))\Theta(\log k + \log(k/\delta)/D(\rho)). At ρ=0\rho = 0, identification is exact if and only if every pair is separated once, which takes ⌈log⁡2k⌉\lceil \log_2 k \rceil binary queries.
  • Random sampling (Theorem 5). With ΔQ=min⁡i≠jPr⁡Q[fi≠fj]\Delta_Q = \min_{i \ne j}\Pr_Q[f_i \ne f_j], plurality errs with probability at most (k−1)(1−ΔQ(1−β))n(k-1)(1-\Delta_Q(1-\beta))^n, and every rule errs with probability at least 14(1−ΔQ(1−β))2n\frac{1}{4}(1-\Delta_Q(1-\beta))^{2n}. On Hadamard candidates every rule also needs n≥log⁡(k/(16δ))/(8ΔQ(1−β))n \ge \log(k/(16\delta))/(8\Delta_Q(1-\beta)), so the worst-case cost is Θ(log⁡(k/δ)/(ΔQ(1−β)))\Theta(\log(k/\delta)/(\Delta_Q(1-\beta))), which is Θ(ΔQ−1log⁡(k/δ))\Theta(\Delta_Q^{-1}\log(k/\delta)) at ρ=0\rho = 0.

The experiments that test the Δ−1\Delta^{-1} law (Figure 2, the random arms of Figures 3–4, and the natural queries for language models) draw queries at random, the setting of Theorem 5. At all 44 settings of Figure 2, the measured n⋆n^\star lies inside the window of Theorem 5 and matches the exact value up to Monte Carlo error. The designed arms are fixed designs, governed by Theorem 4.

W3. What the synthesis adds. A designed separating query contributes the exponent D(ρ)=−log⁡βD(\rho) = -\log\beta, which diverges as ρ→0\rho \to 0, while a random query contributes ΔQ(1−β)≤ΔQ\Delta_Q(1-\beta) \le \Delta_Q. Design therefore removes the factor ΔQ−1\Delta_Q^{-1}, and for reliable models also the dependence on δ\delta. The gain is largest for reliable models and rarely disagreeing candidates, where benchmark scores are most readily trusted. Two further results are new: Corollary 6 covers candidates that explain only part of the behavior, and Proposition 7 gives a single submodular objective whose value certifies the error. In simulation the certificate is within a factor of 1.7 of the measured cost at every kk up to 256.

W2 / Q2. Candidate ranking. We adopted the term in the abstract, Section 6.1 and the discussion, and Corollary 6 makes it formal: if the model matches the two candidates with probabilities a>ba > b on separating queries and neither otherwise, ranking errs with probability at most (1−(a−b)2)c(1-(\sqrt{a}-\sqrt{b})^2)^c, with a matching lower bound. The guarantee therefore covers ranking without assuming that the candidates exhaust the behavior, and the paper reports coverage a+ba+b for every model. In current models the two candidates cover 0.53–0.75 of the answers, more than in any final Pythia checkpoint (at most 0.50), coverage increases with size within each family, and answers derived from the prompt or corpus statistics account for 76–90% of the behavior (Figure 5c).

For the reference label, an independent set of 1,200 designed queries (separate random stream, final token unique in the prompt) gives the same label for 131 of the 131 checkpoints and models evaluated on it.

Internal mechanism (new, Section 6.1, Figure 5d; general response, point 4). The certified ranking is tied to the circuit that produces it. Removing the 10% of heads with the highest induction score reverses the ranking in all 18 models ablated, while as many random heads, which cost at least as much WikiText accuracy, leave it unchanged in 34 of 36 draws.

Scale of the experiments. In addition to the original 16 networks (Figure 4a), we trained 960 networks across three widths and five separations, and the zero-parameter prediction holds within 0.014 in every cell (Figure 4b). 14 Pythia runs join the original one (five sizes, both training sets, five seeds each at 160M and 410M), and the change from bigram to induction falls between steps 512 and 1000 in all 15. We also evaluated 12 current open models up to Qwen2.5-72B, using identical queries (Section 6.1, Figure 5c).

Reviewer_fmU7OpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper is concerned with identification - i.e. knowing when two networks are computing the same function. They correctly point out benchmarks alone are not sufficient here. At a very high level, this is solved by varying the inputs to the network, observing the outputs, and showing when these are identical, the networks are likely the same. The paper notes that if benchmarks agree, the underlying difference in model is bounded (at most 2B/epsilon). They then introduce an approach to find inputs where the models will disagree, and define bounds on how many such probes are required. Their experiments, on pythia-410m, confirm these bounds.

Critical strengths

The paper is analytically rigorous - I did not see any obvious mistakes in the derivations. The writing, while hard to parse in many places, is dramatically correct and well formatted.

Critical weaknesses
  1. The motivation needs to be significantly expanded - it is not clear in what setting this form of identification would be needed or useful. The use of probe to refer to a perturbation of the inputs is also confusing and non-standard.

  2. The models chosen for experiments are weak - pythia-410m is both very small (and hence likely has different probe behaviour to 70b+ param models), and is quite old at this point. It would be far more relevant to use modern models.

  3. The derivations are quite straightforward and not surprising - I do not feel they add anything to the literature.

Questions for authors

Could you expand on "This distinction matters whenever the goal is not only to estimate performance, but also to determine which behavior a deployed model will follow under targeted distribution shift." What scenarios precisely are referred to here?

1 comment
AuthorsOpenReview ↗

Response to Reviewer fmU7

Thank you for the questions on motivation, terminology, model scale and novelty. Each is now addressed in the paper.

Q / W1. In what scenarios is identification needed? The introduction now gives three settings, each matched to an experiment:

  1. Shortcut audits. A model that reads a spurious cue and one that computes the intended rule agree wherever cue and rule agree, so a benchmark separates them only through rare counterexamples. A deployment shift that decorrelates the two exposes the difference on every input. The trained-network experiment in Section 6 is this case: at η=0.02\eta = 0.02, random in-distribution evaluation needs 114 queries to tell the two apart at 95%, while one designed query suffices, in every cell of the 960 networks we trained.
  2. Context versus memory in language models. Copying from the context and producing the corpus-typical continuation give the same answer on typical text. Which one a model follows determines its behavior under retrieval augmentation, conflicting documents or knowledge editing. Section 6.1 measures this in 15 pretraining runs and 12 current models.
  3. Change audits. After fine-tuning, quantization or further training, one needs to know whether the model still executes the same procedure, even when its benchmark score has not moved. Theorem 2 shows that the benchmark cannot answer this, and Theorems 4–5 give the query budget in advance. The head ablations of Section 6.1 are such an audit: removing the induction heads and removing as many random heads lower WikiText accuracy by similar amounts (median −2.4 and −2.8 points), yet designed queries find the ranking reversed after the first in all 18 models ablated and after the second in only 2 of 36 draws.

Terminology. We agree that "probe" is easily confused with probing classifiers. The revision uses "query" throughout, defines it and distinguishes it from probing classifiers. Because ICLR does not permit title changes during the discussion period, the title will become Benchmarks Are Blind to Mechanism: How Many Queries Identify What a Network Computes? when that is allowed.

W2. Modern and larger models. The revision evaluates 12 current open models, released 2024–2026, with the same queries: Qwen3.5-0.8B, Qwen3.5-2B, Gemma-2-2B, Qwen3.5-4B, Llama-3.1-8B, Qwen3.5-9B, Gemma-2-9B, Qwen3.5-27B, Gemma-4-31B, OLMo-3.1-32B, Qwen3.5-35B-A3B, Qwen2.5-72B. The largest has 72B parameters. All rank induction above bigram. The two candidates cover 0.53–0.75 of the answers, more than any final Pythia checkpoint (at most 0.50), and coverage rises with size within each family. The cost of certifying the ranking falls to 4–9 designed queries, from a median of 21 for the final Pythia checkpoints, so within each family larger models are cheaper to certify. The same prompt- and corpus-derived candidates are used for every model, so the identification problem is identical across scales.

W3. Novelty of the derivations. The revision adds results that do not follow from applying standard tools directly:

  • Two regimes with different exponents. A fixed design gains D(ρ)=−log⁡βD(\rho) = -\log\beta per separating query and random sampling gains ΔQ(1−β)\Delta_Q(1-\beta) per query, and both come with matching lower bounds, including the log⁡k\log k factor. Design therefore removes the factor ΔQ−1\Delta_Q^{-1} and, for reliable models, the dependence on δ\delta. Benchmarks fall furthest short of what is achievable when models are reliable and the candidates rarely disagree.
  • Partial coverage. Corollary 6 shows that candidates need not exhaust the behavior. Unmatched answers enter only through (a−b)2(\sqrt{a}-\sqrt{b})^2.
  • A certified design objective. Ψ(S)=∑i<j(1−βcij(S))\Psi(S) = \sum_{i < j}(1-\beta^{c_{ij}(S)}) is monotone submodular, so greedy selection attains a (1−1/e)(1-1/e) fraction of the best value, and the value itself bounds the identification error before any model is queried (Proposition 7).

Each result is checked against measurements without fitted constants:

  • agreement with the exact cost at all 44 regime settings;
  • on Hadamard candidates (k=4k = 4 to 6464), the measured cost lies between the new worst-case lower bound and the upper bound in all 18 settings and grows linearly in log⁡k\log k;
  • the zero-parameter curve within 0.014 for 960 trained networks;
  • the cost of natural queries across 132 language-model checkpoints and models, predicted from designed-query rates with median ratio 1.00.
Reviewer_s5LrOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper investigates how to identify neural network mechanisms using carefully designed probes rather than conventional benchmark evaluations. The authors introduce probe-set separation (Δ) and derive theoretical bounds on the required number of queries. A submodular multicover strategy is proposed to select informative probes. Experiments on synthetic mechanisms, trained transformers, and Pythia-410m checkpoints demonstrate improved identification efficiency over random probing.

Critical strengths
  1. The paper clearly distinguishes mechanism identification from benchmark performance evaluation. The separation-based framework provides an interpretable perspective on designing informative evaluation inputs.

  2. Experiments across synthetic settings and trained neural networks demonstrate that designed probes can substantially reduce the number of queries required for behavioral hypothesis identification.

Critical weaknesses
  1. Theorem 5 claims a necessary query bound that may not hold for deliberately selected probes, particularly in the noiseless setting. The distinction between random sampling and deterministic probe selection needs to be clarified.

  2. In the Pythia-410m experiment, the two candidate mechanisms explain only approximately 43% of predictions. Therefore, the results primarily demonstrate discrimination between predefined behavioral hypotheses rather than identification of the model's actual computational mechanisms.

Questions for authors
  1. Does Theorem 5 apply to randomly sampled probes or deliberately selected probes? How does the claimed lower bound hold when a single noiseless probe can perfectly distinguish two candidates?

  2. Given that the two candidate mechanisms explain only approximately 43% of Pythia predictions, how can the authors justify interpreting the results as mechanism identification rather than relative agreement between candidate behaviors?

  3. Does the stated (1−1/e) approximation guarantee apply to the complete probe-selection algorithm with dynamically increasing saturation levels, or only to the fixed-saturation objective?

3 comments
AuthorsOpenReview ↗

Response to Reviewer s5Lr

Thank you for three precise questions. Each led to a formal change in the paper.

Q1. Does Theorem 5 apply to random or selected probes, and what about one noiseless separating probe? The original Theorem 5 is a random-sampling statement. The revision states both regimes, each with matching upper and lower bounds:

  • Random sampling (now Theorem 5). For queries drawn from QQ with separation ΔQ\Delta_Q, the cost is Θ(log⁡(k/δ)/(ΔQ(1−β)))\Theta(\log(k/\delta)/(\Delta_Q(1-\beta))), including the log⁡k\log k factor.
  • Fixed design (now Theorem 4). The bound is in terms of the separating count cij(S)c_{ij}(S): plurality errs with probability at most ∑j≠⋆βc⋆j\sum_{j \ne \star}\beta^{c_{\star j}}, and every rule errs with probability at least 14β2cij\frac{1}{4}\beta^{2c_{ij}}. At ρ=0\rho = 0, a single separating query per pair identifies exactly, as in your example.

The comparison has a consequence discussed in Section 4: design removes the factor ΔQ−1\Delta_Q^{-1}, and for reliable models also the dependence on δ\delta. Figure 2 tests the random-sampling theorem, and at all 44 settings the measured n⋆n^\star matches the exact value up to Monte Carlo error.

Q2. The Pythia candidates cover about 43%. Is this mechanism identification or relative agreement? It is candidate ranking, and the revision says so in the abstract, Section 6.1 and the conclusions. Corollary 6 shows that ranking is what the certificate guarantees under partial coverage: with match probabilities a>ba > b and abstention otherwise, ranking errs with probability at most (1−(a−b)2)c(1-(\sqrt{a}-\sqrt{b})^2)^c, and no rule does better than a quarter of the square of that quantity. Coverage thus enters the rate instead of being assumed. The paper reports coverage for every model and decomposes the remaining answers. Across the 12 current models coverage is 0.53–0.75, above every final Pythia checkpoint, and it grows with size within each family (Figure 5c).

Section 6.1 also checks the ranking against the network's internals (general response, point 4). In all 15 Pythia runs the label switches where the induction-head score jumps. Ablating the heads with the highest score reverses the ranking in all 18 models ablated, whereas random ablations of the same size, with an equal or larger accuracy cost, leave it unchanged in 34 of 36 draws. The ranking therefore follows the circuit that implements the behavior.

Q3. Does (1−1/e)(1-1/e) apply to the full algorithm with rising saturation? In the revision it does. The schedule is replaced by one objective, Ψ(S)=∑i<j(1−βcij(S))\Psi(S) = \sum_{i < j}(1-\beta^{c_{ij}(S)}):

  • It is monotone submodular, because 1−βc1-\beta^{c} is concave in the modular count cc, so the (1−1/e)(1-1/e) guarantee applies to the complete greedy procedure.
  • 2k((k2)−Ψ(S))\frac{2}{k}(\binom{k}{2} - \Psi(S)) upper-bounds the identification error of SS, so greedy minimizes a certificate that is computable before any model is queried.
  • The old schedule is the β→0\beta \to 0 limit of Ψ\Psi, with ties broken at the next level.

The two procedures give the same costs (5, 7, 9, 11–12, 13–14, 16 and 18 queries for k=4,…,256k = 4, \dots, 256). The certificate guarantees 5% error with 8 to 26 queries, against 432 to 976 for random sampling.

Reviewer_s5LrOpenReview ↗

Follow-up on the Rebuttal

Thank you for the response. The revisions have addressed most of my concerns, especially the distinction between random and selected probes. The additional Pythia experiments are also helpful. I still have two questions:

  1. Does the revised lower bound hold in the noiseless setting when a single probe can distinguish two candidates?
  2. Does the 5% error guarantee refer to the average error across candidates or the worst-case error for each candidate?
AuthorsOpenReview ↗

Response to the follow-up questions

Thank you for the follow-up and for the two precise questions.

1. Yes. In the noiseless setting the lower bound holds, and a single separating query attains it.

  • Fixed design (Theorem 4). The lower bound is stated through the Bhattacharyya coefficient, max⁡⋆∈{i,j}Pr⁡⋆[error]≥14β2cij(S)\max_{\star \in \lbrace i,j \rbrace}\Pr_\star[\text{error}] \ge \frac{1}{4}\beta^{2c_{ij}(S)}, and its proof (Appendix A) holds for every ρ∈[0,12]\rho \in [0, \frac{1}{2}]. At ρ=0\rho = 0 we have β=0\beta = 0, so β2cij(S)\beta^{2c_{ij}(S)} is 00 when cij(S)≥1c_{ij}(S) \ge 1 and 11 when cij(S)=0c_{ij}(S) = 0. If the design contains one query that distinguishes the two candidates, the lower bound is 00 and the upper bound ∑j≠⋆βc⋆j(S)\sum_{j \ne \star}\beta^{c_{\star j}(S)} is also 00: that single query identifies the active candidate with zero error, as in your example. If the design contains no such query, the bound gives 14\frac{1}{4}, and directly 12\frac{1}{2}, since the two candidates then give identical answers on SS. At ρ=0\rho = 0 the necessary and the sufficient conditions therefore coincide: one separating query per pair is both required and enough, which for kk binary candidates takes ⌈log⁡2k⌉\lceil \log_2 k \rceil queries, one query when k=2k = 2. Theorem 4 states this case explicitly; the logarithmic form (2) is its ρ>0\rho > 0 rearrangement.
  • Random sampling (Theorem 5). Here a separating query exists in the pool, but each random draw reaches one only with probability ΔQ\Delta_Q. For k=2k = 2 and ρ=0\rho = 0 the error is exactly 12(1−ΔQ)n\frac{1}{2}(1-\Delta_Q)^n, so n⋆=⌈log⁡(1/(2δ))/log⁡(1/(1−ΔQ))⌉n^\star = \lceil \log(1/(2\delta)) / \log(1/(1-\Delta_Q)) \rceil, and the lower bound log⁡(1/(4δ))/(2log⁡(1/(1−ΔQ)))\log(1/(4\delta)) / (2\log(1/(1-\Delta_Q))) of Theorem 5 is within a constant factor of this exact value. The ρ=0\rho = 0 curve of Figure 2 matches the exact value within one query at all 11 separations.

2. The 5% figures refer to the average error, and the same designs certify the worst case with at most two more queries. Theorems 4 and 5 bound the error of every active candidate, that is, the worst case over candidates. The certificate δ^(S)\hat{\delta}(S) of Proposition 7 (the 8 to 26 queries in our reply to Q3) and the 5% target of Figure 3 refer to the error averaged over a uniformly drawn candidate, as in the simulations, which draw the true candidate uniformly in each trial. We optimize the average because it yields the monotone submodular objective Ψ\Psi; the maximum over candidates is not submodular.

Theorem 4 bounds the error of candidate ii by ∑j≠iβcij(S)\sum_{j \ne i}\beta^{c_{ij}(S)}, so δ^max⁡(S)=max⁡i∑j≠iβcij(S)\hat\delta_{\max}(S) = \max_i \sum_{j \ne i}\beta^{c_{ij}(S)} is a worst-case certificate, again computed before any model is queried. On the greedy designs of Figure 3 it falls below 5% at 8, 12, 15, 19, 22, 25 and 27 queries for k=4,8,…,256k = 4, 8, \dots, 256, at most two more than the average certificate. A 5% error for every candidate is therefore guaranteed with at most 27 designed queries, while random sampling needs 432 to 976 queries to reach 5% average error alone.

The revised PDF now states the worst-case certificate and these numbers in Sections 5 and 6.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the revision

We thank the reviewers for careful and specific reviews. Revised passages are marked in blue in the PDF.

1. Fixed designs and random sampling are now separate theorems, each with matching upper and lower bounds (Section 4; 51Qk, s5Lr).

  • Theorem 4 (fixed design). For a fixed query set SS, plurality errs with probability at most ∑j≠⋆βc⋆j(S)\sum_{j \ne \star}\beta^{c_{\star j}(S)}, where cij(S)c_{ij}(S) counts the queries in SS that separate ii and jj, and β=2ρ(1−ρ)\beta = 2\sqrt{\rho(1-\rho)}. Every rule errs with probability at least 14β2cij(S)\frac{1}{4}\beta^{2c_{ij}(S)}. At ρ=0\rho = 0, one separating query per pair identifies exactly, as 51Qk and s5Lr point out.
  • Theorem 5 (random sampling). For queries drawn i.i.d. from QQ with separation ΔQ\Delta_Q, the cost is Θ(log⁡(k/δ)/(ΔQ(1−β)))\Theta(\log(k/\delta)/(\Delta_Q(1-\beta))). A new Fano bound on Hadamard candidates matches the upper bound in kk, δ\delta, ΔQ\Delta_Q and ρ\rho, and gives Θ(log⁡k+log⁡(k/δ)/D(ρ))\Theta(\log k + \log(k/\delta)/D(\rho)) for fixed designs, so the log⁡k\log k factor is necessary in both regimes.
  • Consequence. A designed separating query contributes the exponent D(ρ)=−log⁡βD(\rho) = -\log\beta, which grows without bound as the model becomes reliable, while a random query contributes at most ΔQ\Delta_Q. Design therefore removes the factor ΔQ−1\Delta_Q^{-1}, and for reliable models also the dependence on δ\delta.

2. Candidate ranking under partial coverage (Corollary 6; 51Qk, s5Lr). If the model matches candidates AA and BB with probabilities a>ba > b on separating queries and neither otherwise, the ranking fails with probability at most (1−(a−b)2)c(1-(\sqrt{a}-\sqrt{b})^2)^c, with a matching lower bound. The guarantee does not assume that the candidates exhaust the behavior. "Candidate ranking" is now the term used throughout, and coverage a+ba+b is reported for every model.

3. One design objective whose value certifies the error (Proposition 7; s5Lr). Ψ(S)=∑i<j(1−βcij(S))\Psi(S) = \sum_{i < j}(1-\beta^{c_{ij}(S)}) is monotone submodular, so the (1−1/e)(1-1/e) guarantee covers the complete greedy procedure, and 2k((k2)−Ψ(S))\frac{2}{k}(\binom{k}{2} - \Psi(S)) bounds the identification error of SS before any model is queried. The saturation schedule of the submitted version is the β→0\beta \to 0 limit of Ψ\Psi.

4. Experiments at scale (fmU7, 51Qk).

  • Simulation, k=4k = 4 to 256256. At all 44 regime settings (Δ\Delta from 0.02 to 0.95, ρ\rho up to 0.25), the measured cost lies inside the Theorem 5 window and matches the exact value up to Monte Carlo error. On Hadamard candidates it lies between the two worst-case bounds in all 18 settings. At k=256k = 256, 18 designed queries suffice where random sampling needs 912.
  • Trained networks. 960 new networks (widths 32/64/128, five separations η∈[0.02,0.4]\eta \in [0.02, 0.4]). The random-query curve matches 1−12(1−η)n1-\frac{1}{2}(1-\eta)^n within 0.014 in every cell with no fitted constant, and one designed query identifies at least 98.4% of networks in every cell.
  • Language models. 15 Pythia runs (14 new): five sizes from 160M to 2.8B, standard and deduplicated data, five PolyPythias seeds each at 160M and 410M. In every run the dominant candidate changes from bigram to induction between steps 512 and 1000. Across 132 checkpoints and models, the cost of natural queries is predicted from designed-query rates and Δ\Delta without fitting: median measured/predicted ratio 1.00, 92% within a factor of 1.5.
  • Current models. 12 current open models from Qwen3.5-0.8B to Qwen2.5-72B. All rank induction above bigram. The two candidates cover 0.53–0.75 of the answers, more than any final Pythia checkpoint (at most 0.50), coverage grows with size within each family, and certifying the ranking takes 4–9 designed queries.
  • Internal mechanism (new, Section 6.1, Figure 5d). In all 15 runs the label switches where the induction-head score jumps. Ablating the 10% of heads with the highest score reverses the certified ranking in all 18 models ablated (15 Pythia, three current). Ablating as many random heads lowers WikiText accuracy at least as much (median −2.8 vs −2.4 points) but leaves the ranking unchanged in 34 of 36 draws, and both exceptions remove the strongest previous-token head, the other half of the induction circuit. Benchmark accuracy does not distinguish the two ablations, while 22 to 62 designed queries certify the reversed ranking.

5. Motivation and terminology (fmU7). The introduction now describes three settings: shortcut audits, context versus memory in language models, and change audits after fine-tuning or quantization. The text uses "query" throughout to avoid confusion with probing classifiers, and the title will become Benchmarks Are Blind to Mechanism: How Many Queries Identify What a Network Computes? once ICLR allows title changes.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.