Skip to content

pareto_front() returns rows that another row dominates when scores tie on one objective #77

Open

Description

@0z5a

Bug Description

SearchResult.pareto_front() (and therefore get_best_result() and Search.best_result for any multi-objective search) keeps a row that ties the best row on one objective and is worse on another.

SearchResult.calculate_pareto_front keeps every row for which np.any(scores <= point) (MIN) or np.any(scores >= point) (MAX). A row is therefore dropped only when it is strictly worse than the current point on every objective. A row that is equal on one objective and worse on another survives, although the point dominates it.

The unit tests already state the intended definition, in the class docstring of TestCalculatePareteFrontMin:

For minimization: point A dominates point B if A is <= B on all objectives and strictly < on at least one.

Under that definition (1, 1) dominates (1, 5), but the same test then asserts the opposite (assert mask[2] is np.True_ # (1,5) is not dominated by (1,1) — equal on dim 0). The MAX test does the same for (5, 5) and (5, 1).

Minimal reproducer:

import pandas as pd
from compileiq.results import SearchResult
from compileiq.types import ProblemType

df = pd.DataFrame(
    [[0, 0, 1, 1, {"cfg": "a"}], [1, 0, 1, 5, {"cfg": "b"}]],
    columns=["metadata", "generation", "score_1", "score_2", "params"],
)
r = SearchResult(df=df, problem_type=ProblemType.MIN, num_scores=2)
print([(row["score_1"], row["score_2"]) for row in r.pareto_front()])
# actual:   [(1, 1), (1, 5)]
# expected: [(1, 1)]

Why this matters for compiler-flag searches: one objective is often a count, such as spill bytes or registers, and many flag sets give the same value (often 0). With objectives (kernel time, spill bytes), every zero-spill row ends up on the returned "front", not just the fastest one. Measured on main (bf21d9e), checked against a brute-force dominance check:

  • Search(...).start() with 12 x 3 candidates and the objective (time_us rounded to 0.1, spill_bytes): in four runs pareto_front() returned 14, 12, 13 and 15 rows, while a brute-force check gave 1, 1, 1 and 2. Every extra row is a zero-spill row that is slower than the best one. (The engine was the repo's pure-Python scripted test engine, since the native engine is not available on macOS; the result does not depend on the engine because the ranking runs on the result table.)
  • Integer scores with ties (2–3 objectives, MIN and MAX, 1,000 cases): the output matched brute force in 24 of 1,000 cases.

The compileiq-validate-result skill re-measures every front candidate at 100 or more trials, so each dominated row costs a full validation run.

Fix: keep a row only if it is strictly better than the current point on some objective, or exactly equal to it on all objectives. That keeps the existing behavior that identical rows all stay on the front (test_identical_points_both_on_front). I have a patch with tests and can open a PR.

System Information

CompileIQ main @ bf21d9e (source checkout), Python 3.12, pandas 2.3.3, numpy 2.4.4, macOS arm64.

This issue was drafted with Claude Code (claude-opus-5-5); the results above are from the runs described.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions