Hi Jake,
Thanks for contributing to our forum discussion! We’re also very excited about the Hypergraph Partitioning Challenge and want to design it as best as we can, so we really appreciate any and all feedback.
In case you weren’t aware, the team has been working on a new “Enhanced Block Reward Function” to counter the dominance of greedy algorithms across all challenges. We believe this issue stems from the current reward function prioritising the number of solutions found over the reliability of securing a solution for each instance attempted. You can find more details in our latest post here. We believe that once this mechanism is implemented, coupled with increased fuel limits, it will drive meaningful innovation by focusing more on solution quality and discouraging greedy approaches. This, in turn, will allow the better_than_baseline factor to more effectively incentivise higher solution quality.
The role of the baseline algorithm is to establish a performance target to be exceeded by the better_than_baseline factor for each randomly generated instance, creating a clear metric for what qualifies as a valid solution from one instance to the next. This is necessary because the randomness of our instance generation means we do not know the optimal solution in advance, so we need an alternative reference. We need the baseline to be efficient since instance generation is part of the solution verification process; if generating the instance took as long as solving it, we’d lose the asymmetry and compromise our Sybil-defense. Additionally, the baseline should offer a performance metric that is consistent and stable across instances—e.g., consistently about 20% below the best-known partition from a SOTA solver like KaHyPar. These two factors—efficiency and consistency—should be the only considerations for choosing our baseline solver.
Incentivising high-quality algorithms while ensuring that greedy approaches do not dominate is vital. To address these issues, we are implementing additional measures within the reward function and fuel limits. If our new updates or proposals don’t have the desired effect, we will continue to work on this issue until it is resolved.
Thanks again for your comments—we really appreciate them and hope this response clears up why the baseline isn’t a factor in incentivising higher solution quality and more innovative algorithms.
Thanks!