Sigma Update Part II

Protocol Enhancements
1

Part II completes the Sigma update, aligning TIG with industry and academic practice. This update implements the following changes:

  1. The Definition of a Solution
  2. Benchmark Averaging
  3. Challenge Tracks
  4. Two-Tier Solution Verification
  5. Benchmarker Access to Fuel

These changes will make the protocol fairer and simpler, whilst incentivising higher value innovation.

Part I is already live.

The Definition of a Solution

Current: In TIG, a solution is a nonce that solves a challenge instance to at least a benchmarker-specified quality threshold, while satisfying all instance constraints (e.g., in Vehicle Routing, vehicles must arrive no later than each customer’s due time; in the Quadratic Knapsack Problem, total weight must not exceed capacity).

Sigma Update Part II: Any nonce whose output satisfies the instance constraints is a solution. Quality no longer determines whether something counts as a solution—it determines how well it performs. Benchmarkers still have strong incentives to find high-quality solutions via the reward mechanism, which now uses Benchmark Averaging.

Benchmark Averaging

When committing to a benchmark, a benchmarker chooses:

  • an algorithm,
  • the hyperparameters,
  • a number of bundles (of nonces),
  • a challenge Track, and
  • a fuel limit.

For each bundle in the benchmark, the bundle outputs a \text{bundle\_quality} and, once verified, is plotted on the Challenge Track Plot at the coordinate (Track, \text{bundle\_quality}).

The details :

  • The parameter Track controls the type of the challenge instances (see the Challenge Tracks section below).

  • A bundle is defined as a subset of nonces in a benchmark. Each track has a bundle parameter \eta\in \mathbb{N} which is defined as the number of nonces in a bundle. When committing to a benchmark, a benchmarker will commit to a track and a \text{num\_bundles}, and will then compute \eta \cdot \text{num\_bundles} nonces.

  • We compute the quality of each bundle in the benchmark as follows. For a given \text{bundle}, its quality \text{bundle\_quality} is defined as the average of the qualities of the solutions in it.

  • After a benchmark has been verified, each of its bundles are plotted on the Challenge Track Plot at the points (Track, \text{bundle\_quality}).

  • If any nonce in a benchmark fails to yield a valid solution, the entire benchmark fails (the benchmarker reports the failure and the benchmark is dropped).

  • Since benchmarkers no longer commit to a solution quality, they must configure hyperparameters or fuel (e.g., run-time) to target higher-quality solutions.

  • Each challenge defines a minimum quality threshold, such that, if any of the qualities are below that threshold then the benchmark will be dropped.

This approach better matches how performance is assessed in industry and academia, reduces variance versus baselines (curbing overly greedy methods), and simplifies the protocol by removing the separate “reliability” concept.

Challenge Tracks

The concept of difficulty parameters no longer exists in the TIG protocol, with Challenge Tracks and Benchmark Averaging replacing it. Benchmarkers are now required to commit to a particular challenge Track for each benchmark.

  • Each challenge will define a fixed list of allowed Track ids.

  • From this list, benchmarkers commit to benchmark a Track.

This prevents compute being spread too thin over similar challenge instances. Now we can let benchmarkers focus compute to get higher quality solutions. This aligns with academic benchmarking. For example the Track could determine the size of the challenge instance. Tracks also let TIG define a range of sub-challenges with different instance-generation procedures, encouraging innovation in interesting problem features rather than simply changing the problem size.

Rewarding Tracks

Benchmarker rewards are no longer determined by the pareto frontier. The Tracks are rewarded as follows: in each track rank the bundles by their \text{bundle\_quality}, the top p bundles in each track are then defined as the qualifying bundles. Now a benchmarkers “number of qualifying bundles” is the metric used in their challenge factor calculation.

Two Tiered Solution Verification

This applies only to challenges that use a baseline algorithm.

The goal is to introduce more performant baselines, reducing variance and yielding a stronger comparative metric. Historically, baselines had to be extremely fast due to proof-of-work verification constraints protecting the network from DDOS attacks. With Sigma, verification is split into two tiers:

Tier 1 — Proof-of-work verification
Confirm the submitted solution is at least as good as the cheap baseline (e.g., pure greedy).

Tier 2 — Quality Measurement
Compute the solution’s quality using a sophisticated baseline.

Hence when verifying a nonce we carry out the following Steps in the verification process :

  1. Generate instance.
  2. Check that the solution satisfies the instance constraints:
    • If invalid → verification fails.
  3. Run cheap baseline algorithm (pure greedy).
    • If solution is not better than the cheap baseline → verification fails.
  4. Run sophisticated baseline algorithm (previous well-performing TIG algorithm).
    • Compute solution quality, check it matches the quality claimed by the benchmarker.

Benchmarker Access to Fuel

In TIG, an algorithm’s fuel is used as a proxy for the compute it consumes. When starting a benchmark, benchmarkers now pre-commit to a fuel budget. If, while solving a nonce, an algorithm exceeds this budget, it is terminated and the current saved solution is returned instead — see Sigma update part 1.

Giving benchmarkers direct control over fuel lets them roughly control how long their algorithms will run. In addition, the maximum fuel limit is increasing, allowing benchmarkers to target higher-quality solutions when they are willing to spend more compute.