A Temporal Reasoning Benchmarking Framework for LRMs via Difficulty-controlled and Dynamic Test Generation

Shide Zhou; Kailong Wang; Ling Shi; Haoyu Wang

Source-linked AI summary

A Temporal Reasoning Benchmarking Framework for LRMs via Difficulty-controlled and Dynamic Test Generation

Shide Zhou, Kailong Wang, Ling Shi, Haoyu Wang

arXiv:2607.04784v1Jul 6, 2026cs.SEcs.AI

TL;DR

Existing temporal-reasoning benchmarks provide limited difficulty control and process verification, leaving genuine deduction difficult to distinguish from pattern matching. TRACE addresses this with controllable Allen’s Interval Algebra tasks and trace-based auditing, finding performance strongly tracks difficulty (Pearson’s r approximately −0.96).

Problem
Temporal-reasoning benchmarks face contamination risks, coarse difficulty control, and outcome-centric evaluation that cannot distinguish genuine deduction from pattern matching.
Method
TRACE generates temporal constraint-satisfaction tasks with Allen’s Interval Algebra, tunable complexity, and a trace-based oracle verifying reasoning faithfulness.
Results
Pearson’s r approximately −0.96 between difficulty score and model accuracy, alongside scale-dependent Degenerative Loops and Reasoning Explosion under extreme complexity.
Takeaways & Limitations
Trace-level auditing is necessary to assess whether LRMs execute logic rather than merely mimic it, because outcome accuracy alone is insufficient for reliability.
Takeaways & Limitations
TRACE prioritizes logical control over naturalistic diversity and therefore does not substitute for benchmarks involving semantic ambiguity, linguistic nuance, and noisy real-world context.

Abstract

from arXiv · show

Defining the reasoning boundaries and ensuring the reliability of Large Reasoning Models (LRMs) remains a critical challenge. Current benchmarks primarily rely on static datasets susceptible to data contamination or synthetic tasks lacking fine-grained difficulty control. Furthermore, standard outcome-based evaluations often conceal reasoning flaws by neglecting the reasoning process. To address these limitations, we introduce TRACE, a testing framework that models temporal reasoning as constraint satisfaction problems via Allen's Interval Algebra. This approach enables precise regulation of logical complexity and incorporates a Trace-Based Verification Oracle to validate reasoning faithfulness. Using this framework, we construct TRACEBench, an extensive benchmark comprising 1,200 synthesized test instances across graded difficulty levels. We employ TRACE to evaluate eight widely used LRMs on TRACEBench. The results confirm a strong negative correlation between model performance and our difficulty metric (Pearson's r approximately -0.96), validating the effectiveness of our difficulty control mechanism. Moreover, our trace-based analysis exposes significant discrepancies between reasoning validity and final answers, revealing a high spurious guessing rate of approximately 28% in mid-sized models. In addition, we diagnose scale-dependent failure modes, ranging from Degenerative Loops in small models to Reasoning Explosion in advanced architectures. TRACE thus provides a robust, automated platform for benchmarking the true temporal reasoning capabilities of LRMs.

1 Introduction

TRACE addresses contamination, coarse difficulty control, and insufficient verification in temporal-reasoning benchmarks through dynamic generation, fine-grained complexity control, and dual trace-and-answer verification. Using TRACEBench, the study evaluates eight LRMs and identifies scale-dependent failure modes under extreme complexity.

Motivation: Reasoning improvements remain difficult to interpret because they may reflect genuine deduction or sophisticated pattern matching, complicating reliability assessment.This uncertainty motivates a specialized benchmarking framework for temporal reasoning.
Motivation: Existing benchmarks risk contamination through static aggregation or rely on coarse-grained difficulty proxies in synthetic tasks.Static suites can enable memorization, while synthetic frameworks reduce contamination risks but lack fine-grained control.
TRACE framework: TRACE combines dynamic data generation, fine-grained difficulty control, and dual verification using Allen’s Interval Algebra and a trace-based oracle.The framework is designed to validate both reasoning traces and final outcomes while synthesizing logically consistent temporal tasks with tunable complexity.
TRACEBench: 1,200 synthesized test instances span six difficulty levels in TRACEBench, which evaluates eight widely used LRMs without external solvers.Restricting external solvers focuses the assessment on intrinsic logical reasoning rather than tool-calling abilities.
Failure modes: Small and mid-sized models exhibit Degenerative Loops, whereas advanced models primarily encounter Reasoning Explosion under extreme complexity.Reasoning Explosion occurs when valid chains become too long and exceed the context window.

2 Background and Related Work

Large reasoning models extend inference with explicit intermediate deliberation, while reasoning benchmarks have progressed from static general tests toward synthetic, dynamic, and difficulty-controllable evaluation. Temporal benchmarks increasingly target dynamic synthesis, but existing methods remain largely outcome-centric or use coarse difficulty proxies.

Large Reasoning Models: LRMs use extended test-time inference to decompose complex problems into intermediate logical steps before producing a final conclusion.Specialized post-training, including reinforcement learning and rejection sampling, helps models internalize this deliberative process.
Reasoning Benchmarks: Reasoning evaluation has expanded from static mathematical and symbolic datasets to broad cross-domain and specialized logic-intensive benchmarks.GSM8K and MATH probe multi-step mathematical derivation, while BIG-Bench Hard and MMLU cover broader reasoning tasks.
Synthetic and Difficulty-Controlled Evaluation: Recent frameworks use synthetic generation and explicit difficulty controls to reduce contamination risks and improve evaluation granularity.PrOntoQA and DyVal generate logic puzzles, while GRADE models difficulty through reasoning depth and semantic distance.
Temporal Reasoning Benchmarks: Temporal reasoning benchmarks have progressed from static aggregation toward taxonomies and dynamic synthesis covering frequency, duration, ordering, symbolic, commonsense, and event-based reasoning.TRAM unifies datasets, TimeBench organizes temporal reasoning categories, and Test of Time and t-BEN use synthetic generation to mitigate memorization risks.
Open Evaluation Gap: Existing temporal evaluation remains largely outcome-centric or dependent on coarse-grained difficulty proxies, leaving a need for finer-grained assessment.This limitation persists despite recent synthetic and dynamic dataset-generation efforts.

3 Methodology

TRACE is a difficulty-controllable framework for evaluating LRMs on complex temporal reasoning scenarios. It dynamically generates tasks with tunable complexity and verifies reasoning faithfulness through a rigorous mechanism.

Framework design: TRACE evaluates LRMs on complex temporal reasoning scenarios using a difficulty-controllable testing framework.The methodology is designed specifically to control task difficulty during evaluation.
Dynamic task generation: The framework dynamically generates reasoning tasks with tunable complexity.Task complexity can be adjusted during generation rather than fixed in a static dataset.
Reasoning verification: TRACE includes a rigorous verification mechanism for assessing the faithfulness of model reasoning processes.The verification mechanism complements outcome-based evaluation by examining the reasoning process itself.

3.1 Overview of TRACE

TRACE generates temporal-reasoning tests through difficulty-configured constraint graphs, translates implicit logical relations into natural-language tasks, and evaluates LRMs using independently produced reasoning traces and final answers. A trace-based verifier then extracts model reasoning and validates it with a constraint solver.

Workflow: TRACE begins with a user-specified difficulty level and constructs mathematically consistent constraint graphs as each test case’s logical backbone.The workflow uses the Difficulty-Aware Constraint Generator described in Section 3.2.
Workflow: The Task Constructor converts abstract constraints into natural-language contexts and asks questions about implicit relations requiring deductive reasoning.Implicit relations are logical consequences not explicitly stated in the context.
Workflow: Target LRMs solve generated tasks independently without external tools or solvers, isolating evaluation of internal reasoning.Structured prompting requires both a formal reasoning process and a final answer.
Workflow: TRACE extracts reasoning traces from model responses and uses a constraint solver to validate them through its Trace-Based Verifier.The verifier is described in Section 3.4 and operates after task execution.

3.2 Difficulty-Aware Constraint Graph Generation

TRACE represents temporal reasoning tasks as labeled constraint graphs and controls difficulty through event-set scale and relation complexity. It then generates candidate configurations by estimating graph size, sampling weighted relations, and greedily calibrating their achieved complexity while preserving logical consistency.

Difficulty Definition: Difficulty jointly depends on event-set scale and constraint complexity, with |V|^α capturing scale growth and w(r) representing relation-specific inference cost.The formulation reflects increasing context and reasoning depth as events grow, while assigning different costs to temporal relations.
Problem Formalization: A temporal task is modeled as G = (V, E), with unique events in V and explicit Allen-labeled constraints in E.Implicit relations that must be inferred are excluded from E.
Complexity Calibration: D_ref = 10 and w ≈ 1.46 for the three-event atomic task yield α ≈ 1.75, anchoring the metric to a solvable transitive-inference baseline.The calibration uses 10 = 3^α · 1.46 and is intended to make difficulty grow smoothly with problem scale.
Candidate Configuration Generation: TRACE converts target difficulty D_tar into (n, m, L), estimates event count, samples constraint density, and selects relations using weights near the target mean complexity.The configuration contains n events, m explicit constraints, and an m-element multiset L of Allen relations.
Greedy Calibration: When achieved and target mean weights differ beyond tolerance, greedy swaps of extreme-weight relations move w_ach toward w_tar while keeping m fixed.The procedure repeatedly replaces highest- or lowest-weight relations symmetrically according to the direction of the error.
Path-Consistent Graph Instantiation: TRACE constructs the configured graph incrementally to guarantee satisfiability, avoiding contradictions from arbitrary assignments and structural bias from uneven constraint accumulation.Relation augmentation must embed remaining relations without concentrating disproportionate constraints on particular nodes.

3.3 Temporal Reasoning Task Construction

TRACE constructs temporal reasoning tasks from constraint graphs by verbalizing explicit premises, propagating constraints to identify deterministic implicit relations, and generating binary verification queries with ground-truth answers. A standardized prompt then presents the task and requires a structured JSON reasoning trace and final answer.

Task representation: Each task is formalized as T = (F, Q, A), comprising shared premise facts, candidate natural-language queries, and corresponding ground-truth answers.The task structure is derived from a generated temporal constraint graph G = (V, E).
Fact extraction: Fact Extraction maps each explicit Allen constraint to a natural-language descriptor, producing the textual fact set F.A predefined lexicon converts symbolic relations such as O into descriptors such as “overlaps.”
Constraint propagation: Constraint Propagation applies path consistency to compute permissible relations for event pairs and filters out pairs already explicitly defined in E.The remaining pairs represent implicit relationships requiring deduction rather than simple retrieval.
Question formulation: TRACE selects only deterministic inferred pairs satisfying |R_inferred(u, v)| = 1, then creates binary verification questions for each standard Allen relation.The unique inferred relation determines the corresponding ground-truth label, and all generated questions and labels populate Q and A.
Prompt construction: A standardized six-component prompt supplies constraints, Allen relation definitions, facts, questions, instructions, and an example while requiring JSON reasoning traces alongside final answers.This format enables subsequent parsing and verification of the model’s underlying logic.

3.4 Trace-Based Verification Oracle

TRACE’s verification oracle parses each model-generated reasoning trace and checks every derivation step against the ground-truth constraint network’s solver-implied temporal relations. It combines strict reasoning-chain validity with final-answer correctness to distinguish faithful reasoning from spurious or failed outcomes.

Verification mechanism: The oracle executes temporal reasoning tasks, parses structured traces, and validates each derivation step against the ground-truth constraints.Its purpose is to detect valid temporal reasoning rather than statistical shortcuts.
Trace extraction: A robust regex parser extracts the step-by-step reasoning trace from the LRM’s structured JSON output, accommodating formatting irregularities.The output includes an internal thinking process, a reasoning chain, and a final answer.
Step validation: For each extracted triplet, TRACE uses path consistency on the ground-truth graph to compute the solver-implied propagated relation set.This replaces comparison with a predefined reference or rule-based solution by checking algebraic closure.
Step validation: A reasoning step is valid only when its claimed relation set exactly matches the relation set implied by the constraint-solver closure.The strict criterion accepts any derivation route that satisfies every step and rejects ambiguous or incorrect intermediate claims.
Faithfulness assessment: TRACE classifies outcomes using the conjunction of reasoning-chain correctness and binary final-answer correctness into True Reasoning, Spurious Guessing, Answer Misalignment, and Complete Failure.These categories respectively distinguish correct valid reasoning, correct answers with flawed reasoning, sound reasoning with incorrect answers, and failure on both dimensions.

4 Evaluation … 4.3 RQ2: Benchmarking LLM Performance

TRACE evaluates eight LRMs on TRACEBench, a six-level temporal reasoning benchmark generated with precise difficulty control. Performance generally scales with model size, while architecture and model scale shape distinct reasoning strengths and failure modes.

4 Evaluation: TRACE frames evaluation around four questions on difficulty controllability, model performance, reasoning faithfulness, and characteristic failure modes.
4.1 Evaluation Setup: The evaluation covers four distilled DeepSeek-R1 models and four advanced API-based models, with all models limited to 8,192 generated tokens.The distilled models comprise Qwen-based 7B, 14B, and 32B variants plus Llama-8B; advanced models are Gemini-2.5-Flash, DeepSeek-R1, GPT-5-mini, and Claude-Sonnet-4.6.
4.1 Evaluation Setup: TRACEBench contains 1,200 reasoning questions across six difficulty levels, from Dtar ∈{10, 45, 80, 115, 150, 185}.Each tier uses 40 distinct constraint graphs and 200 questions across those graphs.
4.2 RQ1: Analysis of Difficulty Controllability: Average graph nodes increase from 3.00 to 16.00 and edges from 2.00 to 59.98 as target difficulty rises from 10 to 185.Achieved difficulty closely matches targets, including 44.97 at target 45 and 185.40 at target 185.
4.2 RQ1: Analysis of Difficulty Controllability: r_avg = −0.96: all evaluated LRMs show a strong negative correlation between relative difficulty and True Reasoning Accuracy.For example, DeepSeek-R1-Distill-Qwen-32B falls from 67.50% at difficulty 10 to 29.50% at difficulty 185, while Llama-8B falls from 46.00% to 15.50%.
4.3 RQ2: Benchmarking LLM Performance: At difficulty 10, Qwen-7B, Qwen-14B, and Qwen-32B achieve True Reasoning accuracies of 54.50%, 67.00%, and 67.50%, respectively.The Qwen series shows a positive relationship between temporal reasoning capability and model scale, especially as difficulty increases.
4.3 RQ2: Benchmarking LLM Performance: Llama-8B scores 46.00% versus Qwen-7B’s 54.50% at difficulty 10, but smaller Llama-8B becomes more robust as task complexity escalates.The findings identify base architecture as a critical factor, with Llama-8B approaching larger Qwen models under greater difficulty.
4.3 RQ2: Benchmarking LLM Performance: 56 and 52 spurious samples per level: Qwen-14B and Qwen-32B show the highest Spurious Guessing rates, while Llama-8B and Qwen-7B average 17.83 and 16.17 Answer Misalignment samples per level.Advanced models achieve average True Reasoning Accuracies of 83.00% for Claude-Sonnet-4.6, 80.50% for DeepSeek-R1, and 79.83% for GPT-5-mini, but extreme complexity remains challenging.

4.4 RQ3: Assessment of Reasoning Faithfulness

TRACE’s trace-based analysis reveals that outcome-based accuracy can substantially overestimate true temporal reasoning, especially in mid-sized models. Advanced models show much closer alignment between correct answers and valid reasoning traces, supporting trace-based verification.

RQ3: Assessment of Reasoning Faithfulness: Spurious guessing measures correct final labels produced despite invalid reasoning traces, exposing discrepancies between outcome-based accuracy and true reasoning performance.It detects reliance on statistical shortcuts rather than logical deduction.
RQ3: Assessment of Reasoning Faithfulness: 28.00% and 26.00% are the average spurious guessing rates of DeepSeek-R1-Distill-Qwen-14B and 32B across all difficulties.The 14B model peaks at 35.00% at Difficulty 150.
RQ3: Assessment of Reasoning Faithfulness: 28.50% is the DeepSeek-R1-Distill-Qwen-7B spurious guessing rate at Difficulty 45, followed by a sharp decline as complexity increases.The decline aligns with performance collapse rather than improved reasoning faithfulness, as correct-label predictions become less reliable at high complexity.
RQ3: Assessment of Reasoning Faithfulness: 7.83% is DeepSeek-R1’s average spurious guessing rate, remaining low with only minor fluctuations at intermediate difficulty.GPT-5-mini and Claude-Sonnet-4.6 also maintain relatively low and stable spurious rates.
RQ3: Assessment of Reasoning Faithfulness: Up to 28.00% average spurious guessing shows that outcome-based metrics significantly overestimate mid-sized-model performance, whereas advanced models align answers more consistently with valid reasoning.These findings motivate TRACE’s trace-based verification for precise evaluation.

4.5 RQ4: Diagnosis of Failure Modes

The diagnosis identifies three logical failure modes—direct inference errors, reasoning stagnation, and hallucination under complexity—and two structural modes: format non-compliance and context-window exhaustion. Failure patterns vary by model scale, with direct inference errors dominating logical errors and advanced models exhibiting reasoning explosion.

Logical Failures: Direct Inference Error is the most common logical failure, arising when models misapply transitivity or temporal constraints and reach incorrect conclusions.It accounts for at least 50% of logical errors across every evaluated model.
Logical Failures: Reasoning Stagnation produces lengthy, structurally valid traces that rephrase or permute facts without making logical progress, forcing models to guess.It remains a persistent baseline issue across distilled models.
Logical Failures: Hallucination under Complexity causes models to introduce undefined events or non-standard relations into JSON reasoning traces across model scales.Examples include non-existent events such as “As” and “?” and relations such as “less_than” or “cannot overlap.”
Structural Failures: Format Non-Compliance is concentrated in small and mid-sized models, while Context Window Exhaustion truncates generation after the token limit is exceeded.The exhaustion mechanisms include Reasoning Explosion from exponentially growing inference chains and Degenerative Loops involving indefinite repetition.
Structural Failures: 100.00% of DeepSeek-R1’s structural failures are driven by Reasoning Explosion, whereas Degenerative Loops are severe in open-weights distilled models and Gemini-2.5-Flash.Format issues are primarily confined to smaller models; GPT-5-mini and Claude-Sonnet-4.6 recorded zero parse failures.

5 Discussion

The discussion argues that reliable LRM evaluation must verify reasoning processes rather than rely on final-answer accuracy, while positioning TRACE as a diagnostic of intrinsic deduction. It also acknowledges that controlled synthesis sacrifices naturalistic linguistic diversity and suggests process supervision and consistency penalties for development.

The Shift to Process-Centric Verification: Outcome-based accuracy cannot distinguish genuine deduction from statistical “Clever Hans” behavior, motivating verification of reasoning as a traceable process.The discussion frames process-centric verification as necessary for safety and reliability in high-stakes LRM applications.
Guidance for LRM Development: Process Reward Models can supervise intermediate deductive steps, while consistency penalties can target mismatches between reasoning traces and final labels.These recommendations address spurious guessing and answer misalignment during LRM training and alignment.
Evaluating Pure Reasoning: TRACE isolates intrinsic logical capabilities by enforcing self-contained reasoning without external solver augmentation, which would instead evaluate tool-use proficiency.The framework is presented as a targeted diagnostic instrument across varying complexities.
Trade-offs in Controlled Synthesis: Controlled synthesis prioritizes logical control over naturalistic diversity, isolating deductive capacity while omitting real-world semantic ambiguity, linguistic nuance, and noisy context.Accordingly, TRACE is characterized as a diagnostic instrument for intrinsic reasoning rather than a fully naturalistic evaluation.

6 Conclusion

TRACE uses Allen’s Interval Algebra to generate difficulty-controllable temporal reasoning tasks for LRM benchmarking, culminating in the graded TRACEBench benchmark. Its evaluation aligns task complexity with model performance while revealing that outcome-only metrics can mask Spurious Guessing in mid-sized models.

6 Conclusion: TRACE leverages Allen’s Interval Algebra to generate difficulty-controllable tasks for benchmarking LRMs.The framework is designed to regulate task difficulty systematically.
6 Conclusion: TRACEBench is a comprehensive graded benchmark designed to systematically probe LRM reasoning boundaries.The benchmark is constructed directly from the TRACE framework.
6 Conclusion: Evaluation confirms precise alignment between task complexity and model performance.This supports the framework’s difficulty-control design.
6 Conclusion: Outcome-based metrics are inadequate because Spurious Guessing is prevalent in mid-sized models.Trace-based evaluation exposes reasoning problems that final-answer metrics can miss.