Evidence accumulates as a linear product, so log-evidence underflows to -inf on large games #12

New Issue

2026-08-04T19:15:38Z

logaritmisk commented

2026-08-04 19:15:38 +00:00

Per-link evidence is multiplied in linear space and only logged at the very end (src/game.rs:358):

let evidence: f64 = links.iter().map(|l| l.evidence()).product();

then Game::log_evidence is self.evidence.ln() (src/game.rs:436), and TimeSlice::log_evidence does event.evidence.ln() per event (src/time_slice.rs:563).

Each link's evidence is a probability in (0, 1]. An n-team game has n-1 links, so the product decays geometrically in the team count. With typical per-link evidence around 0.5, the product hits the f64 subnormal floor at roughly 1000 links and flushes to exactly 0.0 — ln(0.0) is -inf, which then propagates through the sum() in History::log_evidence_internal (src/history.rs:350-367) and makes the whole history's log-evidence -inf.

Well before full underflow, the product loses precision: multiplying many small floats accumulates relative error that summing logs does not.

Where it bites

Large free-for-alls and ranked fields — Game::free_for_all (src/game.rs:527) builds one team per player, so a 1000-player FFA is a 999-link chain. That is exactly the "5000 events / 50000 competitors" scale the T3 benchmarks were reaching for.

Fix

Accumulate in log space throughout:

Store log_evidence: f64 on Game/OwnedGame instead of evidence: f64, summing l.evidence().ln() over links.
TimeSlice::log_evidence then sums stored log values directly instead of .ln()-ing a product.
DiffFactor::evidence() (src/game.rs:40) can keep returning linear evidence from the factor, or the factors' cached values can move to log space too — TruncFactor::log_evidence and MarginFactor::log_evidence already do .ln() at the boundary (src/factor/trunc.rs:70, src/factor/margin.rs:63).

Related robustness issue in the same code path

The cached evidence can legitimately be zero or negative, and nothing guards ln():

TruncFactor's cavity_evidence computes 1.0 - cdf(margin, mu, sigma) (src/factor/trunc.rs:79). For a heavily one-sided diff, cdf rounds to exactly 1.0 and the evidence becomes 0.0 → ln(0.0) = -inf. The erfc approximation in use (src/lib.rs:72) has ~1e-7 accuracy, so cdf can even exceed 1.0 slightly, making the evidence negative → ln of a negative is NaN.
The tie branch cdf(margin, …) - cdf(-margin, …) can likewise round to 0.0 for a narrow margin far from the mean.

Both should be clamped to a small positive floor (or computed via a log-space complementary formulation) so log-evidence stays finite.

log_evidence also returns evidence_cached.unwrap_or(1.0).ln() — i.e. silently 0.0 for a factor that was never propagated. That should be unreachable, and an explicit debug_assert!/expect would say so.

Acceptance

Log-evidence stays finite for a 2000-team ranked game and for a history with thousands of events.
A test constructs a near-certain outcome (very large diff mean relative to sigma) and asserts finite, non-NaN log-evidence.
Numerical parity with the current implementation on the existing goldens, within test epsilons.

Per-link evidence is multiplied in linear space and only logged at the very end (`src/game.rs:358`): ```rust let evidence: f64 = links.iter().map(|l| l.evidence()).product(); ``` then `Game::log_evidence` is `self.evidence.ln()` (`src/game.rs:436`), and `TimeSlice::log_evidence` does `event.evidence.ln()` per event (`src/time_slice.rs:563`). Each link's evidence is a probability in `(0, 1]`. An `n`-team game has `n-1` links, so the product decays geometrically in the team count. With typical per-link evidence around 0.5, the product hits the `f64` subnormal floor at roughly 1000 links and flushes to exactly `0.0` — `ln(0.0)` is `-inf`, which then propagates through the `sum()` in `History::log_evidence_internal` (`src/history.rs:350-367`) and makes the whole history's log-evidence `-inf`. Well before full underflow, the product loses precision: multiplying many small floats accumulates relative error that summing logs does not. ## Where it bites Large free-for-alls and ranked fields — `Game::free_for_all` (`src/game.rs:527`) builds one team per player, so a 1000-player FFA is a 999-link chain. That is exactly the "5000 events / 50000 competitors" scale the T3 benchmarks were reaching for. ## Fix Accumulate in log space throughout: - Store `log_evidence: f64` on `Game`/`OwnedGame` instead of `evidence: f64`, summing `l.evidence().ln()` over links. - `TimeSlice::log_evidence` then sums stored log values directly instead of `.ln()`-ing a product. - `DiffFactor::evidence()` (`src/game.rs:40`) can keep returning linear evidence from the factor, or the factors' cached values can move to log space too — `TruncFactor::log_evidence` and `MarginFactor::log_evidence` already do `.ln()` at the boundary (`src/factor/trunc.rs:70`, `src/factor/margin.rs:63`). ## Related robustness issue in the same code path The cached evidence can legitimately be zero or negative, and nothing guards `ln()`: - `TruncFactor`'s `cavity_evidence` computes `1.0 - cdf(margin, mu, sigma)` (`src/factor/trunc.rs:79`). For a heavily one-sided diff, `cdf` rounds to exactly `1.0` and the evidence becomes `0.0` → `ln(0.0) = -inf`. The `erfc` approximation in use (`src/lib.rs:72`) has ~1e-7 accuracy, so `cdf` can even exceed 1.0 slightly, making the evidence *negative* → `ln` of a negative is `NaN`. - The tie branch `cdf(margin, …) - cdf(-margin, …)` can likewise round to `0.0` for a narrow margin far from the mean. Both should be clamped to a small positive floor (or computed via a log-space complementary formulation) so log-evidence stays finite. `log_evidence` also returns `evidence_cached.unwrap_or(1.0).ln()` — i.e. silently `0.0` for a factor that was never propagated. That should be unreachable, and an explicit `debug_assert!`/`expect` would say so. ## Acceptance - Log-evidence stays finite for a 2000-team ranked game and for a history with thousands of events. - A test constructs a near-certain outcome (very large diff mean relative to sigma) and asserts finite, non-NaN log-evidence. - Numerical parity with the current implementation on the existing goldens, within test epsilons.

logaritmisk referenced this issue

2026-08-04 19:20:44 +00:00

Dead and duplicated code: a stale `iterate_to_convergence`, a copy-pasted sweep, and `#[allow(dead_code)]` used as a mute button #23

logaritmisk referenced this issue

2026-08-04 19:21:40 +00:00

Test suite has no coverage for degenerate inputs, release-mode behaviour, or non-finite results #26

logaritmisk commented

2026-08-04 20:11:38 +00:00

Fixed in 0f1a1b8. Game, OwnedGame and time_slice::Event carry log_evidence directly, summed over links rather than multiplied then logged.

The per-link value is also floored at f64::MIN_POSITIVE at its source, covering both failure modes noted above: 1.0 - cdf(..) rounding to zero for a near-certain outcome, and the erfc approximation's ~1e-7 error pushing cdf past 1.0 so the difference goes negative and ln returns NaN.

Existing log-evidence goldens are unchanged, which confirms the accumulation is numerically equivalent over the range where the old form worked. Two regression tests in tests/degenerate_inputs.rs: a 1200-team chain (which underflowed the linear product to exactly zero) and a ±5000-mu blowout in both directions.

Fixed in 0f1a1b8. `Game`, `OwnedGame` and `time_slice::Event` carry `log_evidence` directly, summed over links rather than multiplied then logged. The per-link value is also floored at `f64::MIN_POSITIVE` at its source, covering both failure modes noted above: `1.0 - cdf(..)` rounding to zero for a near-certain outcome, and the `erfc` approximation's ~1e-7 error pushing `cdf` past 1.0 so the difference goes negative and `ln` returns NaN. Existing log-evidence goldens are unchanged, which confirms the accumulation is numerically equivalent over the range where the old form worked. Two regression tests in `tests/degenerate_inputs.rs`: a 1200-team chain (which underflowed the linear product to exactly zero) and a ±5000-mu blowout in both directions.

logaritmisk closed this issue

2026-08-04 20:13:34 +00:00

logaritmisk added the bug numerics labels 2026-09-07 13:53:11 +00:00

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: logaritmisk/trueskill-tt#12

Evidence accumulates as a linear product, so log-evidence underflows to -inf on large games #12

Where it bites

Fix

Related robustness issue in the same code path

Acceptance

Evidence accumulates as a linear product, so log-evidence underflows to `-inf` on large games #12