# Boxicity-guided constraint attention

- ID: 238
- Canonical URL: https://synthcore.org/idea/238/boxicity-guided-constraint-attention
- API JSON: https://synthcore.org/api/idea/238.json
- API Markdown: https://synthcore.org/api/idea/238.md
- Verification status: unverified
- Source: [arXiv:2608.27381](https://arxiv.org/abs/2608.27381)
- Category: architecture
- Solves: accuracy, scalability, stability
- ML areas: attention, graph-nn, moe-routing
- Math tags: graph-theory, combinatorics, geometry
- Ratings: usefulness 5/10; difficulty 5/10; novelty 8/10

## Idea description

Replace an unconstrained pairwise attention score with an intersection of coordinate-wise threshold or interval compatibility heads. Each head is a supergraph that permits pairs satisfying one constraint, while the final attention edge exists only when every head permits the pair. This provides an interpretable inductive bias for multi-constraint relations and prevents the model from approximating a conjunction using a single unstable nonlinear score.

## Mathematical statement

Lemma 2 states that a graph G has boxicity at most d exactly when there are interval graphs I_1,...,I_d on the same vertex set such that E(G)=intersection over j of E(I_j); each I_j is a supergraph of G. Definition 3 defines a threshold graph T(alpha,S) on vertex set V by {v,w} in E(T) if and only if alpha(v)+alpha(w)>=S, where alpha:V->R is a scalar vertex score and S is a threshold. The paper studies the graph D(m) whose vertices are bounded integer vectors x=(x_1,...,x_n), with 0<=x_i<=m_i, excluding the all-zero and all-m_i vectors, and whose zero-product adjacency is represented by x~y if and only if x_i+y_i>=m_i for every coordinate i. Lemma 41 gives boxicity(D(m))>=n-1 except for a small degenerate case, and the paper exhibits an induced n-fold join of two-vertex independent sets: for each i, x^i and y^i are non-adjacent, while every vertex from pair i is adjacent to every vertex from pair j whenever i!=j. We use these facts as an architectural rule: a conjunction of n independent compatibility constraints should receive at least n-1 separate heads, rather than being compressed into one scalar pair score.

## Key formulas

- $$E(G)=\bigcap_{j=1}^{d}E(I_j),$$
- $$\{v,w\}\in E\bigl(T(\alpha,S)\bigr)\iff \alpha(v)+\alpha(w)\geq S,$$
- $$x\sim y\iff \forall k\in[n],\;x_k+y_k\geq m_k,$$
- $$\operatorname{boxicity}(D(\mathbf m))\geq n-1\qquad\left(\mathbf m\neq\mathbf 1_2,\;n\geq2\right).$$

## Implementation notes

1. Integration point: modify the pairwise attention mask or MoE router before softmax. Given token or set embeddings h_i, create d scalar coordinate embeddings z_i in R^d with z_i,k=m_k sigmoid(MLP_k(h_i)); choose d heads, preferably d>=n-1 for an n-constraint task. Head k computes a pair compatibility score c_ijk=(z_i,k+z_j,k-m_k)/tau_k, where tau_k>0 is learned or fixed. The hard version accepts a pair only when c_ijk>=0 for every k; the soft version adds a conjunction bias b_ij=-lambda sum_k softplus(-c_ijk) to the attention logits. Pseudocode: z=clamp(m*sigmoid(proj(h)),0,m); for k in 1..d: c[:,:,k]=(z[:,None,k]+z[None,:,k]-m[k])/tau[k]; penalty=sum(softplus(-c),axis=-1); logits=QK^T/sqrt(d_model)-lambda*penalty; logits=masked_fill((c>=0).all(-1), -inf) only during an optional hard-mask phase; output=softmax(logits)V. 2. The mathematical component is the coordinate-wise threshold relation and its edge-wise intersection. Estimate the useful number of heads empirically by training d in {1, n-1, n, 2n}; do not assume the lower bound applies to arbitrary learned relations. Monitor the fraction of pairs satisfying each constraint and the entropy of the final mask. 3. First experiment: use synthetic set-intersection or resource-allocation classification. Represent each item by an n-dimensional bounded integer vector and label pairs positive exactly when x_k+y_k>=m_k for all k. Compare a standard single MLP pair scorer, ordinary dot-product attention, and the proposed d-head module at equal parameter count. Test n=4,8,16 and noisy continuous inputs. Success means higher held-out accuracy under coordinate permutations, sharper calibration of positive and negative pair probabilities, and lower sample count needed to reach 99% accuracy. For a graph-neural-network version, use the learned conjunction as the adjacency mask and measure accuracy and memory against dense message passing. The expected practical benefit is strongest when valid interactions are sparse: report the fraction of masked pairs and wall-clock attention speed after block-sparse conversion, while checking that hard masking does not disconnect useful tokens.

## Disclaimer

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