Pareto Frontier

When two configurations are compared on cost and on success rate, one is often cheaper and the other more accurate, and neither is simply better. The Pareto frontier is the set of options that survive a first, preference-free filter: an option stays if no other option is at least as good on every objective and strictly better on at least one.

Written for cost to be minimized and success rate to be maximized, option \(x\) dominates option \(y\) when \(\text{cost}(x) \le \text{cost}(y)\), \(\text{success}(x) \ge \text{success}(y)\), and at least one of the two inequalities is strict. An option that nothing dominates is non-dominated, and the set of such options is the frontier. Anyone who prefers lower cost and higher success, however the two are weighed, can discard a dominated option without losing anything. The same dominance relation is used to compare recommenders on several metrics.

A small example

Seven hypothetical configurations of an AI feature are listed with their cost per 1,000 tasks and their measured success rate. Cost means total spend per task, including retries and review, and not the price of one call, because a configuration can be cheap per call and expensive per task. The script finds dominated options with a pairwise check and the frontier with a single pass. It ran on Python 3.12.14 on macOS.

# Hypothetical configurations: (name, cost per 1,000 tasks in dollars, success rate)
configs = [
    ("A small only",        8.0, 0.70),
    ("B small x3 retries", 14.0, 0.74),
    ("C mid only",         15.0, 0.88),
    ("D cascade",          21.0, 0.93),
    ("E large only",       29.0, 0.95),
    ("F large + checker",  52.0, 0.99),
    ("G mid + checker",    41.0, 0.92),
]

def dominates(x, y):
    return x[1] <= y[1] and x[2] >= y[2] and (x[1] < y[1] or x[2] > y[2])

print("dominated by:")
for y in configs:
    d = [x[0][0] for x in configs if dominates(x, y)]
    print(f"  {y[0]:<20} {', '.join(d) if d else '-'}")

front = []
best = -1.0
for c in sorted(configs, key=lambda c: (c[1], -c[2])):
    if c[2] > best:
        front.append(c); best = c[2]
print("\nfrontier (sorted by cost):")
prev = None
for c in front:
    if prev:
        slope = (c[1] - prev[1]) / ((c[2] - prev[2]) * 100)
        print(f"  {c[0]:<20} ${c[1]:5.1f}  {c[2]:.2f}   +${c[1]-prev[1]:4.1f} for +{(c[2]-prev[2])*100:.0f} pts -> ${slope:.2f} per 1,000 tasks per point")
    else:
        print(f"  {c[0]:<20} ${c[1]:5.1f}  {c[2]:.2f}")
    prev = c

print("\nbest choice when each successful task is worth v dollars (maximize 1000*v*success - cost):")
for v in (0.05, 0.10, 0.20, 0.50, 1.00):
    b = max(front, key=lambda c: 1000*v*c[2] - c[1])
    print(f"  v=${v:.2f}: {b[0]}")
chosen = set()
for i in range(1, 20001):
    v = i / 10000
    chosen.add(max(front, key=lambda c: 1000*v*c[2] - c[1])[0])
print("\nfrontier points chosen for some v in (0, 2]:", sorted(chosen))
print("never chosen by any v:",  for c in front if c[0] not in chosen])

print("\nminimum cost with success >= target:")
for t in (0.75, 0.90, 0.95, 0.99):
    ok =  >= t]
    print(f"  target {t:.2f}: {ok[0][0] if ok else 'none'}")

import math
print("\nstandard error of a success rate measured on n cases:")
for n in (200, 1000):
    for p in (0.93, 0.95):
        print(f"  n={n:>4} p={p}: se={math.sqrt(p*(1-p)/n):.4f}")

The output is:

dominated by:
  A small only         -
  B small x3 retries   -
  C mid only           -
  D cascade            -
  E large only         -
  F large + checker    -
  G mid + checker      D, E

frontier (sorted by cost):
  A small only         $  8.0  0.70
  B small x3 retries   $ 14.0  0.74   +$ 6.0 for +4 pts -> $1.50 per 1,000 tasks per point
  C mid only           $ 15.0  0.88   +$ 1.0 for +14 pts -> $0.07 per 1,000 tasks per point
  D cascade            $ 21.0  0.93   +$ 6.0 for +5 pts -> $1.20 per 1,000 tasks per point
  E large only         $ 29.0  0.95   +$ 8.0 for +2 pts -> $4.00 per 1,000 tasks per point
  F large + checker    $ 52.0  0.99   +$23.0 for +4 pts -> $5.75 per 1,000 tasks per point

best choice when each successful task is worth v dollars (maximize 1000*v*success - cost):
  v=$0.05: C mid only
  v=$0.10: C mid only
  v=$0.20: D cascade
  v=$0.50: E large only
  v=$1.00: F large + checker

frontier points chosen for some v in (0, 2]: ['A small only', 'C mid only', 'D cascade', 'E large only', 'F large + checker']
never chosen by any v: ['B small x3 retries']

minimum cost with success >= target:
  target 0.75: C mid only
  target 0.90: D cascade
  target 0.95: E large only
  target 0.99: F large + checker

standard error of a success rate measured on n cases:
  n= 200 p=0.93: se=0.0180
  n= 200 p=0.95: se=0.0154
  n=1000 p=0.93: se=0.0081
  n=1000 p=0.95: se=0.0069

Only G, the mid-tier model with a checker, is dominated. D costs \$21 against \$41 and succeeds more often, and E also costs less and succeeds more often. The other six options each win on at least one objective against every rival, so they form the frontier. G could still look reasonable in a spreadsheet that sorts by one column at a time; the dominance check is what shows that two cheaper options beat it on both.

Finding the frontier in one pass

With two objectives, sort the options by cost, breaking ties by higher success first, and walk down the list. Keep an option only if its success rate is higher than that of every cheaper option kept so far, because otherwise some cheaper option is at least as successful. This implementation keeps one representative when several options have identical cost and success; those tied options do not dominate one another. The sort dominates the running time, so the cost is \(O(n \log n)\). With three or more objectives no single ordering works, and the usual approach is to compare pairs of options, which takes \(O(n^2)\) comparisons.

Choosing a point on the frontier

The frontier does not pick a winner. The incremental price of success can rise or fall along the frontier: A to B costs \$1.50 per 1,000 tasks per added percentage point, while B to C costs about \$0.07. Later in this example, C to D costs \$1.20 and E to F costs \$5.75. A choice needs a preference that fixes how much a point of success is worth. Two common forms are shown in the output. One puts a dollar value \(v\) on each successful task and maximizes \(1000\,v \cdot \text{success} – \text{cost}\); the best option moves from C to D to E to F as \(v\) grows from \$0.05 to \$1.00. The other sets a success floor and takes the cheapest option above it, so a floor of 0.90 selects D and a floor of 0.95 selects E. Either way the answer lies on the frontier.

The two rules do not reach the same points. B is on the frontier, since nothing is both cheaper and more successful, but it sits below the line joining A and C, and no value of \(v\) makes B the maximizer; the output confirms that B is never chosen by the value rule. Only a floor placed just above 0.70, up to 0.74, would pick it, and C costs one dollar more for 14 more points. A frontier point can be legitimate under the definition and still be a poor practical choice.

Measured frontiers are estimates

The success rates in a real comparison come from a finite evaluation set. A rate near 0.95 measured on 200 cases has a standard error of about 0.015, and about 0.007 on 1,000 cases, as the last lines of the output show. For independent evaluation samples of 200 cases each, the difference between rates of 0.93 and 0.95 has a standard error of roughly 0.024. For configurations evaluated on the same cases, estimate uncertainty from the paired outcome differences instead. Under the independent-sample approximation, the two-point gap between D and E and even the three-point gap between E and G are within about 1.3 standard errors. At that sample size the data cannot order D and E with confidence, and the claim that E dominates G is weaker than the table suggests. Costs are usually measured more precisely than success rates. Options near the frontier can switch sides when the evaluation set changes, so treat options within the measurement error as candidates and not as a ranked list.

References

• Wikipedia, Pareto efficiency