# TCP: a Benchmark for Temporal Constraint-Based Planning

arXiv: https://arxiv.org/abs/2505.19927 · HTML: https://mlsanity.com/paper/2505.19927/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 19 of its 25 references that are in the map.
- First posted on arXiv 26 May 2025.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)

## Builds on (most cited first, 19 of 19)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Gemma 3 Technical Report](https://mlsanity.com/paper/2503.19786/) (2025)
- [TravelPlanner: A Benchmark for Real-World Planning with Language Agents](https://mlsanity.com/paper/2402.01622/) (2024)
- [PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change](https://mlsanity.com/paper/2206.10498/) (2022)
- [SelfCheck: Using LLMs to Zero-Shot Check Their Own Step-by-Step Reasoning](https://mlsanity.com/paper/2308.00436/) (2023)
- [A Dataset for Answering Time-Sensitive Questions](https://mlsanity.com/paper/2108.06314/) (2021)
- [On the Self-Verification Limitations of Large Language Models on Reasoning and Planning Tasks](https://mlsanity.com/paper/2402.08115/) (2024)
- [NATURAL PLAN: Benchmarking LLMs on Natural Language Planning](https://mlsanity.com/paper/2406.04520/) (2024)
- [Large Language Models Can Learn Temporal Reasoning](https://mlsanity.com/paper/2401.06853/) (2024)
- [Question Answering Over Temporal Knowledge Graphs](https://mlsanity.com/paper/2106.01515/) (2021)
- [Test of Time: A Benchmark for Evaluating LLMs on Temporal Reasoning](https://mlsanity.com/paper/2406.09170/) (2024)
- [Distilling Script Knowledge from Large Language Models for Constrained Language Planning](https://mlsanity.com/paper/2305.05252/) (2023)
- [Graph-enhanced Large Language Models in Asynchronous Plan Reasoning](https://mlsanity.com/paper/2402.02805/) (2024)
- [Robust Planning with LLM-Modulo Framework: Case Study in Travel Planning](https://mlsanity.com/paper/2405.20625/) (2024)
- [Are Large Language Models Temporally Grounded?](https://mlsanity.com/paper/2311.08398/) (2023)
- [TimeArena: Shaping Efficient Multitasking Language Agents in a Time-Aware Simulation](https://mlsanity.com/paper/2402.05733/) (2024)
- [ChronoSense: Exploring Temporal Understanding in Large Language Models with Time Intervals of Events](https://mlsanity.com/paper/2501.03040/) (2025)
- [Haste Makes Waste: Evaluating Planning Abilities of LLMs for Efficient and Feasible Multitasking with Time Constraints Between Actions](https://mlsanity.com/paper/2503.02238/) (2025)

## Built on by (most cited first, 8 of 8)

- [DeepPlanning: Benchmarking Long-Horizon Agentic Planning with Verifiable Constraints](https://mlsanity.com/paper/2601.18137/) (2026)
- [When Parallelism Pays Off: Cohesion-Aware Task Partitioning for Multi-Agent Coding](https://mlsanity.com/paper/2606.00953/) (2026)
- [Do Language Models Update their Forecasts with New Information?](https://mlsanity.com/paper/2509.23936/) (2025)
- [Self-Exploring Language Models for Explainable Link Forecasting on Temporal Graphs via Reinforcement Learning](https://mlsanity.com/paper/2509.00975/) (2025)
- [Can Large Language Models Generalize Procedures Across Representations?](https://mlsanity.com/paper/2602.03542/) (2026)
- [Evaluating Temporal Consistency in Multi-Turn Language Models](https://mlsanity.com/paper/2604.23051/) (2026)
- [SCHEDBench: A Benchmark for Evaluating LLM Constraint Faithfulness in Natural-Language Combinatorial Scheduling](https://mlsanity.com/paper/2608.00991/) (2026)
- [Iti-Validator: A Guardrail Framework for Validating and Correcting LLM-Generated Itineraries](https://mlsanity.com/paper/2510.24719/) (2025)

## Abstract (arXiv)

Temporal reasoning and planning are essential capabilities for large language models (LLMs), yet most existing benchmarks evaluate them in isolation and under limited forms of complexity. To address this gap, we introduce the Temporal Constraint-based Planning (TCP) benchmark that jointly assesses both capabilities. Each instance in TCP features a naturalistic dialogue around a collaborative project, where diverse and interdependent temporal constraints are explicitly or implicitly expressed, and models must infer an optimal schedule that satisfies all constraints. To construct TCP, we generate abstract problem prototypes that are then paired with realistic scenarios from various domains and enriched into dialogues using an LLM. A human quality check is performed on a sampled subset to confirm the reliability of our benchmark. We evaluate state-of-the-art LLMs and find that even the strongest models may struggle with TCP, highlighting its difficulty and revealing limitations in LLMs' temporal constraint-based planning abilities. We analyze underlying failure cases, open source our benchmark, and hope our findings can inspire future research.