Exploration Efficiency Coverage Metrics

This note records an initial planning discussion about evaluating whether a router-generator factorization can make test-time or RL exploration more sample-efficient by deliberately covering strategy space rather than repeatedly sampling from the same high-probability strategies.

Related notes:

• Exploration efficiency methods
• Abstract strategy vs solution
• Exploration efficiency gains
• Iterative self-improvement via analogical exploration

Core Setup

For an input $x$, let $s_x(y)$ be an evaluation-time strategy label for an observed sample $y$. In synthetic settings this should be the ground-truth strategy label. In LLM-scale settings it should be an independent labeling mechanism, such as a rubric, classifier, or human annotation, rather than the learned latent variable itself.

An adaptive exploration policy $A$ samples a sequence $y_1,\ldots,y_K$, where each $y_i$ may depend on $x$ and previous samples $y_{<i}$. Define $s_i = s_x(y_i)$ and $S_i = \{s_1,\ldots,s_i\}$. The evaluation goal is to measure how quickly $S_i$ grows as the sample budget increases.

Synthetic-Sequences Strategy Attribution

In path:experiments/synthetic_sequences/tasks/, generated responses are parsed and validated by the task implementation. For a generated y_text, the evaluation should call task.validate_y_text(x, y_text) and use ValidationResult.strategy_matches as the strategy evidence for that sample.

Coverage is set-valued in this setting. If one generated trace matches multiple strategies, all matched strategies count as covered for that input. The update rule is

$$S_t = S_{t-1} \cup M_t,$$

where $M_t$ is the set of strategy IDs in strategy_matches for sample $t$. Parse failures, structurally invalid generations, and off-strategy generations add no strategies because their match set is absent or empty.

For the first synthetic-sequences evaluation, the denominator should be the task's declared strategy set:

$$M_x = |\mathrm{task.strategies()}|.$$

This differs from using training-row strategy labels. Training data rows have labels because they were generated from a known strategy, but generated model responses should be attributed by parsing and validating the generated trace.

Metric Candidates

The marginal novelty curve measures the probability that sample $i$ discovers a strategy not seen in earlier samples:

$$N_A(i) = \Pr[s_i \notin S_{i-1}].$$

The expected coverage curve measures the expected fraction of available strategies discovered by budget $k$:

$$C_A(k) = \mathbb{E}\left[\frac{|S_k|}{M_x}\right],$$

where $M_x$ is the number of valid strategies for input $x$. This is the strongest candidate for the main visualization because it is direct, monotone, and comparable across methods.

The full-coverage curve measures the probability of having seen every strategy by budget $k$:

$$F_A(k) = \Pr[|S_k| = M_x].$$

This is clean when $M_x$ is small, but it may be too harsh when there are many strategies or when rare strategies are poorly defined.

The time-to-coverage metric reports the number of samples needed to reach a coverage threshold $\tau$:

$$T_A(\tau) = \min \left\{k : \frac{|S_k|}{M_x} \ge \tau \right\}.$$

Useful thresholds are likely $\tau \in \{0.5, 0.8, 1.0\}$, summarized by mean, median, and distribution across inputs.

For a fixed budget $K$, a compact aggregate is the coverage area under the curve:

$$\mathrm{AUC}_A(K) = \frac{1}{K} \sum_{k=1}^K C_A(k).$$

One can normalize against iid base sampling and an oracle no-repeat strategy sampler:

$$\mathrm{Gain}_A(K) = \frac{\mathrm{AUC}_A(K) - \mathrm{AUC}_{\mathrm{iid}}(K)}{\mathrm{AUC}_{\mathrm{oracle}}(K) - \mathrm{AUC}_{\mathrm{iid}}(K)}.$$

This normalized gain asks how much of the available improvement over iid sampling has been recovered.

Iid Baseline

Let the base model induce strategy probabilities $p_x(s) = \Pr_{y \sim p(\cdot|x)}[s_x(y)=s]$. Under iid base sampling, the expected number of discovered strategies after $k$ samples is

$$\mathbb{E}[|S_k|] = \sum_s \left(1 - (1 - p_x(s))^k\right).$$

The iid marginal novelty curve is

$$N_{\mathrm{iid}}(i) = \sum_s p_x(s)(1 - p_x(s))^{i-1}.$$

This makes the evaluation a strategy-space coupon-collector problem. Uniform strategy distributions waste samples through repeats once common strategies have already appeared; imbalanced strategy distributions have long tails dominated by rare strategies.

Visualization Candidates

The main figure should plot expected coverage $C_A(k)$ against sample budget $k$, with iid base sampling, oracle no-repeat sampling, and latent-exploration methods on the same axes.

A second plot should show the marginal novelty curve $N_A(i)$. This directly visualizes whether the next sample is still likely to reveal a new strategy.

A distributional summary should show $T_A(0.8)$ or $T_A(1.0)$ across inputs, using a violin, box, or survival-style plot.

A qualitative strategy barcode heatmap could make redundancy visible: rows are inputs, columns are sample index, and colors are strategy labels, with a marker for first appearances.

Guardrails

Report valid or correct strategy coverage alongside raw strategy coverage. A method should not look good because it generates many invalid or low-quality modes.

Separate latent coverage from strategy coverage. Latent-space dispersion is a diagnostic of the method, while externally labeled strategy coverage is the primary evaluation target.

Track whether gains come from avoiding repeats among common strategies or from finding genuinely rare strategies. These are different operational regimes and may favor different exploration policies.

The initial experimental ladder should be: oracle-labeled synthetic setting, learned latent factorization on synthetic data, then LLM-scale strategy labeling with downstream utility such as best-of-$k$ correctness.