PaperlayerView exact revision on arXiv

Source-linked AI summary

Open-ended Scientific Discovery with Possibilistic Reasoning

Anita Yang, Siu Lun Chau, Tomoya Wakayama, Krikamol Muandet, Masaki Adachi

arXiv:2610.11289v1cs.AI

TL;DR

Open-ended scientific discovery must test hypotheses adaptively while accounting for undiscovered explanations and potentially revisable background knowledge. The paper formalizes AASD with possibility theory and introduces abductive utility and possibility frontier search. The algorithm maintains anytime validity and achieves asymptotic ε-optimal utility under suitable conditions, with strong performance reported on synthetic and real-world tasks.

  • Problem

    Existing anytime-valid methods handle adaptive hypotheses, but open-ended discovery must also account for better explanations not yet proposed and background knowledge that may need revision.

    Source: §1 · p. 1

  • Method

    The paper formalizes AASD using possibility theory, defines abductive utility as a discovery-progress measure, and develops possibility frontier search.

    Source: §1 · p. 2

  • Results

    Possibility frontier search maintains anytime validity and achieves ε-optimal abductive utility asymptotically under suitable conditions; experiments show strong performance on synthetic and real-world tasks.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Abductive utility provides a computable measure of discovery progress without human intervention.

    Source: §1 · p. 2

    Open-endedness concerns expanding candidate hypotheses within a fixed environmental model, action space, and background contour; misspecifying the background possibility model may bias hypothesis preferences.

    Source: §7 · p. 8

Abstract

from arXiv · show

Autonomous scientific discovery with LLMs requires generating and testing hypotheses adaptively as evidence accumulates while maintaining statistical validity. Existing anytime-valid methods can handle data-dependent hypotheses, but open-ended discovery poses a deeper challenge: the best discovered hypothesis may still be the best of a bad lot, with better explanations yet undiscovered, while even background knowledge such as physical laws may require revision in light of new findings. In response, we formalize the problem as Abductive Autonomous Scientific Discovery (AASD) using possibility theory. We introduce abductive utility, a computable measure of discovery progress, and possibility frontier search, the first algorithm for AASD, which maintains anytime validity and achieves $\varepsilon$-optimal abductive utility asymptotically under suitable conditions. Experiments on synthetic and real-world scientific-discovery tasks show strong performance.

1 INTRODUCTION

The introduction frames scientific discovery as finding explanations for noisy experimental evidence while recognizing that current candidates and background knowledge may both be incomplete. It proposes possibility-based AASD, abductive utility, and possibility frontier search to guide open-ended discovery with anytime-valid guarantees.

1 INTRODUCTION

  • Physical-science discovery tests competing explanations against noisy, finite, costly experiments, unlike computationally verified mathematical discovery.Multiple explanations may remain plausible, so discovery need not yield a unique answer.Source: §1 · p. 1
  • Hypotheses are selected first for empirical adequacy, then for compatibility with background knowledge, and finally for simplicity among ties.Simplicity is operationalized by the number of states a hypothesis permits.Source: §1 · p. 2
  • Prior approaches address only parts of the problem: adaptive falsification does not rank plausible explanations and assumes a fixed hypothesis set, while surprise requires known explanations to be excluded first.Human-in-the-loop abductive judgment is also described as not scaling.Source: §1 · p. 2
  • AASD formalizes open-ended scientific discovery with possibility theory, treating excluded candidates as evidence of an incomplete hypothesis space and possible conflict with background knowledge as grounds for revision.The introduction also asks for a computable measure to guide search as hypotheses and evidence accumulate.Source: §1 · p. 2
  • Possibility frontier search maintains anytime validity and achieves ε-optimal abductive utility asymptotically under suitable conditions; experiments show strong performance on synthetic and real-world discovery tasks.The paper also derives an observable stopping certificate for ε-optimality.Source: §1 · p. 2

2 SETUP AND BACKGROUND

The setup models experiments as noisy observations of an unknown environment and defines the target as a true, background-compatible hypothesis. The background introduces possibility representations and anytime-valid inference for sequential evidence.

2.1 Problem Setting: AASD

  • The AASD setting treats the true environment as unknown, collects noisy measurements through chosen experiments, and seeks a hypothesis containing the true state with high background compatibility.The theoretical analysis assumes a well-specified model and a sufficiently expressive action set for distinguishing distinct parameter values.Source: §2.1 · pp. 2–3

2.2 Background

  • Possibility functions represent how strongly states remain excluded, while e-processes support sequential testing with guarantees robust to optional stopping and adaptive data collection.The e-process rejection guarantee transfers to the defined e-possibility function.Source: §2.2 · p. 3

3 POSSIBILISTIC REASONING

Possibilistic reasoning separates evidence-based certification from background-compatibility scoring. A lexicographic rule then selects among certified hypotheses, using simplicity to break compatibility ties.

3 POSSIBILISTIC REASONING

  • Abductive utility combines evidential possibility, which determines certified claims, with background possibility, which scores them.The two components keep evidence-based validity distinct from background-based ranking.Source: §3 · p. 3

3.1 Evidential Possibility

  • Evidence classifies claims as contradicted, open, or certified; on the anytime-valid event, true candidates are never pruned and certified candidates remain certified.The version space shrinks over time, and the figure presents this as the first stage of a two-stage assessment.Source: §3.1 · pp. 3–4, Figure 2 · p. 4

3.2 Background Possibility

  • Background-compatibility utility measures the minimum compatibility across states allowed by a hypothesis, and maximizing it minimizes the cost of uniformly accommodating those states.The utility is candidate-wise and remains fixed over time.Source: §3.2 · p. 4

3.3 Lexicographic preferences and simplicity

  • Selection is lexicographic: empirical validity first, background compatibility second, and simplicity among tied hypotheses, measured by represented-state cardinality.When certified hypotheses tie in utility, cardinality favors more specific claims.Source: §3.3 · p. 4

4 OPEN-ENDED DISCOVERY

Possibility Frontier Search alternates between expanding hypotheses and selecting experiments to resolve promising open candidates. It combines statistical certification with a preference for compatibility with background knowledge and simplicity.

4 OPEN-ENDED DISCOVERY

  • Possibility Frontier Search alternates hypothesis expansion with experiment selection to resolve promising open hypotheses.The algorithm returns a certified ε-optimal claim when its observable stopping condition is met.Source: §4 · p. 4

4.1 Hypothesis Expansion

  • Expansion retains nontrivial proposals that exclude the current version space and stops early when a proposal contains that space.Each round draws at most B hypotheses; the algorithm uses rejection sampling for concreteness.Source: §4.1 · pp. 4–5

4.2 Possibility Frontier Search

  • Frontier design targets open candidates that could improve the current best, selecting experiments to distinguish active hypothesis pairs.For finite pair and action sets, the design can be implemented as a linear program.Source: §4.2 · p. 5, Figure 3 · p. 5
  • On Eδ, the utility bound brackets U⋆ when a certified claim exists; stopping limits false or ε-suboptimal returns to δ, but finite termination is not guaranteed.The procedure also avoids stopping while a known open candidate could improve the lexicographic preference.Source: §4.2 · p. 5

4.3 Theoretical Analysis

  • Under stated finite-state, likelihood, noise, and generator-coverage conditions, a certified near-optimal hypothesis is eventually retained almost surely on Eδ.The recovery analysis concerns the nonterminated continuation with termination and the external observation cap disabled.Source: §4.3 · pp. 5–6

4.4 Related Work

  • Unlike prior evaluation within predefined models, this work integrates e-possibility with growing hypotheses, fixed background preference, and frontier-based experimental design.Its active-testing design uses maximin optimality on a data-dependent possibility frontier rather than asymptotic fixed-family optimality.Source: §4.4 · p. 6

5 SYNTHETIC EXPERIMENT

The synthetic study tests discovery when the initial hypothesis set omits the truth and the informative background model is misspecified. It evaluates recovery, abductive utility, and adaptive experimental design.

5.1 Environmental Setup

  • The setup uses a known ground truth, but no initial hypothesis contains it, so recovery requires hypothesis expansion.The hypothesis space has 1,540 parameter states and 44 reachable hypotheses, three of which contain the truth.Source: §5.1 · p. 6, §5 · p. 6, Figure 4 · p. 6

Background possibility.

  • Background knowledge comes from historical observations and is informative but misspecified relative to the current environment.A Gaussian possibility derived from the background model supplies the hypothesis utility.Source: Background possibility · pp. 6–7

5.2 Experiments

  • Only AutoDiscovery and our method reach a true hypothesis under incomplete H0; ours converges to U⋆, while the other methods cannot.The figure reports that ours returns a certified hypothesis at t = 2 or 3 with empirical precision 1.0, followed by improving abductive utility.Source: Figure 5 · p. 7, §5.2 · p. 7
  • The method selects experiments by possibility-frontier maximin design, while MLE, MAP, and AutoDiscovery use uniform random sampling.The baselines lack a prescribed adaptive experimental-design policy over the action set.Source: Background possibility · p. 7, §5.2 · p. 7
  • Frontier allocation reaches U⋆ sooner than random actions, while larger ε triggers earlier stopping as the utility gap grows.The ablation compares the frontier policy with random actions and examines the stopping threshold and gap.Source: §5.2 · p. 7, Figure 6 · p. 7

6 REAL-WORLD DATASET

The paper evaluates natural-language hypothesis discovery in exploratory real-world case studies, using sequential measurements and LLM-based hypothesis generation. Its method eventually improves hypothesis matching and abductive utility on both datasets, while utility tracks matching without requiring a gold hypothesis.

6 REAL-WORLD DATASET

  • These real-world experiments are exploratory case studies using approximate statistical tests and LLM-based generation; exact anytime validity and recovery guarantees are not established.Full experimental details are provided in Appendix H.2.Source: §6 · p. 7

6.1 Environmental Setup

  • The exploratory real-world case studies use the Incarceration/SES datasets; each starts with five natural-language hypotheses and their logical complements, plus a held-out gold hypothesis for evaluation.The research question is supplied to the learner, while the environmental state is unknown.Source: §6.1 · p. 8
  • The experimental environment represents accessible quantities as population parameters and queries as noisy measurements; the joint background possibility contour takes the minimum across estimands.Because abductive utility minimizes over allowed states, unspecified estimands can lower the score.Source: §6.1 · p. 8
  • Each dataset is split into 16 folds, with up to two queries tested per round on unseen data, for at most 32 sequential test executions.Tests are fixed before the next fold is observed; shared-fold statewise contributions are averaged and multiplied across folds to form an e-process.Source: §6.1 · p. 8

6.2 Experiments

  • Figure 8 shows our method eventually achieves higher HMS and abductive utility, and lower | ˆHt| on both datasets.Abductive utility and | ˆHt| closely track HMS, suggesting utility can monitor discovery progress without a gold hypothesis.Source: Figure 8 · p. 8, §6.2 · p. 8
  • Experiments use GPT-5 for hypothesis generation and LLM-based evaluation, comparing against AutoDiscovery with HMS, abductive utility, and hypothesis-set cardinality as metrics.MLE and MAP are omitted because they use a prespecified statistical model class and do not directly provide open-ended natural-language hypothesis evaluation in this setting.Source: §6.2 · p. 8

7 CONCLUSION AND LIMITATION

The conclusion presents AASD, abductive utility, and possibility frontier search as the paper’s problem formulation, discovery metric, and algorithm. Its open-endedness is limited to expanding candidate hypotheses under fixed environmental and background representations.

7 CONCLUSION AND LIMITATION

  • The paper introduces AASD, abductive utility as a discovery metric, and possibility frontier search as its solving algorithm.The conclusion also notes that background possibility quality and calibration affect which admissible hypotheses are preferred.Source: §7 · p. 8
  • Open-endedness means expanding candidate hypotheses within a fixed environmental model, action space, and background contour, not online expansion of Θ or revision of K.The conclusion distinguishes candidate-set expansion from revising the environment or background knowledge representation.Source: §7 · p. 8
  • A misspecified background possibility model may bias which admissible hypotheses are preferred.The preference also depends on the model’s quality and calibration.Source: §7 · p. 8

Supplements

The supplement represents hypotheses through the states where their experimentally testable implications hold. Certification applies to this representation, rather than to additional natural-language claims.

A.1 Hypotheses as subsets of the state space

  • A claim is identified with the states under which its experimentally testable implications hold.This represents the claim as a subset of the state space.Source: §A.1 · p. 13
  • Semantically identical claims share a membership predicate and are deduplicated; natural-language claims must be compiled into that predicate before certification.Source: §A.1 · p. 13
  • A certificate covers the compiled predicate, not extra causal or mechanistic wording absent from its statistical representation.The passage points to Appendix G for further discussion.Source: §A.1 · p. 13

A.2 Adaptive-hypothesis validity

The supplement gives adaptive-validity guarantees, formalizes a preference for more specific certified claims, and analyzes rejection-conditioned hypothesis generation. Asymptotic coverage depends on an explicit assumption about the implemented expansion step.

A.2 Adaptive-hypothesis validity

  • With probability at least 1 − β, every member of every Ct(α, β) is true, with no union bound over claims.The corollary applies to data-dependent candidate archives and local thresholds 0 < α ≤ β < 1.Source: §A.2 · p. 13
  • On Eδ, a true retained claim cannot be pruned, certified claims remain certified, and abductive utility is nondecreasing while the procedure continues.These properties are stated for continuation with the stopping condition disabled.Source: §A.2 · p. 13

B GUARANTEED BACKGROUND POSSIBILITY AND REFINEMENT

  • Among available certified claims, the reporting rule cannot choose a claim when a certified strict refinement is available; this archive-relative preference does not guarantee useful refinements were generated.The preference does not require candidates to form an antichain or to be disjoint.Source: B GUARANTEED BACKGROUND POSSIBILITY… · p. 14

C CONDITIONAL HYPOTHESIS GENERATION

  • With conditionally i.i.d. proposals and positive probability of a certified proposal, rejection-conditioned expansion terminates almost surely and returns a certified draw.The accepted draw follows the proposal kernel conditioned on acceptance.Source: C CONDITIONAL HYPOTHESIS GENERATION · p. 14
  • The operational expansion caps attempts at B, retains uncertified proper proposals as open claims, and counts invalid proposals and duplicates against that budget.On Eδ, no true candidate is discarded as contradicted.Source: C CONDITIONAL HYPOTHESIS GENERATION · p. 14, §C.1 · p. 15

C.1 Formal generator coverage

  • The coverage assumption requires a positive per-expansion chance of finding a certified near-optimal claim and need not hold for an unrestricted free-form generator.It is an explicit assumption on the implemented expansion step.Source: §C.1 · p. 15

C.2 Implementation

Possibility Frontier Search allocates experiments to separate currently selected hypothesis pairs and remains open to alternatives not yet proposed. Its maximin guarantee is specific to the current frontier; full recovery also depends on hypothesis generation and information gathered across rounds.

C.2 Implementation

  • Algorithm 2 uses rejection sampling and returns the retained archive after at most B attempts, whether or not a new certified claim is found.A language-model proposal mechanism can be used within the registered semantic interface; this implementation alone does not establish Assumption 2.Source: §C.2 · p. 15

D POSSIBILITY FRONTIER SEARCH AS A FRACTIONAL DESIGN

  • The fractional design can be implemented by randomized sampling; deterministic allocation tracking gives approximately the same cumulative allocation.Random sampling gives the cleanest one-step expectation identity.Source: D POSSIBILITY FRONTIER SEARCH AS A… · p. 15

D.1 Separation delivered by the selected pair set

  • When the frontier is empty, all-pairs selection has positive separation under the stated finite-space and falsifiability assumptions; frontier-only selection may leave excluded pairs uninformed.Without exploration, periodic all-pairs steps, or a non-starvation condition, falsifiability alone does not ensure information for excluded pairs.Source: §D.1 · pp. 15–16
  • The current pair-set design is maximin optimal among randomized one-step experiment designs for the selected frontier pairs.The finite-round guarantee concerns the current frontier criterion, not a fixed hypothesis family.Source: §D.1 · p. 16, §D.2 · p. 16

D.2 Scope of the maximin optimality statement

  • The selected allocation maximizes worst-pair expected discrepancy over the current frontier, but does not alone guarantee complete-procedure recovery.Recovery also depends on hypothesis generation and information acquired across rounds.Source: §D.2 · p. 16

D.3 Implementation.

The analysis establishes statewise validity under adaptive experiments and gives recovery and stopping guarantees under stated assumptions. The guarantees depend on information acquisition and reachability conditions, while the observable stopping certificate has separate scope limits.

E.1 Full-support likelihood-ratio mixture

  • Under the tested state, the likelihood-ratio mixture is a nonnegative supermartingale and therefore provides valid statewise evidence under adaptive experiments.It is a martingale if every alternative law is absolutely continuous with respect to the tested law for every action.Source: §E.1 · p. 17

E.2 Sub-Gaussian likelihood-ratio rate model

  • The exponential-rate analysis assumes finite directed KL divergences and a uniform conditional sub-Gaussian proxy for log-likelihood-ratio increments.A directed KL divergence or a nonnegative lower bound can serve as the discrepancy measure.Source: §E.2 · p. 18

E.3 Readiness under the actual frontier policy

  • The readiness guarantee requires positive information for each relevant frontier pair; falsifiability alone does not ensure this under a frontier-only policy.A sufficient condition is the stated linear lower bound at every required time; positive asymptotic pair frequency alone does not establish it.Source: §E.3 · p. 18

F.1 Reachable class and target

  • The recovery analysis defines reachability through positive probability of eventually proposing a target claim, with measurable comparison classes required for general representations.The finite-state analysis uses this reachability definition; positive point mass is not appropriate for an atomless generator.Source: §F.1 · p. 19

F.2 Proof of Theorem 1

  • Once a target is certifiable, the proof bounds repeated failure to propose it and retains certified targets as the version space shrinks.The iteration gives a failure bound of (1 − q)^(t−s+1).Source: §F.2 · p. 19

F.3 Asymptotic consequence

  • On the coverage event, a target is eventually obtained and retained almost surely, pointwise in ε.The conclusion does not imply continued refinement after the actual procedure stops.Source: §F.3 · p. 20

F.4 Observable stopping guarantee

  • The guarded stopping rule certifies primary optimality on the simultaneous coverage event, without requiring generator-coverage or non-starvation constants.The guarantee assumes a fixed background contour, a finite current archive, and measurable evaluations and tie-breaking.Source: §F.4 · p. 20
  • The stopping bound is joint in termination and failure, not a conditional error bound given termination, and it certifies primary utility rather than minimum cardinality or experimental cost.Termination need not occur when a restricted language leaves a positive utility gap or an ungenerated refinement remains possible.Source: §F.4 · p. 20

F.5 Stopping and sample complexity with known constants

With known recovery constants, the paper gives an explicit experimental sample-complexity bound. It also specifies how natural-language claims can be tested through a registered interface, while identifying limits on calibration, optimality, and computational accounting.

F.5 Stopping and sample complexity with known constants

  • The explicit horizon splits failure probability between evidence acquisition and target generation, with each contribution bounded by ζ/2.The bound uses the recovery theorem and is distinct from an observable stopping certificate; the horizon need not be computable for a free-form generator.Source: §F.5 · p. 21

G.1 Natural-language hypotheses and reusable tests

  • A compiled claim is a subset of qualitative sign configurations, and its statewise evidence yields simultaneous version-space coverage under the stated conditional null validity.Fresh folds address reuse and adaptive specification but do not prove conditional calibration; opposite-sign distribution classes may contain arbitrarily small effects.Source: §G.1 · p. 22

G.2 Nonunique explanations

  • Recovery concerns the utility of the single returned claim, not global recovery of the smallest utility maximizer.Semantic paraphrases share one representation and cardinality.Source: §G.2 · p. 22

G.3 Computational cost

  • The frontier LP and archive-classification costs are stated assuming claim scores and memberships are available; constructing the background contour and computing global extrema can add costs.Archive classification costs O(SM) membership queries, and the LP has L + 1 variables with one inequality per distinct constrained pair.Source: §G.3 · p. 22

H ADDITIONAL EXPERIMENTAL DETAILS AND RESULTS

H.1 Synthetic experiment

The appendix examines possibility-frontier discovery in synthetic settings, describes a real-world experimental interface, and evaluates validity under adaptive hypothesis selection. In post-hoc selection over 42 fixed candidates, certification criteria controlled both error types below the nominal level while retaining competitive power, and necessity distinguished compatibility from sufficient evidential support.

H.1 Synthetic experiment

  • The incomplete-initialization synthetic test uses 16 starting candidate sets, all excluding the three true reachable hypotheses.The setup defines |H⋆| = 3.Source: §H.1 · p. 23

Hypothesis Expansion.

  • For both incomplete and complete initialization, the method abstains when no hypothesis is certified, has zero empirical false certifications across evaluated runs, and certification rate increases as evidence accumulates.Figure 9 shows the false-certification rate below the target δ = 0.1.Source: Hypothesis Expansion · p. 25, Figure 9 · p. 25

H.2 Real-World Dataset Experiment

  • Real-world runs use 16 disjoint folds and at most 32 prespecified test executions, with validated falsification actions proposed for generated hypotheses and their complements.Actions are fixed before the corresponding unseen fold is observed.Source: §H.2 · p. 26
  • An LLM proposes falsifiable hypotheses and complements; accepted hypotheses reuse applicable accumulated evidence, while falsified hypotheses are discarded and certified ones are ranked by abductive utility.The selected certified hypotheses maximize utility, with ties favoring smaller cardinality.Source: §H.2 · p. 28

H.3 Validity under Adaptive Hypothesis Selection

  • The validity experiment examines anytime validity and power under post-hoc hypothesis selection, and whether necessity distinguishes compatibility from sufficient evidential support.It evaluates the evidential criteria defining the certified set.Source: §H.3 · p. 28
  • The experiment used sequential N(θ⋆, 1) observations through T=100 and evaluated all 42 candidates on the same accumulated data at each round.The certification threshold was δ=0.05, and the fixed candidate family enabled comparison with Bonferroni correction.Source: §H.3 · p. 28
  • Both certification error types stayed below δ=0.05; power matched naive reuse and exceeded Bonferroni for moderate effect sizes.Bonferroni was substantially more conservative, while naive reuse slightly exceeded the nominal error level for some states.Source: Figure 10 · p. 29, §H.3 · p. 29
  • Naive reuse selected the candidate with the largest e-value and used 1/δ, while Bonferroni used the family-wise threshold 42/δ.The individual e-processes were anytime-valid, so the baselines required no additional temporal correction.Source: §H.3 · p. 29
  • Compatibility can persist near the true boundary, whereas necessity requires sufficient evidence against the complement; smaller δ shifts necessity toward more negative boundary distances.With τ=1.0 in the primary experiment, the τ=0.5 and τ=2.0 ablation maintained error control at δ=0.05 with power comparable to naive reuse.Source: §H.3 · p. 30, Figure 11 · p. 30

Related papers

Loading 2610.11289v1…