MOOSE-Star: Unlocking Tractable Training for Scientific Discovery by Breaking the Complexity Barrier

• URL: http://arxiv.org/abs/2603.03756v1
• Date: Wed, 04 Mar 2026 06:11:18 GMT
• Title: MOOSE-Star: Unlocking Tractable Training for Scientific Discovery by Breaking the Complexity Barrier
• Authors: Zonglin Yang, Lidong Bing,
• Abstract summary: MOOSE-Star is a unified framework enabling tractable training and scalable inference.<n>TOMATO-Star is a dataset of 108717 decomposed papers (38,400 GPU hours) for training.
• Score: 56.250921274032066
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: While large language models (LLMs) show promise in scientific discovery, existing research focuses on inference or feedback-driven training, leaving the direct modeling of the generative reasoning process, $P(\text{hypothesis}|\text{background})$ ($P(h|b)$), unexplored. We demonstrate that directly training $P(h|b)$ is mathematically intractable due to the combinatorial complexity ($O(N^k)$) inherent in retrieving and composing inspirations from a vast knowledge base. To break this barrier, we introduce MOOSE-Star, a unified framework enabling tractable training and scalable inference. In the best case, MOOSE-Star reduces complexity from exponential to logarithmic ($O(\log N)$) by (1) training on decomposed subtasks derived from the probabilistic equation of discovery, (2) employing motivation-guided hierarchical search to enable logarithmic retrieval and prune irrelevant subspaces, and (3) utilizing bounded composition for robustness against retrieval noise. To facilitate this, we release TOMATO-Star, a dataset of 108,717 decomposed papers (38,400 GPU hours) for training. Furthermore, we show that while brute-force sampling hits a ''complexity wall,'' MOOSE-Star exhibits continuous test-time scaling.

Related papers

• Unifying Tree Search Algorithm and Reward Design for LLM Reasoning: A Survey [92.71325249013535]
  Deliberative tree search is a cornerstone of Large Language Model (LLM) research.<n>This paper introduces a unified framework that deconstructs search algorithms into three core components.
  arXiv  Detail & Related papers  (2025-10-11T03:29:18Z)
• Enabling Pareto-Stationarity Exploration in Multi-Objective Reinforcement Learning: A Multi-Objective Weighted-Chebyshev Actor-Critic Approach [23.834874532235382]
  We propose a weighted-ulineMulineActor-critic (MOCHA) algorithm for multi-objective reinforcement learning (MORL)<n>By carefully choosing learning rates, the sample complexity for each exploration can be given $tildemathcalO(epsilon-2)$.<n>The performance of MOCHA algorithm significantly outperforms other baseline MORL approaches.
  arXiv  Detail & Related papers  (2025-07-29T00:11:59Z)
• FLARE: Faithful Logic-Aided Reasoning and Exploration [47.46564769245296]
  We introduce a novel approach for traversing the problem space using task decompositions.<n>We use the Large Language Models to plan a solution, soft-formalise the query into facts and predicates using a logic programming code.<n>Our method allows us to compute the faithfulness of the reasoning process w.r.t. the generated code and analyse the steps of the multi-hop search without relying on external solvers.
  arXiv  Detail & Related papers  (2024-10-14T19:39:11Z)
• Reinforcement Learning from Human Feedback without Reward Inference: Model-Free Algorithm and Instance-Dependent Analysis [16.288866201806382]
  We develop a model-free RLHF best policy identification algorithm, called $mathsfBSAD$, without explicit reward model inference.<n>The algorithm identifies the optimal policy directly from human preference information in a backward manner.
  arXiv  Detail & Related papers  (2024-06-11T17:01:41Z)
• Provably Efficient Adversarial Imitation Learning with Unknown Transitions [24.70187647541753]
  Imitation learning (IL) has proven to be an effective method for learning good policies from expert demonstrations. This paper explores the theoretical underpinnings of AIL in the presence of unknown transitions. We propose an algorithm, MB-TAIL, that achieves the minimax optimal expert sample complexity of $widetildeO (H3/2 |S|/varepsilon)$ and interaction complexity of $widetildeO (H3 |S|2 |A|/varepsilon2)$.
  arXiv  Detail & Related papers  (2023-06-11T02:46:41Z)
• Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
  We propose a new reward-free algorithm for learning linear Markov decision processes (MDPs) At the core of our algorithm is uncertainty-weighted value-targeted regression with exploration-driven pseudo-reward. We show that our algorithm only needs to explore $tilde O( d2varepsilon-2)$ episodes to find an $varepsilon$-optimal policy.
  arXiv  Detail & Related papers  (2023-03-17T17:53:28Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning [123.69175280309226]
  One of the challenges in online reinforcement learning (RL) is that the agent needs to trade off the exploration of the environment and the exploitation of the samples to optimize its behavior. We propose to tackle the exploration-exploitation problem following a decoupled approach composed of: 1) An "objective-specific" algorithm that prescribes how many samples to collect at which states, as if it has access to a generative model (i.e., sparse simulator of the environment); 2) An "objective-agnostic" sample collection responsible for generating the prescribed samples as fast as possible.
  arXiv  Detail & Related papers  (2020-07-13T15:17:35Z)
• Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
  This work shows that these hardness barriers do not preclude efficient reinforcement learning for rich and interesting subclasses of Partially Observable Decision Processes (POMDPs) We present a sample-efficient algorithm, OOM-UCB, for episodic finite undercomplete POMDPs, where the number of observations is larger than the number of latent states and where exploration is essential for learning, thus distinguishing our results from prior works.
  arXiv  Detail & Related papers  (2020-06-22T17:58:54Z)
• Task-agnostic Exploration in Reinforcement Learning [35.403304641170386]
  We present an efficient task-agnostic reinforcement learning algorithm, textscUCBZero. It finds $epsilon$-optimal policies for $N$ arbitrary tasks after at most $tilde O(log(N)H5SA/epsilon2)$ exploration episodes. We also provide an $Omega(log (N)H2SA/epsilon2)$ lower bound, showing that the $log$ dependency on $N$ is unavoidable.
  arXiv  Detail & Related papers  (2020-06-16T20:23:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.