AlgoBench: Benchmarking Algorithmic Adaptation in Code Generation

• URL: http://arxiv.org/abs/2607.00062v1
• Date: Tue, 30 Jun 2026 10:13:12 GMT
• Title: AlgoBench: Benchmarking Algorithmic Adaptation in Code Generation
• Abstract summary: We introduce ALGOBENCH, a framework that automatically builds novel algorithmic problems from known competitive-programming problems.<n>We show that performance drops sharply on ALGOBENCH variants, retrieval can increase reuse of the old algorithm, and many correct-looking solutions fail to meet the required complexity.
• Score: 7.798940465229644
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: High pass rates on established programming benchmarks such as HumanEval and LiveCodeBench do not always show whether a model can reason about algorithms. Many fixed benchmarks eventually become part of the public training ecosystem through released problem statements, editorials, and generated solutions, allowing later models to improve partly by exposure rather than by stronger algorithmic ability. We introduce ALGOBENCH, a framework that automatically builds novel algorithmic problems from known competitive-programming problems through structured constraint-shifting transformations. Each accepted ALGOBENCH variant is traceable to a source problem, but must make the original reference algorithm fail. Beyond pass@$k$, we introduce complexity-aware metrics -- including OPTT, OPTS, TRAPRATE, GAPT, and CONSENS -- to test whether a solution is not only functionally correct but also asymptotically suitable for the generated problem. Experiments across multiple LLMs and prompting strategies show that performance drops sharply on ALGOBENCH variants, retrieval can increase reuse of the old algorithm, and many correct-looking solutions fail to meet the required complexity. Error analysis shows that failures are mainly algorithmic rather than implementation-level, suggesting that ALGOBENCH evaluates adaptation beyond functional correctness.

Related papers

• FrontierOR: Benchmarking LLMs' Capacity for Efficient Algorithm Design in Large-Scale Optimization [61.43300970020897]
  Large language models (LLMs) are increasingly used for optimization modeling and solver-code generation.<n>Existing benchmarks are limited to small or simplified examples far below real-world scale and complexity.<n>We introduce FrontierOR, among the first benchmarks to evaluate LLM-based efficient algorithm design for realistic large-scale optimization problems.
  arXiv  Detail & Related papers  (2026-05-24T20:10:42Z)
• Budget-Efficient Automatic Algorithm Design via Code Graph [2.982218441172364]
  Large language models (LLMs) have emerged as powerful tools for automatic algorithm design (AAD)<n>We formalize budget-efficient automatic algorithm design, wherein the search policy maximizes realized fitness subject to limited computational cost.<n>We validate our method empirically on three optimization problems, demonstrating consistent superiority of our graph-based search over full-algorithm search at equal token budget.
  arXiv  Detail & Related papers  (2026-05-11T14:01:52Z)
• Early Discoveries of Algorithmist I: Promise of Provable Algorithm Synthesis at Scale [9.349595533902479]
  Algorithmist is an autonomous researcher agent on top of GitHub Copilot.<n>We evaluate it on research-level tasks in private data analysis and clustering.<n>Results suggest a new paradigm in which LLM systems generate research-paper-quality algorithmic artifacts tailored to each dataset and deployment setting.
  arXiv  Detail & Related papers  (2026-03-23T04:06:55Z)
• Discovering Algorithms with Computational Language Processing [0.7062238472483737]
  We present a framework automating algorithm discovery by conceptualizing them as sequences of operations, represented as tokens.<n>These computational tokens are chained using a grammar, enabling the formation of increasingly sophisticated procedures.<n>Our ensemble Monte Carlo tree search (MCTS) guided by reinforcement learning (RL) explores token chaining and drives the creation of new tokens.
  arXiv  Detail & Related papers  (2025-07-03T21:45:17Z)
• AlgOS: Algorithm Operating System [2.5352713493505785]
  AlgOS is an unopinionated, modular framework for algorithmic implementations.<n>It is designed to reduce the overhead of implementing new algorithms and to standardise the comparison of algorithms.
  arXiv  Detail & Related papers  (2025-04-07T10:36:46Z)
• PlanGEN: A Multi-Agent Framework for Generating Planning and Reasoning Trajectories for Complex Problem Solving [89.60370366013142]
  We propose PlanGEN, a model-agnostic and easily scalable agent framework with three key components: constraint, verification, and selection agents.<n>Specifically, our approach proposes constraint-guided iterative verification to enhance performance of inference-time algorithms.
  arXiv  Detail & Related papers  (2025-02-22T06:21:56Z)
• 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)
• FastDiagP: An Algorithm for Parallelized Direct Diagnosis [64.65251961564606]
  FastDiag is a typical direct diagnosis algorithm that supports diagnosis calculation without predetermining conflicts. We propose a novel algorithm, so-called FastDiagP, which is based on the idea of speculative programming. This mechanism helps to provide consistency checks with fast answers and boosts the algorithm's runtime performance.
  arXiv  Detail & Related papers  (2023-05-11T16:26:23Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms. For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime. In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem. We adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon.
  arXiv  Detail & Related papers  (2021-09-13T18:10:52Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)

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.