QSTRBench: a New Benchmark to Evaluate the Ability of Language Models to Reason with Qualitative Spatial and Temporal Calculi

Technical Summary of QSTRBench: A New Benchmark to Evaluate the Ability of Language Models to Reason with Qualitative Spatial and Temporal Calculi

Problem Statement
Qualitative Spatial and Temporal Reasoning (QSTR) is a well-established field concerned with representing and reasoning about qualitative information (e.g., "left of," "before," "part of") using formal calculi. While Large Language Models (LLMs) have demonstrated impressive capabilities in natural language processing, their ability to perform rigorous reasoning within these formal systems remains unverified. Existing benchmarks often lack systematic coverage of core QSTR inference tasks or rely on informal questions not grounded in specific calculi. Furthermore, there is a debate regarding whether LLMs genuinely reason or merely replicate patterns from training data. This paper addresses the question of whether contemporary LLMs can perform the specific reasoning tasks associated with QSTR calculi: determining converse relations, computing relational compositions, and identifying conceptual neighbourhoods.

Methodology
The authors introduce QSTRBench, a comprehensive benchmark designed to test LLMs on nine distinct QSTR calculi: Point Algebra (PA), Allen's Interval Algebra (IA), Interval and Duration (INDU), Region Connection Calculus (RCC-5, RCC-8, RCC-22), the Nine Intersection Model (9IM), Cardinal Direction Calculus (CDC), and Revised STAR.

The benchmark evaluates three specific inference tasks for each calculus:

1. Converse: Given a relation $R(x, y)$, determine the relation $R^{-1}(y, x)$.
2. Composition Table (CT): Given $R_1(x, y)$ and $R_2(y, z)$, determine the possible relations between $x$ and $z$.
3. Conceptual Neighbourhood (CN): Identify relations that can directly follow a given relation under continuous deformation or translation.

The dataset comprises 1,806 questions covering 102 base relations across the selected calculi. To test robustness and the potential for pattern matching versus genuine reasoning, the authors created an extended dataset (QSTRBenchExtended) with 14,372 questions. This extended set varies prompt presentation through:

• Notation: Prefix vs. infix.
• Terminology: Standard English words, mathematical symbols, and "nonce" words (randomly generated terms with no semantic meaning).
• Description Styles: Natural language text, schematic ASCII diagrams, and LaTeX formulas.
• Anonymization: Swapping relation names (e.g., labeling "TPP" as "EC") to test if models rely on training data or prompt-specific logic.

The study evaluated 32 contemporary LLMs, ranging from frontier commercial models (e.g., GPT-5.2, Gemini-2.5-Pro, Grok-4) to smaller open-weights models (e.g., Llama-3, Gemma-3). Experiments were conducted with strict temperature settings (0.01) to minimize stochasticity, and results were reported as micro-averages of accuracy.

Key Contributions

1. Benchmark Creation: The release of QSTRBench and QSTRBenchExtended, providing the first extensive, open-source dataset for evaluating QSTR reasoning in LLMs across multiple calculi and prompt variations.
2. Novel Data: The publication of the RCC-22 Conceptual Neighbourhood (CN) for the first time, derived and verified by the authors.
3. Systematic Evaluation: A rigorous evaluation of 32 models across three inference tasks, analyzing performance not just by accuracy but also by token usage, reasoning traces, and consistency across repeats.
4. Methodological Rigor: The use of nonce words and schematic descriptions to probe whether models are retrieving memorized facts or performing logical inference.

Results

• General Performance: All tested models performed better than random guessing, but no model consistently answered all questions correctly. Performance varied significantly by calculus and task type.
• Task Difficulty: Models performed best on Converse questions, followed by Composition Table (CT) questions, with Conceptual Neighbourhood (CN) questions being the most challenging.
• Calculus Difficulty: Point Algebra (PA) was the most straightforward (highest accuracy), while RCC-22 was the most difficult. Interestingly, accuracy did not strictly correlate with the number of base relations; for instance, INDU (25 relations) was easier than RCC-22 (22 relations).
• Model Performance:
  • GPT-5.2 (with high reasoning effort) emerged as the top performer overall, achieving near-perfect scores on PA, CDC, and STAR, though it still struggled with RCC-22.
  • OpenAI's GPT-5.1 performed poorly (0.22 accuracy), significantly underperforming its predecessor (GPT-5) and successor (GPT-5.2), suggesting issues with its "adaptive reasoning" configuration.
  • Small Models: Smaller models (e.g., Gemma-3 1B, Llama-3 8B) performed very poorly, often failing basic identity or transitivity checks.
• Reasoning vs. Retrieval:
  • Models generally maintained high accuracy with standard prompts but showed degraded performance when relation names were swapped or replaced with nonce words, suggesting a reliance on training data patterns.
  • However, o1 and GPT-5.2 showed some ability to generalize even when descriptions were schematic or names were anonymized, though accuracy dropped significantly with schematic diagrams compared to text.
  • Hallucinations: Models frequently hallucinated non-existent relation names (e.g., "TPPPi" or invalid INDU relations), indicating a lack of deep semantic understanding of the calculi.
• Token Usage: More complex calculi (like RCC-22) required significantly more output tokens (orders of magnitude more than PA) for high-reasoning models, yet this did not guarantee perfect accuracy.

Significance and Claims
The paper claims that while LLMs demonstrate a capacity to simulate reasoning (outperforming random chance), they do not yet possess reliable, consistent reasoning capabilities for formal QSTR calculi. The authors emphasize that:

• Inconsistency: Even the best models produce different answers to the same question across repeats, even with fixed seeds.
• Limitations of Training Data: The drop in performance with nonce words and schematic prompts suggests that current models rely heavily on memorized patterns from training corpora rather than deriving answers from first principles.
• Complexity Barrier: The difficulty of RCC-22 compared to simpler calculi highlights a ceiling in current model capabilities regarding complex spatial topologies.
• Future Utility: The benchmark serves as a necessary tool for tracking progress in AI reasoning. The authors suggest that while LLMs may eventually replace symbolic reasoners, current neurosymbolic approaches (using LLMs to translate natural language to symbolic solvers) are still prone to translation errors that cause downstream failures.

The paper concludes modestly, noting that the evaluation is a snapshot of a rapidly evolving field and that the primary lasting value lies in the benchmark itself and the methodology for testing reasoning robustness.