Who Gets Left Out of the Context Window: Group-Calibrated Evidence Budgets for Knowledge-Graph Question Answering

Language models that answer questions over a knowledge graph first turn part of the graph into text. A retriever picks some multi-hop paths (chains like person -> born_in -> city -> located_in -> country), writes them out as sentences in some order, and hands them to the model. The context window is finite, so the system has to cut somewhere. Retrieval scores and ordering heuristics reward well-connected entities, so the cut plausibly falls hardest on sparsely documented entities. If sparseness tracks a multi-valued attribute of the entity, such as nationality, ethnicity, or gender category, the result is a hidden accuracy gap between groups. That gap is created by the step that writes the graph as text, before the model reasons at all.

This note proposes to measure that gap and to correct it where it arises. The correction does not adjust the model's final answers. It adjusts how the evidence budget is spent. We learn one score offset per group, so the chance that the gold reasoning path makes it into the context is roughly equal across many overlapping groups. The groups include K-valued attributes and entity-degree bins. The overall token budget stays fixed. Because every group is matched to a single shared target rather than compared pairwise, the number of constraints grows with K rather than K². The central empirical question can be falsified: does the group gap come mainly from missing evidence (a recall gap) or from how the model uses evidence it already has (a verification gap)? The first favors our method. The second favors cheap post-hoc correction of answer scores, and we would switch to that.

Core Claim

In knowledge-graph question answering pipelines that linearize retrieved paths (writing them out as a flat token sequence) under a fixed budget, we claim that accuracy differences across multi-valued entity groups are driven mostly by which paths get serialized and where they appear. We further claim that group-conditional calibration of the retriever's evidence-inclusion probability can shrink the worst-group gap with little or no loss in overall Hits@1. Correcting the final answer scores cannot achieve the same, because it cannot bring back evidence that was never shown to the model.

Three strands of prior work motivate this claim. Graph Linearization Methods for Reasoning on Graphs with Large Language Models orders edges by degree, PageRank, or core number and relabels nodes by rank. It reports about a 35% accuracy gain on max-degree estimation in GraphQA, which shows that serialization order steers what the model attends to. That work is purely structural and never asks who is disadvantaged by the ordering. EDITS debiases node attributes and rewires adjacency before message passing in a graph neural network. It shows that graph structure itself carries bias correlated with sensitive attributes, but it studies node classification with binary groups, with no text and no multi-hop queries. Integrating Social Determinants of Health into Knowledge Graphs re-weights edges to multi-valued social-determinant nodes for link prediction. It is still a single-step, non-text setting.

The multi-hop systems we build on are GNN-RAG and Chain-of-Decomposition (CoD). GNN-RAG serializes the shortest paths to candidates found by a graph neural network. CoD retrieves with T5, reformulates with templates, and verifies paths with a 7B model. Both choose and order evidence only by topology or relevance, and neither reports per-group accuracy. Our method changes their retrieval stage and leaves the reasoning stage untouched.

The method itself comes from the literature on fairness beyond two groups. Beyond Adult and COMPAS (FairProjection) and Multi-Output Distributional Fairness via Post-Processing (TAB) both argue that pairwise parity across K groups and M classes blows up as O(K²M) constraints. Instead, they project every group toward a common target. Fair Risk Control does this iteratively over overlapping and nested groups, with near-zero utility cost (cross-entropy 9.9291 vs. 9.9285 on WikiText-2). We reuse that iterative scheme, known as multicalibration. The difference is that we apply it to a new quantity: the probability that the gold evidence is included in the context. Those papers apply it to the final prediction. FairProjection itself warns that post-processing depends on a reasonably accurate base model. We read that warning as the reason to intervene upstream.

Research Program

The first step is diagnostic. For each question with a gold reasoning path, we record whether any gold path survives into the serialized context at budget B. We split each accuracy gap into two terms. The first is the difference in gold-path recall between groups. The second is the difference in accuracy given that the gold path was included. This decomposition is the pivot of the whole proposal. If the second term dominates, the retrieval-stage method is the wrong tool and we would pursue answer-level calibration instead.

The second step is the intervention. Let $s(p)$ be the retriever's score for candidate path $p$ on question $q$. Let $g(q)$ be the set of groups $q$ belongs to, determined by the topic entity's attributes and degree bin. Groups overlap, for example nationality × gender × degree bin. We keep the top paths under the adjusted score

$$\tilde s(p) = s(p) + \sum_{k \in g(q)} \lambda_k ,$$

where $\lambda_k$ is a learned offset for group $k$. On a development split we fit the offsets iteratively, in the style of Fair Risk Control, so that for every group $k$ the gold-path recall satisfies

$$\left| \Pr[\text{gold path in context} \mid k] - \bar r \right| \le \epsilon ,$$

where $\bar r$ is the population-average recall at the same average token budget and $\epsilon$ is a tolerance. There is one offset and one constraint per group, not one per pair. The budget is shared, so no extra tokens are spent on average. The offsets reallocate tokens toward questions whose groups are under-recalled.

The third step targets position rather than inclusion. In the linearized context, we order paths by adjusted relevance and relabel entities by rank inside the retrieved subgraph, not by global degree. This tests whether ordering creates a second gap beyond inclusion, in line with the order sensitivity documented by Graph Linearization Methods.

The group annotations do not exist yet and must be built. For WebQSP and ComplexWebQuestions (CWQ), both over Freebase, we select questions whose topic entity is a person or organization. We attach multi-valued attributes from the knowledge graph, such as nationality (collapsed to world regions), gender (all recorded values), and ethnicity where present, along with quantile bins of entity degree. Groups with too few questions are merged or reported with confidence intervals. Small subgroups are the known failure point of multi-group guarantees, according to FairProjection.

Baselines

The naive reference point is shortest-path retrieval truncated at budget B, serialized in retrieval order, with no group information. This shows the size of the gap in an unmodified pipeline.

The strongest existing method is CoD. It reports 77.42% Hits@1 on CWQ and 86.54% on WebQSP with Llama-2 7B, and its ablation shows a 14.33% drop without path verbalization. We will run CoD's released pipeline on our annotated subsets with the same 7B verifier. We will insert our offsets only into its T5 retrieval ranking and hold the verifier, templates, and average token count fixed. The second strong baseline is GNN-RAG, which reports a 62.8% Hit rate on CWQ with a 7B model. It gets the same treatment on its shortest-path extraction. Beating these baselines means reducing worst-group Hits@1 gap and raising worst-group Hits@1 by amounts outside bootstrap confidence intervals, while overall Hits@1 stays within one point of the reported and reproduced numbers. We will report our reproduced numbers next to the cited ones. The per-group numbers are new, and the file contains no reported per-group result for either system.

The key competing correction is post-hoc calibration of the final answer scores with FairProjection and with Fair Risk Control. We apply it to the same pipeline's candidate scores over the same groups and give it the same development split and the same tuning budget for its tolerance parameter. We also run a pairwise demographic-parity penalty on the retriever's ranking scores, trained with the same compute, to test the claim that O(K²) constraints degrade utility at our K.

Three ablations isolate the ingredients. The first uses the offsets without the reordering. The second uses the reordering without the offsets. The third replaces the multi-valued groups with degree bins only. That last ablation tells us whether "fairness" here is just degree correction in disguise, which would be a useful and honest finding either way.

Why not just…?

Why not just calibrate the final answer scores post hoc? This is the real threat. On WikiText-2, Fair Risk Control closed disparity gaps at essentially zero cost, so if the gap is a verification gap, this is simpler and probably better. It has a structural limit, though. If the gold path never reached the model, rescoring candidates can only lower accuracy for the advantaged groups, not raise it for the disadvantaged ones. FairProjection's own dependence on the quality of the base model points the same way. The recall and verification decomposition in the first step settles which regime we are in. We will also report whether each method narrows gaps by lifting the worst group or by lowering the best.

Why not just prompt the model to be fair? Prompting cannot change which evidence was retrieved. UltRAG shows that language models are poor at executing graph traversals themselves, and Graph Linearization Methods shows that serialization order affects results in ways instructions do not undo. We still include a fairness-instructed prompt on the naive pipeline as a cheap control.

Why not just enlarge the context budget or shuffle the order? If every gold path fits, the inclusion gap disappears by construction. For that reason, we sweep B and report the budget at which the naive gap closes. If that budget is small, our method matters only in a narrow regime, and we will say so. Real graphs saturate context windows, as Graph Linearization Methods notes, so a fixed budget is the practical case. Random shuffling is included as an ordering ablation. It may remove positional bias, but it cannot address inclusion.

Proposed Experiments

Before touching real data, a controlled study on GraphQA-style synthetic graphs plants a K-valued attribute and varies how strongly it correlates with degree. This should show whether the gap grows with that correlation under degree-ordered linearization and whether the offsets remove it. We then run the main study on annotated CWQ and WebQSP subsets with Llama-2 7B for both CoD and GNN-RAG. We report overall Hits@1, worst-group Hits@1, the maximum gap across groups, per-group gold-path recall, and tokens per question. For the budget sweep, MetaQA-3 serves as a degree-bin-only transfer check, since it has no demographic attributes. emrKBQA offers a small clinical probe with patient-level groups, and we treat it as exploratory because it covers only 100 patients.

Three results decide the outcome. First, the recall term must account for most of the naive gap on CWQ. Second, the offset method must beat answer-score calibration on worst-group Hits@1 at equal overall Hits@1. Third, the gain must survive when groups are restricted to multi-valued attributes with degree controlled for. If the first check fails, we abandon retrieval-side correction and study answer-level multicalibration of path verifiers instead.