pith. sign in

arxiv: 2606.30948 · v1 · pith:4IDSF5M2new · submitted 2026-06-29 · 💻 cs.CC · cs.PF· cs.PL

The Fourth-Root Complexity of Data Movement

Chen Ding This is my paper

Pith reviewed 2026-07-01 01:26 UTC · model grok-4.3

classification 💻 cs.CC cs.PFcs.PL
keywords data movementmemory hierarchytime complexityscalabilitymiss ratiopower lawexponential decayfourth root
0
0 comments X

The pith

Data-access cost scales with the fourth root of data size for a common class of applications

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper challenges the standard assumption in time complexity that each data access costs constant time. Instead, it uses an abstract memory hierarchy to show that for many applications, the effective cost per access grows proportionally to the fourth root of the total data size N. This means that as datasets get larger, each memory operation becomes more expensive in a predictable way. The analysis focuses on scalability rather than raw performance and distinguishes between different miss-ratio behaviors. A sympathetic reader would care because it suggests fundamental limits on how well algorithms scale with bigger data.

Core claim

The central claim is that based on an abstract memory hierarchy, the data-access cost for a common class of applications scales as N to the power of 1/4, where N is the data size. The paper provides a precise analysis showing the constant-factor difference between power-law and exponential-decay miss ratios.

What carries the argument

The abstract memory hierarchy model, which derives the fourth-root scaling from assumptions on data access patterns and miss ratios.

If this is right

  • The analysis predicts scalability limits rather than absolute performance numbers.
  • A constant-factor difference appears between power-law miss ratios and exponential-decay miss ratios.
  • Data-access costs increase predictably with data size for the covered class of applications.
  • Standard O(1) access cost assumptions do not hold under the hierarchy model.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Hardware memory systems might need redesigns that explicitly target this scaling behavior.
  • Algorithm choices could shift toward minimizing data movement volume rather than operation count.
  • The result may apply to related problems in parallel computing where hierarchy depth affects movement costs.
  • Empirical tests on real systems with growing datasets could validate or refute the predicted rate.

Load-bearing premise

The analysis relies on an abstract memory hierarchy model accurately capturing behavior for a common class of applications.

What would settle it

Measuring whether per-access data movement cost in large-scale applications grows proportionally to N to the power of 1/4 as data size increases.

read the original abstract

Time complexity typically assumes $O(1)$ cost per data access. This paper presents an analysis based on an abstract memory hierarchy. For a common class of applications, it shows that the data-access cost scales with the fourth root of data size, that is, as data size $N$ increases, the cost of each access increases at the rate of $N^\frac{1}{4}$. While the analysis does not predict performance, it predicts scalability. Specifically, the paper provides a precise analysis that shows the constant-factor difference between cases where the miss ratio follows a power law versus an exponential decay.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript claims that standard time complexity's O(1) per-access assumption is replaced, under an abstract memory hierarchy model, by a data-access cost that scales as N^{1/4} for a common class of applications whose access patterns yield power-law or exponential miss ratios. It further asserts a precise constant-factor analysis distinguishing the two miss-ratio regimes and emphasizes that the result predicts scalability rather than absolute performance.

Significance. If the central scaling result is substantiated by the model, the work would offer a concrete theoretical prediction for memory-bound scalability in large-N regimes, moving beyond the uniform-cost RAM model. The explicit constant-factor comparison between power-law and exponential cases is a positive feature that supplies falsifiable distinctions.

major comments (2)
  1. [Abstract] Abstract: the N^{1/4} scaling is asserted to follow from the abstract memory hierarchy and the definition of the application class, yet the provided text supplies no derivation, no explicit miss-ratio functions, and no mapping from hierarchy parameters (level sizes, latencies) to the exponent. Because the scaling exponent is the central claim, the manuscript must exhibit the step-by-step reduction that produces exactly 1/4 rather than another power.
  2. [Abstract] Abstract (application class and miss-ratio regimes): the result is stated to hold only for the delineated class whose patterns produce either power-law or exponential miss ratios, and the paper distinguishes the two cases for constant factors. The manuscript must specify the precise boundary conditions on the application class and the miss-ratio exponent that are required for the fourth-root regime to appear; without this, the claim reduces to a model-specific observation rather than a general result for a 'common class'.
minor comments (1)
  1. [Abstract] Abstract: the phrase 'precise analysis that shows the constant-factor difference' would be clearer if it indicated whether the constants are derived parameter-free or obtained by fitting.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments on the abstract. We agree that the abstract should more explicitly outline the derivation and boundary conditions to strengthen the central claims, and we will revise it accordingly while preserving the manuscript's focus on scalability predictions.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the N^{1/4} scaling is asserted to follow from the abstract memory hierarchy and the definition of the application class, yet the provided text supplies no derivation, no explicit miss-ratio functions, and no mapping from hierarchy parameters (level sizes, latencies) to the exponent. Because the scaling exponent is the central claim, the manuscript must exhibit the step-by-step reduction that produces exactly 1/4 rather than another power.

    Authors: The full derivation, including explicit miss-ratio functions and the mapping from hierarchy parameters to the exponent, is developed in the body of the manuscript. However, we acknowledge that the abstract as written does not provide even a high-level outline of this reduction. We will revise the abstract to include a concise step-by-step summary of how the N^{1/4} scaling emerges from the model. revision: yes

  2. Referee: [Abstract] Abstract (application class and miss-ratio regimes): the result is stated to hold only for the delineated class whose patterns produce either power-law or exponential miss ratios, and the paper distinguishes the two cases for constant factors. The manuscript must specify the precise boundary conditions on the application class and the miss-ratio exponent that are required for the fourth-root regime to appear; without this, the claim reduces to a model-specific observation rather than a general result for a 'common class'.

    Authors: We agree that the abstract would benefit from more precise boundary conditions on the miss-ratio exponents that produce the fourth-root regime. We will revise the abstract to state these conditions explicitly, clarifying the requirements on the application class for the result to hold. revision: yes

Circularity Check

0 steps flagged

No circularity: scaling derived from explicit hierarchy model assumptions

full rationale

The paper states that its N^{1/4} access-cost scaling follows from analysis of an abstract memory hierarchy applied to a defined class of applications whose miss ratios are either power-law or exponential. The abstract and skeptic summary give no indication that the exponent is obtained by fitting parameters to data, by self-definition, or by load-bearing self-citation; instead the result is presented as a direct consequence of the model's level sizes, latencies, and miss-ratio functions. Because the derivation is self-contained against the stated premises and no reduction to input-by-construction is exhibited, the circularity score is 0.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract only; limited details available on assumptions or parameters.

axioms (1)
  • domain assumption Abstract memory hierarchy model with varying access costs
    Central premise stated in the abstract as the basis for the analysis.

pith-pipeline@v0.9.1-grok · 5615 in / 1017 out tokens · 46700 ms · 2026-07-01T01:26:06.033937+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

300 extracted references · 56 canonical work pages

  1. [1]

    2026 , editor =

    Fangzhou Liu and Yifan Zhu and Yekai Pan and Chen Ding and Yanghui Wu , title =. 2026 , editor =

    2026

  2. [2]

    2026 , eprint=

    Fully Symbolic Analysis of Loop Locality: Using Imaginary Reuse to Infer Real Performance , author=. 2026 , eprint=

    2026

  3. [3]

    Sawtooth Wavefront Reordering: Enhanced

    Yifan Zhu and Yekai Pan and Chen Ding , year=. Sawtooth Wavefront Reordering: Enhanced

  4. [4]

    Sawtooth Wavefront Reordering: Enhanced

    Yifan Zhu and Yekai Pan and Chen Ding , year=. Sawtooth Wavefront Reordering: Enhanced. 2601.16032 , archivePrefix=

    work page arXiv

  5. [5]

    Submitted to PLDI 2026 , year =

    Anonymous , title =. Submitted to PLDI 2026 , year =

    2026

  6. [6]

    Vincent Michelini and Yanhui Wu and Chen Ding and Dorin Patru , title =

  7. [7]

    Chen Ding and Yifan Zhu , title =

  8. [8]

    Yiyang Wang and Chen Ding and Leo Sciortino and Linlin Chen , title =

  9. [9]

    Kneipp and and Matthew Gould and Chen Ding and Linlin Chen and Dorin Patru , title =

    Marcus Figorito and Vincent Michelini and Ben Reber Alexander H. Kneipp and and Matthew Gould and Chen Ding and Linlin Chen and Dorin Patru , title =

  10. [10]

    Proceedings of the International Workshop on Memory System, Management and Optimization , year =

    Symmetric Locality: Definition and Initial Results , author =. Proceedings of the International Workshop on Memory System, Management and Optimization , year =

  11. [11]

    2024 , eprint=

    Rewrite it in Rust: A Computational Physics Case Study , author=. 2024 , eprint=

    2024

  12. [12]

    2024 , timestamp =

    Fangzhou Liu and Yifan Zhu and Shaotong Sun and Chen Ding and Wesley Smith and Kaave Seyed Hosseini , title =. 2024 , timestamp =

    2024

  13. [13]

    2024 , url =

    Fangzhou Liu and Yifan Zhu and Shaotong Sun , title =. 2024 , url =

    2024

  14. [14]

    Shaotong Sun and Yifan Zhu and Xingzhi Ye and Chen Ding , title =

  15. [15]

    2023 , timestamp =

    Chengao Shi and Fan Jiang and Zhenguo Liu and Chen Ding and Jiang Xu , title =. 2023 , timestamp =

    2023

  16. [16]

    Kneipp and Marcus Figorito , title =

    Chen Ding and Ben Reber and Dorin Patru and Alexander H. Kneipp and Marcus Figorito , title =. 2023 , timestamp =

    2023

  17. [17]

    2023 , eprint=

    DMC4ML: Data Movement Complexity for Machine Learning , author=. 2023 , eprint=

    2023

  18. [18]

    and Liu, Fangzhou and Prechtl, Ian and Ding, Chen and Chen, Linlin and Patru, Dorin , title =

    Reber, Benjamin and Gould, Matthew and Kneipp, Alexander H. and Liu, Fangzhou and Prechtl, Ian and Ding, Chen and Chen, Linlin and Patru, Dorin , title =. 2023 , volume =

    2023

  19. [19]

    Blast from the Past: Least Expected Use

    Sayak Chakraborti and Zhizhou Zhang and Noah Bertram and Chen Ding and Sandhya Dwarkadas , editor =. Blast from the Past: Least Expected Use. 2023 , bibsource =

    2023

  20. [20]

    Beyond time complexity: data movement complexity analysis for matrix multiplication , booktitle = ICS, pages =

    Wesley Smith and Aidan Goldfarb and Chen Ding , editor =. Beyond time complexity: data movement complexity analysis for matrix multiplication , booktitle = ICS, pages =. 2022 , bibsource =

    2022

  21. [21]

    Cache-coherent

    Chen Ding and Benjamin Reber and Dorin Patru , editor =. Cache-coherent. 2022 , timestamp =

    2022

  22. [22]

    2022 , timestamp =

    Chen Ding and Dong Chen and Fangzhou Liu and Benjamin Reber and Wesley Smith , title =. 2022 , timestamp =

    2022

  23. [23]

    Chen Ding and Wesley Smith , title =

  24. [24]

    2021 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) , pages =

    Donovan Snyder and Chen Ding , title =. 2021 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) , pages =. 2021 , timestamp =

    2021

  25. [25]

    Uniform lease vs

    Dong Chen and Chen Ding and Fangzhou Liu and Benjamin Reber and Wesley Smith and Pengcheng Li , editor =. Uniform lease vs. 2021 , timestamp =

    2021

  26. [26]

    2021 , timestamp =

    Wesley Smith and Daniel Byrne and Chen Ding , title =. 2021 , timestamp =

    2021

  27. [27]

    32nd Annual Symposium on Combinatorial Pattern Matching,

    Joshua Sobel and Noah Bertram and Chen Ding and Fatemeh Nargesian and Daniel Gildea , editor =. 32nd Annual Symposium on Combinatorial Pattern Matching,. 2021 , timestamp =

    2021

  28. [28]

    2020 , note =

    Fangzhou Liu and Dong Chen and Wesley Smith and Chen Ding , editor =. 2020 , note =

    2020

  29. [29]

    2020 , timestamp =

    Ian Prechtl and Ben Reber and Chen Ding and Dorin Patru and Dong Chen , title =. 2020 , timestamp =

    2020

  30. [30]

    2020 , note =

    Ian Prechtl and Chen Ding and Dorin Patru , title =. 2020 , note =

    2020

  31. [31]

    Languages and Compilers for Parallel Computing,

    Dong Chen and Chen Ding and Dorin Patru , editor =. Languages and Compilers for Parallel Computing,. 2019 , timestamp =

    2019

  32. [32]

    Denning and Yunquan Zhang , title =

    Liang Yuan and Chen Ding and Wesley Smith and Peter J. Denning and Yunquan Zhang , title =. 2019 , timestamp =

    2019

  33. [33]

    2019 , note =

    Yumeng (Lucinda) Liu and Daniel Busaba and Chen Ding and Daniel Gildea , title =. 2019 , note =

    2019

  34. [34]

    2019 , url =

    Peng Zhao and Chen Ding and Lei Liu and Jiping Yu and Wentao Han and Xiaobing Feng , title =. 2019 , url =. doi:10.1007/s11390-019-1936-6 , timestamp =

    work page doi:10.1007/s11390-019-1936-6 2019

  35. [35]

    2019 , url =

    Rahman Lavaee and John Criswell and Chen Ding , title =. 2019 , url =. doi:10.1145/3302516.3307358 , timestamp =

    work page doi:10.1145/3302516.3307358 2019

  36. [36]

    2019 , url =

    Pengcheng Li and Hao Luo and Chen Ding , title =. 2019 , url =. doi:10.1145/3315573.3329987 , timestamp =

    work page doi:10.1145/3315573.3329987 2019

  37. [37]

    2019 , url =

    Pengcheng Li and Colin Pronovost and William Wilson and Benjamin Tait and Jie Zhou and Chen Ding and John Criswell , title =. 2019 , url =. doi:10.1145/3297858.3304067 , timestamp =

    work page doi:10.1145/3297858.3304067 2019

  38. [38]

    Jacob Brock , title =

  39. [39]

    2018 , pages =

    Liu, Yumeng (Lucinda) and Busaba, Daniel and Ding, Chen and Gildea, Daniel , title =. 2018 , pages =

    2018

  40. [40]

    2018 , url =

    Dong Chen and Fangzhou Liu and Chen Ding and Sreepathi Pai , title =. 2018 , url =. doi:10.1145/3192366.3192402 , timestamp =

    work page doi:10.1145/3192366.3192402 2018

  41. [41]

    2018 , url =

    Hao Luo and Guoyang Chen and Fangzhou Liu and Pengcheng Li and Chen Ding and Xipeng Shen , title =. 2018 , url =. doi:10.1145/3240302.3240419 , timestamp =

    work page doi:10.1145/3240302.3240419 2018

  42. [42]

    2018 , url =

    Zhizhou Zhang and Chencheng Ye and Rahman Lavaee and Ning Gu and Chen Ding , title =. 2018 , url =. doi:10.1145/3240302.3240425 , timestamp =

    work page doi:10.1145/3240302.3240425 2018

  43. [43]

    2018 , url =

    Jacob Brock and Chen Ding and Rahman Lavaee and Fangzhou Liu and Liang Yuan , title =. 2018 , url =. doi:10.1145/3210563.3210565 , timestamp =

    work page doi:10.1145/3210563.3210565 2018

  44. [44]

    2018 , url =

    Xiameng Hu and Xiaolin Wang and Lan Zhou and Yingwei Luo and Zhenlin Wang and Chen Ding and Chencheng Ye , title =. 2018 , url =. doi:10.1145/3185751 , timestamp =

    work page doi:10.1145/3185751 2018

  45. [45]

    2018 , url =

    Jacob Brock and Chen Ding and Xiaoran Xu and Yan Zhang , title =. 2018 , url =. doi:10.1145/3178372.3179523 , timestamp =

    work page doi:10.1145/3178372.3179523 2018

  46. [46]

    Rahman Lavaee , title =

  47. [47]

    2018 , url =

    Liang Yuan and Wesley Smith and Sicong Fan and Zixu Chen and Chen Ding and Yunquan Zhang , title =. 2018 , url =. doi:10.1007/978-3-030-34627-0\_5 , timestamp =

    work page doi:10.1007/978-3-030-34627-0 2018

  48. [48]

    2017 , url =

    Chencheng Ye and Chen Ding and Hao Luo and Jacob Brock and Dong Chen and Hai Jin , title =. 2017 , url =. doi:10.1145/3134437 , timestamp =

    work page doi:10.1145/3134437 2017

  49. [49]

    Chakrabarti and Chen Ding and Liang Yuan , title =

    Pengcheng Li and Dhruva R. Chakrabarti and Chen Ding and Liang Yuan , title =. 2017 , url =. doi:10.1109/IPDPS.2017.83 , timestamp =

    work page doi:10.1109/ipdps.2017.83 2017

  50. [50]

    Zhang and Chen Ding , title =

    Pengcheng Li and Xiaoyu Hu and Dong Chen and Jacob Brock and Hao Luo and Eddy Z. Zhang and Chen Ding , title =. 2017 , url =. doi:10.1145/3046678 , timestamp =

    work page doi:10.1145/3046678 2017

  51. [51]

    2017 , url =

    Hao Luo and Pengcheng Li and Chen Ding , title =. 2017 , url =

    2017

  52. [52]

    International Journal of Parallel Programming , volume =

    Chencheng Ye and Jacob Brock and Chen Ding and Hai Jin , title =. International Journal of Parallel Programming , volume =. 2017 , url =. doi:10.1007/s10766-015-0384-3 , timestamp =

    work page doi:10.1007/s10766-015-0384-3 2017

  53. [53]

    2017 , url =

    Xiameng Hu and Xiaolin Wang and Lan Zhou and Yingwei Luo and Chen Ding and Song Jiang and Zhenlin Wang , title =. 2017 , url =. doi:10.1109/TC.2016.2618920 , timestamp =

    work page doi:10.1109/tc.2016.2618920 2017

  54. [54]

    2017 , url =

    Xiameng Hu and Xiaolin Wang and Yechen Li and Yingwei Luo and Chen Ding and Zhenlin Wang , title =. 2017 , url =. doi:10.1109/TPDS.2016.2611572 , timestamp =

    work page doi:10.1109/tpds.2016.2611572 2017

  55. [55]

    Chakrabarti , title =

    Pengcheng Li and Dhruva R. Chakrabarti , title =. 2016 , url =. doi:10.1007/978-3-319-52709-3_8 , timestamp =

    work page doi:10.1007/978-3-319-52709-3_8 2016

  56. [56]

    2016 , url =

    Lei Liu and Yong Li and Chen Ding and Hao Yang and Chengyong Wu , title =. 2016 , url =. doi:10.1109/TC.2015.2462813 , timestamp =

    work page doi:10.1109/tc.2015.2462813 2016

  57. [57]

    2016 , url =

    Jacob Brock and Chencheng Ye and Chen Ding , title =. 2016 , url =. doi:10.1145/2989081.2989123 , timestamp =

    work page doi:10.1145/2989081.2989123 2016

  58. [58]

    2016 , url =

    Dong Chen and Chencheng Ye and Chen Ding , title =. 2016 , url =. doi:10.1145/2989081.2989119 , timestamp =

    work page doi:10.1145/2989081.2989119 2016

  59. [59]

    2016 , url =

    Raj Parihar and Jacob Brock and Chen Ding and Michael C. Huang , title =. 2016 , url =. doi:10.1145/2926697.2926705 , timestamp =

    work page doi:10.1145/2926697.2926705 2016

  60. [60]

    2016 , url =

    Pengcheng Li and Hao Luo and Chen Ding , title =. 2016 , url =. doi:10.1145/2926697.2926708 , timestamp =

    work page doi:10.1145/2926697.2926708 2016

  61. [61]

    2016 , note =

    Data-centric combinatorial optimization of parallel code , author =. 2016 , note =

    2016

  62. [62]

    2016 , url =

    Xiameng Hu and Xiaolin Wang and Lan Zhou and Yingwei Luo and Chen Ding and Zhenlin Wang , title =. 2016 , url =

    2016

  63. [63]

    2016 , url =

    Rahman Lavaee , title =. 2016 , url =. doi:10.1145/2837614.2837669 , timestamp =

    work page doi:10.1145/2837614.2837669 2016

  64. [64]

    Hao Luo and Jacob Brock and Chencheng Ye and Pengcheng Li and Chen Ding , title =

  65. [65]

    A Data Centric Perspective on Memory Placement , booktitle = MEMSYS, pages =

    Chen Ding and Hao Luo and Chencheng Ye , title =. 2015 , url =. doi:10.1145/2818950.2818958 , timestamp =

    work page doi:10.1145/2818950.2818958 2015

  66. [66]

    Xiameng Hu and Xiaolin Wang and Yechen Li and Lan Zhou and Yingwei Luo and Chen Ding and Song Jiang and Zhenlin Wang , title =

  67. [67]

    International Journal of Parallel Programming , year =

    Rochester Elastic Cache Utility (RECU): Unequal Cache Sharing is Good Economics , author =. International Journal of Parallel Programming , year =

  68. [68]

    Chencheng Ye and Jacob Brock and Chen Ding and Hai Jin , title =

  69. [69]

    Jacob Brock and Chencheng Ye and Chen Ding and Yechen Li and Xiaolin Wang and Yingwei Luo , title =

  70. [70]

    Optimal Program Symbiosis in Shared Cache , booktitle = CCGRID, month =

  71. [71]

    2015 , bibsource =

    Xiaolin Wang and Yechen Li and Yingwei Luo and Xiameng Hu and Jacob Brock and Chen Ding and Zhenlin Wang , title =. 2015 , bibsource =

    2015

  72. [72]

    Hao Luo and Pengcheng Li and Chen Ding , title =

  73. [73]

    Performance Metrics and Models for Shared Cache , journal =

    Chen Ding and Xiaoya Xiang and Bin Bao and Hao Luo and Ying. Performance Metrics and Models for Shared Cache , journal =. 2014 , volume =. doi:10.1007/s11390-014-1460-7 , timestamp =

    work page doi:10.1007/s11390-014-1460-7 2014

  74. [74]

    Li, Pengcheng and Ding, Chen and Luo, Hao , title =

  75. [75]

    Ding, Chen and Li, Pengcheng , title =

  76. [76]

    2014 , url =

    Li, Pengcheng and Luo, Hao and Ding, Chen and Hu, Ziang and Ye, Handong , title =. 2014 , url =

    2014

  77. [77]

    Program interaction on multicore: theory and applications , publisher=

    Ding, Chen and Yuan, Liang , pages=. Program interaction on multicore: theory and applications , publisher=. Journal of Computer Engineering and Science , volume=. 2014 , month =

    2014

  78. [78]

    Chen Ding and Brian Gernhart and Pengcheng Li and Matthew Hertz , title =

  79. [79]

    Xiaoya Xiang , title =

  80. [80]

    2014 , month =

    Xiaoming Gu , title =. 2014 , month =

    2014

Showing first 80 references.