O(N) and Beyond: Cracking the Code of Computational Complexity in AI/ML

Latest 34 papers on computational complexity: Jul. 25, 2026

Computational complexity remains a critical bottleneck across AI and ML, influencing everything from model deployability on edge devices to the tractability of fundamental problems. Recent research is pushing the boundaries, developing ingenious methods to achieve greater efficiency, faster inference, and even breakthrough performance with reduced complexity. This digest explores several exciting advancements that are redefining what’s possible in the world of efficient AI.

The Big Idea(s) & Core Innovations

The overarching theme in this collection of papers is a relentless pursuit of efficiency without sacrificing performance, often achieved through clever architectural design, novel algorithms, and a deeper understanding of computational bottlenecks. One significant thrust is the linearization of complexity in traditionally quadratic operations, especially in attention mechanisms and multi-scale data processing. For instance, Alibaba International Digital Commerce and their collaborators, in their paper “LISA: Linear-Indexed Sparse Attention for Efficient Long-Context Reasoning”, introduce LISA, a hybrid attention module that combines global linear attention with fixed-size sparse self-attention. This innovative approach achieves a remarkable 50% inference speedup at 16K context lengths and a 5.6% accuracy improvement on mathematical reasoning tasks by reducing complexity from O(n²) to O(nM), where M << n. They highlight that linear and sparse attention are anti-correlated, providing complementary information that can be effectively fused.

Similarly, in time series forecasting, the “M2Patch: Structured Latent Space Modeling over Multi-Scale Temporal Patches for Multivariate Time Series Forecasting” by Xingsheng Chen and colleagues from the University of Hong Kong, replaces quadratic self-attention with depthwise separable convolutions and progressive dilation. This architecture achieves state-of-the-art performance across 10 benchmarks with linear computational complexity, proving that efficient CNN-based designs can outperform transformer-based models for certain tasks. Extending this, the “HyBDM: Multi-Scale Hybrid Experts for Time Series Forecasting with Bidirectional Dependency Modeling” from Soul of Harlequin Lab introduces a multi-scale hybrid model combining a BiConv-Mamba for global patterns and a Local Window Transformer for local variations, also maintaining linear O(L) complexity while outperforming many quadratic alternatives.

Another innovative trend is the use of approximate computing and quantization for extreme efficiency, particularly for edge devices. F. Bulten et al. from the University of Twente, in “Toward Energy-Efficient and Low-Power Arrhythmia Detection for Wearable Devices”, demonstrate that 8-bit precision and approximate multipliers with symmetrical error distributions can reduce power consumption in arrhythmia detection by 64.9% while maintaining high accuracy, even exceeding cardiologist sensitivity. This is a powerful insight: for some applications, lower precision can act as implicit regularization, improving performance while drastically cutting energy usage. In a similar vein, “Efficient Audio-Visual Event Recognition via Knowledge Distillation and Dynamic INT8 Quantization” by Parinaz Binandeh Dehaghani et al. from the University of Porto, achieves over 80% model size reduction and 59% parameter reduction for audio-visual event recognition through architectural compression, knowledge distillation, and dynamic INT8 quantization, making it suitable for resource-constrained edge AI.

Addressing fundamental theoretical challenges, Cornelius Brand and collaborators from Vienna University of Technology, in “New Complexity-Theoretic Frontiers of Tractability for Neural Network Training”, present polynomial-time algorithms for training constant-size ReLU networks with specific structural properties (out-degree at most 1). They even introduce a “blow-up” transformation that makes any constant-size ReLU architecture efficiently trainable, pushing the boundaries of tractability significantly. This work suggests that carefully structured networks, even if deep, can be trained optimally in polynomial time, challenging long-held assumptions about network training complexity.

Under the Hood: Models, Datasets, & Benchmarks

These advancements are often built upon or validated against crucial resources, models, and benchmarks:

• LISA: Tested on mathematical reasoning benchmarks like GSM8K, MATH-500, AMC23, and AIME using distilled DeepSeek-R1 Qwen models.
• M2Patch: Utilizes depthwise separable convolutions with exponentially growing dilation, validated across 10 real-world benchmarks. Code available: https://github.com/XsChen524/m2patch.
• HyBDM: Combines BiConv-Mamba and Local Window Transformer, extensively evaluated on six benchmarks including ETTh, Weather, and Traffic datasets. (No public code link provided in summary).
• Arrhythmia Detection: Based on approximate multipliers and 8-bit precision, evaluated using the MIT-BIH Arrhythmia Database.
• Audio-Visual Event Recognition: Employs a lightweight student architecture, VideoMAE for visual features, and AST for audio, tested on the AVE dataset.
• EGRNet (Semantic Segmentation): Features a novel Edge-Gated Refinement module and depthwise separable convolutions, achieves 65.28% mIoU on the Cityscapes dataset with just 0.46M parameters.
• SEMA (Vision Transformers): Proves attention dispersion and combines window attention with arithmetic averaging for global context. Achieves strong performance on ImageNet-1K, COCO 2017, and ADE20K. Code: https://github.com/nhatthanhtran/SEMA.
• Jetson-PI (Robotics): Employs Foresight-Aligned Asynchronous Correction for real-time VLA robot control on Jetson Orin, achieving 14.8% success rate improvement over VLASH on the LIBERO benchmark. Code: https://github.com/PKU-SEC-Lab/Jetson-PI and https://github.com/PKU-SEC-Lab/Jetson-PI-Edge.
• Sarus (Privacy-Preserving Perception): Leverages CKKS homomorphic encryption and Gaussian moment vectors for multi-vendor AV perception fusion, validated on the KITTI dataset. Code: https://github.com/mhasan08/sarus.
• Randomized Kronecker Tensor Decomposition: Introduces randomized SVDs into the TTr1SVD framework, with rigorous error analysis and speedups on synthetic and real-world datasets. Code: https://github.com/kbatseli/TKPSVD.
• DLMP-Based Bilevel Coordination: Uses a novel normal-minus-beta distribution for net-demand uncertainty in microgrid EV charging, validated on the IEEE 33-bus system with Gurobi solver.
• AI-Driven Multi-Hop Relay Selection: Uses edge-aware GINE (Graph Neural Networks) trained on MILP optimal labels via SUMO simulations and GEMV2 propagation model. Tested on 286,602 urban vehicular graph snapshots.
• Predictive Process Monitoring: Features a control-flow-aware segmentation algorithm and segment-level SHAP values, evaluated on synthetic (SimBank) and real-world event logs (BPIC17, BPIC15). Code: https://github.com/kSahatova/segment-level-expl-PPM.git.
• Unlearnable Data (Survey): A comprehensive review with a taxonomy and a public repository: https://github.com/LiJiahao-Alex/Awesome-UnLearnable-Data.
• Token Reduction for VPR: First systematic benchmark of token reduction on vision transformers for Visual Place Recognition, using DINOv2 on multiple datasets. Code: https://github.com/Tong-Jin01/TokenReduction4VPR.

Impact & The Road Ahead

The impact of this research is profound, touching nearly every facet of AI/ML deployment. The advancements in linearizing attention mechanisms and multi-scale modeling (LISA, M2Patch, HyBDM, SEMA) promise to unlock the potential of large models for real-time applications and longer context windows, moving beyond the prohibitive O(N²) barrier. For embedded systems and wearable devices, the breakthroughs in approximate computing (Arrhythmia Detection, Audio-Visual Event Recognition) and lightweight architectures (EGRNet, MambaPSA) mean that sophisticated AI capabilities can be deployed in resource-constrained environments, enabling continuous health monitoring, efficient autonomous vehicles, and advanced edge AI. The theoretical insights into tractability (Neural Network Training, Odd Domination, Graph Edit Distance) offer a blueprint for designing fundamentally more efficient algorithms and understanding the limits of computation, guiding future architectural choices. Furthermore, the development of explainable (Audio Deepfake Detection, Process Monitoring) and privacy-preserving (Sarus) methods fosters trust and broader adoption of AI in sensitive domains. Finally, the novel optimization techniques for complex systems (Min-Max Regret Task Allocation, Learning-enabled Acceleration of Scenario-based MPC, Low-Complexity Channel Estimation) highlight a future where AI itself is used to optimize its own deployment and solve large-scale real-world problems more effectively.

The road ahead involves further integrating these innovations, perhaps combining architectural tractability guarantees with approximate computing for ultra-efficient, provably optimal AI systems. The arms race between Unlearnable Data and adversarial defenses will continue to shape secure ML. As models grow, these complexity-aware strategies will not just be an advantage but a necessity, paving the way for ubiquitous, responsible, and powerful AI that scales to truly global challenges.

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.