O(N) Complexity and Beyond: A Glimpse into the Future of Efficient AI/ML

Latest 54 papers on computational complexity: May. 9, 2026

The quest for efficiency is a perennial challenge in AI/ML, especially as models grow in complexity and data scales. High computational costs, often scaling quadratically or even exponentially with input size or problem dimensions, limit real-world deployment and scientific exploration. But what if we could break these barriers? Recent research is pushing the boundaries, demonstrating breakthroughs that achieve linear (O(N)) or even sub-linear complexity, opening doors to previously intractable problems. This post dives into these exciting advancements, synthesizing insights from a collection of cutting-edge papers that promise a more scalable, robust, and accessible future for AI/ML.

The Big Idea(s) & Core Innovations

At the heart of these advancements lies a common theme: smart approximations and structural exploitation that allow complex operations to be re-envisioned with dramatically reduced computational footprints. Instead of brute-force computations, researchers are leveraging fundamental mathematical properties, architectural innovations, and biologically inspired mechanisms to achieve efficiency without sacrificing performance.

For instance, the paper “Nora: Normalized Orthogonal Row Alignment for Scalable Matrix Optimizer” by Jinghui Yuan, Jiaxuan Zou, et al. from Northwestern Polytechnical University, Xi’an Jiaotong University, and others, introduces a novel optimizer for LLM training that achieves O(mn) complexity. Their key insight is using row-wise projection of momentum and normalization to approximate Muon-like preconditioning, delivering up to 71x speedup over Newton-Schulz methods. Similarly, “ITS-Mina: A Harris Hawks Optimization-Based All-MLP Framework with Iterative Refinement and External Attention for Multivariate Time Series Forecasting” by Pourya Zamanvaziri et al. from Shahid Beheshti University demonstrates that an all-MLP architecture with iterative refinement and external attention can achieve state-of-the-art time series forecasting with linear complexity, effectively replacing quadratic self-attention mechanisms. Their innovative shared-parameter residual mixer allows for deep computation without parameter explosion.

In the realm of multi-agent systems, “Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamics” by Philip Jordan and Maryam Kamgarpour from SYCAMORE, EPFL tackles the multi-agency curse. They propose an independent learning algorithm that achieves quasi-polynomial complexity, avoiding exponential scaling with the number of players by leveraging decoupled dynamics and filter stability to approximate POMGs with finite-window policies. This is a significant step towards practical multi-agent reinforcement learning.

Another striking example is “Efficient Traffic Forecasting on Large-Scale Road Network by Regularized Adaptive Graph Convolution” by Kaiqi Wu et al. from Sun Yat-Sen University. They present RAGC, which introduces the Efficient Cosine Operator (ECO) to perform graph convolutions with linear O(N) complexity, a dramatic improvement over the traditional O(N^2) of standard graph convolution operations. This is crucial for large-scale road networks. Similarly, “SCGNN: Semantic Consistency enhanced Graph Neural Network Guided by Granular-ball Computing” by Genhao Tian et al. from JiangSu University of Science and Technology uses granular-ball computing (GBC) to reduce graph preprocessing from quadratic O(n²d) to near-linear O(ndkt), allowing GNNs to scale to millions of nodes where k-NN would fail.

For graph similarity, “Efficient Accelerated Graph Edit Distance Computation on GPU” by Adel Dabah and Andreas Herten from Jülich Supercomputing Center achieves 300x speedup over CPU baselines for the NP-hard Graph Edit Distance problem using a K-Best search tree and clever GPU mapping. This makes GED-based applications practical. In a similar vein, “Fast and Faithful Edge Bundling using Spectral Sparsification” by Xingjue Jiang et al. from the University of Sydney speeds up graph visualization by 61% through spectral sparsification, demonstrating that leveraging graph theory can significantly improve efficiency while maintaining fidelity.

“Linear-Time Global Visual Modeling without Explicit Attention” by Ruize He et al. from Tsinghua University challenges the necessity of explicit attention. Their WeightFormer architecture reinterprets attention as a dynamic MLP, achieving Transformer-level global modeling with linear complexity by compressing global context into dynamically predicted parameters. This offers a compelling alternative to quadratic self-attention. Further pushing the boundaries of efficient vision, “SAMIC: A Lightweight Semantic-Aware Mamba for Efficient Perceptual Image Compression” by Jiaqian Zhang et al. from Xi’an Jiaotong University utilizes Mamba state space models and semantic-aware scanning for image compression, achieving state-of-the-art perceptual quality with only 25M parameters and linear complexity.

Hybrid approaches are also proving critical. “Geometry-Aware State Space Model: A New Paradigm for Whole-Slide Image Representation” by Enhui Chai et al. from PuzzleLogic Pte Ltd and University of California, Irvine introduces BatMIL, a framework for whole-slide image classification that combines hybrid hyperbolic-Euclidean geometry with a structured state space model (S4) backbone and Mixture-of-Experts (MoE) routing. This allows for linear complexity in modeling long-range dependencies while adaptively handling regional heterogeneity in gigapixel images.

In numerical linear algebra, “Finding accurate eigenvalues and eigenvectors of positive semi-definite matrices given a subspace” by Yuji Nakatsukasa and Zheng Tang from the University of Oxford shows Nyström’s method can be arbitrarily more accurate than Rayleigh-Ritz for leading eigenvalues of PSD matrices with fast-decaying spectra, all while maintaining the same O(Nk + nk²) complexity. This insight is crucial for kernel methods in ML.

Even in quantum cryptography, the paper “Fundamental Limitations of Post-Quantum Cryptographic Architectures” by Jiho Jung et al. from Seoul National University highlights that the security of LWE-based cryptography relies on transient engineering limitations (like QRAM costs) rather than impenetrable theoretical foundations. This fundamental reassessment of computational security at the quantum level points to the critical role of understanding complexity even in future computational paradigms.

Under the Hood: Models, Datasets, & Benchmarks

These innovations are often driven by, and in turn contribute to, a rich ecosystem of models, datasets, and benchmarks. Here’s a snapshot of some key resources highlighted by these papers:

• Models & Frameworks:
  • Nora Optimizer: A novel matrix-based optimizer, providing a reference implementation in Section C of its paper. (Paper Link)
  • ITS-Mina: An all-MLP framework for time series forecasting, using iterative refinement and external attention.
  • PACMAB: A decentralized perception-aware combinatorial multi-armed bandit learning solution for mobile crowdsensing. (Paper Link)
  • BatMIL: A Multiple Instance Learning framework for whole-slide image classification, combining S4 state space models and MoE routing. Leverages foundation models like UNI and Virchow2. (Paper Link)
  • SCGNN: A plug-and-play GNN framework integrating granular-ball computing, compatible with various GNN backbones (GCN, GAT, GIN, etc.).
  • WeightFormer: An architecture that replaces attention with dynamic parameters for linear-time global visual modeling. Code: https://github.com/LeapLabTHU/WeightFormer
  • SAMIC: A Mamba-based perceptual image compression framework with semantic-aware scanning. Code: https://github.com/Jasmine-aiq/SAMIC
  • ENFORCE: A neural network architecture with an adaptive projection module (AdaNP) for enforcing nonlinear constraints. Code: https://github.com/process-intelligence-research/ENFORCE (and pip install enforce-nn)
  • FAST-GED: A GPU-accelerated framework for Graph Edit Distance computation. Code: https://gitlab.jsc.fz-juelich.de/dabah2/fast-ged/-/tree/main
  • RAGC: A Regularized Adaptive Graph Convolution approach for efficient traffic forecasting. Code: https://github.com/wkq-wukaiqi/RAGC
  • FUN (Focal U-Net): An end-to-end framework for joint hyperspectral image reconstruction and object detection. Code and dataset: https://github.com/ShawnDong98/FUN
  • SRGAN-CKAN: A hybrid super-resolution framework integrating Convolutional Kolmogorov-Arnold Networks. Code: https://github.com/RINavarro/SRGAN-CKAN
  • FiLMMeD: A neural-based model for Multi-Depot Vehicle Routing Problem variants using Feature-wise Linear Modulation. Code: https://github.com/AJ-Correa/FiLMMeD/tree/main
  • TreeBO: A Bayesian optimization method with recursive binary partitioning for linear time complexity. (Paper Link)
  • AECM Algorithm: An Alternating Expectation-Conditional Maximization algorithm for deterministic ML direction finding. (Paper Link)
  • CT-Lite: A framework for efficient medical image analysis on JPEG-compressed CT volumes. Uses Feature Attention Style Transfer and Structured Factorized Projections. (Paper Link)
  • Structured Recurrent SNNs: A multi-layer recurrent SNN architecture with local plasticity and modulatory populations. (Paper Link)
  • DOERL: The first doubly oracle-efficient reinforcement learning algorithm. (Paper Link)
• Datasets & Benchmarks:
  • WSI Datasets: CAMELYON16/17, PANDA, TCGA-BLCA/BRCA/CESC/NSCLC (BatMIL).
  • Graph Datasets: Cora, CiteSeer, PubMed, Wiki, Physics, ogbn-arxiv/products (SCGNN); CMU Face, IAM Graph Database, Mutagenicity (FAST-GED); Augsburg, Berlin, Houston2013 (RSCNet).
  • Time Series Datasets: Traffic, Electricity, ETTh1/2, ETTm1/2 (ITS-Mina); LargeST dataset (https://github.com/LiTiD/Leeds/blob/master/README.md) (RAGC).
  • Medical Image Datasets: CT-RATE, NIDCH, RAD-ChestCT (CT-Lite).
  • Recommender Systems Datasets: Beauty, Fashion, Games, Books (ConvRec).
  • Video Datasets: KTH Action Dataset (Opto-Atomic Spatio-Temporal Holographic Correlators).
  • Natural Language Processing Datasets: Multi-CounterFact (MCF), ZsRE (Forward Replay).
  • Wireless Communication Datasets: DeepMIMO (https://deepmimo.net/) (Benchmarking Wireless Representations, Data-driven approach for Outdoor Channel Prediction).

Impact & The Road Ahead

These research efforts collectively paint a vibrant picture of a future where AI/ML is not just powerful, but also practically efficient. The ability to manage computational complexity effectively, scaling from large-scale road networks and gigapixel medical images to real-time robotics and fundamental cryptographic security, will democratize access to advanced AI and accelerate scientific discovery.

The implications are far-reaching:

• Democratization of AI: Linear and sub-linear complexity algorithms make advanced models accessible on more modest hardware, lowering barriers for researchers and developers.
• Real-time Applications: From bipedal walking robots operating at 100 Hz (“Right Model, Right Time: Real-Time Cascaded-Fidelity MPC for Bipedal Walking” by Franek Stark et al. from DFKI) to near real-time cardiac diagnostics (“A Neural Latent Dynamics Approach for Solving Inverse Problems in Cardiac Electrophysiology” by Edoardo Centofanti et al. from the University of Pavia), efficiency is paramount for impactful real-world systems.
• Sustainable AI: Reduced computational load translates directly to lower energy consumption, contributing to more environmentally friendly AI deployments.
• Fundamental Understanding: The computational lens proposed in “Computational foundations of the human world” by Marcus J. Hamilton et al. from the University of Texas at San Antonio suggests that understanding computational constraints might be key to understanding human social systems themselves. Meanwhile, the exploration of fundamental limitations in post-quantum cryptography highlights the ongoing critical need to examine the very foundations of computational security.
• Enhanced Reliability: Robustness to noise and data scarcity, as seen in “Benchmarking Wireless Representations: High-Dimensional vs. Compressed Embeddings for Efficiency and Robustness” by Murilo Batista et al. from RWTH Aachen University, is vital for deploying AI in unpredictable environments.

The road ahead involves further exploring hybrid models, exploiting inherent data structures (like sparsity and low-rank properties), and developing more advanced theoretical frameworks that connect efficiency with underlying mathematical principles. As AI continues to permeate every aspect of our lives, the focus on computational complexity will only intensify, driving us toward ever more powerful and performant systems that truly understand the right model for the right time, at the right computational cost. The future of AI is not just about intelligence, but about intelligent efficiency.

Please leave this field empty

Hi there 👋

Get a roundup of the latest AI paper digests in a quick, clean weekly email.

Check your inbox or spam folder to confirm your subscription.