Tool Call Dependency Graphs Enable Deep LLM Reasoning Evaluation and Better Explanations

Abstract

Evaluation of tool-augmented Large Language Models (LLMs) has not advanced far beyond final answer accuracy, and neglects in-depth evaluation of reasoning ability despite it being a central claim of recent models. We aim to address this gap by developing a dependency graph-based evaluation to give insight into meta-level reasoning ability. We create a two-stage algorithm to construct dependency graphs from a series of LLM-generated tool calls: in the first stage creating nodes for tool calls, then in the second creating edges where tool call results are identified as being used as arguments in subsequent calls. The resulting graph facilitates the development of graph-theoretic metrics which allows deeper evaluation of the reasoning ability of LLMs over the task in question. We also use the dependency graph to assist with the generation of natural language explanations of the question-answering process. We create a baseline explanation generated from the list of tool calls, and a graph-augmented explanation which incorporates information about information provenance. A human evaluation study shows that our graph-augmented explanations are preferred across three key explainability criteria, although the extra detail contained impacts ease of understanding.