Murray ShanahanDec 29, 2022
Mark Riedl

We know from the long history of “classical” AI techniques tha ends-means reasoning (backward chaining) can be highly effective and more efficient than forward-reasoning.

This paper achieves significant gains on logic reasoning by inducing an LM to chain backwards from conclusion to premise: https://arxiv.org/abs/2212.13894

The LM is “wrapped” by a larger, ire traditional algorithm. This is notable because it acknowledges that LMs can be made more powerful with external routines.

1/3

LAMBADA: Backward Chaining for Automated Reasoning in Natural Language

Remarkable progress has been made on automated reasoning with natural text, by using Language Models (LMs) and methods such as Chain-of-Thought and Selection-Inference. These techniques search for proofs in the forward direction from axioms to the conclusion, which suffers from a combinatorial explosion of the search space, and thus high failure rates for problems requiring longer chains of reasoning. The classical automated reasoning literature has shown that reasoning in the backward direction (i.e. from the intended conclusion to supporting axioms) is significantly more efficient at proof-finding. Importing this intuition into the LM setting, we develop a Backward Chaining algorithm, called LAMBADA, that decomposes reasoning into four sub-modules. These sub-modules are simply implemented by few-shot prompted LM inference. We show that LAMBADA achieves sizable accuracy boosts over state-of-the-art forward reasoning methods on challenging logical reasoning datasets, particularly when deep and accurate proof chains are required.

arXiv.org
Dec 29, 2022 at 2:07amWeb
Show threadMark RiedlDec 29, 2022

My team has been looking into wrapping Language Models within backward chaining algorithms for a few years now. In the context of story generation. Plot coherence has a lot of similarities with logical reasoning, though without the need for hard guarantees (readers can be forgiving sbout certain types of omissions).

Our most recent work wraps an LM in an algorithm inspired by ends-means backward chaining search: https://arxiv.org/abs/2212.08718 (came out a few days earlier 😉)

2/3

Neural Story Planning

Automated plot generation is the challenge of generating a sequence of events that will be perceived by readers as the plot of a coherent story. Traditional symbolic planners plan a story from a goal state and guarantee logical causal plot coherence but rely on a library of hand-crafted actions with their preconditions and effects. This closed world setting limits the length and diversity of what symbolic planners can generate. On the other hand, pre-trained neural language models can generate stories with great diversity, while being generally incapable of ending a story in a specified manner and can have trouble maintaining coherence. In this paper, we present an approach to story plot generation that unifies causal planning with neural language models. We propose to use commonsense knowledge extracted from large language models to recursively expand a story plot in a backward chaining fashion. Specifically, our system infers the preconditions for events in the story and then events that will cause those conditions to become true. We performed automatic evaluation to measure narrative coherence as indicated by the ability to answer questions about whether different events in the story are causally related to other events. Results indicate that our proposed method produces more coherent plotlines than several strong baselines.

arXiv.org
Show threadMark RiedlDec 29, 2022

Our first attempt at backward-chaining with language models wrapped an LM in a recursive question-answering routine, where the algorithm attempted to guess what questions readers might have and preemptively answer them https://arxiv.org/abs/2112.03808

Anyway, I’m pretty excited about using LMs as part of a larger, structured process instead of just entering a prompt and generating continuations.

3/3

Automated Story Generation as Question-Answering

Neural language model-based approaches to automated story generation suffer from two important limitations. First, language model-based story generators generally do not work toward a given goal or ending. Second, they often lose coherence as the story gets longer. We propose a novel approach to automated story generation that treats the problem as one of generative question-answering. Our proposed story generation system starts with sentences encapsulating the final event of the story. The system then iteratively (1) analyzes the text describing the most recent event, (2) generates a question about "why" a character is doing the thing they are doing in the event, and then (3) attempts to generate another, preceding event that answers this question.

arXiv.org
Show threadMarco 🌳 ZoccaDec 29, 2022
@Riedl Along similar lines, I'm doing some experiments with the "entailment trees" paradigm from AI2 : https://arxiv.org/abs/2104.08661
Explaining Answers with Entailment Trees

Our goal, in the context of open-domain textual question-answering (QA), is to explain answers by showing the line of reasoning from what is known to the answer, rather than simply showing a fragment of textual evidence (a "rationale'"). If this could be done, new opportunities for understanding and debugging the system's reasoning become possible. Our approach is to generate explanations in the form of entailment trees, namely a tree of multipremise entailment steps from facts that are known, through intermediate conclusions, to the hypothesis of interest (namely the question + answer). To train a model with this skill, we created ENTAILMENTBANK, the first dataset to contain multistep entailment trees. Given a hypothesis (question + answer), we define three increasingly difficult explanation tasks: generate a valid entailment tree given (a) all relevant sentences (b) all relevant and some irrelevant sentences, or (c) a corpus. We show that a strong language model can partially solve these tasks, in particular when the relevant sentences are included in the input (e.g., 35% of trees for (a) are perfect), and with indications of generalization to other domains. This work is significant as it provides a new type of dataset (multistep entailments) and baselines, offering a new avenue for the community to generate richer, more systematic explanations.

arXiv.org
Show threadMark RiedlDec 29, 2022
@ocramz I remember that paper. The dataset is interesting. The experiments still try to solve the entire entailment by fine-tuning a LM to spit out an entire tree at once, though, so I didn’t consider it as chaining through iterative querying.
Show threadJoanna Bryson, blatheringDec 29, 2022
@Riedl you know you can edit toots? ("mire")
Show threadMark RiedlDec 30, 2022
@j2bryson I have to be aware of my autocorrect errors first. Thanks
Show threadJakub KotowskiDec 30, 2022
@Riedl next step: implementing something like Magic Sets to combine forward- and backward- chaining!