Repository files navigation

🎉🎉PLEASE SEE THE UPDATED VERSION HERE🎉🎉:https://github.com/ataylor24/MAGMA_v2

Are Large-Language Models Graph Algorithmic Reasoners? [pdf]

The MAGMA Benchmark is designed to evaluate the performance of large language models (LLMs) on classical graph algorithms using intermediate steps. Despite advances in LLMs, they exhibit significant limitations in structured, multistep reasoning tasks, particularly those involving explicit graph structures. Our benchmark addresses this gap by evaluating state-of-the-art LLMs on five fundamental algorithms: BFS, DFS, Dijkstra's, Floyd-Warshall, and Prim's MST.

We are actively updating this benchmark! Please reach out to the contact email below with any update requests/bug fixes.

• Comprehensive Benchmark: Evaluates LLM performance on classical graph algorithms.
• Intermediate Steps Evaluation: Focuses on the accuracy of intermediate reasoning steps.
• Multiple Algorithms: Includes BFS, DFS, Dijkstra's, Floyd-Warshall, and Prim's MST.
• Advanced Prompting Techniques: Explores advanced prompting techniques and algorithmic instructions.

• Python 3.10 or higher

git clone https://github.com/yourusername/LLM-CLRS-Graph-Reasoning-Benchmark.gitcd LLM-CLRS-Graph-Reasoning-Benchmark

To create a Conda environment with the required dependencies, run the following command:

conda env create --file environment.yml

This will create a new Conda environment with all the dependencies specified in theenvironment.yml file.

Activate the newly created environment using:

conda activate nar2

An example of a script used to run the benchmark on the included algorithms is included inrun_scripts.

bash run_scripts/bfs_CoT.sh

An example of a script used to run the benchmark on a selected algorithm is included ininference_scripts.

bash inference_scripts/bfs_CoT.sh

You can customize the model training settings using the configuration fileconfiguration_example/config_qlora.yaml.

The benchmark uses the following metrics:

• Exact Match Accuracy: Measures the correctness of the final output. (Primary metric used in the paper)
• F1 Score Measures the partial correcness of the final output.Note: We also include 'partial' accuracies that provide credit for outputs that are similar to the desired output but lack the full response template.

For both the Exact Match Accuracy and F1 score metrics, we provide the following variants:

• Intermediate Steps Accuracy: Evaluates the performance of models on intermediate steps.
• Final Step Accuracy Evaluates the performance of models on only the final step.
• Trajectory Accuracy Evaluates the performance of models on the full trajectory (i.e. intermediate steps & final step)
• Independent Accuracy Evaluates the performance of models on each independent inference (trajectory agnostic).

We welcome contributions to improve this benchmark. Please follow these steps:

1. Fork the repository.
2. Create a new branch (git checkout -b feature-branch).
3. Commit your changes (git commit -am 'Add new feature').
4. Push to the branch (git push origin feature-branch).
5. Open a Pull Request.

Seedata_generation for further details.

Seed used = 100898

BFS Llama3r &alpha: 8

Otherwise, baseline data generation and model training follow default settings for parameters.

This project is licensed under the MIT License - see theLICENSE file for details.

Data used in the benchmark is translated from the CLRS benchmark, which can be found here:https://github.com/google-deepmind/clrs

Model training adapted from the Huggingface Alignment Handbook:https://github.com/huggingface/alignment-handbook.git

For questions or feedback, please open an issue or contact us atataylor2@cs.ucla.edu.

Thank you for using the LLM-CLRS Graph Reasoning Benchmark! We hope this benchmark helps advance the understanding and capabilities of large language models in structured reasoning tasks.