Measuring and Narrowing the Compositionality Gap in Language Models

2022/10/07 by Ofir Press, Press, Ofir, Muru Zhang +8 · 177 citations
Computer Science · #Topic Modeling #Natural Language Processing Techniques #Software Engineering Research

paper · pdf · doi:10.48550/arxiv.2210.03350

Abstract

We investigate the ability of language models to perform compositional reasoning tasks where the overall solution depends on correctly composing the answers to sub-problems. We measure how often models can correctly answer all sub-problems but not generate the overall solution, a ratio we call the compositionality gap. We evaluate this ratio by asking multi-hop questions with answers that require composing multiple facts unlikely to have been observed together during pretraining. In the GPT-3 family of models, as model size increases we show that the single-hop question answering performance improves faster than the multi-hop performance does, therefore the compositionality gap does not decrease. This surprising result suggests that while more powerful models memorize and recall more factual knowledge, they show no corresponding improvement in their ability to perform this kind of compositional reasoning. We then demonstrate how elicitive prompting (such as chain of thought) narrows the compositionality gap by reasoning explicitly. We present a new method, self-ask, that further improves on chain of thought. In our method, the model explicitly asks itself (and answers) follow-up questions before answering the initial question. We finally show that self-ask's structured prompting lets us easily plug in a search engine to answer the follow-up questions, which additionally improves accuracy.

Cited by

• From Proprietary to Open-Source: Bridging the Distribution Gap via Multi-Agent Protocol Distillation in Agentic Search
• Agentic Entropy-Balanced Policy Optimization
• Delegation Intelligence in Deep Search: A Controllable Framework for Disentangled Capability Diagnosis
• DiscoLoop: Looping Discrete Embeddings and Continuous Hidden States for Multi-hop Reasoning
• Robust Interpretation of Historical Documents in Knowledge Graphs Through Query Inference and Execution
• VecTree-RAG: An Agentic Retrieval-Augmented Generation Framework Combining Vector and Tree Retrieval for Efficiency and Accuracy
• SymStep: Symbolic Step Verification for Logical Reasoning
• Co-Evolving Graph and Text Memory for Training-Free Multi-Hop Question Answering
• ATOD: Annealed Turn-Aware On-Policy Distillation for Multi-Turn Agentic Tasks
• Reason Before You Retrieve: Agentic Planning for Multi-modal RAG
• Repeated-Token Counting Reveals a Dissociation Between Representations and Outputs
• Laser: Governing Long-Horizon Agentic Search via Structured Protocol and Context Register
• LongVideoAgent: Multi-Agent Reasoning with Long Videos
• GenEnv: Difficulty-Aligned Co-Evolution Between LLM Agents and Environment Simulators
• AdaSearch: Balancing Parametric Knowledge and Search in Large Language Models via Reinforcement Learning
• DataFlow: An LLM-Driven Framework for Unified Data Preparation and Workflow Automation in the Era of Data-Centric AI
• ToolForge: A Data Synthesis Pipeline for Multi-Hop Search without Real-World APIs
• MMhops-R1: Multimodal Multi-hop Reasoning
• AutoTool: Dynamic Tool Selection and Integration for Agentic Reasoning
• Socratic Students: Teaching Language Models to Learn by Asking Questions
• CoDA: A Context-Decoupled Hierarchical Agent with Reinforcement Learning
• Replace, Don't Expand: Mitigating Context Dilution in Multi-Hop RAG via Fixed-Budget Evidence Assembly
• GPG: Generalized Policy Gradient Theorem for Transformer-based Policies
• Source Coverage and Citation Bias in LLM-based vs. Traditional Search Engines
• Encoder-Free Knowledge-Graph Reasoning with LLMs via Hyperdimensional Path Retrieval
• LocalSearchBench: Benchmarking Agentic Search in Real-World Local Life Services
• Enhancing Agentic RL with Progressive Reward Shaping and Value-based Sampling Policy Optimization
• The Missing Layer of AGI: From Pattern Alchemy to Coordination Physics
• CARL: Criticality-Aware Agentic Reinforcement Learning
• On GRPO Collapse in Search-R1: The Lazy Likelihood-Displacement Death Spiral
• Cross-Lingual Prompt Steerability: Towards Accurate and Robust LLM Behavior across Languages
• Agentic Policy Optimization via Instruction-Policy Co-Evolution
• In-Context Compositional Learning via Sparse Coding Transformer
• NeuroPath: Neurobiology-Inspired Path Tracking and Reflection for Semantically Coherent Retrieval
• Multi-Agent Deep Research: Training Multi-Agent Systems with M-GRPO
• LiveSearchBench: An Automatically Constructed Benchmark for Retrieval and Reasoning over Dynamic Knowledge
• CriticSearch: Fine-Grained Credit Assignment for Search Agents via a Retrospective Critic
• Retrieval as a Decision: Training-Free Adaptive Gating for Efficient RAG
• A mathematical theory of balancing relational generalization and memorization
• From Experience to Strategy: Empowering LLM Agents with Trainable Graph Memory
• Think Before You Retrieve: Learning Test-Time Adaptive Search with Small Language Models
• MemSearcher: Training LLMs to Reason, Search and Manage Memory via End-to-End Reinforcement Learning
• Continuum: Efficient and Robust Multi-Turn LLM Agent Scheduling with KV Cache Time-to-Live
• How Focused Are LLMs? A Quantitative Study via Repetitive Deterministic Prediction Tasks
• Test-time Scaling of LLMs: A Survey from A Subproblem Structure Perspective
• Interact-RAG: Reason and Interact with the Corpus, Beyond Black-Box Retrieval
• InfoFlow: Reinforcing Search Agent Via Reward Density Optimization
• Graph-Enhanced Policy Optimization in LLM Agent Training
• GAP: Graph-Based Agent Planning with Parallel Tool Use and Reinforcement Learning
• BM25 Wins at Scale: A Scaling Study of Retrieval-Augmented Generation Paradigms
• Metis: Memory Foundation Model
• SimpleWikiSearch: A Clean Offline Wikipedia Environment for Agentic Search
• The Architecture of Errors: From Universal Impossibility to Patch-Local LLM Reliability
• Metacognition Should Be the Scientific Framework for Bounded and Effective Self-Governance in Generative AI
• Sharpness-Guided Group Relative Policy Optimization via Probability Shaping
• Repurposing Synthetic Data for Fine-grained Search Agent Supervision
• Metadata-Driven Retrieval-Augmented Generation for Financial Question Answering
• Can Language Models Compose Skills In-Context?
• Culturally Grounded Physical Commonsense Reasoning in Italian and English: A Submission to the MRL 2025 Shared Task
• FAIR-RAG: Faithful Adaptive Iterative Refinement for Retrieval-Augmented Generation
• Rethinking the Design of Reinforcement Learning-Based Deep Research Agents
• Bridging Language Gaps with Adaptive RAG: Improving Indonesian Language Question Answering
• GlobalRAG: Enhancing Global Reasoning in Multi-hop Question Answering via Reinforcement Learning
• Think Straight, Stop Smart: Structured Reasoning for Efficient Multi-Hop RAG
• Search Self-play: Pushing the Frontier of Agent Capability without Supervision
• MENTOR: A Reinforcement Learning Framework for Enabling Tool Use in Small Models via Teacher-Optimized Rewards
• AgentChangeBench: A Multi-Dimensional Evaluation Framework for Goal-Shift Robustness in Conversational AI
• Towards Mixed-Modal Retrieval for Universal Retrieval-Augmented Generation
• SafeSearch: Do Not Trade Safety for Utility in LLM Search Agents
• Knowing the Facts but Choosing the Shortcut: Understanding How Large Language Models Compare Entities
• A Comprehensive Survey on Reinforcement Learning-based Agentic Search: Foundations, Roles, Optimizations, Evaluations, and Applications
• Prompt Optimization via Retrieved Reasoning Assets and Multi-Agent Analysis
• Cost-Aware Retrieval-Augmentation Reasoning Models with Adaptive Retrieval Depth
• EvolveR: Self-Evolving LLM Agents through an Experience-Driven Lifecycle
• Structure-R1: Dynamically Leveraging Structural Knowledge in LLM Reasoning through Reinforcement Learning
• Information Gain-based Policy Optimization: A Simple and Effective Approach for Multi-Turn LLM Agents
• Stop-RAG: Value-Based Retrieval Control for Iterative RAG
• PRISM: Agentic Retrieval with LLMs for Multi-Hop Question Answering
• Towards Agentic Self-Learning LLMs in Search Environment
• MemoTime: Memory-Augmented Temporal Knowledge Graph Enhanced Large Language Model Reasoning
• Learnable Game-theoretic Policy Optimization for Data-centric Self-explanation Rationalization
• Beyond Correctness: Rewarding Faithful Reasoning in Retrieval-Augmented Generation
• The Curious Case of Curiosity across Human Cultures and LLMs
• Memory as Action: Autonomous Context Curation for Long-Horizon Agentic Tasks
• A Survey on Parallel Reasoning
• Uncertainty Quantification for Retrieval-Augmented Reasoning
• LLM-Specific Utility: A New Perspective for Retrieval-Augmented Generation
• Proof-of-Use: Mitigating Tool-Call Hacking in Deep Research Agents
• BrowserAgent: Building Web Agents with Human-Inspired Web Browsing Actions
• RECON: Reasoning with Condensation for Efficient Retrieval-Augmented Generation
• Audit-of-Understanding: Posterior-Constrained Inference for Mathematical Reasoning in Language Models
• ADMIT: Few-shot Knowledge Poisoning Attacks on RAG-based Fact Checking
• Beyond the limitation of a single query: Train your LLM for query expansion with Reinforcement Learning
• Demystifying Reinforcement Learning for Long-Horizon Tool-Using Agents: A Comprehensive Recipe
• How Do Language Models Compose Functions?
• DSPO: Stable and Efficient Policy Optimization for Agentic Search and Reasoning
• FOR-Prompting: From Objection to Revision via an Asymmetric Prompting Protocol
• Agent Learning via Early Experience
• STEPER: Step-wise Knowledge Distillation for Enhancing Reasoning Ability in Multi-Step Retrieval-Augmented Language Models
• HiPRAG: Hierarchical Process Rewards for Efficient Agentic Retrieval Augmented Generation
• A²Search: Ambiguity-Aware Question Answering with Reinforcement Learning
• Beneficial Reasoning Behaviors in Agentic Search and Effective Post-training to Obtain Them
• Adaptive Tool Generation with Models as Tools and Reinforcement Learning
• Stratified GRPO: Handling Structural Heterogeneity in Reinforcement Learning of LLM Search Agents
• DecEx-RAG: Boosting Agentic Retrieval-Augmented Generation with Decision and Execution Optimization via Process Supervision
• MARS: Co-evolving Dual-System Deep Research via Multi-Agent Reinforcement Learning
• Beyond Outcome Reward: Decoupling Search and Answering Improves LLM Agents
• Dual-stage and Lightweight Patient Chart Summarization for Emergency Physicians
• AlphaApollo: Orchestrating Foundation Models and Professional Tools into a Self-Evolving System for Deep Agentic Reasoning
• Lateral Tree-of-Thoughts Surpasses ToT by Incorporating Logically-Consistent, Low-Utility Candidates
• AutoMaAS: Self-Evolving Multi-Agent Architecture Search for Large Language Models
• ReSeek: A Self-Correcting Framework for Search Agents with Instructive Rewards
• Erase to Improve: Erasable Reinforcement Learning for Search-Augmented LLMs
• RE-Searcher: Robust Agentic Search with Goal-oriented Planning and Self-reflection
• RoRecomp: Enhancing Reasoning Efficiency via Rollout Response Recomposition in Reinforcement Learning
• Hybrid Reward Normalization for Process-supervised Non-verifiable Agentic Tasks
• MAS²: Self-Generative, Self-Configuring, Self-Rectifying Multi-Agent Systems
• AceSearcher: Bootstrapping Reasoning and Search for LLMs via Reinforced Self-Play
• Explore-Execute Chain: Towards an Efficient Structured Reasoning Paradigm
• The Impact of Role Design in In-Context Learning for Large Language Models
• MedCritical: Enhancing Medical Reasoning in Small Language Models via Self-Collaborative Correction
• Toward Effective Tool-Integrated Reasoning via Self-Evolved Preference Learning
• Learn the Ropes, Then Trust the Wins: Self-imitation with Progressive Exploration for Agentic Reinforcement Learning
• Do LLM Agents Know How to Ground, Recover, and Assess? A Benchmark for Epistemic Competence in Information-Seeking Agents
• PANICL: Mitigating Over-Reliance on Single Prompt in Visual In-Context Learning
• Tree Search for LLM Agent Reinforcement Learning
• Binary Autoencoder for Mechanistic Interpretability of Large Language Models
• A Fano-Style Accuracy Upper Bound for LLM Single-Pass Reasoning in Multi-Hop QA
• CLAUSE: Agentic Neuro-Symbolic Knowledge Graph Reasoning via Dynamic Learnable Context Engineering
• UserRL: Training Interactive User-Centric Agent via Reinforcement Learning
• ContextNest: Verifiable Context Governance for Autonomous AI Agent
• Dr-DCI: Scaling Direct Corpus Interaction via Dynamic Workspace Expansion
• From Language to Action: A Review of Large Language Models as Autonomous Agents and Tool Users
• DeepDive: Advancing Deep Search Agents with Knowledge Graphs and Multi-Turn RL
• Unbiased Reasoning for Knowledge-Intensive Tasks in Large Language Models via Conditional Front-Door Adjustment
• PromptGuard: An Orchestrated Prompting Framework for Principled Synthetic Text Generation for Vulnerable Populations using LLMs with Enhanced Safety, Fairness, and Controllability
• AgentGym-RL: Training LLM Agents for Long-Horizon Decision Making through Multi-Turn Reinforcement Learning
• Reinforcement Learning Foundations for Deep Research Systems: A Survey
• DecoupleSearch: Decouple Planning and Search via Hierarchical Reward Modeling
• Fishing for Answers: Exploring One-shot vs. Iterative Retrieval Strategies for Retrieval Augmented Generation
• Explainable Knowledge Graph Retrieval-Augmented Generation (KG-RAG) with KG-SMILE
• Implicit Reasoning in Large Language Models: A Comprehensive Survey
• CMR-SPB: Cross-Modal Multi-Hop Reasoning over Text, Image, and Speech with Path Balance
• Memento: Fine-tuning LLM Agents without Fine-tuning LLMs
• KoBLEX: Open Legal Question Answering with Multi-hop Reasoning
• Iterative In-Context Learning to Enhance LLMs Abstract Reasoning: The Case-Study of Algebraic Tasks
• VerlTool: Towards Holistic Agentic Reinforcement Learning with Tool Use
• Vis-CoT: A Human-in-the-Loop Framework for Interactive Visualization and Intervention in LLM Chain-of-Thought Reasoning
• EviNote-RAG: Enhancing RAG Models via Answer-Supportive Evidence Notes
• Open Data Synthesis For Deep Research
• COCORELI: Cooperative, Compositional Reconstitution & Execution of Language Instructions
• PVPO: Pre-Estimated Value-Based Policy Optimization for Agentic Reasoning
• AI-SearchPlanner: Modular Agentic Search via Pareto-Optimal Multi-Objective Reinforcement Learning
• Can Compact Language Models Search Like Agents? Distillation-Guided Policy Optimization for Preserving Agentic RAG Capabilities
• CataractSurg-80K: Knowledge-Driven Benchmarking for Structured Reasoning in Ophthalmic Surgery Planning
• AgentCoMa: A Compositional Benchmark Mixing Commonsense and Mathematical Reasoning in Real-World Scenarios
• Test-time Corpus Feedback: From Retrieval to RAG
• Select to Know: An Internal-External Knowledge Self-Selection Framework for Domain-Specific Question Answering
• Atom-Searcher: Enhancing Agentic Deep Research via Fine-Grained Atomic Thought Reward
• MoNaCo: More Natural and Complex Questions for Reasoning Across Dozens of Documents
• SSRL: Self-Search Reinforcement Learning
• PRELUDE: A Benchmark Designed to Require Global Comprehension and Reasoning over Long Contexts
• ParallelSearch: Train your LLMs to Decompose Query and Search Sub-queries in Parallel with Reinforcement Learning
• Careful Queries, Credible Results: Teaching RAG Models Advanced Web Search Tools with Reinforcement Learning
• Beyond Ten Turns: Unlocking Long-Horizon Agentic Search with Large-Scale Asynchronous RL
• UR²: Unify RAG and Reasoning through Reinforcement Learning
• First Ask Then Answer: A Framework Design for AI Dialogue Based on Supplementary Questioning with Large Language Models
• ICM-Fusion: In-Context Meta-Optimized LoRA Fusion for Multi-Task Adaptation
• Enhancing Serendipity Recommendation System by Constructing Dynamic User Knowledge Graphs with Large Language Models
• VeriGUI: Verifiable Long-Chain GUI Dataset
• Beyond Chunks and Graphs: Retrieval-Augmented Generation through Triplet-Driven Thinking
• AGENTICT²S:Robust Text-to-SPARQL via Agentic Collaborative Reasoning over Heterogeneous Knowledge Graphs for the Circular Economy
• A Survey of LLM-based Deep Search Agents: Paradigm, Optimization, Evaluation, and Challenges
• From Query to Logic: Ontology-Driven Multi-Hop Reasoning in LLMs
• MAO-ARAG: Multi-Agent Orchestration for Adaptive Retrieval-Augmented Generation
• From Sufficiency to Reflection: Reinforcement-Guided Thinking Quality in Retrieval-Augmented Reasoning for LLMs
• Explainability Through Systematicity: The Hard Systematicity Challenge for Artificial Intelligence

Related

• Teaching Smaller Language Models To Generalise To Unseen Compositional Questions
• Question Decomposition Improves the Faithfulness of Model-Generated Reasoning
• Do Large Language Models Have Compositional Ability? An Investigation into Limitations and Scalability
• Teaching Smaller Language Models To Generalise To Unseen Compositional Questions (Full Thesis)
• Language Models Benefit from Preparation with Elicited Knowledge