# 2-System Greedy Token Selection

- ID: 1944
- Canonical URL: https://synthcore.org/idea/1944/2-system-greedy-token-selection
- API JSON: https://synthcore.org/api/idea/1944.json
- API Markdown: https://synthcore.org/api/idea/1944.md
- Verification status: unverified
- Source: [arXiv:2608.07413](https://arxiv.org/abs/2608.07413)
- Category: architecture
- Solves: speedup, memory, accuracy
- ML areas: attention, transformer, inference-speedup
- Math tags: combinatorics, optimization, information-theory
- Ratings: usefulness 6/10; difficulty 5/10; novelty 6/10

## Idea description

Replace top-k token pruning by greedy maximization of a diversity-aware monotone submodular utility under a spacing or coverage constraint. The selector repeatedly chooses the feasible token with the largest marginal utility, avoiding the redundant-token failure mode of independent score ranking while inheriting a constant-factor approximation guarantee under the stated 2-system abstraction.

## Mathematical statement

The paper represents a discrete configuration by an integer-valued position vector \(\mathbf v=[v_1,\ldots,v_{N_{\mathrm{BS}}}]\in\mathbb N^{1\times N_{\mathrm{BS}}}\), with each \(v_m\in\{1,\ldots,N_{\mathrm S}\}\), and states that its objective is monotone submodular maximization subject to a 2-system constraint. For the neural adaptation, let \(U\) be the candidate token set, \(S\subseteq U\) the selected tokens, and \(f:2^U\to\mathbb R_{\ge0}\) the utility. Monotonicity means \(A\subseteq B\Rightarrow f(A)\le f(B)\); submodularity means diminishing returns: \(f(A\cup\{x\})-f(A)\ge f(B\cup\{x\})-f(B)\) for \(A\subseteq B\) and \(x\notin B\). Define \(\Delta(x\mid S)=f(S\cup\{x\})-f(S)\). A feasible family \(\mathcal F\) is a 2-system when, for every ground-set subset, the cardinalities of maximal feasible subsets differ by at most a factor of 2. The paper's greedy result gives \(f(S_{\mathrm{greedy}})\ge\frac13 f(S^*)\), where \(S^*\) is the optimal feasible subset. Use the concrete monotone submodular utility \(f(S)=\log\det(I_d+\tau^{-1}E_SE_S^\top)\), where \(E_S\) contains selected token embeddings, \(d\) is embedding dimension, and \(\tau>0\) is a regularizer.

## Key formulas

- $$\mathbf v=[v_1,v_2,\ldots,v_{N_{\mathrm{BS}}}]\in\mathbb N^{1\times N_{\mathrm{BS}}},\qquad v_m\in\{1,2,\ldots,N_{\mathrm S}\}.$$
- $$\Delta(x\mid S)=f(S\cup\{x\})-f(S),\qquad A\subseteq B,\ x\notin B\ \Longrightarrow\ \Delta(x\mid A)\ge \Delta(x\mid B).$$
- $$S_{t+1}=S_t\cup\left\{\arg\max_{x\in U\setminus S_t:\ S_t\cup\{x\}\in\mathcal F}\Delta(x\mid S_t)\right\},$$
- $$f(S_{\mathrm{greedy}})\ge \frac{1}{3}f(S^*),\qquad f(S)=\log\det\!\left(I_d+\tau^{-1}E_SE_S^\top\right).$$

## Implementation notes

Integrate this at the input of a ViT or multimodal transformer, immediately after patch or token embeddings are computed and before the expensive self-attention blocks. Given a sequence of N candidate embeddings e_i in R^d, select at most K tokens while enforcing a diversity constraint: a candidate is feasible only if it is at least w sequence positions from every selected token, or, in a semantic variant, has cosine similarity below a threshold with every selected token. Initialize S as the empty set and G as I_d. At each iteration, scan feasible candidates and compute the rank-one log-determinant marginal delta_i = log(1 + tau^{-1} e_i^T G^{-1} e_i). Select the candidate with largest delta_i, add it to S, and update G <- G + tau^{-1} e_i e_i^T. Stop at K tokens or when no candidate remains feasible. Use Cholesky rank-one updates rather than explicitly inverting G. The paper contributes the diminishing-returns greedy rule and the 1/3 guarantee under a 2-system; the implementation estimates utility from current token embeddings. For imperfect or noisy embeddings, average each candidate's marginal over two stochastic augmentations or maintain an exponential moving average of marginals. First test on CIFAR-100 with DeiT-Tiny or ViT-Tiny, retaining 25%, 50%, and 75% of patches. Compare against random pruning, learned top-k gates, and cosine-diversity greedy at equal selector FLOPs. Success means higher accuracy at a fixed retained-token count, equal accuracy with at least 1.5x lower attention FLOPs, and lower selection variance across augmentations.

## Disclaimer

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