AutoSR: Automatic Symbolic Regression by Searching Research States

Overview§

AutoSR introduces a framework that elevates symbolic regression from searching isolated equations to searching research states. A research state couples a candidate equation with the reasoning, computational evidence, and independent review accumulated along its investigative branch. Two types of agents—proposers and reviewers—collaborate to refine these states, guided by progressive-widening Monte Carlo tree search (PW-MCTS). This preserves the scientific record and enables the final output to include not just the best relation but also the evidence and justification for its selection.

Core Methodology§

Research States§

A research state $s$ is defined as a tuple $$s = (\mathcal{E}, \mathcal{D}, \mathcal{H}, \mathcal{R})$$ where $\mathcal{E}$ is the candidate symbolic expression, $\mathcal{D}$ is the set of data probes and computational evidence, $\mathcal{H}$ is the historical reasoning chain (motivations, hypotheses, failed attempts), and $\mathcal{R}$ is a set of independent reviews. This representation allows the search to retain context that traditional equation-level searches discard.

Proposer–Reviewer Agents§

A proposer agent analyzes the current state and generates new investigative actions, such as proposing a new functional form, a different data transformation, or a targeted validation experiment. A reviewer agent independently critiques the proposal, checking for algebraic equivalence, overfitting, extrapolation behavior, and numerical stability. The interaction forms a trajectory of states that captures not only what worked but also why it worked.

Progressive-Widening MCTS§

PW-MCTS allocates computation across competing research branches. Unlike standard MCTS, progressive widening limits the number of children per node initially and expands it as the visit count grows. The selection policy is UCT-style: $$a^* = \arg\max_a Q(s,a) + c \sqrt{\frac{\ln N(s)}{N(s,a)}}$$ where $Q(s,a)$ estimates the scientific merit of taking action $a$ from state $s$, $N(s)$ is the number of visits to $s$, and $N(s,a)$ is the visit count for action $a$. After expansion, the proposer generates a child state and the reviewer evaluates it; the resulting reward (e.g., a composite score based on model fit, complexity, and review agreement) is backpropagated.

Synthesis and Justification§

The accumulated research record in each state is finally synthesized into a natural-language report that explains the leading relation, the evidence supporting it, and the alternative branches that were abandoned. This makes the system's output scientifically accountable, not just mathematically optimal.

Code Sketch§

The following Python block outlines the core loop of AutoSR with simplified agent logic:

class ResearchState:
    def __init__(self, expr, evidence, history, reviews):
        self.expr = expr
        self.evidence = evidence
        self.history = history
        self.reviews = reviews

def pw_mcts(initial_state, proposer, reviewer, budget):
    root = Node(initial_state)
    for _ in range(budget):
        node = tree_policy(root)
        result = evaluate(node.state, proposer, reviewer)
        backpropagate(node, result)
    return best_state(root)

def tree_policy(node):
    while not node.is_leaf():
        if len(node.children) < node.expansion_limit:
            new_child = expand(node, proposer)  # propose a next step
            return new_child
        node = best_child(node, c=0.1)
    return node

def evaluate(state, proposer, reviewer):
    # Proposer generates candidate actions, reviewer computes a score
    score = reviewer.review(state)
    return score

Key Results§

AutoSR recovers algebraically equivalent relations in all nine selected challenges from the cp3-bench and LSR-Transform suites. It is the first published system to recover all three cp3-bench problems and succeeds across six structurally diverse LSR-Transform instances. The framework shows that preserving the scientific record improves both search efficiency and the credibility of the final equation, opening a path toward automated scientific investigation rather than merely curve fitting.