The Serial Scaling Hypothesis

• URL: http://arxiv.org/abs/2507.12549v1
• Date: Wed, 16 Jul 2025 18:01:26 GMT
• Title: The Serial Scaling Hypothesis
• Authors: Yuxi Liu, Konpat Preechakul, Kananart Kuwaranancharoen, Yutong Bai,
• Abstract summary: Inherently serial problems require dependent computational steps that cannot be parallelized.<n>We argue that recognizing the serial nature of reasoning holds profound implications on machine learning, model design, hardware development.<n>As AI tackles increasingly complex reasoning, deliberately scaling serial computation-not just parallel computation-is essential for continued progress.
• Score: 8.375582694104923
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While machine learning has advanced through massive parallelization, we identify a critical blind spot: some problems are fundamentally sequential. These "inherently serial" problems-from mathematical reasoning to physical simulations to sequential decision-making-require dependent computational steps that cannot be parallelized. Drawing from complexity theory, we formalize this distinction and demonstrate that current parallel-centric architectures face fundamental limitations on such tasks. We argue that recognizing the serial nature of computation holds profound implications on machine learning, model design, hardware development. As AI tackles increasingly complex reasoning, deliberately scaling serial computation-not just parallel computation-is essential for continued progress.

Related papers

• A Quantum Computational Perspective on Spread Complexity [0.0]
  We establish a direct connection between spread complexity and quantum circuit complexity by demonstrating that spread complexity emerges as a limiting case of a circuit complexity framework built from two fundamental operations: time-evolution and superposition.<n>Our approach leverages a computational setup where unitary gates and beam-splitting operations generate target states, with the minimal cost of synthesis yielding a complexity measure that converges to spread complexity in the infinitesimal time-evolution limit.
  arXiv  Detail & Related papers  (2025-06-08T19:04:42Z)
• Computational Thinking Reasoning in Large Language Models [69.28428524878885]
  Computational Thinking Model (CTM) is a novel framework that incorporates computational thinking paradigms into large language models (LLMs)<n>Live code execution is seamlessly integrated into the reasoning process, allowing CTM to think by computing.<n>CTM outperforms conventional reasoning models and tool-augmented baselines in terms of accuracy, interpretability, and generalizability.
  arXiv  Detail & Related papers  (2025-06-03T09:11:15Z)
• Accelerate Parallelizable Reasoning via Parallel Decoding within One Sequence [0.0]
  We leverage the inherent parallelizability of certain tasks to accelerate the reasoning process.<n> Experimental results show that our method achieves over 100% speedup in decoding time while maintaining the answer quality.
  arXiv  Detail & Related papers  (2025-03-26T13:28:57Z)
• PromptCoT: Synthesizing Olympiad-level Problems for Mathematical Reasoning in Large Language Models [59.920971312822736]
  We introduce PromptCoT, a novel approach for automatically generating high-quality Olympiad-level math problems.<n>The proposed method synthesizes complex problems based on mathematical concepts and the rationale behind problem construction.<n>Our method is evaluated on standard benchmarks including GSM8K, MATH-500, and AIME2024, where it consistently outperforms existing problem generation methods.
  arXiv  Detail & Related papers  (2025-03-04T06:32:30Z)
• When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
  We propose complexity-impacted reasoning score (CIRS) to measure correlation between code and reasoning abilities. Specifically, we use the abstract syntax tree to encode the structural information and calculate logical complexity. Code will be integrated into the EasyInstruct framework at https://github.com/zjunlp/EasyInstruct.
  arXiv  Detail & Related papers  (2023-08-29T17:22:39Z)
• Faith and Fate: Limits of Transformers on Compositionality [109.79516190693415]
  We investigate the limits of transformer large language models across three representative compositional tasks. These tasks require breaking problems down into sub-steps and synthesizing these steps into a precise answer. Our empirical findings suggest that transformer LLMs solve compositional tasks by reducing multi-step compositional reasoning into linearized subgraph matching.
  arXiv  Detail & Related papers  (2023-05-29T23:24:14Z)
• The Basis of Design Tools for Quantum Computing: Arrays, Decision Diagrams, Tensor Networks, and ZX-Calculus [55.58528469973086]
  Quantum computers promise to efficiently solve important problems classical computers never will. A fully automated quantum software stack needs to be developed. This work provides a look "under the hood" of today's tools and showcases how these means are utilized in them, e.g., for simulation, compilation, and verification of quantum circuits.
  arXiv  Detail & Related papers  (2023-01-10T19:00:00Z)
• A Stable, Fast, and Fully Automatic Learning Algorithm for Predictive Coding Networks [65.34977803841007]
  Predictive coding networks are neuroscience-inspired models with roots in both Bayesian statistics and neuroscience. We show how by simply changing the temporal scheduling of the update rule for the synaptic weights leads to an algorithm that is much more efficient and stable than the original one.
  arXiv  Detail & Related papers  (2022-11-16T00:11:04Z)
• End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinking [52.05847268235338]
  We show how machine learning systems can perform logical extrapolation without overthinking problems. We propose a recall architecture that keeps an explicit copy of the problem instance in memory so that it cannot be forgotten. We also employ a progressive training routine that prevents the model from learning behaviors that are specific to number and instead pushes it to learn behaviors that can be repeated indefinitely.
  arXiv  Detail & Related papers  (2022-02-11T18:43:28Z)
• Random thoughts about Complexity, Data and Models [0.0]
  Data Science and Machine learning have been growing strong for the past decade. We investigate the subtle relation between "data and models" Key issue for appraisal of relation between algorithmic complexity and algorithmic learning is to do with concepts of compressibility, determinism and predictability.
  arXiv  Detail & Related papers  (2020-04-16T14:27:22Z)
• Relaxed Scheduling for Scalable Belief Propagation [27.226933626287305]
  We focus on efficient parallel algorithms for the key machine learning task of inference on graphical models. We show how to leverage relaxed scalable schedulers in this context. Our approach outperforms previous parallel belief propagation implementations both in terms of scalability and in terms of wall-clock convergence time.
  arXiv  Detail & Related papers  (2020-02-25T10:28:04Z)

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.