# O(n)-parameter transitive pairwise head

- ID: 189
- Canonical URL: https://synthcore.org/idea/189/o-n-parameter-transitive-pairwise-head
- API JSON: https://synthcore.org/api/idea/189.json
- API Markdown: https://synthcore.org/api/idea/189.md
- Verification status: unverified
- Source: [arXiv:2608.25923](https://arxiv.org/abs/2608.25923)
- Category: architecture
- Solves: memory, scalability, generalization
- ML areas: embedding, graph-nn, inference-speedup
- Math tags: linear-algebra, geometry, combinatorics
- Ratings: usefulness 5/10; difficulty 4/10; novelty 5/10

## Idea description

Replace an independently learned n-by-n pairwise score tensor with coordinates in the paper's n-1 dimensional consistent subspace. The neural network predicts only basis coefficients, and a fixed reconstruction produces all pairwise logits, reducing the comparison representation from O(n^2) degrees of freedom to O(n) while guaranteeing transitivity.

## Mathematical statement

The space of skew-symmetric n by n matrices has dimension n(n-1)/2, whereas the additive-consistent subspace A_n has dimension n-1. Let B_1,...,B_{n-1} be the paper's orthogonal basis, where B_k=[b^{(k)}_{ij}]. Every consistent logit matrix has the expansion S=sum_{k=1}^{n-1} alpha_k B_k, with alpha_k=<S,B_k>/<B_k,B_k>. Equivalently, S_{ij}=u_i-u_j for item utilities u. Therefore all triangle identities S_{ij}+S_{jk}+S_{ki}=0 hold exactly. The neural head learns alpha in R^{n-1} and reconstructs S using the fixed basis; unlike an unconstrained pairwise tensor, it cannot represent contradictory preference cycles.

## Key formulas

- $$S=\sum_{k=1}^{n-1}\alpha_kB_k,\qquad \alpha_k=\frac{\langle S,B_k\rangle}{\langle B_k,B_k\rangle}$$
- $$S_{ij}=\sum_{k=1}^{n-1}\alpha_k b^{(k)}_{ij}=u_i-u_j$$
- $$\dim(\mathcal A_n)=n-1\ll\frac{n(n-1)}{2}=\dim(\mathfrak{so}(n))$$
- $$S_{ij}+S_{jk}+S_{ki}=0\qquad\text{for all }i,j,k$$

## Implementation notes

(1) Use this in a ranking, preference, retrieval, or set-comparison module whose current final output is an n by n score matrix. Replace its final pairwise layer with a linear or MLP head that outputs `alpha` of shape [batch,n-1]. Store a fixed tensor B of shape [n-1,n,n], normalized so `(B[k]*B[k]).sum()` is one. (2) Reconstruct with `S=(alpha[..., :, None, None]*B).sum(dim=-3)`, set the diagonal to zero, and use `sigmoid(S[i,j])` for pairwise probabilities or sort a utility vector recovered from the basis coordinates. The simplest equivalent implementation predicts utilities u of shape [batch,n] and computes `S=u[..., :,None]-u[...,None,:]`; the basis form is useful when the paper's sparse or windowed basis is desired. (3) The fixed basis, dimensionality reduction, and cycle guarantee come from the paper; alpha is learned by ordinary backpropagation. For variable-size sets, use a maximum-size basis with a validity mask, or generate an orthonormal centered basis for each n at runtime. (4) First run a synthetic n=32 Bradley-Terry benchmark and a MovieLens pairwise-preference benchmark. Compare the O(n^2) unconstrained pairwise head with the O(n) transitive head at matched hidden width and training steps. Measure parameter count, activation memory, forward latency, pairwise accuracy, ranking regret, and triangle-cycle count. The expected result is zero predicted cycles, substantially lower memory and latency, and comparable or better held-out ranking accuracy when labels contain contradictions. A negative result would be a large clean-data accuracy gap caused by the transitivity assumption.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.