Beyond Accuracy: Diagnosing Algebraic Reasoning Failures in LLMs Across Nine Complexity Dimensions

• URL: http://arxiv.org/abs/2604.06799v1
• Date: Wed, 08 Apr 2026 08:12:45 GMT
• Title: Beyond Accuracy: Diagnosing Algebraic Reasoning Failures in LLMs Across Nine Complexity Dimensions
• Abstract summary: Algebraic reasoning remains one of the most informative stress tests for large language models.<n>Current benchmarks provide no mechanism for attributing failure to a specific cause.<n>We introduce a nine-dimension framework in which each factor is varied independently while all others are held fixed.
• Score: 8.616356693448985
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Algebraic reasoning remains one of the most informative stress tests for large language models, yet current benchmarks provide no mechanism for attributing failure to a specific cause. When a model fails an algebraic problem, a single accuracy score cannot reveal whether the expression was too deeply nested, the operator too uncommon, the intermediate state count too high, or the dependency chain too long. Prior work has studied individual failure modes in isolation, but no framework has varied each complexity factor independently under strict experimental control. No prior system has offered automatic generation and verification of problems of increasing complexity to track model progress over time. We introduce a nine-dimension algebraic complexity framework in which each factor is varied independently while all others are held fixed, with problem generation and verification handled by a parametric pipeline requiring no human annotation. Each dimension is grounded in a documented LLM failure mode and captures a structurally distinct aspect of algebraic difficulty, including expression nesting depth, simultaneous intermediate result count, sub-expression complexity, operator hardness, and dependent reasoning chain length. We evaluated seven instruction-tuned models spanning 8B to 235B parameters across all nine dimensions and find that working memory is the dominant scale-invariant bottleneck. Every model collapses between 20 and 30 parallel branches regardless of parameter count, pointing to a hard architectural constraint rather than a solvable capacity limitation. Our analysis further identifies a minimal yet diagnostically sufficient subset of five dimensions that together span the full space of documented algebraic failure modes, providing a complete complexity profile of a model's algebraic reasoning capacity.

Related papers

• Tight Bounds for Data-driven Multiple Hyper-parameter Tuning with Structured Loss Function [18.20955065779317]
  We introduce tight pseudo-dimension bounds for multi-dimensional data-driven tuning.<n>By constructing problem instances across distinct sample regimes, we prove our upper bounds are tightly saturated.<n>We extend our framework to accommodate general bi-level validation-loss tuning and broader semi-algebraic applications.
  arXiv  Detail & Related papers  (2026-08-18T04:02:51Z)
• Empirical Evidence of Complexity-Induced Limits in Large Language Models on Finite Discrete State-Space Problems with Explicit Validity Constraints [0.6524460254566904]
  We systematically evaluate the robustness of reasoning in Large Reasoning Models (LRMs) under progressively increasing problem complexity.<n>We construct a suite of nine classical reasoning tasks: Boolean Satisfiability, Cryptarithmetic, Graph Coloring, River Crossing, Tower of Hanoi, Water Jug, Checker Jumping, Sudoku, and Rubik's Cube.<n>We observe substantial accuracy declines, often exceeding 50%, accompanied by inconsistent reasoning traces, constraint violations, loss of state tracking, and confidently incorrect outputs.
  arXiv  Detail & Related papers  (2026-04-15T00:35:22Z)
• Beyond Memorization: Testing LLM Reasoning on Unseen Theory of Computation Tasks [8.210112631285666]
  Large language models (LLMs) have demonstrated strong performance on formal language tasks.<n>We introduce a benchmark for deterministic finite automata (DFA) construction from regular languages.<n>We show that models achieve perfect accuracy on factual questions and 84-90% on seen tasks, but accuracy drops sharply on unseen problems.
  arXiv  Detail & Related papers  (2026-01-19T21:00:31Z)
• Estimating Ising Models in Total Variation Distance [23.343281561400033]
  We consider the problem of estimating Ising models over $n$ variables in Total Variation (TV) distance, given $l$ independent samples from the model.<n>Our main contribution is a unified analysis of the Maximum Pseudo-Likelihood Estorimator (MPLE) for two general classes of Ising models.<n>Our results yield optimal or near-time algorithms and optimal or near-time sample complexity guarantees in a variety of settings.
  arXiv  Detail & Related papers  (2025-11-26T03:15:41Z)
• Bridging Reasoning to Learning: Unmasking Illusions using Complexity Out of Distribution Generalization [8.236500918322138]
  We propose Complexity Out of Distribution (Complexity OoD) generalization as a framework to define and measure reasoning.<n>A model exhibits Complexity OoD generalization when it maintains performance on test instances whose minimal required solution complexity exceeds that of all training examples.<n>We translate this perspective into practice with recommendations for operationalizing Complexity OoD across the stack.
  arXiv  Detail & Related papers  (2025-10-06T13:08:31Z)
• Why Can't Transformers Learn Multiplication? Reverse-Engineering Reveals Long-Range Dependency Pitfalls [54.57326125204404]
  Language models are increasingly capable, yet still fail at a seemingly simple task of multi-digit multiplication.<n>We study why, by reverse-engineering a model that successfully learns multiplication via emphimplicit chain-of-thought'
  arXiv  Detail & Related papers  (2025-09-30T19:03:26Z)
• Syzygy of Thoughts: Improving LLM CoT with the Minimal Free Resolution [59.39066657300045]
  Chain-of-Thought (CoT) prompting enhances the reasoning of large language models (LLMs) by decomposing problems into sequential steps.<n>We propose Syzygy of Thoughts (SoT)-a novel framework that extends CoT by introducing auxiliary, interrelated reasoning paths.<n>SoT captures deeper logical dependencies, enabling more robust and structured problem-solving.
  arXiv  Detail & Related papers  (2025-04-13T13:35:41Z)
• A Probabilistic Neuro-symbolic Layer for Algebraic Constraint Satisfaction [13.245011236407166]
  In safety-critical applications, satisfaction of constraints linear continuous environments is crucial, e.g., an autonomous agent should never crash or go off-road.<n>We introduce different approximations that guarantee the satisfaction of non-junctionable constraints.<n>This formulation enables efficient and exact renormalization via symbolic integration.
  arXiv  Detail & Related papers  (2025-03-25T08:58:04Z)
• Identification and Estimation of Simultaneous Equation Models Using Higher-Order Cumulant Restrictions [5.882065571122133]
  Identifying structural parameters in linear simultaneous-equation models is a longstanding challenge.<n>We show that neither zero covariance proofs nor whitening is necessary to identify structural parameters.<n>Our framework provides a transparent overidentification test.
  arXiv  Detail & Related papers  (2025-01-12T11:27:39Z)
• MathGAP: Out-of-Distribution Evaluation on Problems with Arbitrarily Complex Proofs [80.96119560172224]
  MathGAP generates problem statements and chain-of-thought reasoning traces according to specifications about their arithmetic proof structure.<n>Using MathGAP, we find that LLMs show a significant decrease in performance as proofs get deeper and wider.
  arXiv  Detail & Related papers  (2024-10-17T12:48:14Z)
• Faith and Fate: Limits of Transformers on Compositionality [109.79516190693415]
  We investigate the limits of transformer large language models across three representative compositional tasks. These tasks require breaking problems down into sub-steps and synthesizing these steps into a precise answer. Our empirical findings suggest that transformer LLMs solve compositional tasks by reducing multi-step compositional reasoning into linearized subgraph matching.
  arXiv  Detail & Related papers  (2023-05-29T23:24:14Z)
• The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning [80.1018596899899]
  We argue that neural network models share this same preference, formalized using Kolmogorov complexity. Our experiments show that pre-trained and even randomly language models prefer to generate low-complexity sequences. These observations justify the trend in deep learning of unifying seemingly disparate problems with an increasingly small set of machine learning models.
  arXiv  Detail & Related papers  (2023-04-11T17:22:22Z)
• Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
  Most datasets only capture a simpler subproblem and likely suffer from spurious features. We study adversarial robustness - a local generalization property - to reveal hard, model-specific instances and spurious features. Unlike in other applications, where perturbation models are designed around subjective notions of imperceptibility, our perturbation models are efficient and sound. Surprisingly, with such perturbations, a sufficiently expressive neural solver does not suffer from the limitations of the accuracy-robustness trade-off common in supervised learning.
  arXiv  Detail & Related papers  (2021-10-21T07:28:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.