Source-linked AI summary
Identifying Intelligent Processes via Online Sequential Testing
Aritra Das, Debayan Gupta
TL;DR
Identifying a black-box language model requires more than choosing among fixed sensing actions: evaluators must also decide which probes to build. The paper formalizes outer probe design and inner sequential identification, reducing fixed-margin design to weighted set cover and relating pairwise separation to an upper bound on inner value.
Problem
Classical active sequential testing assumes sensing actions and observation laws are fixed, while LLM identification also requires choosing which probes to build.
Source: §1 · p. 1Method
The paper separates outer probe design from inner identification, characterizes fixed-margin designs by weighted set cover, and gives a one-shot guarantee for empirical cover sets.
Source: §3.3 · p. 6, §4.2 · p. 8Results
An η-separating design yields an upper bound on inner identification value for every prior and error target, and the fixed-margin design problem reduces exactly to weighted set cover.
Source: §3.2 · p. 5, §3.3 · p. 6Takeaways & Limitations
Pairwise separation can guide probe design by guaranteeing an inner sample-complexity bound, without determining the exact sequential value.
Source: §3.2 · pp. 5–6The margin Δ(S) bounds but does not determine inner value, which also depends on the prior, full response laws, asymmetric KL divergences, and adaptive combinations of evaluations.
Source: §3.2 · p. 6
Abstract
from arXiv · showhide
Active sequential hypothesis testing studies how to identify an unknown hypothesis with a given set of sensing actions. We study this in the setting of identifying large language models (LLMs), \textit{i.e.}, if a user is conversing with an LLM drawn from a known set of models, how can they identify which one is in use? Here, the available sensing actions (evaluations) are themselves a design choice: an evaluator must first decide which environments and prompt families to construct, and only then decide how to use them sequentially. We formalize these two levels as an outer probe-design problem and an inner identification problem. Simply put, the outer stage selects a set of probes to be sent to the entire set of models, creating a kind of fingerprint dataset. This is followed by the inner stage, which sequentially sends a budget-minimizing set of those probes to identify the model in use. For the outer problem, we show that selecting which evaluations to construct at minimum cost, so that every pair of candidates is distinguished, is exactly a weighted set cover problem. Since the response distributions of the candidate models are not known exactly but only through calibration samples, we give a one-shot procedure that estimates the cover instance from these samples. For the inner problem, we bound the number of evaluations needed to identify the unknown model in terms of how well the available evaluations distinguish each pair of candidates.
1 Introduction
Active sequential testing selects evaluations and a stopping rule when sensing actions and observation laws are fixed in advance. TIPTOE adds the prior choice of which probes to build, then studies sequential identification using the resulting probe set.
1 Introduction
- Classical active sequential testing chooses actions, a stopping time, and a final declaration when sensing actions and observation laws are fixed in advance [5].In the LLM setting, an evaluator can choose prompts or interactive tasks, observe responses, and adapt later evaluations to the data collected.Source: §1 · p. 1
- Probe construction is a separate decision because building an environment or curating a prompt family can incur a one-time cost even if the probe is rarely used.Choosing probes changes the available action set, so it cannot be represented merely by a policy over existing actions.Source: §1 · p. 1
- TIPTOE separates probe design from inner sequential identification, with pairwise separation margins used to guarantee inner sample complexity.Source: §1 · p. 1
2 Sequential identification under a fixed design
The fixed-design formulation specifies candidate models, evaluations, and their response laws, then defines sequential identification using only the available evaluations. It treats the greedy information-gain rule as one admissible policy, not as an optimality claim.
2.1 Experiment and posterior
- Each evaluation has a model-specific response law, and responses may be completions, interaction trajectories, or other measurable records; evaluations start from fresh model contexts.The unknown model index is drawn from a prior over the finite candidate set.Source: §2.1 · p. 2
- One-step information gain is the mutual information between model identity and the next response, conditional on current belief and the chosen evaluation.Source: §2.1 · p. 3
2.2 The inner identification problem
- A fixed-design admissible procedure uses a policy over available evaluations, an almost-surely finite stopping time, and a terminal model estimate; the value is the constrained primal test [5, Sections 2.1 and 5.3].An empty feasible set has value +∞.Source: §2.2 · p. 3
- Declaring a model when its posterior exceeds the confidence threshold gives an error bound through the conditional maximum-posterior error, 1−max_i b_tau(i).Source: §2.2 · p. 3
- The myopic information-gain rule is one admissible inner policy, and no optimality claim for it is used.It is well defined for finite evaluation sets after tie-breaking is fixed.Source: §2.2 · p. 3
3 Outer probe design
TIPTOE treats probe construction as a costed outer design problem, then uses pairwise separation to bound the inner identification effort. It reduces fixed-margin probe selection to weighted set cover.
3.1 A finite dictionary of modules
- Each probe module has a positive one-time construction cost and makes a finite set of evaluations available; overlapping modules pay separate costs but duplicate evaluations appear only once.Construction cost is paid before testing the unknown model.Source: §3.1 · p. 4
3.2 Finite response summaries and pairwise separation
- Mapping large response spaces to K categories enables frequency-based calibration, but summarized distributions can erase differences present in full response laws.Categories can represent outcomes such as success or failure, score ranges, or error types.Source: §3.2 · p. 4
- Pairwise ℓ1 separation supports binary tests combined in a tournament, yielding an upper bound on inner identification value; the margin does not determine that value exactly.The exact sequential value also depends on the prior, full response laws, asymmetric KL divergences, and adaptive combinations of evaluations.Source: §3.2 · pp. 5–6
3.3 The fixed-margin design problem
- A fixed-margin design is η-separating exactly when its selected modules cover every candidate pair, reducing minimum-cost probe selection to weighted set cover.The budgeted margin can be recovered by sorting the finite set of pairwise module-separation values and testing cover feasibility.Source: §3.3 · pp. 6–7
4 Learning the cover instance from calibration samples
The calibration procedure estimates the cover instance from independent samples drawn for each candidate and evaluation. A two-margin guarantee controls the empirical cover, including what infeasibility implies.
4 Learning the cover instance from calibration samples
- Calibration assumes independent sample access for every candidate–evaluation pair, with samples drawn from known candidate models separately from later interaction with the unknown model.A sample is reused in pairwise scores involving its candidate and in modules containing its evaluation.Source: §4 · p. 7
4.1 Two margins
- Two margins allow finite-sample decisions despite scores arbitrarily close to a single threshold; pairs in [η−, η+) may be classified either way.The calibration failure probability β is separate from the online identification error δ.Source: §4.1 · p. 7
4.2 Uniform one-shot calibration
- With probability at least 1−β, the empirical sets satisfy the two-margin condition, and empirical-cover infeasibility rules out any η+-separating design.The infeasibility conclusion follows because a pair missing from every empirical cover set is also absent from every cover set at margin η+.Source: §4.2 · pp. 8–9