Can LLMs Prove Robotic Path Planning Optimality? A Benchmark for Research-Level Algorithm Verification

• URL: http://arxiv.org/abs/2603.19464v1
• Date: Thu, 19 Mar 2026 20:55:46 GMT
• Title: Can LLMs Prove Robotic Path Planning Optimality? A Benchmark for Research-Level Algorithm Verification
• Abstract summary: We introduce the first benchmark for evaluating Large Language Models (LLMs) on approximation-ratio proofs of robotic path planning algorithms.<n>Our evaluation reveals that even the strongest models struggle to produce fully valid proofs without external domain knowledge.
• Score: 5.637461397736495
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Robotic path planning problems are often NP-hard, and practical solutions typically rely on approximation algorithms with provable performance guarantees for general cases. While designing such algorithms is challenging, formally proving their approximation optimality is even more demanding, which requires domain-specific geometric insights and multi-step mathematical reasoning over complex operational constraints. Recent Large Language Models (LLMs) have demonstrated strong performance on mathematical reasoning benchmarks, yet their ability to assist with research-level optimality proofs in robotic path planning remains under-explored. In this work, we introduce the first benchmark for evaluating LLMs on approximation-ratio proofs of robotic path planning algorithms. The benchmark consists of 34 research-grade proof tasks spanning diverse planning problem types and complexity levels, each requiring structured reasoning over algorithm descriptions, problem constraints, and theoretical guarantees. Our evaluation of state-of-the-art proprietary and open-source LLMs reveals that even the strongest models struggle to produce fully valid proofs without external domain knowledge. However, providing LLMs with task-specific in-context lemmas substantially improves reasoning quality, a factor that is more effective than generic chain-of-thought prompting or supplying the ground-truth approximation ratio as posterior knowledge. We further provide fine-grained error analysis to characterize common logical failures and hallucinations, and demonstrate how each error type can be mitigated through targeted context augmentation.

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)
• Breaking the Computational Barrier: Provably Efficient Actor-Critic for Low-Rank MDPs [53.412166189410904]
  We use supervised learning as a computational proxy to establish a hierarchy of commonly adopted RL oracles under low-rank Markov Decision Processes (MDPs)<n>Motivated by this observation, we propose a novel optimistic actor-critic algorithm that relies solely on the policy evaluation oracle.<n>We prove that our algorithm outperforms the existing sample complexity guarantees for low-rank MDPs while avoiding computationally expensive planning or optimization oracles commonly assumed in prior works.
  arXiv  Detail & Related papers  (2026-05-02T04:46:54Z)
• Evaluating the Formal Reasoning Capabilities of Large Language Models through Chomsky Hierarchy [62.32144504442516]
  It is unknown whether SOTA LLMs can grasp the structured, hierarchical complexity of formal languages.<n>ChomskyBench is a benchmark for systematically evaluating LLMs through the lens of Chomsky Hierarchy.<n>ChomskyBench is composed of a comprehensive suite of language recognition and generation tasks designed to test capabilities at each level.
  arXiv  Detail & Related papers  (2026-04-03T04:06:39Z)
• 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)
• AlgBench: To What Extent Do Large Reasoning Models Understand Algorithms? [21.836954662380094]
  We propose AlgBench, an expert-curated benchmark that evaluates Large Reasoning Models (LRMs) under an algorithm-centric paradigm.<n>AlgBench consists of over 3,000 original problems spanning 27 algorithms, constructed by ACM algorithmic experts.<n> Empirical evaluations on leading LRMs (e.g., Gemini-3-Pro, DeepSeek-v3.2-Speciale and GPT-o3) reveal substantial performance.
  arXiv  Detail & Related papers  (2026-01-08T14:54:44Z)
• Position: We Need An Algorithmic Understanding of Generative AI [7.425924654036041]
  This position paper proposes AlgEval: a framework for systematic research into the algorithms that LLMs learn and use.<n>AlgEval aims to uncover algorithmic primitives, reflected in latent representations, attention, and inference-time compute, and their algorithmic composition to solve task-specific problems.
  arXiv  Detail & Related papers  (2025-07-10T08:38:47Z)
• Bridging Pattern-Aware Complexity with NP-Hard Optimization: A Unifying Framework and Empirical Study [0.0]
  We propose a novel patternaware framework to reduce effective computational complexity across domains.<n>With rigorous definitions, theorems, and a meta learning driven solver pipeline, we introduce metrics like Pattern Utilization Efficiency (PUE) and achieve up to 79 percent solution quality gains.
  arXiv  Detail & Related papers  (2025-03-12T11:05:06Z)
• EVOLvE: Evaluating and Optimizing LLMs For In-Context Exploration [76.66831821738927]
  Large language models (LLMs) remain under-studied in scenarios requiring optimal decision-making under uncertainty.<n>We measure LLMs' (in)ability to make optimal decisions in bandits, a state-less reinforcement learning setting relevant to many applications.<n>Motivated by the existence of optimal exploration algorithms, we propose efficient ways to integrate this algorithmic knowledge into LLMs.
  arXiv  Detail & Related papers  (2024-10-08T17:54:03Z)
• Designing Algorithms Empowered by Language Models: An Analytical Framework, Case Studies, and Insights [86.06371692309972]
  This work presents an analytical framework for the design and analysis of large language models (LLMs)-based algorithms.<n>Our proposed framework serves as an attempt to mitigate such headaches.
  arXiv  Detail & Related papers  (2024-07-20T07:39:07Z)
• Exploring Viable Algorithmic Options for Learning from Demonstration (LfD): A Parameterized Complexity Approach [0.0]
  In this paper, we show how such a systematic exploration of algorithmic options can be done using parameterized complexity analysis. We show that none of our problems can be solved efficiently either in general or relative to a number of (often simultaneous) restrictions on environments, demonstrations, and policies.
  arXiv  Detail & Related papers  (2022-05-10T15:54:06Z)
• 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.