When Can Language Models Join Without Relation Names? Unique-Path Traversal versus End-to-End Accuracy under Path Ambiguity
Abstract
OIR is the test: relation words such as “works at” are replaced by codes, and the model is not given a dictionary. ARM is a one-line header in the prompt that names the condition, for example OPAQUE_AMBIG. Named-arm keeps that header and a readable id. Hashed-id keeps the header and replaces the id with a hash. No-ARM deletes the header.
Context
is the graph in the prompt. Gold is the correct city. Decoy is the city on the added second path. UNKNOWN is the reply when the model does not choose a city. We ask whether 2-hop answering over small labeled graphs needs readable relation names, or only equality among identifiers. Opaque isomorphic reasoning (OIR) replaces relation strings with keyed opaque tokens, withholds a legend, and scores the answer node rather than an emitted (r1, r2). A named-arm prompt names the condition in a one-line ARM header and uses readable case ids; hashed-id packing keeps that ARM line and hashes the ids; no-ARM packing drops the header. Unique sealed routes—one 2-hop from a start already in the question—still execute (OpenAI unique English/opaque 200/200; hashed-id no-ARM 200/200 at 512 tokens; opaque unique 32/32; both-opaque unique 32/32 on three families). When two complete same-type 2-hops compete and no hop is written, a CONTEXT-only instruction makes UNKNOWN the appropriate reply:
Context
gives no explicit cue for one city. Named-arm OpenAI usually yields that reply, not the decoy: 38/200 gold, UNKNOWN 151, decoy 11. English two-path is 199/200 under the same instruction, so the format does not force abstention when names identify a route. Packaging reduces abstention on those same two-path graphs, not a packaging-free opacity law (UNKNOWN 151→44 with hashed case ids, ARM line kept, gold 134/200, decoy 20; UNKNOWN 5 with the header dropped at 4096/medium). Dropping the header, at 4096 tokens and reasoning effort medium, is a two-path cell (unique-path was not run at that budget): cyclic-decoy English two-path is 197/200 and opaque two-path is 174/200. Entity names stay English and we score the answer node, not (r1, r2), so two-path exact-match cannot be attributed to a join over
Context
English relation names restore OpenAI with anonymous entities (opaque-entity two-path 32/32 vs. both-opaque 1/32). HMAC-SHA256 is one generator of that renaming on each instance's finite atom set, not a cryptographic or privacy primitive. On the primary 2×2, seals hide relation strings; entity names remain. They are not a confidentiality proof.