Active Hypothesis Testing under Computational Budgets with Applications to GWAS and LLM

1. Problem Formulation

The paper addresses the challenge of performing large-scale multiple hypothesis testing when computing exact test statistics (p-values or e-values) is computationally expensive or resource-intensive.

• Context: In fields like genomics (GWAS) or clinical prediction using Large Language Models (LLMs), researchers often face a scenario where they have $N$ hypotheses but a strict global computational budget $n_b$ (where $n_b \ll N$).
• Inputs: For each hypothesis $i$, there are two types of statistics:
  1. Exact Statistic ($X_i$): A "gold-standard" statistic (e.g., exact p-value $P_i$ or e-value $E_i$) that is valid for inference but costly to compute.
  2. Auxiliary Statistic ($X^a_i$): An inexpensive, readily available statistic (e.g., model predictions, noisy measurements, or proxy p-values) that is informative about the exact statistic but not valid for formal inference on its own.
• Objective: Construct a valid test statistic for every hypothesis such that the total number of expensive computations strictly adheres to the pre-specified budget $n_b$, while maximizing statistical power (True Positive Rate).

2. Methodology

The authors propose a unified framework for Active Hypothesis Testing that integrates budget constraints directly into the inferential process.

A. Active Statistic Construction

The core innovation is the construction of an "active" statistic that probabilistically decides whether to compute the exact statistic or use a transformed auxiliary statistic.

1. Control Function ($h$): A data-adaptive function maps the auxiliary statistic $X^a$ to a probability $h(X^a) \in [0, 1]$. This determines the likelihood of computing the expensive exact statistic.
2. Randomization: A uniform random variable $U \sim \text{Uniform}(0, 1)$ is used to make the decision.
   • If $U < h(X^a)$: Compute the exact statistic $X$.
   • If $U \geq h(X^a)$: Do not compute $X$; instead, output a transformed version of the auxiliary statistic.
3. Validity Guarantees:
   • Active e-values: The authors derive conditions for functions $a(\cdot)$ and $b(\cdot)$ such that the resulting statistic $E_{\text{active}}$ satisfies $\mathbb{E}[E_{\text{active}}] \leq 1$. They prove that the optimal construction involves a decomposition parameter $\beta \in [0, 1]$:
     $$E_{\text{active}} = \begin{cases} \frac{\beta}{1-h(E^a)} & \text{if } U \geq h(E^a) \\ \frac{1-\beta}{h(E^a)} \cdot E & \text{if } U < h(E^a) \end{cases}$$
   • Active p-values: Similarly, they construct valid p-values satisfying the super-uniformity property ($P(P_{\text{active}} \leq s) \leq s$). They provide distinct optimal constructions for:
     • Independence: When $P$ and $P^a$ are independent.
     • General Dependence: A more conservative construction using $\sup h(x)$ to guarantee validity under arbitrary dependence structures.

B. Budget-Constrained Allocation

To ensure the total number of queries exactly equals $n_b$ (rather than being a random variable as in previous independent-query methods), the authors introduce a Normalized Allocation Scheme:

1. Utility Functions: Define a utility $u_i(X^a_i)$ for each hypothesis based on the strength of the auxiliary signal (e.g., $u(x) = x$ for direct signals, $u(x) = 1/(x+\epsilon)$ for inverse signals).
2. Control Probabilities: The probability of querying hypothesis $i$ is set to:
   $$h_i(X^a) = n_b \cdot \frac{u_i(X^a_i)}{\sum_{j=1}^N u_j(X^a_j)}$$
   This ensures $\sum h_i = n_b$.
3. Dependent Sampling: To enforce the exact sum constraint $\sum C_i = n_b$ (where $C_i$ is the binary query indicator), the authors use a dependent sampling mechanism (Proposition 3). Instead of independent coin flips, they sample indicators based on cumulative sums of probabilities and a single uniform variable $U$, ensuring the budget is met exactly on every run.

C. Algorithm

The proposed Algorithm 1 (Budgeted Active Inference) integrates these steps:

1. Compute base utilities from auxiliary statistics.
2. Normalize utilities to get target probabilities $h_i$.
3. Apply adaptive compression (logarithmic transformation) if any $h_i > 1$.
4. Perform dependent sampling to determine which hypotheses get the exact statistic.
5. Construct the final active statistics for all $N$ hypotheses.

3. Key Contributions

1. Theoretical Framework: Established a general framework for active hypothesis testing that guarantees exact budget adherence while maintaining statistical validity for both p-values and e-values.
2. Optimality and Admissibility:
   • Proved that the proposed constructions are optimal (point-wise largest e-values, smallest p-values) for a fixed control function.
   • Established admissibility results: No single control function or hyperparameter $\beta$ universally dominates all others; the optimal choice depends on the data distribution.
3. Dependence Handling: Provided specific, valid constructions for both independent and general dependent settings, addressing a gap in existing literature where many methods assume independence.
4. Comparison with Prior Work: Demonstrated that the recent method by Xu et al. (2025b) is a special case of their framework. The authors' method provides point-wise dominant statistics (higher power) for e-values and strictly more powerful p-values under independence, while also enforcing strict budget constraints (which Xu et al. do not).
5. Real-World Applications: Validated the framework on two distinct domains:
   • GWAS: Using hypertension summary statistics as a cheap proxy to prioritize myocardial infarction (MI) SNP discovery.
   • LLM-based Clinical Prediction: Using an LLM to impute missing expensive clinical features (heart failure diagnosis) to guide hypothesis testing on patient mortality.

4. Results

• Simulations:

  • The proposed method (Active-Default) consistently outperformed baselines (Random selection, Xu et al.'s method, and Active-Xu) in terms of Efficiency (True Positives per Query).
  • While unconstrained methods (ALL, Xu) achieved higher absolute power, they violated the budget constraint significantly (often exceeding the budget by 4-8x).
  • Active-Default strictly adhered to the budget $n_b$ in all simulations and achieved the highest efficiency, particularly as the proportion of true signals increased.
  • The method remained robust even when the auxiliary signal was noisy or correlated.

• Real-Data Applications:

  • GWAS: The framework successfully identified known cardiovascular risk loci (e.g., rs1333047 in the 9p21.3 locus) with high efficiency, demonstrating that public summary statistics can effectively guide expensive genomic analysis.
  • LLM Clinical Prediction: Using an LLM to impute missing data allowed the framework to prioritize high-risk patients for expensive confirmatory tests. The method controlled the False Discovery Rate (FDR) at the target level (0.1) while maximizing the number of true positive discoveries per query.

5. Significance

This work bridges the gap between statistical inference and computational resource management.

• Practical Impact: It provides a principled solution for researchers working with limited computational resources (e.g., expensive simulations, destructive experiments, or large-scale LLM inference).
• Theoretical Rigor: Unlike heuristic approaches, the framework offers rigorous guarantees on FDR control and exact budget adherence, making it suitable for high-stakes scientific discovery.
• Flexibility: The framework is model-free regarding the auxiliary statistics, allowing it to integrate diverse data sources, including black-box AI models, without requiring knowledge of their internal generative processes.
• Scalability: By enabling the prioritization of hypotheses based on cheap proxies, the method makes large-scale hypothesis testing feasible in scenarios where full enumeration is impossible.