Vote-k: a complete guide

Few-shot prompting lives or dies on which examples you put in the prompt. But before you can retrieve a good example, someone has to label one, and labeling budget is the real bottleneck. Vote-k attacks that bottleneck: it picks a small, diverse, representative set of unlabeled examples to annotate once, so every later prompt retrieves from a pool that actually covers your task. In the original paper it beat random example selection by 12.9% and 11.4% relative, at annotation budgets of just 18 and 100 examples (Su et al., 2022).

See it work

Say you're building a sentiment classifier with in-context learning. You have 10,000 unlabeled reviews and budget to hand-label only 18 of them. The 18 you label become your retrieval pool: at test time you grab the nearest few and drop them in the prompt.

Label the wrong 18 and your pool has blind spots. Here's the contrast.

TASK: 5-way sentiment, label 18 reviews to seed an in-context pool.

RANDOM SELECTION
  18 reviews drawn uniformly at random.
  → 11 are "positive", 4 "neutral", 3 the rest.
  → almost no "very negative" or sarcastic examples.
  → test-time retrieval keeps pulling near-duplicate positives.
  Accuracy on held-out test set: baseline.

VOTE-K SELECTION
  Embed all 10,000 reviews, build a similarity graph.
  Vote for examples that cover dense regions WITHOUT piling
  onto each other, so the 18 span the space:
  → short raves, long rants, sarcasm, mixed, terse "meh".
  → test-time retrieval finds a genuinely similar neighbor
    for far more test inputs.
  Accuracy: +12.9% relative over random at this budget.

Same model, same budget, same retriever. The only thing that changed is which 18 examples got labeled.

The mental model

Think of it like assembling a focus group. You don't want 18 clones of the same enthusiastic customer; you want 18 people who, between them, represent everyone who'll ever walk through the door. Each person should stand for a cluster of real customers (representative), and no two should be near-duplicates (diverse).

Vote-k labels the examples that vote for each other the most, while quietly docking the score of anyone who sits too close to someone you already picked.

How it works

Vote-k is a two-step framework. Step one, selective annotation, runs once, offline, before you've seen a single test input: it chooses which unlabeled examples to send to a human. Step two, prompt retrieval, runs at inference: for each test input it pulls the most similar annotated examples into the prompt by cosine similarity.

The clever part is step one. It's an unsupervised, graph-based method that runs in two phases.

1. Embed everything. Encode every unlabeled example with Sentence-BERT (the paper uses all-mpnet-base-v2).
2. Build a graph. Make a directed graph where each example points to its k nearest neighbors by cosine similarity. Default k is 150.
3. Vote (phase 1). Score each unselected node by how many neighbors vote for it, discounting votes near already-picked nodes. Greedily take the highest scorer, repeat until you've chosen M/10 examples (M is your total budget).
4. Label the seeds. A human annotates those M/10 examples.
5. Score confidence (phase 2). Run the model with the seed pool as in-context examples and predict on the remaining unlabeled data. Rank by the model's confidence.
6. Fill the rest. Split the remainder into M equal-size confidence buckets, throw away the easiest (most confident) bucket, and pick diverse examples from the harder ones until you hit M total.

The vote score is the whole engine. For a candidate node u, you sum a contribution from each of its still-unselected neighbors v, and each contribution decays as v's neighborhood fills up with already-picked nodes:

# rho = 10 (decay), k = 150 (graph degree)
def vote_score(u, graph, selected, rho=10):
    score = 0.0
    for v in graph.neighbors(u):          # u's k nearest neighbors
        if v in selected:
            continue
        c = count_selected_neighbors(v, graph, selected)
        score += rho ** (-c)              # vote worth less near picks
    return score

That rho ** (-c) is the diversity discount. The first time a region gets a pick, nearby votes count fully; each extra pick in that region makes new votes there worth a tenth as much. So the algorithm spreads out instead of clustering.

Why it works

Where it shines

Vote-k pays off whenever labeling is expensive and you'll reuse the labeled pool across many queries. The paper tested it on 10 datasets spanning four task families, and it beat random selection on all of them.

• Classification — MRPC, SST-5, MNLI, DBpedia, RTE.
• Commonsense / multiple choice — HellaSwag.
• Dialogue — MWoZ (task-oriented dialogue state tracking).
• Generation — GeoQuery (text-to-code), Natural Questions (open-domain QA), XSUM (summarization).

At a budget of 100 annotations, absolute gains over random ranged from 1.9 to 9.9 points across these tasks. The headline relative gains were 12.9% at budget 18 and 11.4% at budget 100. The bigger result: vote-k matched supervised fine-tuning while using 10 to 100 times less annotation, because it labels a tiny, well-chosen pool instead of a large training set.

When to use it (and when not)

Reach for vote-k when:

• Labeling needs a human or an expert, so every annotation has real cost.
• You'll serve many test inputs from one fixed, annotated pool.
• Your unlabeled pool is diverse and you can't eyeball which examples cover it.

Skip it when:

• You already have a big labeled set, just retrieve similar examples directly.
• It's a one-off prompt, hand-picking a few good examples is faster.
• Your pool is tiny or homogeneous, random selection won't lose much.

On cost: phase 1 is cheap (embeddings plus graph math), but phase 2 runs the model over your whole unlabeled pool to score confidence, which on a large pool is the dominant expense. That's the one-time setup cost. Per-request cost at inference is just normal retrieval, no different from any few-shot prompt.

Model fit: vote-k is model-agnostic for selection but assumes you have a capable in-context learner for phase 2 and for serving. Stronger models make the confidence signal more meaningful. The selection itself works with any sentence embedder.

Variants and alternatives

Implementation

The workflow is short because the cost lives in compute and human labeling, not code.

1. Collect your unlabeled pool and set a budget M.
2. Embed every example with a sentence encoder (all-mpnet-base-v2 is the paper's choice).
3. Build the directed kNN graph (k = 150) on cosine similarity.
4. Run phase 1 voting to get M/10 seeds; send them to annotators.
5. Run phase 2: predict on the rest with the seed pool, bucket by confidence, fill to M.
6. Serve: at test time, retrieve the nearest annotated examples by cosine similarity and build the prompt.

At inference the prompt is just ordinary few-shot, the pool is what changed:

[Retrieved example 1]  Input: ...  Label: ...
[Retrieved example 2]  Input: ...  Label: ...
[Retrieved example 3]  Input: ...  Label: ...

Input: <test input>
Label:

Configuration

Do and don't

• Do reuse the annotated pool across every query, that's where the budget pays off.
• Do start with fast vote-k if a full model pass over the pool is too slow.
• Don't expect relevance to your niche, vote-k spreads across the whole pool.
• Don't re-embed with a mismatched encoder at serve time, keep selection and retrieval embeddings consistent.

Debugging

• Pool misses a region → your embedder may not separate that region; try a stronger encoder before raising the budget.
• Phase 2 too slow → drop to fast vote-k or subsample the pool before scoring confidence.
• Gains look flat vs random → pool is likely homogeneous; vote-k helps most on diverse data.
• Retrieval pulls irrelevant examples → check that test inputs actually overlap the pool's distribution.

Proving it works

Hold out a labeled test set and compare apples to apples: same model, same retriever, same budget, only the selection method changes.

def eval_selection(select_fn, pool, budget, test_set, model):
    chosen = select_fn(pool, budget)        # vote_k or random
    annotate(chosen)                         # attach gold labels
    correct = 0
    for x in test_set:
        examples = retrieve_nearest(x, chosen, n=3)
        pred = model.predict(x, examples)
        correct += (pred == x.gold)
    return correct / len(test_set)

# run with select_fn = random_select and = vote_k, compare

If vote-k doesn't beat random by a clear margin, your pool probably isn't diverse enough to matter.

Limitations

• Diversity over relevance. As noted, it favors representative breadth, which can leave task-critical regions thin.
• Setup compute. The phase-2 confidence pass scales with pool size and can dominate cost on large pools.
• Still needs humans. It cuts how many labels you need, not the need for accurate labels.
• Embedder-dependent. Selection quality is only as good as the embedding space; a weak encoder gives a misleading graph.

Ecosystem

Vote-k sits in the selective-annotation corner of in-context learning. Its closest relatives:

• Fast vote-k — the same graph voting without the confidence phase; near-identical quality at roughly a tenth of the cost, and the default people reach for in practice.
• Similarity-based retrieval (KNN prompting) — the test-time half of the framework; vote-k feeds it a better pool.
• FastGAS — later graph-based annotation-selection work that pushes efficiency further.

A natural hybrid: use vote-k (or fast vote-k) to build the pool, then layer your favorite retrieval and ordering tricks on top at inference. Selection and retrieval are orthogonal, so improvements compound.

Future directions

Selective annotation is a young area. Open threads include cheaper confidence estimation so phase 2 scales to web-size pools, relevance-aware voting that blends task signal with diversity, and selection methods that adapt as the test distribution shifts. The core lesson already holds: with in-context learning, which examples you label can matter as much as how many.

Summary

• Vote-k is a two-step framework: select a diverse, representative pool to annotate offline, then retrieve similar examples from it at test time.
• Selection is unsupervised and graph-based: embed with Sentence-BERT, build a k=150 nearest-neighbor graph, and vote with a rho=10 diversity discount.
• Phase 1 picks M/10 seeds by graph voting; phase 2 spends the rest on low-confidence, diverse examples after a model pass.
• It beat random selection by 12.9% / 11.4% relative at budgets of 18 / 100, and matched fine-tuning with 10–100x less annotation across 10 datasets.
• Reach for it when labels are expensive and reused across many queries; skip it for one-off prompts or already-labeled data.
• Use fast vote-k when the phase-2 model pass is too costly; it keeps most of the gain for a fraction of the compute.