Deciphering LLM's Algorithmic Reasoning Capabilities: A Dynamic Hybrid Evaluation Framework for Graph Traversal Tasks

This study focuses on the core question of whether LLMs implicitly approximate classic graph traversal algorithms such as BFS/DFS, and has developed a multi-dimensional interpretable evaluation framework (including scratchpad reasoning, representational similarity analysis, attention pattern analysis, and hybrid symbolic-neural network systems). Preliminary findings show that LLMs exhibit BFS-like reasoning patterns on some graph structures, but not completely; performance drops significantly in complex graph scenarios; hybrid systems are superior in consistency and accuracy. This research provides empirical evidence for understanding LLM reasoning mechanisms and the direction of neuro-symbolic AI.

Nature of the Problem

Large language models exhibit 'reasoning' behavior in complex problems, but the core question is: do they perform true structured algorithmic reasoning, or just pattern matching based on training data? This distinction determines their reliability in tasks requiring strict logical guarantees.

Core Research Questions

This project targets the field of graph traversal and explores:

• Do LLMs follow structured reasoning paths like BFS/DFS?
• What are the performance differences of models on different graph structures?
• Can hybrid symbolic + neural network systems improve reasoning consistency and accuracy?

Reasons for Choosing Graph Traversal

Graph traversal algorithms are clearly defined and verifiable, graph structure variants are rich (trees, grids, etc.), and they are basic components of many practical reasoning tasks.

Researchers designed a comprehensive evaluation framework, including four types of technologies:

1. Scratchpad-based Reasoning Evaluation

Require the model to explicitly write intermediate steps, which can track reasoning paths, compare with standard algorithm trajectories, and identify error patterns and backtracking behaviors.

2. Representational Similarity Analysis (RSA)

Calculate the similarity between the model's internal representations and algorithm execution states: extract hidden layer activations, compute correlation matrices with algorithm state vectors, and generate RSA heatmaps to visualize corresponding patterns.

3. Attention Pattern Analysis

Analyze Transformer attention weight distribution: Does the model focus on adjacent nodes? Does attention follow topological structures? Do different attention heads take on different functions?

4. Hybrid Symbolic-Neural Network Planner

Comparison experiment system: symbolic components execute BFS/A* algorithms, neural components process natural language input or provide heuristic evaluation, and work collaboratively to test performance and interpretability.

The project is built based on Python and PyTorch, with main dependencies:

• Hugging Face Transformers: load pre-trained models
• PyTorch: reasoning and gradient calculation
• NumPy/SciPy: numerical computation and statistical analysis
• Custom graph environment: generate and manipulate various graph structures

Core code modules:

• graphs.py: graph environment definition and visualization
• evaluation_runner.py: main experiment program
• planner.py: hybrid planner implementation
• attention_analysis.py: attention pattern analysis
• rsa_analysis.py: representational similarity calculation
• scratchpad_runner.py: step-by-step reasoning evaluation

Preliminary Experimental Phenomena

• Partial BFS Similarity: LLMs exhibit BFS-like reasoning patterns on some graph structures, but the similarity is not complete;
• Performance Drop in Complex Graphs: When graph structure complexity increases, the model's reasoning consistency and accuracy drop significantly;
• Advantages of Hybrid Systems: Symbolic + neural hybrid systems perform better in consistency and accuracy.

Research Implications

• LLMs may learn implicit strategies approximating algorithms, but the learning is incomplete;
• Pure neural network methods have limitations in tasks requiring strict logical guarantees;
• Neuro-symbolic hybrid architectures are a feasible path to improve reasoning reliability.

Application Value

• Model Evaluation: Provide a standardized evaluation benchmark for LLM reasoning capabilities;
• Architecture Improvement: Guide the design of model architectures more suitable for algorithmic reasoning;
• Hybrid System Development: Provide empirical evidence for the design of neuro-symbolic AI systems.

Future Directions

• Extend to larger-scale language models;
• Improve reasoning evaluation metrics;
• Apply the method to practical planning tasks.

Through rigorous experimental design and multi-dimensional analysis, this study provides valuable empirical data for LLM's algorithmic reasoning capabilities. It neither supports the pessimistic view that 'LLMs are only pattern matchers' nor believes that they have mastered true algorithmic reasoning. The revealed picture is: LLMs have learned some aspects of algorithmic reasoning, but the learning is incomplete and prone to failure in complex scenarios. In the future, the reliability and interpretability of AI reasoning can be improved through optimizing training methods, architecture design, or hybrid systems.