Uncertainty-Aware Reasoning over LLM-Generated Scene Graphs for Language-Guided Search

Abstract

Large language models can extract scene-graph triplets from text, but repeated sampling under stochastic decoding yields inconsistent relations. This thesis treats those outputs as samples from a belief over edges: K runs are aggregated into empirical edge probabilities, with edge- and graph-level Shannon entropy and explicit predicate disagreement on subject–object pairs that admit competing predicates. On a fixed caption set, higher sampling temperature increases relational uncertainty in a structured way. The main empirical finding is decision-level: on predicate-disagreement instances, language-guided search is simulated under identical replanning dynamics. What is new is coupling that entropy to probe order on top of a fixed empirical triplet belief; what is shown is that the two policies (greedy baseline and uncertainty-aware) then diverge in visit order and in steps to a known ground truth, with nontrivial asymmetry in paired step counts while greedy wins on step count only twice in aggregate across temperatures, so relational uncertainty changes simulated decisions under identical beliefs, not only scalar summaries of spread.