Descent-Set Shuffle Composition

Integrate this as an auxiliary composition branch in a Transformer or bidirectional RNN, after two chunks have been encoded and before their representations are pooled or passed to a classifier. For every chunk, compute scalar order scores \(u_i=w^\top h_i\), then adjacent descent probabilities \(s_i=\sigma((u_i-u_{i+1})/\tau)\). Construct a distribution \(p_A(D)\) over binary descent masks by multiplying Bernoulli factors \(\prod_{i\in D}s_i\prod_{i\notin D}(1-s_i)\), retaining masks with at most \(K\) descents and renormalizing. For lengths \(A,B\leq 8\), precompute \(M_{A,B}(D,E,F)\): choose canonical numeric representatives with descent sets \(D\) and \(E\), enumerate every binary interleaving path containing \(A\) symbols of type 1 and \(B\) of type 2, merge the representatives, compute its descent mask, and increment the corresponding count. The shuffle product is implemented as r[F] += p[D] * q[E] * M[D,E,F], followed by normalization and projection through a learned matrix \(W_D\). Add \(W_Dr\) to the ordinary concatenation representation. For longer chunks, estimate \(M\) using 256-1024 sampled interleavings and frequency counts. If the merged chunk is available, compute its direct distribution \(r_{direct}\) and add \(\lambda\mathcal L_{shuffle}\); otherwise use only the projected shuffle representation. First test on a synthetic task where two labeled sequences are randomly interleaved and the model predicts the source ordering rule. Compare a 2-layer Transformer baseline against the augmented model at equal hidden size and FLOPs. Success means higher accuracy on unseen interleaving distributions and improved accuracy with 5-10 times less training data; randomizing descent masks should remove the gain.