Evaluating Efficiency and Novelty of LLM-Generated Code for Graph Analysis

• URL: http://arxiv.org/abs/2507.06463v1
• Date: Wed, 09 Jul 2025 00:46:30 GMT
• Title: Evaluating Efficiency and Novelty of LLM-Generated Code for Graph Analysis
• Authors: Atieh Barati Nia, Mohammad Dindoost, David A. Bader,
• Abstract summary: We present the first systematic study of Large Language Models' ability to generate efficient C implementations of graph-analysis routines.<n>Eight state-of-the-art models are benchmarked.<n>Results show that Claude Sonnet 4 Extended achieves the best result in the case of ready-to-use code generation and efficiency.
• Score: 0.40964539027092917
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large Language Models (LLMs) are increasingly used to automate software development, yet most prior evaluations focus on functional correctness or high-level languages such as Python. We present the first systematic study of LLMs' ability to generate efficient C implementations of graph-analysis routines--code that must satisfy the stringent runtime and memory constraints. Eight state-of-the-art models (OpenAI ChatGPT o3 and o4-mini-high, Anthropic Claude 4 Sonnet and Sonnet Extended, Google Gemini 2.5 Flash and Pro, xAI Grok 3-Think, and DeepSeek DeepThink R1) are benchmarked by two distinct approaches. The first approach checks the ability of LLMs in generating an algorithm outperforming other present algorithms in the benchmark. The second approach evaluates the ability of LLMs to generate graph algorithms for integration into the benchmark. Results show that Claude Sonnet 4 Extended achieves the best result in the case of ready-to-use code generation and efficiency, outperforming human-written baselines in triangle counting. The study confirms that contemporary LLMs excel at optimizing and integrating established algorithms but not inventing novel techniques. We provide prompts, the first approach's generated code, and measurement scripts to foster reproducible research.

Related papers

• When Do LLMs Help With Node Classification? A Comprehensive Analysis [21.120619437937382]
  We develop a comprehensive and testbed for node classification using Large Language Models (LLMs)<n>It includes 10 homophilic datasets, 4 heterophilic datasets, 8 LLM-based algorithms, 8 classic baselines, and 3 learning paradigms.<n>Our findings uncover 8 insights, e.g., (1) LLM-based methods can significantly outperform traditional methods in a semi-supervised setting, while the advantage is marginal in a supervised setting.
  arXiv  Detail & Related papers  (2025-02-02T15:56:05Z)
• Are Large-Language Models Graph Algorithmic Reasoners? [45.592341677933646]
  We introduce a benchmark designed to evaluate Large Language Models (LLMs) performance on classical algorithmic reasoning tasks on explicit graphs. Our benchmark encompasses five fundamental algorithms: Breadth-First Search (BFS) and Depth-First Search (DFS) for connectivity, Dijkstra's algorithm and Floyd-Warshall algorithm for all nodes shortest path, and Prim's Minimum Spanning Tree (MST-Prim's) algorithm.
  arXiv  Detail & Related papers  (2024-10-29T23:28:37Z)
• Can Large Language Models Invent Algorithms to Improve Themselves?: Algorithm Discovery for Recursive Self-Improvement through Reinforcement Learning [3.6117068575553595]
  Self-Developing is a framework that enables Large Language Models to autonomously discover, implement, and refine their own improvement algorithms.<n>We demonstrate this framework through model merging, a practical technique for combining specialized models.<n>On mathematical reasoning benchmarks, the autonomously discovered algorithms improve the seed model's GSM8k performance by 6% and exceed human-designed approaches like Task Arithmetic by 4.3%.
  arXiv  Detail & Related papers  (2024-10-21T04:57:09Z)
• RAGLAB: A Modular and Research-Oriented Unified Framework for Retrieval-Augmented Generation [54.707460684650584]
  Large Language Models (LLMs) demonstrate human-level capabilities in dialogue, reasoning, and knowledge retention. Current research addresses this bottleneck by equipping LLMs with external knowledge, a technique known as Retrieval Augmented Generation (RAG) RAGLAB is a modular and research-oriented open-source library that reproduces 6 existing algorithms and provides a comprehensive ecosystem for investigating RAG algorithms.
  arXiv  Detail & Related papers  (2024-08-21T07:20:48Z)
• What's Wrong with Your Code Generated by Large Language Models? An Extensive Study [80.18342600996601]
  Large language models (LLMs) produce code that is shorter yet more complicated as compared to canonical solutions. We develop a taxonomy of bugs for incorrect codes that includes three categories and 12 sub-categories, and analyze the root cause for common bug types. We propose a novel training-free iterative method that introduces self-critique, enabling LLMs to critique and correct their generated code based on bug types and compiler feedback.
  arXiv  Detail & Related papers  (2024-07-08T17:27:17Z)
• From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models [63.188607839223046]
  This survey focuses on the benefits of scaling compute during inference. We explore three areas under a unified mathematical formalism: token-level generation algorithms, meta-generation algorithms, and efficient generation.
  arXiv  Detail & Related papers  (2024-06-24T17:45:59Z)
• Benchmarking Uncertainty Quantification Methods for Large Language Models with LM-Polygraph [83.90988015005934]
  Uncertainty quantification is a key element of machine learning applications.<n>We introduce a novel benchmark that implements a collection of state-of-the-art UQ baselines.<n>We conduct a large-scale empirical investigation of UQ and normalization techniques across eleven tasks, identifying the most effective approaches.
  arXiv  Detail & Related papers  (2024-06-21T20:06:31Z)
• How Efficient is LLM-Generated Code? A Rigorous & High-Standard Benchmark [39.13045037676502]
  Development of large language models (LLMs) has significantly pushed the frontiers of program synthesis.<n>Most evaluation frameworks focus on the (functional) correctness of generated code; efficiency, as an important measure of code quality, has been overlooked in existing evaluations.<n>We develop ENAMEL, a rigorous and high-standard benchmark for evaluating the capability of LLMs in generating efficient code.
  arXiv  Detail & Related papers  (2024-06-10T04:19:20Z)
• Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models [17.059322033670124]
  We propose a novel strategy that propels Large Language Models through algorithmic reasoning pathways. Our results suggest that instructing an LLM using an algorithm can lead to performance surpassing that of the algorithm itself.
  arXiv  Detail & Related papers  (2023-08-20T22:36:23Z)
• ALGO: Synthesizing Algorithmic Programs with LLM-Generated Oracle Verifiers [60.6418431624873]
  Large language models (LLMs) excel at implementing code from functionality descriptions but struggle with algorithmic problems. We propose ALGO, a framework that synthesizes Algorithmic programs with LLM-Generated Oracles to guide the generation and verify their correctness. Experiments show that when equipped with ALGO, we achieve an 8x better one-submission pass rate over the Codex model and a 2.6x better one-submission pass rate over CodeT.
  arXiv  Detail & Related papers  (2023-05-24T00:10:15Z)
• CodeGen2: Lessons for Training LLMs on Programming and Natural Languages [116.74407069443895]
  We unify encoder and decoder-based models into a single prefix-LM. For learning methods, we explore the claim of a "free lunch" hypothesis. For data distributions, the effect of a mixture distribution and multi-epoch training of programming and natural languages on model performance is explored.
  arXiv  Detail & Related papers  (2023-05-03T17:55:25Z)

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.