When a new event type has to be added to an event detector (a system that finds the words in text that signal events such as "acquired" for a merger), the usual bottleneck is finding examples to annotate. The type is rare, so randomly sampled sentences almost never contain it. Annotators then spend most of their budget saying "no." This proposal treats the job of bootstrapping a new event type as a search problem rather than a learning problem. Given a fixed number of yes/no questions to an annotator ("is arrived in this sentence an instance of Visiting?"), the goal is to find as many true triggers as possible. Those found triggers then become the few-shot training set.
The search policy we use is nonmyopic: it plans with the remaining budget in mind. Early on it spends questions on unexplored kinds of contexts. As the budget runs out it shifts automatically to harvesting the most likely positives. The policy's similarity model treats a candidate as matching a known trigger only when both the trigger word and its surrounding context match. That "both" condition is what separates sibling event types such as Arriving and Visiting. Written out explicitly, it requires pairwise interaction features whose size grows with the square of the embedding dimension. We compress these with a Fourier-domain sketch so that standard nearest-neighbour indexing still works over hundreds of thousands of candidates. The claim to be tested is simple. At equal annotation budget, this policy finds more positives than greedy or diversity-based selection, and the detector trained on what it finds is better.
Core Claim
Nonmyopic active search has been shown to beat greedy discovery of rare targets in citation graphs and drug screening. Efficient Nonmyopic Active Search introduces ENS, short for Efficient Nonmyopic Search. ENS scores a candidate by its immediate chance of being a target plus the number of targets expected if all remaining budget were spent at once after observing it. On CiteSeerx, with 500 queries, it finds 189 targets against 155 for two-step lookahead. The method has never been applied to language, and its documented weakness is its dependence on a well-calibrated similarity model. Low-resource event detection is a natural home for it. False negatives, meaning triggers missed entirely, account for over 50% of errors for some models on MAVEN (MAVEN). Few-shot detectors are only as good as the handful of examples someone managed to find.
We claim three things. First, ENS-style search over candidate trigger tokens finds more positives per annotator question than greedy ranking by a zero-shot detector. Second, it does so only when its similarity model uses a product (trigger AND context) kernel rather than a sum. Third, the extra positives turn into higher downstream F1, and are not just near-duplicates.
Research Program
The candidate pool is every content-word token in an unlabeled corpus, each paired with its sentence. A query reveals a binary label for one token in context. With current data $D$ and remaining budget $r$, the ENS score of candidate $x$ is
$$u(x) = p(x \mid D) + \mathbb{E}_{y \sim p(\cdot \mid x, D)}\Big[\textstyle\sum_{x' \in \text{top}_{r-1}} p(x' \mid D \cup \{(x,y)\})\Big].$$
Here $p(x \mid D)$ is the model's probability that $x$ is a trigger of the target type, and the sum runs over the $r-1$ most probable remaining candidates after hypothetically observing label $y$ for $x$. When $r$ is large the second term rewards questions that reshape the posterior. When $r=1$ the score collapses to greedy. We reuse the pruning bound from the ENS paper, which skipped 93% of points in virtual screening. For batches of questions sent to annotators at once, we reuse the pessimistic fictional oracle from Efficient nonmyopic batch active search. It assumes already-picked batch items are negative, which pushes the batch away from near-duplicate sentences.
The posterior is a k-nearest-neighbour model, as in ENS. We make two changes, each aimed at the calibration weakness. The first change is the prior. In place of a uniform prior, each candidate's prior is the score of a zero-shot detector. We will try two: P4E's cloze probability from PILED, and a definition-following LLaMA-2-7B tuned as in Improving Event Definition Following For Zero-Shot Event Detection. The prior is temperature-calibrated on event types disjoint from the target. This is meant to remove the "slow start" ENS shows on CiteSeerx, where it trails greedy for roughly the first 80 steps. In event bootstrapping, budgets of 25 to 100 questions are realistic, so a slow start that long would be fatal.
The second change is the similarity. Let $t \in \mathbb{R}^d$ be the contextual embedding of the trigger token and $c \in \mathbb{R}^d$ a pooled embedding of its sentence. Cosine similarity on the concatenation $[t;c]$ adds the two similarities. A sentence with the right word but the wrong situation therefore still scores about half, which is exactly the sibling-confusion failure. We instead use the product kernel
$$k\big((t,c),(t',c')\big) = \langle t,t'\rangle\,\langle c,c'\rangle = \langle t \otimes c,\; t' \otimes c'\rangle.$$
This kernel is high only when both parts match. Evaluating it pairwise is cheap, but building a k-NN graph over $n \approx 10^5$–$10^6$ candidates by brute force costs $O(n^2 d)$. Approximate nearest-neighbour indexes need explicit vectors, and $t \otimes c$ has $d^2$ entries, about 590k at $d=768$ and 16.7M at $d=4096$. Here the quadratic feature trap is real.
We compress $t \otimes c$ to $m$ dimensions with count sketches combined by FFT-based circular convolution. This is a standard construction. Its use of the Fourier identity, which turns an $O(d^2)$ pairwise sum into an $O(d \log d)$ frequency-domain product, is the same one Learning Decorrelated Representations Efficiently Using Fast Fourier Transform uses to avoid materializing $d \times d$ covariance matrices. That paper supplies the trick; we apply it to kernel features rather than to a training loss. Fast approximation of matrix coherence and statistical leverage constrains the design: random projections distort inner products on sparse or skewed vectors, so we will measure kernel distortion as a function of $m$ rather than assume it is small.
We adopt ENS rather than a reinforcement-learned policy. Budget-Aware Feature Selection for Reinforcement Learning passes the budget into a constrained-MDP policy, which satisfies budgets only in expectation and was shown only at $d=16$. ENS has no training and obeys the budget exactly. Deep Anomaly Detection under Labeling Budget Constraints is the closest budget-limited rare-event work. Its SOEL method queries by k-means++ dispersion, which aims at covering normal data. Our objective instead counts positives found and plans over the remaining horizon.
Baselines
The naive reference is random querying from the candidate pool. Its expected yield equals the type's base rate times the budget, which shows how much any policy gains at all.
The strongest competitor is greedy ranking by the calibrated zero-shot prior: annotate the top-$B$ candidates under the DivED-tuned LLaMA or under P4E's cloze score. It is the strongest because it already encodes the event definition, and with tiny budgets a good prior may be all that matters. No reported result found on Lacuna for greedy zero-shot-ranked annotation on MAVEN. The nearest reported figure is the definition-tuned LLaMA-2-7B's zero-shot Trigger ID F1 of 34.2 on ACE versus 15.9 for GPT-3.5 (Improving Event Definition Following For Zero-Shot Event Detection). That suggests its top-ranked candidates are informative but far from clean.
A second competitor is greedy one-step search on the same k-NN posterior with the same prior and kernel. This isolates the value of nonmyopic planning itself. A third is SOEL-style k-means++ diverse querying (Deep Anomaly Detection under Labeling Budget Constraints), which reports a 6-point AUC gain over eight baselines at 20 queries on image benchmarks. A fourth is entropy-based uncertainty sampling on the detector, the default in active learning.
Two ablations isolate our ingredients. ENS with the additive concatenation kernel tests whether the product kernel matters. ENS with a uniform prior tests whether the informed prior removes the slow start. A third ablation replaces the sketch with the exact product kernel on a subsampled pool small enough to brute-force, which measures what the sketch costs.
All methods share the encoder, the candidate pool, the oracle, the batch size, and the budget. Each method gets the same hyperparameter-search budget (k, temperature, sketch size) on development event types disjoint from the test types. Downstream detectors are trained identically. For the ceiling we cite P4E's reported 69.51 F1 on MAVEN and 85.50 F1 on FewEvent 10-shot (PILED).
"Beating" a competitor has two parts. The first is more positives found at the median budget, with non-overlapping 95% bootstrap intervals across held-out types. The second is equal or higher downstream F1 at the same budget. A policy that wins on positives found but loses on F1 does not count as a win.
Why not just…?
Why not just annotate the top-scoring candidates from a zero-shot detector? This is the real threat. With small budgets and a strong prior, greedy may match ENS, because ENS's advantage on CiteSeerx came from mid-to-late budget stages. The evidence against greedy is indirect. Cost Effective Active Search. reports 56–73% lower discovery cost than greedy for its ENCES policy on drug data, and attributes greedy's "staircase" behaviour to exhausting one cluster and then wandering. We expect the same pattern when a zero-shot detector's top hits are all one surface form ("arrived at"). The experiment sweeps $B$ from 25 to 500 and reports the crossover budget. If greedy wins at every budget below 100, we will say nonmyopic search only pays for larger annotation efforts.
Why not just use standard uncertainty-based active learning? Uncertainty sampling targets the classifier's decision boundary. For a type with a base rate well under 1%, the uncertain region is dominated by negatives. Online Feedback Efficient Active Target Discovery in Partially Observable Environments finds that entropy-driven search spends its budget on empty regions before localizing targets. Our downstream-F1 comparison checks directly whether its better-placed negatives compensate for finding fewer positives.
Why not just use cosine similarity on concatenated embeddings and skip the quadratic features? If the additive kernel ties the product kernel, the sketching machinery is unnecessary and we will drop it. The motivation is the sibling-confusion failure mode of fine-grained ontologies like MAVEN's 168 types. To test it, we report results separately for types that share frequent trigger lemmas with a sibling, where the AND kernel should matter, and for types that do not.
Why not just have a large language model pseudo-label everything? GPT-3.5 reaches only 15.9 Trigger ID F1 zero-shot on ACE (Improving Event Definition Following For Zero-Shot Event Detection), so its labels would be mostly wrong. We include a run that trains P4E on the LLM's top pseudo-labels at matched volume as a reference.
Proposed Experiments
The main testbed is MAVEN in a leave-type-out simulation. For each held-out type, the pool is the training split's candidate tokens, gold labels act as the oracle, and the type starts with zero to two seed triggers. We focus on long-tail types, where search matters most. ACE 2005 (33 types) and FewEvent serve as smaller replications.
The primary metric is positives found as a function of budget. A secondary metric follows the cost-effective search setting: annotator questions needed to reach 10 positives, matching the 10-shot regime. The downstream metric is the held-out type's trigger F1 when P4E is trained on the found positives plus the queried negatives. Diagnostics are the sketch's kernel distortion versus $m$, the distinct trigger lemmas among found positives (a check against near-duplicate harvesting), and pessimistic versus most-likely oracles in batch mode.
Two results decide the proposal. The first is whether ENS with an informed prior beats calibrated greedy at budgets of 50–200 on long-tail MAVEN types, on both positives found and F1. The second is whether that margin disappears when the product kernel is swapped for the additive one. If neither holds, budget-aware search does not earn its complexity for event bootstrapping. That is still a useful negative result, given how often the false-negative bottleneck is blamed on models rather than on the examples they were given.
References
- Efficient Nonmyopic Active Search
- MAVEN: A Massive General Domain Event Detection Dataset
- Efficient nonmyopic batch active search
- PILED: An Identify-and-Localize Framework for Few-Shot Event Detection
- Improving Event Definition Following For Zero-Shot Event Detection
- Learning Decorrelated Representations Efficiently Using Fast Fourier Transform
- Fast approximation of matrix coherence and statistical leverage
- Budget-Aware Feature Selection for Reinforcement Learning
- Deep Anomaly Detection under Labeling Budget Constraints
- Cost Effective Active Search.
- Online Feedback Efficient Active Target Discovery in Partially Observable Environments