4. Min Threshold for Precision

Problem

Fin gates its final answer on a certainty/confidence score: if a generated response's certainty doesn't meet a required threshold, Fin asks a disambiguating clarification question instead of answering directly, rather than risking a wrong answer.

Given historical (certainty_score, was_correct) pairs from past answered queries, find the minimum certainty threshold such that, among all responses with certainty at or above that threshold, the fraction that were actually correct (precision) is at or above a target. The minimum threshold that still hits the bar answers the most queries directly (fewer needless clarification questions) while staying safe. Consider every distinct certainty score present as a candidate threshold, and aim for a sort-once, single-pass O(n log n) solution, not a brute-force O(n²).

Source: src/4_min_threshold_for_precision.py

def min_threshold_for_precision(scored_outcomes: list[tuple[float, bool]], target_precision: float) -> float | None:
    ...

Examples:
>>> min_threshold_for_precision([(0.9, True), (0.8, True), (0.7, False), (0.6, True)], 1.0)
0.8

>>> min_threshold_for_precision([(0.9, False), (0.8, True)], 1.0)
None

Step-by-Step Approach

1. Reframe the question: "find the minimum threshold t such that filtering to score ≥ t and computing precision on the survivors hits target_precision" is a search over the discrete set of distinct certainty scores present in the data.
2. Sort all outcomes descending by certainty score once — this lets you sweep from the highest threshold down to the lowest while incrementally accumulating counts, instead of recomputing precision from scratch for every candidate threshold (the O(n²) brute force).
3. Walk the sorted list left to right, grouping consecutive entries that share the same score — a threshold t must include every entry with score == t together, so they need to be processed as one group, not one at a time.
4. Maintain running correct and total counters as you extend the "at-or-above-t" window group by group; after finishing a group, correct / total is exactly the precision at or above that group's score.
5. Because the smallest qualifying threshold is what's wanted, don't stop at the first threshold that satisfies the target — keep scanning and keep overwriting a "best so far" variable every time the running precision clears the target, so the last (smallest) qualifying threshold wins.
6. Return None if no threshold ever clears the bar, including for empty input.

The key insight: as t decreases, both correct and total in the "at-or-above-t" set only grow, but the ratio correct / total is not monotonic in t — it can rise or fall as the sweep proceeds. That rules out stopping early at the first success, but the sort-then-single-pass structure still gets the answer in O(n log n) instead of the O(n²) of recomputing precision fresh for every candidate threshold.

Reference solution

def min_threshold_for_precision(scored_outcomes: list[tuple[float, bool]], target_precision: float) -> float | None:
    # sort once descending, single pass accumulating running correct/total, O(n log n) time, O(n) space
    if not scored_outcomes:
        return None
    # descending via negated key
    ordered = sorted(scored_outcomes, key=lambda pair: -pair[0])
    best = None
    correct = 0
    total = 0
    i = 0
    n = len(ordered)
    while i < n:
        t = ordered[i][0]
        # group all entries tied at this score together
        while i < n and ordered[i][0] == t:
            total += 1
            if ordered[i][1]:
                correct += 1
            i += 1
        if correct / total >= target_precision:
            # overwrite so the last (smallest) qualifying threshold wins
            best = t
    return best

Key Functions & Tricks

• sorted(scored_outcomes, key=lambda pair: -pair[0]) — descending sort via negated key
• Grouping equal-score entries with a nested while — manual group-by over pre-sorted run
• ordered[i][0] == t — safe float equality since t is drawn from the same list
• correct / total — true division always yields a precise float ratio
• best = None sentinel with overwrite-on-success — keeps the last (smallest) threshold that clears the bar

How to Recognize This Pattern