# Diminishing-Returns Token Selection

- ID: 2129
- Canonical URL: https://synthcore.org/idea/2129/diminishing-returns-token-selection
- API JSON: https://synthcore.org/api/idea/2129.json
- API Markdown: https://synthcore.org/api/idea/2129.md
- Verification status: unverified
- Source: [arXiv:2608.11468](https://arxiv.org/abs/2608.11468)
- Category: regularization
- Solves: accuracy, memory, generalization
- ML areas: attention, transformer, pruning
- Math tags: combinatorics, optimization
- Ratings: usefulness 6/10; difficulty 5/10; novelty 6/10

## Idea description

Give a token, patch, retrieval-item, or expert-selection module a learned utility f_theta(S) over subsets S, and penalize violations of the paper's submodularity and strong-submodularity inequalities. The resulting selector should prefer complementary elements: the marginal value of adding an item decreases when the current selected set is already rich in similar information. At inference, use greedy marginal-gain selection rather than independently thresholding token scores.

## Mathematical statement

For a finite ground set X and subsets A,B subseteq X, the paper defines subadditivity by f(A union B) <= f(A)+f(B), submodularity by f(A union B)+f(A intersection B) <= f(A)+f(B), and strong submodularity by the higher-order alternating inequality sum_{K subseteq {1,...,m}} (-1)^{|K|} f(A_0 union union_{i in K} A_i) <= 0. Here f:2^X -> R is the learned utility of a selected set, A_0,...,A_m are arbitrary subsets, m is the order of the sampled constraint, and K is a subset of indices. For m=1, the inequality is f(A_0)-f(A_0 union A_1) <= 0, which enforces monotonicity. For m=2, it is f(A_0)-f(A_0 union A_1)-f(A_0 union A_2)+f(A_0 union A_1 union A_2) <= 0, an equivalent diminishing-returns form of submodularity. Define the marginal gain Delta_theta(i|S)=f_theta(S union {i})-f_theta(S); submodularity implies Delta_theta(i|A) >= Delta_theta(i|B) whenever A subseteq B and i notin B. Use hinge penalties on sampled violations: L_sub = [f(A union B)+f(A intersection B)-f(A)-f(B)]_+ and L_strong = [sum_K (-1)^{|K|} f(A_0 union union_{i in K} A_i)]_+, where [z]_+=max(z,0).

## Key formulas

- $$f(A\cup B)\leq f(A)+f(B)$$
- $$f(A\cup B)+f(A\cap B)\leq f(A)+f(B)$$
- $$\sum_{K\subseteq\{1,2,\ldots,m\}}(-1)^{|K|}f\left(A_{0}\cup\bigcup_{i\in K}A_{i}\right)\leq 0$$
- $$\mathcal{L}_{\mathrm{sub}}=\left[f_\theta(A\cup B)+f_\theta(A\cap B)-f_\theta(A)-f_\theta(B)\right]_+ + \lambda_{\mathrm{strong}}\left[\sum_{K\subseteq\{1,\ldots,m\}}(-1)^{|K|}f_\theta\left(A_0\cup\bigcup_{i\in K}A_i\right)\right]_+$$

## Implementation notes

Integrate this into a ViT token-pruning module, encoder attention pooling layer, retrieval reranker, or MoE router. For each example, let X={1,...,n} index candidate tokens and let h_i in R^d be their hidden states. Build a set utility f_theta(S) by pooling selected states, for example z_S=sum_{i in S} phi_theta(h_i), f_theta(S)=softplus(rho_theta(z_S, |S|)); subtract a learned or fixed size cost beta|S| if selection must be sparse. During training, sample a base set A0, two or three disjoint increments A1,...,Am, and random subsets A,B from the candidate indices. Evaluate f_theta on all unions required by the inequalities. Add the hinge penalty L_sub above to the task loss. A compact training step is: (1) compute h_1,...,h_n; (2) sample A,B,A0,...,Am; (3) evaluate f_theta on A union B, A intersection B, and every A0 union union_{i in K} Ai; (4) form the two positive-part violations; (5) backpropagate task loss plus lambda_sub L_sub plus lambda_strong L_strong. Estimate no mathematical constants: the inequalities are exact on sampled subsets, while lambda_sub, the maximum order m, and sample count are empirical hyperparameters. At inference, initialize S=emptyset and repeatedly choose i=argmax_{i notin S} Delta_theta(i|S), adding i while the marginal exceeds a threshold or until a budget k is reached. First test on CIFAR-100 or ImageNet-100 with a small DeiT-Tiny: compare standard learned top-k token pruning against this regularized selector at equal kept-token ratios of 25%, 50%, and 75%. Measure validation accuracy, attention FLOPs, selected-token redundancy via pairwise cosine similarity, and the empirical fraction of sampled inequality violations. Success means equal-or-better accuracy at lower token budgets, fewer redundant tokens, and monotone marginal gains during greedy selection.

## Disclaimer

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