Language models and retrievers often treat "not" as if it weren't there. Asked for "something to drink other than soda," a perception system goes looking for soda. Asked to rank a document that says a drug does not cause drowsiness, a dense retriever scores it as if it said the opposite. The problem gets worse when the exclusion sits in the middle of a reasoning chain, as in "the city where the sibling of X who was not born in Y went to school." Separately, a recent result showed that small models (0.6B–7B parameters) can learn to chain facts across several hops by practicing on entirely fictional, rule-generated worlds. They are rewarded only for the correct final answer, and the skill transfers to real multi-hop questions. That training data contains only positive relations. It never asks the model to exclude anything.
We propose adding verified negation to that fictional-world training. Our generator builds multi-hop questions in which an exclusion ("not," "other than," "except") applies at a controlled point in the chain. A logic-program solver computes the exact answer under a closed world, meaning any fact not stated in the fictional universe is false. The solver also computes the forbidden set: the entities a model would wrongly return if it ignored the negation. The student is trained with reinforcement learning, and its reward explicitly penalizes returning forbidden entities. The claim is that exclusion can be learned as a transferable reasoning skill, in the same way positive composition was, provided two things hold. The training signal must punish the specific shortcut of matching the mentioned keyword, and it must teach where in the chain the exclusion applies.
Core Claim
Learning from Synthetic Data Improves Multi-hop Reasoning supplies the method. It trains Qwen3 and Phi-4 students with GRPO (Group Relative Policy Optimization, a reinforcement learning method that scores several sampled answers per question against each other) on PhantomWiki and ReasoningGym. It reports relative F1 gains of 56–131% on real benchmarks for Qwen3-0.6B, and generalization from 2–3-hop training to 9-hop questions. Its generators, however, encode only positive traversal, and the trained models were never tested on negation.
Our hypothesis has two parts, and they can fail separately. First, adding negation templates alone will teach the surface form of exclusion and not its scope. Models will learn to drop the mentioned entity at the end of the chain, which is exactly the post-hoc filtering that LLM-MatLogic shows breaks multi-hop semantics. That paper uses a symbolic matrix executor over knowledge graphs, and it proves that negation must be applied after intermediate "witness" entities are produced and before they are merged or projected onward. It names two failures when this order is violated: scope drift, where a local exclusion wipes out valid answers, and evidence loss, where intermediate roles are collapsed before they are checked. Its oracle-scope diagnostic showed that the language model's inability to bind the scope of a negation is the main bottleneck. Second, a reward that penalizes forbidden entities, applied to questions built so that end-of-chain filtering gives the wrong answer, will teach correct scope binding inside the model's own reasoning, with no external executor. What is new is the pairing of three things: a solver-verified forbidden-set penalty, generation that deliberately places exclusion at different points in the chain, and transfer tests on real negation benchmarks.
Research Program
Generator. We extend PhantomWiki's pipeline (PhantomWiki builds fictional social graphs, writes templated biographies, generates questions from a context-free grammar, and derives answers with Prolog) with three new operators. The first is set difference ("friends of X who are not Y's coworkers"). The second is attribute exclusion ("siblings of X not born in Z"). The third is exclusion by description, where the negated item is identified only by a relation ("other than the person X mentored"). Each question has a negation depth $d$, the hop at which exclusion applies, running from the first intermediate hop to the final answer.
Prolog's negation-as-failure yields gold answers directly. Negation-as-failure means "not provable" counts as "false." This is sound here because the fictional universe is closed, and that closed-world property is precisely why these worlds make negation verifiable in a way web text does not.
For every negated question $q$, the solver also answers its negation-dropped twin $q^-$, which is the same question with the exclusion removed. The forbidden set is $F(q) = A(q^-) \setminus A(q)$, where $A(\cdot)$ is the gold answer set. We keep only questions where $F(q)$ is non-empty. We further mark "scope traps": questions where applying the exclusion only at the end, to the final candidate list, gives a different answer from applying it at depth $d$. This mark is itself computed by running both orders in Prolog.
Reward. For a sampled answer set $\hat{A}$, the reward is
$$ r(\hat{A}) = \mathrm{F1}(\hat{A}, A(q)) - \lambda \, \frac{|\hat{A} \cap F(q)|}{\max(|\hat{A}|, 1)}, $$
where F1 is set overlap with the gold answers and $\lambda \ge 0$ weights the penalty for returning entities the negation should have removed. With $\lambda = 0$ this reduces to the outcome-only reward of the prior synthetic-RL work. That makes $\lambda$ the ablation that isolates our key ingredient.
Training mix. Negated questions are mixed with the original positive questions. This guards against the failure the negation literature warns about, where suppressing the mentioned entity damages ordinary attribute recognition. We sweep the mixing ratio and the share of scope traps. Students are Qwen3-0.6B, 1.7B, and 4B, matching the prior work so its numbers serve as anchors.
Analysis. We report accuracy as a function of negation depth and number of hops. The expected signature is that, without scope traps and without the forbidden-set penalty, models do well when $d$ is the final hop and fail at intermediate $d$. We also check the reasoning traces for whether the exclusion is applied before the next hop. This is a diagnostic only; nothing in training rewards the trace.
Baselines
The naive reference point is the untrained Qwen3 student with chain-of-thought prompting, evaluated on every benchmark below. It sets the floor and shows how much of the problem is present at each model size.
The strongest competitor on this specific question is the positive-only synthetic-RL model from Learning from Synthetic Data Improves Multi-hop Reasoning. We retrain it ourselves using the same backbone, the same number of GRPO steps, the same rollout group size, and the same number of training questions, all on the original positive-only generators. Any gain we show is then attributable to negation content and reward design, not to extra compute. That paper reports relative F1 gains of 56–131% for Qwen3-0.6B on real multi-hop benchmarks. The file gives no absolute per-benchmark numbers, so our retrained run is the reference. Beating it means a clear improvement on negation benchmarks with at most a small loss on MuSiQue F1 (within the run-to-run variance we measure over three seeds).
The key ablations use the identical negation data. The first sets $\lambda = 0$ (negation data, outcome-only reward). The second removes scope traps, keeping only final-hop exclusions. The third uses SFT (supervised fine-tuning) on solver-derived reasoning traces for the same questions. Each gets the same data budget and a learning-rate sweep of equal size.
For negation-aware retrieval, the reported bar is a cross-encoder. On NevIR the largest MonoT5 reaches 50.6% pairwise accuracy (random is 25%), and ColBERTv1 fine-tuned on NevIR reaches only about 25%, according to NevIR. We use our student as a reranker in the same pairwise protocol. Beating the baseline means exceeding 50.6% without training on NevIR.
For multi-hop logical retrieval we use ComLQ, which measures negation violations with LSNC@K (Log-Scaled Negation Consistency, the rate at which top-K results violate the exclusion). It reports only that scores are "consistently low" and that BM25 is competitive. No reported numeric LSNC result found on Lacuna for ComLQ, so we run BM25 and a dense retriever ourselves as first stages and compare rerankers on top of each.
Why not just…?
Why not just use the existing positive-only synthetic-RL model? This is the real threat. If knowledge composition is a general skill, exclusion might come along for free. Nothing in the file shows that it does or doesn't, because those models were never evaluated on negation. Our first experiment settles it. If the retrained positive-only model already matches our model on ComLQ negation queries and NevIR, then the negation generator adds nothing, and we will report that as the finding.
Why not just fine-tune on real negation data such as NevIR or CondaQA? Real negation data is small and teaches single-step contrast. NevIR fine-tuning moved ColBERTv1 only from 19.7% to about 25% pairwise accuracy (NevIR). These datasets contain no chains in which the exclusion must be bound to an intermediate entity. They are also prone to the negation-avoidance problem NevIR describes, where users stop writing negated queries because systems handle them badly, so the data stays scarce. We include a matched-size baseline that fine-tunes on CondaQA-derived pairs and evaluate it on held-out ComLQ and PhantomWiki-Neg scope traps. There we expect it to perform no better than the untrained model.
Why not just prompt a frontier model, or apply a keyword filter after retrieval? Frontier prompting helps but does not close the gap: GPT-4o with Set-of-Marks and chain-of-thought reaches 63.7% on Ref-Adv, where negation makes up 21.25% of expressions (Ref-Adv). It also defeats the purpose of a small, cheap student. Filtering after retrieval is exactly the end-of-chain exclusion that LLM-MatLogic proves produces scope drift. Our scope-trap test set is built so that such a filter gives the wrong answer by construction. We implement the filter as an explicit baseline to show the size of that gap on real questions, not only synthetic ones.
Proposed Experiments
The first decisive check is on a held-out split of PhantomWiki with negation (PhantomWiki-Neg), using unseen universes, hop counts up to 9, and all negation depths. The full method must beat the $\lambda = 0$ and no-scope-trap ablations specifically on intermediate-depth scope traps. If gains appear only when negation applies at the final hop, the scope claim fails.
The second check is transfer to real text. We measure LSNC@100 and recall on the five negation query structures of ComLQ, with the student reranking BM25 candidates, and we break results down by operation order, since ComLQ finds projection-then-intersection to be the harder order. We also measure NevIR pairwise accuracy against the 50.6% MonoT5 figure.
The third check is that positive reasoning is not damaged. MuSiQue F1 must stay within seed variance of the positive-only baseline, which tests the worry that suppressing mentioned entities hurts ordinary composition. MuSiQue reports 47.3 F1 for its best model and 78.0 for humans, which gives context but is not a like-for-like comparison.
A final, exploratory check verbalizes FB15k-237 2in queries into text. It asks whether the trained student, used without the matrix executor, approaches the 11.4 MRR that LLM-MatLogic reports against 7.5 for BetaE. That would indicate the placement rule has moved from an external engine into the model.
Multimodal settings such as Ref-Adv and MMhops are deliberately left out of scope. A text-only result is the prerequisite for claiming that the same fictional-world approach could later cover visual exclusion.
References
- Learning from Synthetic Data Improves Multi-hop Reasoning
- LLM-MatLogic: Executable Exchange Contracts for Knowledge-Graph Query Answering with Scoped Negation
- PhantomWiki: On-Demand Datasets for Reasoning and Retrieval Evaluation
- NevIR: Negation in Neural Information Retrieval
- ComLQ: Benchmarking Complex Logical Queries in Information Retrieval
- Ref-Adv: Exploring MLLM Visual Reasoning in Referring Expression Tasks
- ♫ MuSiQue: Multihop Questions via Single-hop Question Composition