Trading Complexity for Expressivity Through Structured Generalized Linear Token Mixing

• URL: http://arxiv.org/abs/2605.31367v1
• Date: Fri, 29 May 2026 14:38:50 GMT
• Title: Trading Complexity for Expressivity Through Structured Generalized Linear Token Mixing
• Abstract summary: Token mixing layers play a key role in how language models can learn and generate long-range dependencies.<n>This paper explores new trade-offs thanks to a unified framework which separates two crucial features.
• Score: 47.26959210159516
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Token mixing layers play a key role in how language models can learn and generate long-range dependencies. Their efficiency relies on the necessary trade-off between decoding speed and the memory requirements, along with the cache size. Considering causal generation, this paper explores new trade-offs thanks to a unified framework which separates two crucial features: (i) the direct influence of inputs on outputs in one generation step; (ii) the recurrent propagation of information through past outputs. This framework encompasses major architectures such as attention and state-space models, but also generalizes the recurrence equations by allowing each state to depend on multiple past states rather than only the immediate predecessor. By introducing structure, we design new recurrence patterns that provably achieve the desired complexity, while providing theoretical insights on their expressivity -- trading runtime for expressivity in a principled way. Empirical validation is performed on synthetic tasks, along with language modeling. Together, these results provide a unified toolkit for the understanding and design of efficient and expressive token mixers across model families.

Related papers

• UniT: Unified Multimodal Chain-of-Thought Test-time Scaling [85.590774707406]
  Unified models can handle both multimodal understanding and generation within a single architecture, yet they typically operate in a single pass without iteratively refining their outputs.<n>We introduce UniT, a framework for multimodal test-time scaling that enables a single unified model to reason, verify, and refine across multiple rounds.
  arXiv  Detail & Related papers  (2026-02-12T18:59:49Z)
• Understanding and Improving Length Generalization in Hierarchical Sparse Attention Models [33.99822400076112]
  Chunk-based sparse attention has emerged as a promising paradigm for extreme length generalization.<n>We present a systematic dissection of these models to identify the core components driving their performance.<n>We establish a new state-of-the-art for training-free length extrapolation, successfully generalizing models trained on a 4K context to 32 million tokens on RULER and BABILong.
  arXiv  Detail & Related papers  (2025-10-20T06:17:57Z)
• Deconstructing Attention: Investigating Design Principles for Effective Language Modeling [37.92951508140559]
  Transformer language models are widely credited with their dot-product attention mechanism.<n>This work systematically deconstructs attention by designing controlled variants that relax these principles.<n>Surprisingly, even variants that fail in isolation can achieve robust performance when interleaved with standard attention.
  arXiv  Detail & Related papers  (2025-10-13T16:42:14Z)
• Rethinking Transformer Connectivity: TLinFormer, A Path to Exact, Full Context-Aware Linear Attention [0.0]
  This paper introduces a novel linear attention architecture-textbfTLinFormer.<n>By reconfiguring neuron connection patterns, TLinFormer achieves strict linear complexity while computing exact attention scores.<n>We show that TLinFormer exhibits overwhelming advantages in key metrics such as textbfinference latency, textbfKV cache efficiency, and textbfmemory footprint.
  arXiv  Detail & Related papers  (2025-08-28T04:10:19Z)
• Neural Network Reprogrammability: A Unified Theme on Model Reprogramming, Prompt Tuning, and Prompt Instruction [57.19302613163439]
  We introduce neural network reprogrammability as a unifying framework for model adaptation.<n>We present a taxonomy that categorizes such information manipulation approaches across four key dimensions.<n>We also analyze remaining technical challenges and ethical considerations.
  arXiv  Detail & Related papers  (2025-06-05T05:42:27Z)
• Token Reduction Should Go Beyond Efficiency in Generative Models -- From Vision, Language to Multimodality [29.531450446701175]
  This paper argues that token reduction should transcend its traditional efficiency-oriented role in the era of large generative models.<n>We argue that token reduction can facilitate deeper multimodal integration and alignment, maintain coherence over long inputs, and enhance training stability.<n>We outline promising future directions, including algorithm design, reinforcement learning-guided token reduction, token optimization for in-context learning, and broader ML and scientific domains.
  arXiv  Detail & Related papers  (2025-05-23T11:30:30Z)
• Quantifying Memory Utilization with Effective State-Size [73.52115209375343]
  We develop a measure of textitmemory utilization'<n>This metric is tailored to the fundamental class of systems with textitinput-invariant and textitinput-varying linear operators
  arXiv  Detail & Related papers  (2025-04-28T08:12:30Z)
• EnriCo: Enriched Representation and Globally Constrained Inference for Entity and Relation Extraction [3.579132482505273]
  Joint entity and relation extraction plays a pivotal role in various applications, notably in the construction of knowledge graphs. Existing approaches often fall short of two key aspects: richness of representation and coherence in output structure. In our work, we introduce EnriCo, which mitigates these shortcomings.
  arXiv  Detail & Related papers  (2024-04-18T20:15:48Z)
• Real-World Compositional Generalization with Disentangled Sequence-to-Sequence Learning [81.24269148865555]
  A recently proposed Disentangled sequence-to-sequence model (Dangle) shows promising generalization capability. We introduce two key modifications to this model which encourage more disentangled representations and improve its compute and memory efficiency. Specifically, instead of adaptively re-encoding source keys and values at each time step, we disentangle their representations and only re-encode keys periodically.
  arXiv  Detail & Related papers  (2022-12-12T15:40:30Z)
• Bayesian Prompt Learning for Image-Language Model Generalization [64.50204877434878]
  We use the regularization ability of Bayesian methods to frame prompt learning as a variational inference problem. Our approach regularizes the prompt space, reduces overfitting to the seen prompts and improves the prompt generalization on unseen prompts. We demonstrate empirically on 15 benchmarks that Bayesian prompt learning provides an appropriate coverage of the prompt space.
  arXiv  Detail & Related papers  (2022-10-05T17:05:56Z)
• TAGPRIME: A Unified Framework for Relational Structure Extraction [71.88926365652034]
  TAGPRIME is a sequence tagging model that appends priming words about the information of the given condition to the input text. With the self-attention mechanism in pre-trained language models, the priming words make the output contextualized representations contain more information about the given condition. Extensive experiments and analyses on three different tasks that cover ten datasets across five different languages demonstrate the generality and effectiveness of TAGPRIME.
  arXiv  Detail & Related papers  (2022-05-25T08:57:46Z)
• Keyphrase Extraction with Dynamic Graph Convolutional Networks and Diversified Inference [50.768682650658384]
  Keyphrase extraction (KE) aims to summarize a set of phrases that accurately express a concept or a topic covered in a given document. Recent Sequence-to-Sequence (Seq2Seq) based generative framework is widely used in KE task, and it has obtained competitive performance on various benchmarks. In this paper, we propose to adopt the Dynamic Graph Convolutional Networks (DGCN) to solve the above two problems simultaneously.
  arXiv  Detail & Related papers  (2020-10-24T08:11:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.