Symmetry breaking for inductive logic programming

• URL: http://arxiv.org/abs/2508.06263v2
• Date: Mon, 11 Aug 2025 05:05:14 GMT
• Title: Symmetry breaking for inductive logic programming
• Authors: Andrew Cropper, David M. Cerna, Matti Järvisalo,
• Abstract summary: We introduce a method to break symmetries in the hypothesis space.<n>Our experiments on multiple domains, including visual reasoning and game playing, show that our approach can reduce solving times from over an hour to just 17 seconds.
• Score: 23.251472351777934
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The goal of inductive logic programming is to search for a hypothesis that generalises training data and background knowledge. The challenge is searching vast hypothesis spaces, which is exacerbated because many logically equivalent hypotheses exist. To address this challenge, we introduce a method to break symmetries in the hypothesis space. We implement our idea in answer set programming. Our experiments on multiple domains, including visual reasoning and game playing, show that our approach can reduce solving times from over an hour to just 17 seconds.

Related papers

• Symbolic Snapshot Ensembles [17.98221518812985]
  In this paper, we train an ILP algorithm only once and save intermediate hypotheses.<n>Our experiments on multiple benchmarks, including game playing and visual reasoning, show that our approach improves predictive accuracy by 4% with less than 1% computational overhead.
  arXiv  Detail & Related papers  (2025-10-28T17:01:38Z)
• Explore Briefly, Then Decide: Mitigating LLM Overthinking via Cumulative Entropy Regulation [82.62935304152239]
  Large Language Models (LLMs) have demonstrated remarkable reasoning abilities on complex problems using long Chain-of-Thought (CoT) reasoning.<n>They often suffer from overthinking, meaning generating unnecessarily lengthy reasoning steps for simpler problems.<n>We introduce a novel metric Token Entropy Cumulative Average (TECA), which measures the extent of exploration throughout the reasoning process.
  arXiv  Detail & Related papers  (2025-10-02T17:36:50Z)
• Thinking Before You Speak: A Proactive Test-time Scaling Approach [54.8205006555199]
  We implement our idea as a reasoning framework, named emphThinking Before You Speak (TBYS)<n>We design a pipeline for automatically collecting and filtering in-context examples for the generation of emphinsights.<n>Experiments on challenging mathematical datasets verify the effectiveness of TBYS.
  arXiv  Detail & Related papers  (2025-08-26T03:43:32Z)
• Honey, I shrunk the hypothesis space (through logical preprocessing) [19.54008511592332]
  We introduce an approach that'shrinks' the hypothesis space before an ILP system searches it.<n>Our approach uses background knowledge to find rules that cannot be in an optimal hypothesis regardless of the training examples.<n>Our experiments show that our approach can substantially reduce learning times whilst maintaining predictive accuracies.
  arXiv  Detail & Related papers  (2025-06-07T09:53:02Z)
• Controllable Logical Hypothesis Generation for Abductive Reasoning in Knowledge Graphs [54.596180382762036]
  Abductive reasoning in knowledge graphs aims to generate plausible logical hypotheses from observed entities.<n>Due to a lack of controllability, a single observation may yield numerous plausible but redundant or irrelevant hypotheses.<n>We introduce the task of controllable hypothesis generation to improve the practical utility of abductive reasoning.
  arXiv  Detail & Related papers  (2025-05-27T09:36:47Z)
• Hypothesis-Driven Theory-of-Mind Reasoning for Large Language Models [76.6028674686018]
  We introduce thought-tracing, an inference-time reasoning algorithm to trace the mental states of agents.<n>Our algorithm is modeled after the Bayesian theory-of-mind framework.<n>We evaluate thought-tracing on diverse theory-of-mind benchmarks, demonstrating significant performance improvements.
  arXiv  Detail & Related papers  (2025-02-17T15:08:50Z)
• Unveiling the Magic of Code Reasoning through Hypothesis Decomposition and Amendment [54.62926010621013]
  We introduce a novel task, code reasoning, to provide a new perspective for the reasoning abilities of large language models.<n>We summarize three meta-benchmarks based on established forms of logical reasoning, and instantiate these into eight specific benchmark tasks.<n>We present a new pathway exploration pipeline inspired by human intricate problem-solving methods.
  arXiv  Detail & Related papers  (2025-02-17T10:39:58Z)
• Thoughts Are All Over the Place: On the Underthinking of o1-Like LLMs [86.79757571440082]
  Large language models (LLMs) such as OpenAI's o1 have demonstrated remarkable abilities in complex reasoning tasks.<n>We identify a phenomenon we term underthinking, where o1-like LLMs frequently switch between different reasoning thoughts.<n>We propose a decoding strategy with thought switching penalty TIP that discourages premature transitions between thoughts.
  arXiv  Detail & Related papers  (2025-01-30T18:58:18Z)
• Learning logic programs by discovering where not to search [18.27510863075184]
  We introduce an approach that, before searching for a hypothesis, first discovers where not to search' We use given BK to discover constraints on hypotheses, such as that a number cannot be both even and odd. Our experiments on multiple domains show that our approach can substantially reduce learning times.
  arXiv  Detail & Related papers  (2022-02-20T12:32:03Z)
• Learning logic programs by explaining their failures [26.955785230358963]
  We introduce failure explanation techniques for inductive logic programming. If a hypothesis fails, we explain the failure in terms of failing sub-programs. We show that fine-grained failure analysis allows for learning fine-grained constraints on the hypothesis space.
  arXiv  Detail & Related papers  (2021-02-18T14:32:20Z)
• Learning programs by learning from failures [26.955785230358963]
  We describe an inductive logic programming (ILP) approach called learning from failures. In this approach, an ILP system decomposes the learning problem into three separate stages: generate, test, and constrain. We introduce Popper, an ILP system that implements this approach by combining answer set programming and Prolog.
  arXiv  Detail & Related papers  (2020-05-05T14:55:07Z)
• Learning large logic programs by going beyond entailment [18.27510863075184]
  We implement our idea in Brute, a new ILP system which uses best-first search, guided by an example-dependent loss function, to incrementally build programs. Our experiments show that Brute can substantially outperform existing ILP systems in terms of predictive accuracies and learning times.
  arXiv  Detail & Related papers  (2020-04-21T09:31:06Z)

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.