Repeated sampling (20,000 tasks per point; calls include one verifier call per candidate):
N
Best-of-N with verifier: accuracy
calls
Majority vote: accuracy
calls
1
0.55
2
0.55
1
3
0.73
6
0.60
3
5
0.78
10
0.63
5
9
0.81
18
0.65
9
15
0.82
30
0.65
15
Accuracy against calls for best-of-N and majority vote; sampling, prioritisation and bandit tables.
At about the same number of calls, best-of-3 with a verifier (6 calls, 0.73) beat majority vote over 5 (5 calls, 0.63) by ten points.
When wrong answers agree (N = 15): majority vote 0.72 when wrong answers scatter, 0.65 when half share one answer, 0.58 when 90 percent do; best-of-15 with the verifier stayed at 0.82 to 0.83.
Prioritisation (30 tasks, budget 40 cost units, share of the exact optimum, 400 task sets per row):
Error in the agent's value estimates
Arrival order
Highest value first
Cheapest first
Value per cost
0%
0.58
0.86
0.88
0.99
50%
0.58
0.78
0.88
0.92
100%
0.58
0.73
0.88
0.84
200%
0.58
0.70
0.88
0.77
The budget changes how much order matters: with a budget of 120 (almost everything fits) arrival order reached 0.93; with a budget of 10 it reached 0.41, while value-per-cost stayed at 0.99 to 1.00.
Exploration (regret, lower is better; averages over 300 runs):
Horizon T
Always first
Round robin
Explore, then commit
Epsilon-greedy
UCB
Thompson
20
6
3
3
3
3
2
100
32
16
8
8
12
8
500
160
79
26
27
45
24
1,000, with the best strategy dropping halfway
320
157
114
102
83
93
Reading it:
A verifier turns extra attempts into extra accuracy; a vote does not, if errors are correlated. Majority voting needs independent, scattered errors. With a strong attractor it hardly moves.
Cost is linear in N, and a verifier doubles it. Past N of about 5 the accuracy gain per call is small for both.
Prioritise by value per cost, but only as far as you trust the estimates. With noisy value estimates, a rule that ignores value (cheapest first) beat the "smarter" rule. Agents scoring their own tasks are such a source of noise, so calibrate the estimate before trusting it (Level 9).
Exploration pays when there is time. At 20 runs there is little to learn; at 100 or more, a policy that learns beats one that does not by a factor of four.
No exploration policy wins everywhere. UCB1 over-explored at moderate horizons (45 against 24 at 500 runs) but was the best when the best strategy changed. I did not tune any of them.
Exploration needs outcome data. It presumes you can tell success from failure for each run, which is the verifier of module 4 again.
Using these patterns in agents
Spend extra compute where it is checkable: tests, schema validation, deterministic checks. Use a vote only for tasks with a single short answer and diverse errors.
Vary what you sample: different temperatures, prompts or models increase diversity; identical samples add nothing.
Cap N from measured returns, and compute cost per percentage point gained.
Order work by value per cost when both can be measured; keep a deadline or dependency rule for ties and for tasks that unblock others.
Record outcomes per strategy (prompt version, tool, agent) so that selection can learn; keep a small share of runs for exploration so that changes are noticed.
Treat tree search and plan search as the same idea with structure: expand several candidate next steps, score them, and keep the best few (beam), spending calls only on promising branches (general knowledge; not tested here).