Deterministic Pareto Front Updates Via Incremental Dominance Buckets

I ran into a frustrating problem while building a little “best trade-offs” engine: I needed a live Pareto front (set of non-dominated solutions) that updates as new candidate points arrive. The catch was practical: I needed the result to be deterministic and fast, even when many points share equal coordinates.

What problem I was actually solving

Each candidate solution is a point in 2D: (cost, quality). A point A dominates point B if:

cost_A <= cost_B (no worse cost)
quality_A >= quality_B (no worse quality)
and at least one of those is strictly better

The Pareto front is the set of points that aren’t dominated by any other.

The “gotchas” that made this niche (and annoying) were:

Incremental updates: points arrive one-by-one, and I need to update the Pareto front without recomputing everything.
Determinism with ties: if two points have the same cost and different quality, only the best survives; if they have equal quality, order must not affect the result.
Avoiding O(n²): naive “check against every front point” can degrade quickly.

I ended up using a deterministic structure I call incremental dominance buckets: I maintain a set of “front” points sorted by cost, and I only scan the portion that could possibly be affected by the incoming point.

The core idea: monotonic frontier scanning

If the Pareto front is sorted by increasing cost, then quality along the frontier is strictly increasing (when you remove dominated points).

That means: when a new point (c, q) arrives, the only way it can get onto the front is if it beats the current frontier’s quality at the appropriate position.

Concretely, I keep:

A sorted list of frontier points by cost
A list of the corresponding quality values
A dominates rule to decide membership
A “scan and splice” step to remove newly dominated neighbors

This is conceptually similar to maintaining a monotonic skyline, but the determinism comes from handling equal cost carefully.

Implementation (Python): incremental dominance buckets

This version is built to be repeatable regardless of insertion order for equal coordinates.

from bisect import bisect_left
from dataclasses import dataclass
from typing import List, Tuple, Optional


@dataclass(frozen=True, order=True)
class Point:
    cost: int
    quality: int


def pareto_front_insert(front: List[Point], p: Point) -> List[Point]:
    """
    Incrementally update Pareto front in 2D where:
      - lower cost is better
      - higher quality is better

    front is maintained as:
      - sorted by cost ascending
      - with strictly increasing quality across successive costs
    """
    # 1) Handle exact tie on cost deterministically:
    #    Among equal-cost points, only keep the one with highest quality.
    costs = [pt.cost for pt in front]
    i = bisect_left(costs, p.cost)

    # If there is already a point with the same cost:
    if i < len(front) and front[i].cost == p.cost:
        # If existing dominates p (same cost, higher/equal quality), p is discarded.
        if front[i].quality >= p.quality:
            return front
        # Otherwise p dominates the equal-cost one; replace it.
        front = front[:i] + front[i + 1:]

    # 2) Check whether p is dominated by the neighbor to the left.
    #    Since front qualities are increasing, we only need to compare with the
    #    predecessor by cost.
    costs = [pt.cost for pt in front]
    i = bisect_left(costs, p.cost)

    # predecessor exists?
    if i - 1 >= 0:
        pred = front[i - 1]
        # pred has cost <= p.cost. If pred also has quality >= p.quality,
        # then pred dominates p.
        if pred.quality >= p.quality:
            return front

    # 3) Insert p into the correct position.
    front = front[:i] + [p] + front[i:]

    # 4) Remove points dominated by p to the right.
    #    Because qualities increase with cost on the current frontier,
    #    as soon as we find a point with quality > p.quality, p no longer dominates further points.
    j = i + 1
    while j < len(front) and front[j].quality <= p.quality:
        j += 1

    # Points in [i+1, j) are dominated by p (their quality <= p.quality)
    front = front[:i + 1] + front[j:]

    # 5) Remove points dominated by the left neighbor due to replacement gaps.
    #    In this algorithm, this typically isn't needed after the initial checks,
    #    but it keeps invariants tight if the data contains duplicates or replacements.
    #    Ensure frontier quality is increasing.
    #    Remove any unexpected violations (quality not increasing).
    k = 1
    while k < len(front):
        if front[k - 1].quality >= front[k].quality:
            # left dominates right (since cost strictly increases, left has <= cost and >= quality)
            front.pop(k)
        else:
            k += 1

    return front


def build_front(points: List[Tuple[int, int]]) -> List[Point]:
    front: List[Point] = []
    for cost, quality in points:
        front = pareto_front_insert(front, Point(cost, quality))
    return front


def main():
    # Designed to stress:
    # - equal costs
    # - dominated points
    # - insertion order changes
    stream = [
        (5, 1),
        (2, 2),
        (3, 1),  # dominated by (2,2) because cheaper and better quality? Actually cost 2<=3 and quality 2>=1 => yes dominated
        (4, 2),  # not dominated: (2,2) has quality ==2 but cost 2<4; since quality not worse, (2,2) dominates only if quality >= and cost <=, yes dominates (4,2) with equal quality
        (4, 3),  # replaces frontier around cost 4, dominates (4,2) (but (4,2) never survived)
        (1, 1),  # dominated by none? (1,1) might be dominated by (1,1) itself? Check: (2,2) has cost 2>1 so cannot dominate (cost must be <=). So (1,1) stays only if not dominated by predecessor (none) => stays, but later (2,2) might dominate it? yes if quality >= => (2,2) dominates (1,1) would require cost 2<=1 which is false. So both can stay.
        (1, 2),  # same cost as (1,1) but better quality; replaces deterministically
    ]

    front = build_front(stream)
    print("Final Pareto front (cost asc, quality asc):")
    for pt in front:
        print(pt)


if __name__ == "__main__":
    main()

What happens when I run it

Points with the same cost replace the earlier one only if they have higher quality.
For a new point, I first check the immediate predecessor (the only one that can dominate on the left).
Then I insert it.
Finally, I scan forward removing any points whose quality is <= the new point’s quality.

This avoids checking every old front point every time.

Step-by-step walkthrough on a small sequence

Take this pair of inserts:

Insert (5, 1) → front is [(5,1)]
Insert (2, 2):
- predecessor doesn’t exist
- insert position is front start
- remove dominated points on the right:
  - (5,1) has quality 1 <= 2, so it gets removed
- front becomes [(2,2)]
Insert (3, 1):
- predecessor is (2,2) with quality 2 >= 1, so it’s dominated → discarded

This matches the dominance definition exactly, but does so with only local checks.

Why this is deterministic (the tie rules)

Without special handling, insertion order can create different front sets when points share the same cost or when “equal quality” interactions occur.

The determinism is enforced by this rule:

For equal cost, keep only the point with maximum quality
If the incoming point isn’t strictly better at that cost, it’s discarded immediately

So (4,2) will always lose to (4,3) even if (4,2) arrived first.

Complexity notes (practical, not academic)

Let m be the current size of the Pareto front.

The predecessor check is effectively O(log m) for the binary search in the sorted costs list.
The removal scan after insertion can be O(m) in the worst case, but each dominated point is removed when it becomes invalid.
This is usually far faster than checking all candidates against all front points.

For streaming workloads where the frontier stays small compared to total points, it performs well.

Conclusion

I built an incremental Pareto front updater using deterministic incremental dominance buckets: maintain a sorted frontier with monotonic quality, reject points dominated by their predecessor, insert, then scan rightward to remove any newly dominated neighbors. The key “engineering detail” that made results stable was explicit handling of equal cost so ties can’t create insertion-order-dependent front sets.