Can LLMs Reason Structurally? Benchmarking via the lens of Data Structures

Large language models (LLMs) are deployed on increasingly complex tasks that require multi-step decision-making. Understanding their algorithmic reasoning abilities is therefore crucial. However, we lack a diagnostic benchmark for evaluating these capabilities. We propose to use data structures as a principled lens: as fundamental building blocks of algorithms, they naturally probe structural reasoning—the ability to understand and manipulate relationships such as order, hierarchy, and connectivity that underpin algorithmic reasoning. We introduce DSR-Bench (Data Structure Reasoning Benchmark), spanning 20 data structures, 35 operations, and 4,140 problem instances. DSR-Bench features hierarchical task organization, fully automated generation and evaluation, and fine-grained diagnostics. Evaluating 13 state-of-the-art LLMs reveals critical limitations: the top-performing model achieves only 0.46/1 on challenging instances. Three auxiliary probes targeting more realistic usages expose further weaknesses: models perform poorly on spatial data and context-rich scenarios, and they struggle to reason over their own code.

Large language models (LLMs) are increasingly being applied to complex tasks that require multi-step reasoning, such as planning and scheduling. To deploy them responsibly, we need a clear understanding of where their reasoning succeeds and where it breaks down. A key component of this capability is algorithmic reasoning, the ability to solve problems through systematic computational procedures. For example, an LLM assisting with trip planning may need to represent cities as a graph and apply shortest path algorithms to identify the optimal route. We focus on evaluating algorithmic reasoning in LLMs, a fundamental yet often implicit capability that underlies effective problem solving. To this end, we introduce DSR Bench, a benchmark that uses data structures as a natural testbed for algorithmic reasoning. Data structures are the fundamental building blocks of algorithms and provide a principled way to probe how LLMs reason about relationships among entities. For instance, lists represent sequential order, trees encode hierarchical relationships, graphs model connectivity, and queues capture temporal ordering. DSR Bench covers 20 data structures, 35 operations, and 4,140 problem instances. The tasks are designed to increase in difficulty, enabling fine-grained analysis of model failures and helping identify specific types of relationships that challenge model reasoning. We evaluate 13 state-of-the-art LLMs. Beyond canonical data structure tasks, DSR Bench includes additional probes that assess reasoning over multi-dimensional data structures, in realistic scenarios, and in code generation settings.