Counterexample Guided Learning in the Large using Reasoning Agents

• URL: http://arxiv.org/abs/2606.11521v1
• Date: Tue, 09 Jun 2026 23:46:46 GMT
• Title: Counterexample Guided Learning in the Large using Reasoning Agents
• Abstract summary: We show that verifier feedback substantially improves sample efficiency on challenging-induction tasks, reducing the number of labeled examples required and enabling learning of complex target expressions where standard prompting fails.<n>These results suggest that LLMs can benefit from rich feedback beyond treating it as additional data, opening the door for robust verifier-guided methods for LLM-based program synthesis and formal reasoning.
• Score: 15.424030391880677
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: LLMs and LLM agents should improve when given feedback, but identifying when they are able to do so is difficult: feedback is heterogeneous, domain-specific, and difficult to control. We approach this challenge by asking LLMs to perform regular-expression induction, a classical symbolic learning problem where precise mechanisms for feedback exist in the form of counterexamples. In counterexample-guided learning, a learner (LLM) proposes candidate regular expressions from positive/negative-labeled strings, and the teacher (verifier) returns counterexamples showcasing the difference between the candidate and target languages. We identify novel counterexample-guided refinement strategies that enable effective regex learning, such as regularization and symbolic counterexample clusters. We also explore agentic strategies such as reflection and repair loops. Empirically, we find that verifier feedback substantially improves sample efficiency on challenging regex-induction tasks, reducing the number of labeled examples required and enabling learning of complex target expressions where standard prompting fails. For example, on the hardest task groups, our counterexample-guided framework improves success from 3.2% to 38.1% and from 38.9% to 74.1% on two different regex domains. These results suggest that LLMs can benefit from rich feedback beyond treating it as additional data, opening the door for robust verifier-guided methods for LLM-based program synthesis and formal reasoning.

Related papers

• SSR-GRPO: Integrating Supervision and Semantic IDs into Reinforcement Learning for Dense Retrieval in E-commerce [4.188658309210585]
  Embedding-based retrieval (EBR) is pivotal in e-commerce search but often struggles with complex semantics.<n>Recent methods often fine-tune large language models (LLMs) for representation learning.<n>We propose Supervised Retrieval-GRPO with Semantic Identifiers (SSR-GRPO)
  arXiv  Detail & Related papers  (2026-08-20T03:19:20Z)
• Deliberate Evolution: Agentic Reasoning for Sample-Efficient Symbolic Regression with LLMs [52.89778838903305]
  Deliberate Evolution (DE) is an agentic framework that decouples symbolic generation from search control.<n>Experiments on LLM-SRBench show that DE consistently outperforms representative LLM-based SR baselines across diverse scientific domains.
  arXiv  Detail & Related papers  (2026-06-03T02:22:16Z)
• Learning to Disprove: Formal Counterexample Generation with Large Language Models [26.262810717227108]
  Current AI efforts in mathematics focus almost exclusively on proof construction.<n>We formalize this task as formal counterexample generation.<n>We introduce a symbolic mutation strategy that synthesizes diverse training data.
  arXiv  Detail & Related papers  (2026-03-19T22:42:49Z)
• Iterative In-Context Learning to Enhance LLMs Abstract Reasoning: The Case-Study of Algebraic Tasks [40.48180253367968]
  We introduce an in-context learning methodology that improves the generalization capabilities of general purpose LLMs.<n>Our approach employs an iterative example selection strategy, which incrementally constructs a tailored set of few-shot examples.<n>Our experiments reveal that some LLMs achieve better generalization performances when prompted with simpler few-shot examples.
  arXiv  Detail & Related papers  (2025-09-01T08:54:45Z)
• CompassVerifier: A Unified and Robust Verifier for LLMs Evaluation and Outcome Reward [50.97588334916863]
  We develop CompassVerifier, an accurate and robust lightweight verifier model for evaluation and outcome reward.<n>It demonstrates multi-domain competency spanning math, knowledge, and diverse reasoning tasks, with the capability to process various answer types.<n>We introduce VerifierBench benchmark comprising model outputs collected from multiple data sources, augmented through manual analysis of metaerror patterns to enhance CompassVerifier.
  arXiv  Detail & Related papers  (2025-08-05T17:55:24Z)
• Automated Refactoring of Non-Idiomatic Python Code: A Differentiated Replication with LLMs [54.309127753635366]
  We present the results of a replication study in which we investigate GPT-4 effectiveness in recommending and suggesting idiomatic actions.<n>Our findings underscore the potential of LLMs to achieve tasks where, in the past, implementing recommenders based on complex code analyses was required.
  arXiv  Detail & Related papers  (2025-01-28T15:41:54Z)
• Exploring Iterative Controllable Summarization with Large Language Models [22.80433394369022]
  Large language models (LLMs) have demonstrated remarkable performance in abstractive summarization tasks.<n>Our findings show that LLMs struggle more with numerical attributes than with linguistic attributes.<n>We propose a guide-to-explain framework (GTE) for controllable summarization.
  arXiv  Detail & Related papers  (2024-11-19T12:36:02Z)
• ReEval: Automatic Hallucination Evaluation for Retrieval-Augmented Large Language Models via Transferable Adversarial Attacks [91.55895047448249]
  This paper presents ReEval, an LLM-based framework using prompt chaining to perturb the original evidence for generating new test cases. We implement ReEval using ChatGPT and evaluate the resulting variants of two popular open-domain QA datasets. Our generated data is human-readable and useful to trigger hallucination in large language models.
  arXiv  Detail & Related papers  (2023-10-19T06:37:32Z)
• Self-RAG: Learning to Retrieve, Generate, and Critique through Self-Reflection [74.51523859064802]
  We introduce a new framework called Self-Reflective Retrieval-Augmented Generation (Self-RAG) Self-RAG enhances an LM's quality and factuality through retrieval and self-reflection. It significantly outperforms state-of-the-art LLMs and retrieval-augmented models on a diverse set of tasks.
  arXiv  Detail & Related papers  (2023-10-17T18:18:32Z)
• Re-Reading Improves Reasoning in Large Language Models [87.46256176508376]
  We introduce a simple, yet general and effective prompting method, Re2, to enhance the reasoning capabilities of off-the-shelf Large Language Models (LLMs) Unlike most thought-eliciting prompting methods, such as Chain-of-Thought (CoT), Re2 shifts the focus to the input by processing questions twice, thereby enhancing the understanding process. We evaluate Re2 on extensive reasoning benchmarks across 14 datasets, spanning 112 experiments, to validate its effectiveness and generality.
  arXiv  Detail & Related papers  (2023-09-12T14:36:23Z)
• Guiding Large Language Models via Directional Stimulus Prompting [114.84930073977672]
  We introduce Directional Stimulus Prompting, a novel framework for guiding black-box large language models (LLMs) toward specific desired outputs. Instead of directly adjusting LLMs, our method employs a small tunable policy model to generate an auxiliary directional stimulus prompt for each input instance.
  arXiv  Detail & Related papers  (2023-02-22T17:44:15Z)

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.