Compressed threshold-overlap Gram layer

1. Integration point: use this as a fixed-width embedding layer for objects represented by k-element subsets, or as an overlap bias/kernel in set attention. Given a minibatch of sets \(S_1,\ldots,S_b\), store one trainable vector \(z_S\in\mathbb R^r\), or generate \(z_S\) from shared element embeddings followed by an exterior-power pooling module. Replace ordinary dot-product similarity by \(K_{ij}=z_{S_i}^{\top}z_{S_j}\); in attention, add \(\log(|K_{ij}|+\delta)\) as an overlap bias or use a nonnegative transformed version of K as a gated message weight.

2. MVP pseudocode:

r = binom(n - 2*(k-s), s)
Z = trainable_embedding_table(num_k_subsets, r)
for batch of sets S[1:b]:
    K = Z[S] @ Z[S].T
    loss = 0
    for i != j:
        if intersection_size(S[i], S[j]) < s:
            loss += K[i,j]**2
        else:
            loss += relu(epsilon - abs(K[i,j]))**2
    loss += mu * frobenius_norm(Z.T @ Z - I_r)**2
    update network and Z

The first term enforces the paper's prescribed zero pattern; the second prevents the trivial all-zero solution; the orthogonality term keeps the learned factor numerically well-conditioned. For a scalable version, parameterize Z through element embeddings and sampled s-wedge features rather than a table over all \(\binom nk\) sets.

3. Computed from the paper: the admissible parameter regime, target rank r, PSD factorization requirement, and exterior-power determinant identity. Estimated empirically: the actual factor Z, positive-pair margins, and whether the rank target is numerically attainable. Monitor the largest forbidden-pair similarity, the smallest positive-pair magnitude, the effective numerical rank of Z, and downstream validation accuracy.

4. First experiment: use \(n=12,k=4,s=2\), where the theorem predicts \(r=\binom{8}{2}=28\), versus the naive pair-feature dimension \(\binom{12}{2}=66\). Train a small DeepSets or set-transformer model on synthetic classification and retrieval tasks whose labels depend on whether query and candidate sets overlap in at least two elements. Compare the proposed 28-dimensional PSD kernel, the 66-dimensional s-subset incidence kernel, and an unconstrained learned embedding at matched parameter counts. Success means at least 2x lower embedding memory with equal retrieval accuracy, or faster convergence at equal width; also report forbidden-pair leakage \(\max_{|S\cap T|<s}|K_{S,T}|\).