# Counting Without Running: Evaluating LLMs' Reasoning About Code Complexity

arXiv: https://arxiv.org/abs/2512.04355 · HTML: https://mlsanity.com/paper/2512.04355/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 15 of its 27 references that are in the map.
- First posted on arXiv 4 Dec 2025.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)

## Builds on (most cited first, 15 of 15)

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Measuring Coding Challenge Competence With APPS](https://mlsanity.com/paper/2105.09938/) (2021)
- [KernelBench: Can LLMs Write Efficient GPU Kernels?](https://mlsanity.com/paper/2502.10517/) (2025)
- [TritonBench: Benchmarking Large Language Model Capabilities for Generating Triton Operators](https://mlsanity.com/paper/2502.14752/) (2025)
- [Towards Robust Agentic CUDA Kernel Benchmarking, Verification, and Optimization](https://mlsanity.com/paper/2509.14279/) (2025)
- [Large Language Models for Code Analysis: Do LLMs Really Do Their Job?](https://mlsanity.com/paper/2310.12357/) (2023)
- [Ithemal: Accurate, Portable and Fast Basic Block Throughput Estimation using Deep Neural Networks](https://mlsanity.com/paper/1808.07412/) (2018)
- [MultiKernelBench: A Multi-Platform Benchmark for Kernel Generation](https://mlsanity.com/paper/2507.17773/) (2025)
- [CoRe: Benchmarking LLMs Code Reasoning Capabilities through Static Analysis Tasks](https://mlsanity.com/paper/2507.05269/) (2025)
- [The Landscape and Challenges of HPC Research and LLMs](https://mlsanity.com/paper/2402.02018/) (2024)
- [Can Large Language Models Predict Parallel Code Performance?](https://mlsanity.com/paper/2505.03988/) (2025)
- [Omniwise: Predicting GPU Kernels Performance with LLMs](https://mlsanity.com/paper/2506.20886/) (2025)

## Built on by (most cited first, 2 of 2)

- [Evaluating Code Reasoning Abilities of Large Language Models Under Real-World Settings](https://mlsanity.com/paper/2512.14917/) (2025)
- [GPU Forecasters: Language Models as Selective Surrogates for Kernel Runtime Optimization](https://mlsanity.com/paper/2605.31464/) (2026)

## Abstract (arXiv)

Modern GPU software stacks demand developers who can anticipate performance bottlenecks before ever launching a kernel; misjudging floating-point workloads upstream can derail tuning, scheduling, and even hardware procurement. Yet despite rapid progress in code generation, today's Large Language Models (LLMs) are rarely tested on this kind of forward-looking reasoning. We close that gap with gpuFLOPBench, a benchmark that asks models to "count without running" by predicting single and double-precision FLOP counts for 577 CUDA kernels drawn from HeCBench, annotated with ground-truth profiles and eight execution attributes that distinguish trivially analyzable code from kernels whose FLOPs depend on hidden compiler or runtime behavior. Evaluating current closed-source reasoning models shows clear but uneven progress: the newest LLMs achieve perfect classification on straightforward kernels but still incur multiple order-of-magnitude errors whenever implicit FLOPs arise from division, intrinsic math functions, or common subexpressions. These results surface a core limitation of existing code assistants -- the inability to internalize hardware-specific microcode effects -- and position gpuFLOPBench as a focused testbed for developing LLM tooling that can reason about performance with the same rigor as experienced GPU developers. Sources are available at our repository: https://github.com/Scientific-Computing-Lab/gpuFLOPBench