How to Report Computational Complexity in AI Studies — JNGR 5.0 AI Journal

Introduction

In AI research, reporting accuracy or task metrics alone is often not enough to support a complete scientific evaluation. Reviewers and readers increasingly expect clear information about computational complexity, resource usage, scalability, and efficiency. These details help determine whether improvements are practically meaningful and whether results can be reproduced under comparable conditions.

A well-written complexity section distinguishes formal (theoretical) complexity from empirical runtime and memory costs, defines measurement conditions, and presents trade-offs transparently. The framework below provides a clear structure for reporting computational complexity in a professional and defensible way.

1. Separate Theoretical Complexity From Empirical Cost

Begin by stating what types of computational information you report. Common categories include:

  • Theoretical time complexity (asymptotic behavior)
  • Theoretical space complexity (asymptotic memory needs)
  • Empirical training time
  • Empirical inference time
  • Memory consumption during training and inference
  • Resource usage indicators (when relevant and measurable)

Theoretical analysis supports scalability reasoning. Empirical measurements support feasibility and reproducibility. Clarifying the difference improves interpretability.

2. Provide a Formal Time Complexity Description

When applicable, report asymptotic time complexity and define all variables. Specify how computation scales with:

  • Number of samples
  • Input size or sequence length
  • Feature dimensionality
  • Model depth or number of parameters
  • Dataset size and number of training steps

Use standard notation and include clear definitions so that readers can compare your analysis with related work.

3. Report Space Complexity and Memory Footprint

Memory requirements are often a practical constraint. Report, where relevant:

  • Parameter count and model size representation
  • Peak memory usage during training
  • Peak memory usage during inference
  • GPU memory footprint under the reported batch sizes

If your method reduces memory compared to baselines, quantify the reduction and describe how it was measured.

4. Include Empirical Runtime Measurements

Complement formal analysis with controlled empirical measurements. Report:

  • Average training time per epoch or per step (with total training time if relevant)
  • Average inference latency and throughput
  • Batch size and input resolution or sequence length
  • Dataset scale used for timing measurements

Ensure that comparisons with baselines are measured under comparable settings to avoid misleading conclusions.

5. Document the Computational Environment

Runtime results depend strongly on the environment. Provide details that influence performance, such as:

  • GPU model, CPU type, and RAM capacity
  • Software frameworks and version information
  • Precision mode and acceleration settings (when relevant)
  • Parallelization or distributed training configuration (if used)

These details help readers interpret results and reproduce measurements.

6. Compare Computational Cost Against Baselines

Computational metrics are most meaningful when placed in context. When feasible, compare against strong baselines:

  • Relative training time differences
  • Relative inference time differences
  • Parameter count and memory footprint differences
  • Accuracy or performance change relative to added cost

Explain whether baseline numbers were measured by you or sourced from prior publications, and state any limitations.

7. Describe Scalability Behavior

If scalability is part of the contribution, demonstrate how cost changes with scale. For example, show behavior as:

  • Dataset size increases
  • Input dimensionality increases
  • Sequence length increases
  • Model depth or width increases

Scalability reporting helps readers judge whether the approach remains feasible under realistic growth conditions.

8. Discuss Trade-Offs Explicitly

Be clear about what improves and what becomes more expensive. Examples of common trade-offs include:

  • Higher accuracy with increased compute cost
  • Lower memory use with increased training time
  • Improved robustness with additional inference latency

Trade-off discussions should be factual, supported by results, and integrated with the manuscript’s contribution claim.

9. Avoid Ambiguous or Misleading Efficiency Claims

Common issues that reduce credibility include:

  • Reporting runtime without hardware and software context
  • Comparing optimized implementations to non-optimized baselines without disclosure
  • Ignoring tuning and training costs while reporting only inference latency
  • Using different batch sizes or input settings across compared methods

Comprehensive reporting strengthens trust and improves interpretability.

10. Link Complexity Reporting to the Contribution Narrative

Complexity should support the main message of the paper. For example:

  • If the contribution improves scalability, emphasize the scaling behavior clearly
  • If the contribution enables resource-constrained deployment, highlight relevant efficiency measures
  • If cost increases, justify why the added cost is meaningful relative to the achieved benefit

Present complexity results as part of the scientific argument, not as detached reporting.

Common Complexity Reporting Issues

  • Complexity expressions without defined variables
  • Missing empirical timing measurements
  • Inconsistent evaluation settings across methods
  • Missing hardware and software details
  • Scalability claims without evidence
  • Overstated efficiency conclusions

Addressing these points improves clarity, reproducibility, and credibility.

Final Note

Clear computational complexity reporting helps reviewers and readers evaluate feasibility, fairness of comparison, and the practical meaning of reported improvements. Transparent definitions, controlled measurements, and honest trade-off discussion strengthen the scientific integrity of AI research reporting.

Related Resources

For additional information regarding submission and publication policies, please consult the following resources: