Hypothesis Frontier: Verifier Guided LLM and Symbolic Search for First-Order Induction

• URL: http://arxiv.org/abs/2608.10843v1
• Date: Tue, 11 Aug 2026 12:13:35 GMT
• Title: Hypothesis Frontier: Verifier Guided LLM and Symbolic Search for First-Order Induction
• Abstract summary: First-order concept synthesis asks a system to infer one formula that classifies labeled objects consistently across several finite relational structures.<n>We introduce Hypothesis Frontier, a verifier-guided neurosymbolic framework that evaluates each LLM formula on every training object.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: First-order concept synthesis asks a system to infer one formula that classifies labeled objects consistently across several finite relational structures. Every candidate can be evaluated exactly, but quantified first-order formulas form a vast search space, and LLM outputs are often semantically promising without being fully correct. We introduce Hypothesis Frontier, a verifier-guided neurosymbolic framework that evaluates each LLM formula on every training object, retains the strongest verified hypothesis across rounds, and uses its remaining errors to guide subsequent generation. Symbolic processing repairs invalid formulas while remaining anchored to the LLM-generated hypothesis, and simplifies train-valid formulas without changing any training prediction. Under matched models, problem sets, and LLM-round budgets, Hypothesis Frontier solves substantially more problems than repeated original-prompt generation. After the final formulas are selected, exact simplification shortens many train-valid formulas while preserving every training prediction. Exact symbolic reasoning therefore helps both to solve more induction problems and to compress many of the resulting formulas.

Related papers

• NxN E-valuation: Hypothesis Certification via a Conformal CRT Null [7.215201796507224]
  We propose NxN E-valuation, a handy, e-value-based hypothesis-certification algorithm.<n>It lets a hypothesis be verified without building any case-specific certification procedure.<n>NxN E-valuation is especially suited to LLM-based exploration systems.
  arXiv  Detail & Related papers  (2026-08-06T22:14:53Z)
• Learning to Reason with Curriculum II: Compositional Generalization [27.242998212645784]
  We show that an autocurriculum-based approach building on Part I of this series achieves better statistical complexity than direct methods.<n>For a setting inspired by supervised fine-tuning (SFT), curriculum facilitates learning from only $2mathcalO(sqrtlog T)$ tokens of supervision.<n>For a setting inspired by reinforcement learning with verifiable rewards (RLVR), we show that curriculum reduces the requirement on the reference model from coverage at the full sequence length $T$ to coverage at a shorter block length $B ll T$.
  arXiv  Detail & Related papers  (2026-06-26T05:09:08Z)
• From Residuals to Reasons: LLM-Guided Mechanism Inference from Tabular Data [10.795877029195845]
  A persistent challenge in machine learning for scientific applications is jointly achieving prediction and understanding.<n>We introduce Multi-Agent Residual In-Context Learning (MARICL)<n>MARICL improves consistently over its base model on all datasets.
  arXiv  Detail & Related papers  (2026-05-21T15:34:08Z)
• Reaching Beyond the Mode: RL for Distributional Reasoning in Language Models [78.68818219506313]
  This paper describes a multi-answer reinforcement learning approach for training LMs to perform distributional reasoning over multiple answers during inference.<n>Across question-answering, medical diagnostic, and coding benchmarks, we observe improved diversity, coverage, and set-level calibration scores compared to single answer trained baselines.
  arXiv  Detail & Related papers  (2026-03-25T22:20:25Z)
• Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Training [76.12556589212666]
  We show that curriculum post-training avoids the exponential complexity bottleneck.<n>Under outcome-only reward signals, reinforcement learning finetuning achieves high accuracy with sample complexity.<n>We establish guarantees for test-time scaling, where curriculum-aware querying reduces both reward oracle calls and sampling cost from exponential to order.
  arXiv  Detail & Related papers  (2025-11-10T18:29:54Z)
• RL for Reasoning by Adaptively Revealing Rationales [36.50924054394857]
  Supervised fine-tuning (SFT) relies on dense ground-truth labels, which become increasingly costly as sequence length grows.<n>We address this by adaptive backtracking (AdaBack), a per-sample curriculum learning algorithm that reveals only a partial prefix of the target output during training.<n>We show that our adaptive curriculum over partial answers reliably solves problems that are otherwise intractable.
  arXiv  Detail & Related papers  (2025-06-22T17:46:14Z)
• The First Few Tokens Are All You Need: An Efficient and Effective Unsupervised Prefix Fine-Tuning Method for Reasoning Models [69.798277882245]
  We introduce Unsupervised Prefix Fine-Tuning (UPFT) to enhance large language models' reasoning efficiency.<n>UPFT removes the need for labeled data or exhaustive sampling.<n> Experiments show that UPFT matches the performance of supervised methods.
  arXiv  Detail & Related papers  (2025-03-04T18:56:03Z)
• Lachesis: Predicting LLM Inference Accuracy using Structural Properties of Reasoning Paths [12.377041655669728]
  We introduce Lachesis, a predictive model for self-consistency based LLM inferences.<n>We empirically evaluate it using AutoFL, a recently proposed LLM-based fault localisation technique.<n>Results suggest that Lachesis can predict the correctness of answers with a precision of up to 0.8136.
  arXiv  Detail & Related papers  (2024-12-11T10:56:47Z)
• Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods [59.779795063072655]
  Chain-of-Thought (CoT) prompting and its variants have gained popularity as effective methods for solving multi-step reasoning problems. We analyze CoT prompting from a statistical estimation perspective, providing a comprehensive characterization of its sample complexity.
  arXiv  Detail & Related papers  (2024-08-25T04:07:18Z)
• A Hybrid System for Systematic Generalization in Simple Arithmetic Problems [70.91780996370326]
  We propose a hybrid system capable of solving arithmetic problems that require compositional and systematic reasoning over sequences of symbols. We show that the proposed system can accurately solve nested arithmetical expressions even when trained only on a subset including the simplest cases.
  arXiv  Detail & Related papers  (2023-06-29T18:35:41Z)
• Linear Temporal Logic Modulo Theories over Finite Traces (Extended Version) [72.38188258853155]
  This paper studies Linear Temporal Logic over Finite Traces (LTLf) proposition letters are replaced with first-order formulas interpreted over arbitrary theories. The resulting logic, called Satisfiability Modulo Theories (LTLfMT), is semi-decidable.
  arXiv  Detail & Related papers  (2022-04-28T17:57:33Z)

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.