Multi-word monomial hash has exact-collision families: every Bitset with word0 == word1 + 1 hashes to 0

[robertodr]

🤖 AI text below 🤖

What

SplitmixHash combines the words of a multi-word Bitset by XOR-ing per-word mixes with a
position-additive tweak.

cpp/monoprop/Bitset.h:225-247

template <size_t NumBits>
struct SplitmixHash<monoprop::Bitset<NumBits>> {
    static constexpr auto mix(uint64_t x) noexcept -> uint64_t { /* splitmix64 finalizer */ }

    auto operator()(const monoprop::Bitset<NumBits> &bs) const noexcept -> size_t {
        constexpr size_t W = monoprop::Bitset<NumBits>::num_words();
        if constexpr (W == 1) {
            return static_cast<size_t>(mix(bs.word(0)));
        }
        else {
            uint64_t h = 0;
            for (size_t i = 0; i < W; ++i) {
                h ^= mix(bs.word(i) + static_cast<uint64_t>(i));   // <--
            }
            return static_cast<size_t>(h);
        }
    }
};

The single-word case is a clean splitmix64 finalizer and is fine. The multi-word case — i.e. every
NumModes > 32 — is not.

Why this is a problem

XOR is commutative, so the only thing distinguishing word positions is the + i tweak. That makes the
hash invariant under swapping two word positions with a compensating value shift. For two words:

h([a, b])       = mix(a + 0) ^ mix(b + 1)
h([b + 1, a - 1]) = mix(b + 1 + 0) ^ mix(a - 1 + 1) = mix(b + 1) ^ mix(a)     ← identical

The fixed point of that family is worse: whenever word0 == word1 + 1, the two mixes are equal and
cancel, so the hash is exactly 0. That is not a contrived input — it includes ordinary low-weight
monomials. On a 64-mode Majorana system (128 bits, 2 words):

monomial	word0	word1	hash
{bit 1, bit 64} (weight 2)	0b10	0b1	0
{bit 2, bits 64,65} (weight 3)	0b100	0b11	0
{bit 5, bits 64..68} (weight 6)	1<<5	(1<<5)-1	0

…and more generally every (v + 1, v) low-weight pair. The same argument generalises to any word
count: ⊕ᵢ mix(wᵢ + i) collides for any position transposition with the matching value adjustment.

Where it hurts:

• detail::OperatorIndex (cpp/monoprop/detail/operator/OperatorIndex.h) — fold_hash folds the full
  hash to 32 bits, so identical full hashes give identical folds and land in one linear-probe chain.
  A cluster of N such keys costs O(N²) probes plus row_eq_key confirmations on insert and lookup.
• boost::unordered_flat_map via MonomialHash — MonomialMap, MPOperator::init_op_map.
• find_rank (cpp/monoprop/detail/mpi/MPIUtils.h:52), which is monomial_hash(mono) % n_ranks.

To be clear about severity: this is a throughput defect, not a wrong-answer defect. Hashes only
need to be consistent, and they are.

Suggested fix

Chain the mixes instead of XOR-ing them, so position is structural rather than an additive tweak:

uint64_t h = 0;
for (size_t i = 0; i < W; ++i) {
    h = mix(h ^ bs.word(i));
}
return static_cast<size_t>(h);

(or a multiply-accumulate with a final avalanche). Either way it is a few lines in one place.

Why this wants its own PR

Changing the hash changes find_rank, and therefore:

• how terms distribute across MPI ranks and across intra-process partitions;
• the block order of contract_partially's output — already documented as not positionally stable
  ("not positionally stable across partition counts", MonomialPropagator.h), but it will move.

The equivalence tests should survive: cpp/tests/mpi_utils_tests.cpp only asserts find_rank's range
and determinism, and the MPI/partition equivalence suites compare values and multisets rather than
positions. Still, it deserves a dedicated change with its own full-matrix run rather than riding along
with unrelated work.

Verification

• A unit test pinning the collision away: assert hash({bit 1, bit 64}) != 0 and that the
  h([a,b]) == h([b+1,a-1]) family no longer collides, for a 2-word and an 8-word Bitset.
• A distribution smoke test: hash all weight ≤ 4 monomials on a 64-mode system and assert the distinct
  hash count matches the monomial count.
• Full matrix: just test, just test-mpi "1;2;4", just test-wide.
• just bench serial — a measurable improvement here would confirm the collisions were costing real
  probe time; no change would mean the colliding family is rare in the benchmarked workloads, which is
  worth recording either way.

---

Found by a code-reading review of the repository at 29a8050. No build tree was available, so the
collision families above were derived by hand from the source and should be confirmed by the unit test
described above before the fix lands.