PaperlayerView exact revision on arXiv

Source-linked AI summary

Self-Guided LLM Reasoning for Error Diagnosis in Vehicle Routing Problems

Ni Zhang, Jianan Zhou, Yue-Jiao Gong, Zhiguang Cao

arXiv:2610.21393v1cs.AIcs.LG

TL;DR

VRP instances can contain latent errors, but existing approaches commonly assume inputs are error-free and a comprehensive evaluation of direct LLM diagnosis was lacking. This paper evaluates LLM error diagnosis and proposes self-guided reasoning through code-generated insights. The framework substantially improves detection across diverse settings, while direct LLM performance remains weaker on complex errors and instances.

  • Problem

    VRP data can contain latent formatting or feasibility errors, while most existing approaches assume error-free instances and direct LLM diagnosis had not been comprehensively evaluated.

    Source: §1 · p. 1

  • Method

    The framework has LLMs generate analysis code that extracts structured insights to guide error diagnosis and reduce reasoning burden.

    Source: §1 · p. 2, §4 · p. 4, §4.2 · p. 4

  • Results

    Across diverse problem settings and LLM backbones, the framework consistently and substantially improves error detection, achieving near-perfect accuracy.

    Source: §1 · p. 2, §6 · p. 7

  • Takeaways & Limitations

    LLMs handle relatively simple errors more effectively, while performance degrades with more complex errors or instances.

    Source: §1 · p. 1

    LLMs struggle with complex constraint violations such as time windows and distance limits, and detection falls as constraint types increase, especially for five or six types.

    Source: §3.1 · p. 2, §3.2 · p. 3

Abstract

from arXiv · show

Vehicle Routing Problems (VRPs) are fundamental to many real-world applications. Recent advances in large language models (LLMs) have spurred progress in solving these NP-hard problems. However, most existing approaches assume that input instances are error-free, neglecting the presence of faults commonly encountered in real-world data. In this work, we systematically investigate the capability of LLMs to detect (and correct) errors in VRP instances, and identify key limitations, particularly in handling complex instances or errors that substantially increase the LLM's reasoning burden. To overcome these challenges, we propose a self-guided reasoning framework in which LLMs autonomously generate code that provides structured insights to aid in error diagnosis. Experiments across diverse problem settings and LLMs demonstrate that our framework significantly improves error detection performance, achieving near-perfect accuracy.

1 Introduction

This section frames instance-level VRP errors as a practical gap in systems that assume well-formed inputs, then evaluates LLM diagnosis and proposes code-assisted self-guided reasoning. Experiments report near-perfect error-detection accuracy across diverse settings.

1 Introduction

  • VRP instances may contain latent formatting or feasibility errors, while solvers commonly assume well-formed inputs and general-purpose detection programs are difficult to design.Existing diagnosis often relies on domain expertise or post hoc solver-output analysis.Source: §1 · p. 1
  • The section asks whether LLMs can identify and correct instance errors, why this reasoning succeeds or fails, and when mitigation is needed.A comprehensive evaluation of direct LLM error identification and correction was absent, while MOID relies on solver outputs that may reflect solver deficiencies.Source: §1 · p. 1
  • LLMs detect formatting errors and simple capacity or demand violations well, but struggle with time windows, distance limits, and larger error counts.Detection also degrades as instance scale and constraint counts increase; iterative reasoning offers limited benefit on complex errors.Source: §1 · p. 1
  • The framework has LLMs generate code for intermediate reasoning insights, addressing complex-error limitations while reducing reasoning burden.The study also examines how error complexity, instance complexity, and reasoning depth affect detection.Source: §1 · pp. 1–2
  • Near-perfect accuracy is reported for the framework across diverse problem settings, including vehicle routing and bin packing.The reported experiments demonstrate significantly enhanced error-detection performance.Source: §1 · p. 2

2 Related work

Prior VRP work uses LLMs to generate solutions or heuristic code, generally assuming error-free instances. MOID addresses error detection through solver execution, but solver limitations complicate attribution of failures to input errors.

2 Related work

  • Prior LLM approaches generate VRP solutions directly or generate heuristic code and optimization operators.Examples include OPRO, LEMA, and Jiang et al. for direct solutions, and FunSearch, EOH, ReEvo, HSEvo, and AFL for heuristic or operator generation.Source: §2 · p. 2
  • These methods assume feasible, error-free inputs, leaving them unable to handle instance-level errors common in practice.MOID (Li et al. 2025) instead examines solver execution, but solver deficiencies can make solver failures difficult to distinguish from input errors.Source: §2 · p. 2
  • This work addresses the gap by enabling LLMs to identify and reason directly about instance-level errors.Source: §2 · p. 2

3 A Comprehensive Study

The study evaluates LLM error detection across injected-error datasets, varying error complexity, instance complexity, and reasoning depth. Detection weakens with more complex errors and instances, while iterative reasoning helps most on simpler variants.

3 A Comprehensive Study

  • The study constructs error-injected datasets by adding 200 formatting or feasibility errors to 20 instances for each VRP variant.It assesses detection across error complexity, instance complexity, and reasoning depth.Source: §3 · p. 2

3.1 Error Complexity

  • Detection rates fall as constraint complexity increases, approaching zero for time-window and distance-limit errors that require complex calculations or numerical reasoning.Formatting errors and simple violations, such as capacity constraints, are detected more effectively.Source: §3.1 · p. 2
  • Detection performance consistently declines as injected errors accumulate across variants, increasing the burden of identifying multiple faults simultaneously.The study examines variants ranging from single-constraint CVRP to MDOCVRPMBLTW with six constraint types.Source: §3.1 · pp. 2–3

3.2 Instance Complexity

  • Detection rates on 100-node instances are uniformly lower than on 50-node instances across VRP variants and error settings.Larger instances require reasoning over more constraints and dependency relationships.Source: §3.2 · p. 3
  • Average detection performance decreases as constraint types increase, with a sharp drop for instances containing five or six types.The evaluation covers 48 VRP variants with one to six constraint types.Source: §3.2 · p. 3, Table 1 · p. 3

3.3 Reasoning Depth

  • For simple constraints, repeated reasoning approaches 100% detection after several iterations, but gains diminish on complex constraints.The iterative process identifies errors, repairs the instance, and reasons again on the updated version.Source: §3.3 · p. 3

4 Self-Guided Reasoning Framework

The self-guided framework uses LLM-generated analysis code to produce structured insights for error diagnosis. It analyzes the instance, guides code generation and execution, then uses the results to report and revise detected errors.

4 Self-Guided Reasoning Framework

  • The framework turns an LLM reasoning path into executable analysis code that yields structured insights for error detection while reducing reasoning burden.The design offloads complex constraint calculations to code execution and supports programmatic instance evaluation.Source: §4 · p. 4, §4.2 · p. 4

4.1 Instance Analysis

  • Instance analysis identifies the problem type, required sections, and associated constraints, then self-validates their consistency against the instance.The resulting structured summary serves as a reference for later stages.Source: §4.1 · p. 4

4.2 Insight Generation

  • Insight generation identifies likely error locations, creates function-level prompts, and uses generated code to extract diagnostic evidence.Execution failures or runtime bugs are returned to the LLM for code revision before outputs are summarized as error insights.Source: §4.2 · p. 4

4.3 Report Generation

  • Report generation aligns extracted insights with the original instance to describe error types, locations, and potential causes, then revises the instance.The revision aims to produce a valid and consistent instance specification.Source: §4.3 · pp. 4–5

5 Experiment

The experiments evaluate the self-guided framework across 48 VRP variants, varying error number, instance scale, reasoning depth, prompting strategy, problem type, and LLM backend. Across these settings, the framework improves error detection, with high rates on challenging VRPs and gains extending to bin packing and other LLMs.

5 Experiment

  • Experiments compare the framework with direct LLM inference across 48 VRP variants and analyze reasoning depth, error number, instance scale, constraint complexity, and prompting strategies.The evaluation also extends to bin packing and other LLM backends.Source: §5 · p. 5

5.1 Comparison of Error Detection Rate

  • Self-Guided consistently improves EDR across VRP variants, often exceeding 95% and nearing perfect detection, with only marginal runtime increases.Direct LLM inference often falls below 70% EDR on variants involving multiple constraints or complex combinations.Source: §5.1 · p. 5

5.2 Performance Analysis

  • At 15 injected errors, Self-Guided often maintains over 90% accuracy, while direct inference degrades as error number rises, especially on complex variants.As instances grow from 50 to 100 nodes, direct inference generally deteriorates; Self-Guided maintains high EDR across most variants, with moderate drops in the hardest settings.Source: Table 3 · p. 6, §5.2 · p. 6
  • At reasoning depth five, Self-Guided achieves 100% error detection across evaluated VRP variants, while direct inference improves only gradually and does not consistently reach perfection..Source: Table 4 · p. 6, §5.2 · p. 6

5.3 Comparison with Prompt Strategies

  • Self-Guided achieves substantially higher EDR than Self-Refine, critic-guided refinement, and CoT across tested instances, particularly on challenging variants, with modest runtime increases.Each comparison method improves on direct inference, but its gains remain limited on complex VRPs.Source: §5.3 · p. 6, Table 5 · p. 7

5.4 Evaluation on Other Combinatorial Optimization Problems

  • On 1D and 2D bin packing, Self-Guided reaches 97.50% and 94.50% detection rates, respectively, with only marginal runtime increases.It outperforms direct LLM inference in both settings.Source: Table 6 · p. 7, §5.4 · p. 7

5.5 Application to Other LLMs

  • Across GPT-4.1, GPT-4o, and Claude Opus 4, direct inference degrades on complex VRPs, while Self-Guided raises EDR above 90% in most of the hardest cases.The reported gains across models and variants suggest the framework is largely model-agnostic.Source: Table 7 · p. 7, §5.5 · p. 7

6 Conclusion

The paper concludes that self-guided reasoning improves LLM error detection in complex VRP instances, while noting limits in real-world validation and first-round cascading errors. Its evaluation uses controlled synthetic errors and explicit assumptions to make fault attribution interpretable.

6 Conclusion

  • The framework uses LLM-generated reasoning paths to guide code generation and produce insights, improving error detection across settings and LLM backbones, with near-perfect accuracy reported.Further validation on additional domains and real-world noisy datasets would help assess generalization; cascading errors may still interfere during the initial reasoning round.Source: §6 · p. 7

A Vehicle Routing Problems

  • VRPs route vehicles to serve customers while minimizing an objective, typically travel distance or cost, subject to operational constraints.The paper treats VRPs as representative combinatorial optimization benchmarks and summarizes common constraints and variants.Source: A Vehicle Routing Problems · p. 9, Table 8 · p. 9

B.1 Assumption

  • The dataset is built from Route Finder benchmark instances with synthetic faults and assumptions intended to give each faulty instance a unique interpretation.Assumptions include correct capacity and distance limits, at most one error per node, and excluding depot errors when distance-limit or time-window faults are present.Source: §B.1 · p. 9

B.2 Format Errors

  • Format faults include invalid numerical values, missing required values or sections, and duplicate nodes.Examples include out-of-range identifiers, negative demand, absent coordinates, and a repeated node.Source: §B.2 · p. 9

B.3 Feasibility Errors

The feasibility-error appendix describes how selected constraint violations are defined or injected, and reports the experimental dataset and hardware setup.

B.3 Feasibility Errors

  • Capacity violations occur when assigned demand exceeds vehicle capacity and are relatively easy for LLMs to detect; backhaul variants require an absolute-value check and show lower accuracy.The backhaul condition applies to accumulated route demand, which can include positive linehaul and negative backhaul values.Source: §B.3 · p. 9
  • Distance-limit faults use round-trip distance minus 0.1, open-route faults use one-way distance minus 0.1, and time-window faults assign bounds at 0.7 and 0.9 times depot travel distance.For multi-depot settings, distance-related calculations use the nearest depot.Source: §B.3 · pp. 9, 11

C.1 Hyperparameters and Device.

  • Experiments use RouteFinder benchmark datasets with 20 instances of 50 nodes each and up to 200 injected errors, using GPT-4.1 on an AMD EPYC 7702P CPU.Some datasets receive fewer injected errors because of structural constraints.Source: §C.1 · p. 11

C.2 False Positive Analysis on Valid Instances

On correct VRP instances, direct LLM inference can report nonexistent faults, whereas Self-Guided consistently reports the instance as correct.

C.2 False Positive Analysis on Valid Instances

  • Self-Guided reports valid instances as correct, avoiding false positives observed with direct LLM inference across several VRP variants.The table reports the number of faults detected on correct instances.Source: §C.2 · p. 11, Table 10 · p. 11

C.3 Comparison of Instance-Level Error Detection Accuracy

The self-guided framework improves instance-level error detection across VRP variants, supports downstream use of repaired instances, and remains robust as constraint combinations grow more complex.

C.3 Comparison of Instance-Level Error Detection Accuracy

  • Above 85% instance-level accuracy across VRP variants, reaching 100% on CVRPL, while direct inference reaches 10% on CVRPTW and 5% on CVRPL.Instance-level accuracy counts instances for which all errors are correctly identified.Source: Table 11 · p. 11, §C.3 · p. 11

C.4 Downstream Solver Validation on Repaired Instances

  • Framework-revised instances can be used by the AFL solver without additional modification.The supplied passage reports direct usability, not a comparative solver-performance outcome.Source: §C.4 · p. 11

C.5 Impact of Constraint Type Counts.

  • Over 95% error detection across all evaluated constraint-type counts, while direct inference degrades rapidly as constraint types increase.Table 13 reports EDR under different counts of constraint types.Source: Table 13 · p. 11, §C.5 · p. 11

C.6 Evaluation on the Hard-Mode Dataset.

The hard-mode evaluation permits multiple errors within a node, a setting intended to better reflect interacting faults. The self-guided framework remains more robust than direct diagnosis across evaluated VRP variants.

C.6 Evaluation on the Hard-Mode Dataset.

  • The authors note that interacting faults can create more complex failure patterns in real-world operational data.Iterative reasoning alleviates cascading effects, but cannot eliminate them entirely.Source: §C.6 · p. 11
  • Across evaluated VRP variants, the self-guided framework is consistently more robust than direct LLM diagnosis on the hard-mode dataset.The passage notes particularly large improvements on variants with more complex constraints, without giving specific values.Source: Table 14 · p. 12, §C.6 · p. 12
  • The hard-mode dataset allows multiple errors within the same node, unlike the main experiments’ limit of at most one error per node.The main setting uses fixed injection parameters to support attribution-clean evaluation and avoid ambiguity from cascading errors.Source: §C.6 · pp. 11–12

C.7 Error-Type-Specific False Positive Analysis.

The false-positive evaluation finds that the self-guided framework eliminates observed false positives on valid instances. The accompanying prompts specify how the framework validates instances, generates and revises code, and reports repairs.

Prompt 1.2 Self-Validation

  • Self-validation checks consistency among the instance’s constraints, problem name, and required sections, treating the .vrp file as ground truth when contradictions arise.The prompt instructs the model to mark inconsistent answers incorrect and revise them.Source: Prompt 1.2 Self-Validation · p. 12, Prompt 1.3 Revise · p. 13

C.7 Error-Type-Specific False Positive Analysis.

  • The framework eliminated all observed false positives on valid instances, complementing evaluation of repaired instances by a downstream solver.Table 15 counts false-positive detections by constraint type.Source: §C.7 · p. 12, Table 15 · p. 13

D.2 Insight Generation Prompt 2.1 Reasoning Path and Function Prompt Generation

  • The insight-generation prompt asks for a validation plan with one function per check, explicit inputs and outputs, and a main function that runs checks sequentially.The plan covers format validity and feasibility under the specified constraints.Source: §D.2 · p. 14

Prompt 2.2 Code Generation

  • Code generation requires general-purpose validation functions and, for a main function, sequential execution of checks with a total-fault summary.The prompt says not to hardcode instance-specific details.Source: Prompt 2.2 Code Generation · p. 14

Prompt 1.3 Revise

  • The revision prompt directs the model to correct identified issues without changing function count, names, or signatures.It also requires general-purpose, reusable functions rather than instance-specific hardcoding.Source: Prompt 2.3 Code Revision · p. 15

Prompt 2.3 Code Revision

  • Code revision must address identified issues while preserving the generated functions’ count, names, and signatures.The prompt also disallows instance-specific hardcoding.Source: Prompt 2.3 Code Revision · p. 15

Prompt 3.1 Report Generation

  • The report-generation prompt requests distinct fault descriptions, one suggested correction per fault, and corrected raw instance text with minimal necessary changes.It instructs the model to reason from the raw instance and assume capacity and distance-limit values themselves are not faulty.Source: Prompt 3.1 Report Generation · p. 15

D.1 Instance Analysis

The instance-analysis prompt asks the model to identify constraints, name the problem type, and list required sections. Its example output lists capacity, visit, and depot constraints alongside required VRPLIB sections.

Prompt 1.1 Instance Analysis

  • The analysis prompt requests a numbered list of constraints with abbreviations and short explanations, while excluding instance-specific values.It also asks for the standard problem-type abbreviation and required sections.Source: Prompt 1.1 Instance Analysis · p. 12

Output 1.1 Instance Analysis

Related papers

Loading 2610.21393v1…