Edge Order as a Hidden Bias Knob in Graph-Grounded Dialogue

Dialogue systems increasingly receive structured facts about the user, such as a small knowledge graph saying the user is a nurse, from Syria, studied at a given university, and is worried about a job interview. Before a language model can read such a graph, the graph must be flattened into a sequence of tokens. This step is called graph linearization. Many orderings encode the same graph, and prior work shows that the choice of ordering changes how well models reason about structure. This proposal asks a question nobody has tested: does the order in which demographic facts are serialized change how stereotyped the model's reply is, even when the content of the graph and the requested conversational strategy are held fixed? If the answer is yes, the flattening step is an uncontrolled source of bias in every graph-grounded assistant, and it is also a cheap place to intervene.

The setting is intent-conditioned generation. Here the model is first given an explicit communicative act, such as a strategy token like [Providing Suggestions] or [Affirmation], and then writes a reply that carries out that act. This setting makes the question sharp. The intent fixes what the reply should do, so any systematic difference in how it is phrased across users who differ only in gender or nationality is bias inherited from the model, not a legitimate response to the task. The core claim is that demographic influence on the reply depends on where demographic edges sit in the serialized sequence relative to the intent token and the start of the reply. We expect this dependence to be mediated by a small number of early layers. If so, an ordering rule derived from that mechanism should reduce bias more than averaging over random orderings, and should keep task fidelity better than deleting demographic attributes.

What is known and what is missing

Three findings motivate the work. Graph Linearization Methods for Reasoning on Graphs with Large Language Models orders edges by centrality and relabels nodes by structural rank. It reports roughly a 35% gain over random ordering on maximum-degree estimation in GraphQA with LLaMA-3-8B, which shows that order is not neutral to the model. Canonical Tree Cover Neural Networks shows that sequence canonicalization stretches graph distances, with a maximum stretch of about 170x on protein graphs. Graph neighbors end up far apart in the sequence, and unrelated nodes end up adjacent. Neither paper measures social bias. In a person-centric graph, though, a degree-based ordering places the person hub and its attribute edges first by construction, and the distortion places attributes next to arbitrary content.

On the bias side, Probing Social Bias in Labor Market Text Generation by ChatGPT shows that gendered input skews are amplified into masculine-coded output, with correlations up to 0.77 and a drop in lexical variance. It measures this from outside the model with a masked-language-model scorer (PRISM) and never varies how the input is structured. FairBelief finds harmful completions at the top of the probability distribution, not in its tail. That finding constrains us: decoding tweaks such as temperature are unlikely to fix the problem, so the fix has to act on the input or on internal computation. Uncovering Stereotypes in Large Language Models reports that refusal falls (ChatGPT from 32.8% to 29.4%) and stereotyped choices rise as task complexity increases. This creates a tension we test directly. Intent-conditioning papers such as Towards Emotional Support Dialog Systems and Counterspeeches up my sleeve! treat the intent token as a filter that steers generation. The complexity result predicts the opposite: a large serialized graph plus an intent taxonomy may be exactly the load under which stereotypes break through. QUARC, the counterspeech system, targets explicit hate and never audits subtler demographic drift. Rethinking the Alignment of Psychotherapy Dialogue Generation inspects only attention to the strategy token.

For mechanism, we reuse methods from two papers. Investigating Layer Importance in Large Language Models finds that a few early "cornerstone" layers in LLaMA-3-8B carry most of the function: ablating one costs 29.3% average accuracy, while other layers cost less than 1.6%. Unveiling Knowledge Utilization Mechanisms in LLM-based RAG shows that context-specific neurons can be found and switched off. Both studied single-answer tasks, not demographic influence in free-form replies.

Core Claim

Hold three things fixed: the graph's content $G$, the intent $i$, and the dialogue context. Vary only the serialization order $\pi$ and the value of one demographic attribute, $a$ versus its counterfactual $b$. We define the counterfactual bias gap as

$$\Delta(\pi) = \mathbb{E}\big[s(y \mid G_a, \pi, i)\big] - \mathbb{E}\big[s(y \mid G_b, \pi, i)\big],$$

where $y$ is the sampled reply and $s$ is a stereotype score on the reply. The score is either the PRISM-style gendered-language score or a nationality-polarity score in the style of the LLM Stereotype Index. The claim has three parts. First, $\Delta(\pi)$ varies substantially across orderings with identical content. Second, the variation is predicted by the token distance between demographic edges and the intent token, and by whether demographic tokens become sequence-adjacent to evaluative attributes. Third, this influence enters the reply positions through identifiable early layers, which tells us how to build an ordering that minimizes $|\Delta|$ without removing information.

Research Program

We build person-centric profile graphs attached to real dialogues. For ESConv, each help-seeker receives a profile graph with roughly five to forty edges. The graph includes a demographic attribute (gender, or nationality drawn from the LSI country set), occupation, institution, and situation-relevant facts extracted from the dialogue. For LinkedIn/BIOS job-letter generation, we use the same construction around the applicant. Each graph appears in matched pairs that differ only in the demographic value. Each pair is serialized under several orderings: random, degree/PageRank with rank relabeling following Xypolopoulos et al., core-number ordering, BFS structured documents in the style of Link2Doc from Link Prediction on Textual Edge Graphs, and a prose paragraph. We also apply controlled manipulations that move demographic edges to the start, the middle, or the end of the sequence, or next to evaluative attributes. Graph size is the complexity axis.

The models are LLaMA-3-8B and Qwen-2.5-7B, the families used in the linearization study, plus LLaMA-3-70B as a scale check. Each is run in two regimes. In the first, the strategy token is supplied in the prompt. In the second, the model is fine-tuned jointly to predict the strategy and then the reply, as in the Joint model of Liu et al.

The mechanistic stage uses layerwise activation patching. We copy hidden states at demographic-token positions from the $G_b$ run into the $G_a$ run one layer at a time and measure how much of $\Delta$ is removed. Separately, we train linear probes at reply positions to read out the demographic attribute layer by layer. The question is whether the patching effect concentrates in the early cornerstone layers, and whether moving demographic edges in the sequence changes which layers carry the effect. Moving them closer to the intent token is our candidate route for "taking over" the realization of the intent. From the patching map we derive a mechanism-guided ordering. Task-relevant situational edges stay adjacent to the intent token. Demographic edges sit at the position that minimizes measured transfer, with a structural separator, rather than being deleted.

Baselines

The naive reference point is random edge order, which is what most graph-to-prompt pipelines do implicitly. It sets the bias gap and task fidelity that every intervention must improve on.

The strongest existing linearization is centrality ordering with node relabeling from Graph Linearization Methods. It is the best-documented way to make a model read structure well. The file gives no bias result for it. Its reported number is the roughly 35% gain on GraphQA maximum-degree accuracy for LLaMA-3-8B over random ordering. We run it on identical graphs with identical sampling settings. Our ordering beats it only if it lowers $|\Delta|$ with non-overlapping bootstrap intervals and keeps strategy adherence within two points.

Permutation averaging generates replies under $k$ random orders and selects or averages among them. It is the cheapest generic fix for order sensitivity. We give it the same total sampling budget as our method plus $k$ times more, with $k$ up to 8. Our method beats it if its gap is lower at equal or lower compute, which is what we would expect if order produces a systematic shift and not just noise.

Attribute blinding deletes demographic edges entirely. It is the strongest bias remover by construction, so it is judged on what it costs: response faithfulness to profile facts (human-rated), and strategy adherence. Faithfulness matters because demographic facts are sometimes legitimately relevant. For instance, a nationality can bear on visa advice in job contexts.

The Link2Doc-style BFS document and the prose paragraph test whether any structured or natural format already avoids the effect.

For intent-conditioning fidelity, we use the best numbers in the file. QUARC reports 70% intent category accuracy on IntentCONAN against 39% for GPS Counterspeeches up my sleeve!. GPT-4 reaches 63.6% strategy-prediction accuracy on AnnoMI Rethinking the Alignment. These anchor what acceptable adherence looks like. There is no reported result on Lacuna for demographic bias under graph linearization, so the bias comparisons are new measurements.

Two ablations isolate the key ingredient. The first removes the intent token, or replaces it with a free-form system instruction. This shows whether the order effect depends on intent conditioning. The second keeps our ordering's positions but randomizes which layer-derived rule chose them. This shows whether the mechanism adds anything beyond "put demographics last."

Why not just…?

Why not just delete demographic attributes from the graph? This is a real threat whenever the attributes are irrelevant, and we will report it honestly as the bias floor. It fails in two ways we can measure. Proxies such as institution and country of study remain in the graph, and we test whether blinded graphs still produce a gap when only proxies differ. Some replies also need the attribute. The faithfulness ratings will show whether blinding costs task quality that our ordering retains. If blinding matches our method on both bias and faithfulness, the conclusion is that ordering is irrelevant once attributes are removed, and we will state that.

Why not just use plain text instead of a graph? Prose is also a linear order, so the same question applies to it. The prose condition is included as a baseline. If prose shows no order sensitivity while serialized graphs do, the problem lies in graph serialization specifically, and that is a useful finding in itself. The evidence from Link2Doc and from entity-disambiguation work in the file suggests that structured context carries information that prose loses, so prose is not free.

Why not just average over random orderings? If the order effect were pure variance, averaging would remove it and our method would be unnecessary. That outcome is plausible, and the permutation-averaging baseline tests it directly. Our bet is that position produces a systematic shift. For example, demographics placed first may act like a primacy anchor for the hub node under centrality orderings. Under a systematic shift, the average over orderings sits at the mean bias level and not the minimum. If averaging matches our ordering, we drop the mitigation claim and keep the diagnostic one.

Why not just add a "be unbiased" system prompt? FairBelief's finding that stereotypes occupy the top of the distribution, together with the falling refusal rates under complexity in the LSI study, suggests that surface instructions weaken exactly in the large-graph regime we study. We include this prompt as a baseline across graph sizes, so the experiments show directly whether it holds up as complexity grows.

Decisive Checks

The first check falsifies the premise. On matched ESConv and BIOS pairs, we test whether the variance of $\Delta(\pi)$ across orderings with identical content exceeds the variance across reseeded samples at a fixed ordering. We use a permutation test over at least 2,000 pairs per attribute. A null result ends the mitigation thread and is published as evidence that serialization order does not drive bias.

The second check tests the complexity tension. It measures how $\Delta$ and strategy adherence change with graph size, with and without the intent token. A rising gap with size under intent conditioning would show that the intent token does not filter out stereotypes under load.

The third check is mechanistic. It asks whether layerwise patching concentrates the gap in a few early layers, and whether relocating demographic edges shifts the patching profile in the way the ordering rule assumes.

The fourth check is the head-to-head comparison against centrality ordering, permutation averaging, and blinding. Outcomes are the PRISM-style gap (scored with the BIOS-validated scorer, reported AUC 0.97 and expert Spearman 0.85), lexical variance as in Ding's variance-compression finding, HONEST hurtfulness on profile-conditioned completions, strategy adherence measured by a classifier trained on ESConv and AnnoMI labels, and human faithfulness ratings. All are measured at matched compute and with a matched tuning budget for any learned component.