Auto-Discovery-Bench: Diagnosing Structured State Tracking in Oracle-Guided Discovery

Technical Summary: Auto-Discovery-Bench

Problem Statement
Large Language Models (LLMs) are increasingly applied to scientific workflows, yet many scientific tasks require iterative, feedback-driven experimentation where agents must propose hypotheses, select experiments, and update beliefs based on observations. Existing benchmarks often evaluate isolated skills (e.g., coding, literature synthesis) or operate in open-ended environments where failures are difficult to attribute due to confounding factors such as stochastic feedback, domain knowledge gaps, and exploration strategies. There is a lack of controlled diagnostics that preserve the closed-loop structure of discovery while isolating the prerequisite capability of maintaining and updating structured beliefs over long interaction horizons.

Methodology
The authors introduce Auto-Discovery-Bench, a deterministic, oracle-guided diagnostic benchmark designed to evaluate structured state tracking in closed-loop discovery. The benchmark operates on the principle of diagnostic control over ecological realism, utilizing deterministic oracles, known ground truths, and exact evaluation metrics to isolate specific capabilities.

The benchmark consists of three controlled discovery abstractions:

1. Directed Graph Discovery: Agents infer a hidden Directed Acyclic Graph (DAG) representing dependency relations between nodes (molecules). The agent performs interventions on nodes, and the oracle returns post-intervention state observations. Evaluation is based on the similarity between the inferred reachability matrix and the ground truth.
2. Undirected Relational Discovery: Agents infer hidden undirected relationships (edges) between entities (e.g., Game of Thrones houses). Interventions (attacks) perturb a node’s state and propagate to neighbors. The goal is to recover the symmetric adjacency matrix.
3. Symbolic Equation Discovery: Agents recover a hidden symbolic equation governing a physical system (e.g., force as a function of mass, acceleration, etc.). The agent proposes hypotheses and measurement actions, receiving feedback on prediction accuracy and measured outputs. Formulas are generated from a controlled grammar with varying complexity and distractor variables.

In all tasks, the agent operates within an interaction budget, alternating between hypothesis generation and action selection. The benchmark also includes a trajectory-tracking diagnostic, where models must identify state changes across consecutive steps in a given observation matrix, isolating state tracking from exploration and hypothesis generation.

Key Contributions

• Benchmark Introduction: Auto-Discovery-Bench is introduced as a controlled testbed for evaluating structured belief maintenance under repeated feedback, preserving the hypothesis–intervention–update loop.
• Task Instantiation: The protocol is instantiated in three archetypes (directed graph, undirected relational, and symbolic equation discovery) with exact ground truth and deterministic evaluation.
• Diagnostic Insight: The paper provides evidence that long-horizon structured state tracking is a significant bottleneck for oracle-guided discovery, distinct from planning or representation issues.

Results
Experiments were conducted on several state-of-the-art models, including GPT-4o, Gemini 2.5 Pro, Grok-4, Qwen2.5-72B, Claude-3.5-Haiku, and Llama-3.1-70B.

• Scaling Limitations: Performance across all models degrades as the number of variables, trajectory length, and distractors increase. In graph-based tasks, many models fail completely when scaling from small graphs (3 nodes) to larger ones (10 nodes).
• Model Performance:
  • Grok-4 and Gemini 2.5 Pro demonstrated the most consistent high success rates across all tasks. In symbolic equation discovery, they achieved 100% success in simpler settings and maintained high performance (90% and 60%, respectively) in the most complex setting with distractors.
  • GPT-4o and Qwen2.5 performed well in small-graph regimes but saw sharp drops in success rates as complexity increased (e.g., GPT-4o dropped to 15% success in 10-node directed graphs).
  • Claude-3.5-Haiku and Llama-3.1 generally lagged behind, with frequent failures in larger or more complex settings.
• Trajectory Tracking: The separate diagnostic showed that accuracy in tracking state changes decreases significantly with horizon length. Even with Chain-of-Thought (CoT) prompting, performance on long trajectories (e.g., length 20–30) remained weak, indicating a fundamental limitation in maintaining long-range structured information.
• Reasoning Styles: Analysis of reasoning traces revealed that top-performing models (e.g., Gemini 2.5 Pro) used more uncertainty and evidence-based keywords and were more verbose, whereas weaker models were more concise and used fewer uncertainty markers.

Significance and Claims
The paper claims that Auto-Discovery-Bench provides a reproducible, low-confound diagnostic testbed for isolating the capability of maintaining and integrating long-range structured information. The authors emphasize that the benchmark is not intended to replace realistic discovery environments or simulate real scientific practice in full fidelity. Instead, it serves as a lower-bound diagnostic: if models cannot maintain structured state in clean, noise-free settings, they are likely to fail more severely in realistic environments with noise and partial observability. The results highlight that clean feedback alone is insufficient for reliable discovery and that long-horizon state tracking remains a critical bottleneck for current LLM agents.