acceptodds
Under review as a conference paper at ICLR 2027

TRIAL: Benchmarking Temporal Rule Inference through Active Learning

Abstract

Agents that work on long-horizon tasks often have to learn how an unfamiliar system works by experimenting, and decide when their evidence is enough to act on. We introduce TRIAL (Temporal Rule Inference through Active Learning), a benchmark in which an agent identifies a hidden temporal rule, a deterministic finite automaton (DFA), by building experiments in a procedurally generated game world. An exact verifier tracks which rules remain consistent with the agent’s evidence, so TRIAL scores whether an answer is correct and also whether the evidence supports it. We show that frontier agents guess before their evidence settles the rule. When the rule space is large, they exhaust their budget first, and all 88 wrong answers in our main evaluation came within the last 27 of 240 decisions while a median of 260 candidate rules were still possible. When the rule space is small, they commit early with budget to spare, and halving the budget makes these guesses more common. Exact-answer scoring hides the guesses that happen to be right, such as the 29% of Opus’s correct answers with code that were made while other rules remained. With code, Astra and Opus write programs that enumerate the candidate rules, yet no system identifies a rule on the hardest condition. Without code, the agents remove more uncertainty than a greedy information-gain controller, but the uncertainty they report drifts away from what the evidence supports.

Primary area:
datasets and benchmarks
Keywords:
Interactive reasoning, active learning, rule induction, temporal reasoning, finite state automata, agent benchmarks

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_7U44OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes TRIAL, which evaluates active discovery of hidden temporal rules in procedurally generated worlds. Agents construct experiments through navigation and material manipulation, observe partial feedback, and make an irreversible rule commitment. The experiments compare frontier agent systems with and without solver code and file memory. The authors found that no system identifies a rule on the hardest condition. The paper makes several analyses. For example, Exact-answer scoring hides the guesses that happen to be right.

Critical strengths
  1. The benchmark provides precise, turn-level diagnostics of information acquisition. It helps for fine-grained experimental analyses. Also, the difficulty is controlled through hypothesis-space size and experiment cost.
  2. The paper introduces a concrete planning challenge. Requiring agents to construct experiments through environmental actions also introduces a meaningful trade-off between information gain and execution cost. The trajectory-level analysis, including hypothesis elimination, remaining uncertainty, etc., offers more diagnostic information than a binary success rate.
Critical weaknesses
  1. Insufficient validation of task feasibility and the experimental planning baseline. The paper states that no system identifies a rule on the hardest condition. However, a major concern is whether the harder benchmark conditions are reliably identifiable within the allocated interaction budget. The generator guarantees that an accepting state is reachable, but this is not equivalent to guaranteeing that the hidden rule can be uniquely identified within 240 decisions. Without such a reference, it is difficult to determine how much of the observed failure reflects inadequate experimental planning capabilities rather than insufficient budget or limitations of the task interface.

  2. Limited depth of the empirical insights. The main empirical findings are largely consistent with prior expectations. For example, correct answers may remain underdetermined by the collected evidence, agents may exhaust their budgets before resolving uncertainty and then submit wrong answers, and self-reported uncertainty may deviate from the evidence-based reference, etc. These observations are reasonable but they seem not to provide substantially new insights into the mechanisms underlying failures in agentic scientific experimentation.

Questions for authors
  1. Could the authors bring more specific analyses on whether the primary bottleneck lies in experiment selection, long-horizon planning, cost estimation, belief tracking, etc.? The mechanism-level analyses would make the observations of the work more insightful. I would find the empirical contribution substantially stronger if the benchmark were used to uncover more specific, non-trivial failure mechanisms, rather than primarily confirming anticipated consequences on budget-constrained hypothesis identification.
  2. The greedy baseline in Section 4.3 already uses the exact posterior and information gain per action. However, it does not establish whether the hardest main-benchmark targets can be uniquely identified within the allocated budget. Could the authors provide budget-feasible identification trajectories or results from a stronger planning reference for these targets?
1 comment

We thank the reviewer for the thorough review.

Addressing the questions:

primary bottleneck

We tried to focus on leveraging the structural qualities of the task design for evaluation rather than using black box evaluation to score the large volume of data from the benchmark.

budget constraints

This is a good point. Our results show that the agents are able to solve even the hardest environments. The additional results for reviewer 2 show that, as expected, increasing the budget increases the success rate of the agents.

As noted by the reviewer, this dynamic is expected and not unique. We want to highlight our core contribution. Unlike other benchmarks and exploration evaluation environments, where a semi-formal rule is encoded into an environment through a rubric, we begin with a strict formal representation of a rule in DFA form. By adding arbitrary epsilon moves to the DFA, we can easily construct easy (a few epsilon moves) and hard (more epsilon moves) environments that have different syntactic and semantic difficulty whilst remaining structurally identical.

One episode starts in the easy environments. These have very low noise, with some degree of exploration; the agent should be able to brute-force these cheaper environments. As the agent solves the environments, the benchmark progressively loads in harder games that still obey the same rule. Once the agent believes that it has understood the underlying rule, it can commit its hypothesis to the scorer, which can deterministically verify the hypothesis.

The ramp-up nature of the tasks is designed to penalize brute-force strategies. We find that even frontier reasoning agents tend to fall into these patterns.

Reviewer_5U4QOpenReview ↗
Rating
2(−1)
Confidence
4
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces TRIAL, a procedurally generated benchmark in which agents infer hidden temporal rules represented by deterministic finite automata through experiments conducted in a game world. Its central feature is an exact verifier that tracks the rules consistent with the observations, allowing evaluation to distinguish answer correctness from unique identification supported by evidence. Experiments with three agent systems, with and without code access and file memory, demonstrate the diagnostic value of this distinction and reveal difficulties in acquiring sufficiently informative evidence under limited interaction budgets.

Critical strengths
  1. The exact evaluation of evidence sufficiency is a compelling contribution. The verifier makes it possible to determine whether an agent’s observations uniquely identify the hidden rule, including in episodes where the final answer is correct. This provides a principled way to distinguish successful identification from a correct but underdetermined answer. Tracking the consistent hypothesis set throughout an episode also measures meaningful progress in unsuccessful runs.

  2. The benchmark meaningfully connects experimental design with the execution of experiments. Agents must account for navigation, material collection, and other actions when deciding which experiments to perform. The persistence of the hidden rule across changing worlds and material-role assignments creates a useful setting for studying how agents accumulate evidence while managing the practical cost of obtaining it.

Critical weaknesses
  1. The uncertainty analysis needs a more precise interpretation. Agents report answer entropy, but the primary reference in Sec 4.4 is the log support, log⁡2∣Ht∣\log_2 |H_t|. As Appendix C.1 explicitly acknowledges, marginalizing the unknown material-role bindings can produce unequal posterior probabilities among surviving rules, so posterior entropy can be strictly smaller than log support. Consequently, a reported entropy below log support does not by itself establish inaccurate uncertainty estimation. Comparing reports with the actual posterior entropy, and reporting absolute errors alongside signed gaps, would strengthen this analysis. At minimum, the main-text interpretation should reflect the distinction already explained in the appendix.
  2. The related-work discussion would benefit from clearer positioning within both agentic automata learning and temporal-specification learning. The “Agentic automata learning” paragraph currently centers on Menaged et al. (2026), but the broader line of work also includes L*LM [1], CAPAL [2], and CEDAR [3]. These works explore different ways to construct and refine automata through interactions among language models, formal learning algorithms, and sources of feedback. L*LM combines demonstrations with LLM-provided membership judgments; CAPAL addresses persistently noisy membership feedback within the pMAT framework where LLMs are served as membership oracle and equivalence oracle; and CEDAR integrates LLM semantic judgments with execution-based counterexamples to learn automata for embodied skills and constraints. Discussing these approaches together would help clarify how TRIAL’s allocation of responsibility for hypothesis construction, experiment selection, and evidence integration relates to existing agentic automata-learning settings. The connection to temporal-specification learning is also relevant given the paper’s emphasis on temporal rule inference. Lang2LTL [4] and NL2TL [5] study learning or grounding formal temporal specifications from natural-language instructions. Their relationship to TRIAL would help clarify the source of the temporal knowledge being acquired: these systems derive specifications from descriptions of intended behavior, while TRIAL requires agents to discover hidden temporal rules through experiments they design and execute. This comparison would strengthen the motivation for studying temporal inference through interaction and explain which additional challenges the benchmark introduces. Organizing the discussion around the role of the LLM, the source and reliability of feedback, and the learning objective would make TRIAL’s particular contribution more apparent: evaluating experiment selection and commitment decisions under world-dependent action costs, without an equivalence oracle, while checking exactly whether the accumulated evidence uniquely identifies the hidden rule. It would also make the phrase “removing the teacher” more precise by distinguishing the removal of an explicit equivalence oracle from the continued availability of rule-dependent environmental feedback.

References

[1] Marcell Vazquez-Chanlatte, Karim Elmaaroufi, Stefan Witwicki, Matei Zaharia, and Sanjit A. Seshia. 2025. L*LM: Learning Automata from Demonstrations, Examples, and Natural Language. International Conference on Neuro-symbolic Systems, PMLR 288:543–569.

[2] Lekai Chen, Ashutosh Trivedi, and Alvaro Velasquez. 2026. Towards Persistent Noise-Tolerant Active Learning of Regular Languages with Class Query. ICLR 2026.

[3] Lekai Chen, Alvaro Velasquez, and Ashutosh Trivedi. 2026. CEDAR: Automata as Verifiable Interfaces for Language-Guided Embodied Action. arXiv:2608.27797.

[4] Jason Xinyu Liu, Ziyi Yang, Ifrah Idrees, Sam Liang, Benjamin Schornstein, Stefanie Tellex, and Ankit Shah. 2023. Grounding Complex Natural Language Commands for Temporal Tasks in Unseen Environments. CoRL 2023, PMLR 229:1084–1110.

[5] Yongchao Chen, Rujul Gandhi, Yang Zhang, and Chuchu Fan. 2023. NL2TL: Transforming Natural Languages to Temporal Logics using Large Language Models. EMNLP 2023, pp. 15880–15903.

Questions for authors
  1. The code-enabled results suggest that experiment construction may be a major bottleneck, but the command audit only verifies the presence of enumeration code, not its correctness. Could the authors further validate the agents’ candidate-tracking implementations or evaluate agents with a supplied, verified solver to better isolate failures in experiment selection and execution from errors in hypothesis inference?

  2. The main evaluation includes only five distinct target rules per difficulty condition, and each file-memory stream follows a single target order. Could the authors expand the evaluation to include more independently sampled targets and multiple memory-stream orderings to strengthen the reliability of model comparisons and assess whether the observed failure patterns generalize across different rules?

1 comment

We thank the reviewer for the thorough review.

To answer the questions:

Could we validate candidate tracking or supply a verified solver?

We ran an additional condition that supplies the exact set of rules consistent with the observations after every action. On ten new targets in the hardest condition, neither Astra nor Opus made a supported identification with this assistance at the standard 240-decision budget.

Could we evaluate more targets and memory-stream orderings?

We ran 60 additional games on ten new shared targets in the hardest condition, with fresh standard-budget controls, exact-candidate assistance, and double the budget. We show our findings below.

SystemStandard, 240Exact candidates, 240Standard feedback, 480
Astra0/100/104/10
Opus0/100/101/10

These results extend the target sample and show the same difficulty at the standard budget on new rules. We have not tested alternative memory orders. However, the main difficulty also appears in cold-start runs and persists on ten additional targets. In the memory runs conducted for the paper, we observe earlier identification among successful code-enabled games, alongside reuse of helper programs.

Reviewer_4ogsOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

I am putting my entire review here, as a sort of protest against the review form, which just makes it harder to be clear, in my honest opinion.

Paper 54418: TRIAL: Benchmarking Temporal Rule Inference through Active Learning

This paper presents TRIAL, a benchmark for rule learning by LLM agents. TRIAL acts as a surogate for performing real experiments in the world. An "episode" generated by TRIAL consists of multiple "level"s based on a single "rule". The objective is to identify the rule efficiently. The space of possible rules is explicitly provided by TRIAL to the agents. Various LLMs, with and without coding abilities, were applied to TRIAL in multiple "games", and results were reported as a function of rule difficulty.

The paper is problematic as science because none of it is made clear. There is a large vocabulary of concepts used to describe TRIAL: episodes, games, sequences, offerings, levels, experiments, actions, commitments, rules, patterns, explore, fuse, test, materials, shrine, parts of a rule, placements, budget, catalog, referee, controller, readings, completion... All these are obviously must have some technical meaning within TRIAL, but in the paper they are just used as English words. This does not work. From the English words I infer that there is some sort of interaction between the generated episode (game?) and the agent. The examples in the appendices suggest this is ongoing, but Figure 1 suggests it is more one-shot. The primary point of the paper is to present TRIAL, but really it studiously declines to do this. It makes statements about TRIAL, but it does not say what TRIAL really is. So I find it impossible to evaluate TRIAL's utility, and the paper makes no contribution.

Critical strengths

I don't find this part of the review form helpful.

Critical weaknesses

see review above.

Questions for authors

see review above.

1 comment

Thank you for the review.

We would like to note that we describe the construction of the tasks and the terminology in Section 3, and we provide further description in Appendix B.

Regarding Figure 1, we tried to symbolize a long horizon self play aspect through the loop at the middle step.

Regarding the contributions and utility of the paper. Given the amount of effort and attention going into evaluation and training environments, particularly the amount of scrutiny with regard to AI-generated, reward-hackable environments, we present two contributions.

First, we show how we can leverage an epsilon move-based DFA -> NFA expansion to efficiently generate evaluation environments that are verifiable in nature but do not lack syntactic and semantic complexity.

Second, we show that environments built on this insight can pose challenging to frontier models even when full tool use and code generation is enabled. We find that models have a very hard time correctly estimating how much of an environment they have explored, even on repetitive tasks.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.