Signed Block-Aggregation Attention

1. Integration point: apply the construction to the value aggregation operation of a binary-mask attention or graph message-passing layer, after Q/K similarity has produced a Boolean interaction mask A and before the output projection. Do not put signed masks directly inside standard softmax attention; initially use linear attention or signed message passing, where the desired operation is multiplication of A by V. 2. Pseudocode: inputs are Boolean A in R^{n x m}, values V in R^{m x d}, and target decomposition length L_max. For i from 1 to L_max, find a blocky mask B_i and sign sigma_i by minimizing ||A - sum_i sigma_i B_i||_F^2 + lambda times the number of rectangles. Enforce blockiness by representing B_i with row labels r_i[x] in {-1,0,...} and column labels c_i[y] in {-1,0,...}; permit rectangle k only between rows with label k and columns with label k, with each label used at most once on each side. In the forward pass, initialize O=0. For every i and rectangle (X,Y) in B_i, compute S = sum_{y in Y} V[y] and add sigma_i S to every row x in X. 3. The disjoint-rectangle constraint and signed reconstruction come from the paper. Estimate gamma using a small semidefinite relaxation or a low-rank factorization proxy, for example gamma_proxy = min_{A approximately UV^T} max_x ||U_x||_2 times max_y ||V_y||_2. The decomposition algorithm is empirical because the supplied theorem does not specify one. 4. First experiment: use n=m=512 synthetic masks formed from rectangle unions, then masks obtained by thresholding attention logits in a small Transformer on CIFAR-10 patches or a long-range sequence task. Compare dense aggregation, CSR sparse aggregation, and block aggregation at matched reconstruction error. Measure wall-clock time, peak memory, output error, and validation accuracy as L_max varies from 1 to 32. Success means at least 1.5x lower aggregation cost or 2x lower mask-memory usage at equal task accuracy, with reconstruction error below 1e-3 for synthetic masks. If discovered L is consistently large, the theorem has limited practical value for that mask family.