Graph-Based Inference for Feedback-Driven Word Deduction: A Scalable Framework for the Jotto Problem

Dakshi Arora; Prakhar Kumar Srivastava; Ranjib Banerjee

cs.CLSep 8, 2026

Graph-Based Inference for Feedback-Driven Word Deduction: A Scalable Framework for the Jotto Problem

Authors: Dakshi Arora, Prakhar Kumar Srivastava, Ranjib Banerjee

Abstract

A feedback-based word deduction framework based on the Jotto problem is proposed, and the problem space is represented as a weighted graph where all valid words correspond to nodes, and the edge weight is defined by the number of common letters between the two words. Finally, the gameplay is defined as an iterative constraint propagation mechanism where feedback is used to iteratively narrow the incompatible space of the graph, facilitating the reduction of the hypothesis space in a structured and interpretable manner. In contrast to existing approaches, where the problem space is typically defined for fixed-length isograms, the proposed framework generalizes to variable-length words (between 3 and 8 letters) and naturally extends to repeated letter cases, facilitating the treatment of realistic Jotto problem instances within a unified framework for the first time. The proposed framework's applicability and solver dynamics are also discussed through an interactive implementation and a qualitative case study, respectively. Significant automated tests on approximately 3,000 simulated gameplay scenarios identify a novel convergence behavior: the expected number of iterations diminishes with increasing word length. A strong relationship is confirmed using statistical tests to verify a logarithmic relationship, which is also verified using regression modeling and goodness-of-fit tests. In addition to the initial problem statement, this formulation introduces graph pruning as a viable paradigm for feedback-driven inference with interpretability and its association with symbolic reasoning and interactive intelligent systems.

Figures & tables

Word Length	All Words	Unique Letter Words
3	1295	1176
4	4995	3836
5	9972	6373
6	17464	8077
7	15832	7882
8	23768	6074

Table 1: Dictionary size based on word length and character uniqueness

Figure 1: Schematic overview of the proposed graph-based inference workflow.

Figure 2: Average number of iterations required to identify the target word as a function of word length. A clear decreasing trend is observed, indicating faster convergence for longer words.

Model	Regression Equation
Linear	$y=-1.014x+13.995$
Exponential	$y=16.170\,e^{-0.123x}$
Logarithmic	$y=-5.253\,\ln(x)+17.094$
Quadratic	$y=0.089x^{2}-1.996x+16.436$

Table 2: Analytical expressions of the fitted regression models (parameters rounded to three decimal places).

Model	$R^{2}$	SSE	$\chi^{2}$	AIC
Linear	0.962	0.705	0.072	8.177
Exponential	0.978	0.411	0.044	4.941
Logarithmic	0.984	0.295	0.035	2.946
Quadratic	0.978	0.407	0.047	6.885

Table 3: Comparison of regression models using goodness-of-fit metrics. The logarithmic model provides the best overall fit across all evaluation criteria.

Figure 3: Comparison of fitted regression models showing the relationship between word length and average iteration count. The logarithmic model provides the closest agreement with empirical observations.

Figure 4: Representative lexical overlap network with approximately $\sim 700$ nodes. Nodes correspond to valid four-letter English words, while edges encode shared-letter relationships. Only edges with at least two shared letters are shown for visual clarity.

Figure 5: Progressive contraction of the candidate network during the final stages of convergence. Only the last five iterations are shown for clarity, illustrating how feedback-driven pruning isolates the target word good .

Iteration	Guess	Feedback a	Graph Nodes
1	fain	0	1549
2	roue	1	860
3	lots	1	393
4	hyle	0	98
5	comb	1	41
6	scud	1	13

Table 4: Iteration-by-iteration suggestions and feedback for the secret word “good”.

Component	Best Case	Expected Case	Worst Case
Feedback evaluation	$O(L)$	$O(L)$	$O(L)$
Candidate filtering	$O(NL)$	$O(NL)$	$O(NL)$
Heuristic selection	$O(1)$	$O(NL)$	$O(N^{2}L)$
Graph construction	$O(N)$	$O(NkL)$	$O(N^{2}L)$
Total runtime	$O(N_{0}L)$	$O(N_{0}L\log N_{0})$	$O(N_{0}^{2}L)$
Space complexity	$O(N)$	$O(N+E)$	$O(N^{2})$

Table 5: Asymptotic complexity profile of the proposed solver. Expected-case bounds reflect adaptive pruning dynamics observed during empirical evaluation.

Constraint Propagation

See all 10 papers

Feb 24, 2026

Graph Property Inference in Small Language Models: Effects of Representation and Reasoning Strategy

Recent progress in language modeling has expanded the range of tasks that can be approached through natural language interfaces, including problems that require structured reasoning. However, it remains unclear how effectively limited-capacity language models can infer formal properties of relational structures when those structures are presented in textual form. We conduct a systematic study of graph-theoretic property inference in small instruction-tuned language models, isolating the roles of input representation and reasoning strategy. Across a diverse set of local and global graph metrics evaluated on three models, we find that small language models fail to achieve reliable graph property estimation: normalized errors consistently exceed the intrinsic dispersion of target properties, and rank correlations remain weak across all configurations. However, the failure is structured rather than uniform. Adjacency-list encodings consistently reduce error and improve ordinal consistency relative to edge-lists, and multi-branch reasoning yields measurable aggregate gains across configurations. These results show that without task-specific fine-tuning or architectural adaptation, graph property inference in pretrained small language models remains fundamentally unreliable, but that representational organization and inference design produce consistent differences. The findings characterize the conditions under which structured inference degrades and identify which design choices yield improvements even under constrained model capacity.

Michal Podstawski

NASK National Research Institute, Warsaw, Poland

Small Language Models

Ask PDF

Aug 22, 2025

PuzzleJAX: A Benchmark for Reasoning and Learning

We introduce PuzzleJAX, a GPU-accelerated puzzle game engine and description language designed to support rapid benchmarking of tree search, reinforcement learning, and LLM reasoning abilities. Unlike existing GPU-accelerated learning environments that provide hard-coded implementations of fixed sets of games, PuzzleJAX allows dynamic compilation of any game expressible in its domain-specific language (DSL). This DSL follows PuzzleScript, which is a popular and accessible online game engine for designing puzzle games. In this paper, we validate in PuzzleJAX several hundred of the thousands of games designed in PuzzleScript by both professional designers and casual creators since its release in 2013, thereby demonstrating PuzzleJAX's coverage of an expansive, expressive, and human-relevant space of tasks. By analyzing the performance of search, learning, and language models on these games, we show that PuzzleJAX can naturally express tasks that are both simple and intuitive to understand, yet often deeply challenging to master, requiring a combination of control, planning, and high-level insight.

Sam Earle, Graham Todd, Yuchen Li +5

New York University · University of Malta · University of the Witwatersrand +1

RL Benchmarks Game-Playing Agents Benchmark Construction Tree Search Algorithmic Reasoning

Ask PDF

Mar 17, 2026

How Clued up are LLMs? Evaluating Multi-Step Deductive Reasoning in a Text-Based Game Environment

Deducing whodunit proves challenging for LLM agents. In this paper, we implement a text-based multi-agent version of the classic board game Clue as a rule-based testbed for evaluating multi-step deductive reasoning, with six agents drawn from GPT-4o-mini and Gemini-2.5-Flash. We further investigate whether fine-tuning on structured logic puzzles transfers to improved in-game reasoning and gameplay. Across 18 simulated games, agents achieve only four correct wins, indicating difficulty in maintaining consistent deductive reasoning over the course of a full game. Additionally, we find that fine-tuning does not reliably improve performance and, in some cases, appears to increase reasoning volume without improving reasoning precision.

Rebecca Ansell, Autumn Toney-Wails

Department of Computer Science, Georgetown University, Washington, DC, USA · Syntheos, Corp; UNU-Merit, Maastricht, NL

Fine-Tuning Language Models LLM Agent Evaluation Fine-Tuning Multi-Agent LLM Systems Game-Playing Agents

Ask PDF

Abstract

Constraint Propagation

Explore similar work

Graph Property Inference in Small Language Models: Effects of Representation and Reasoning Strategy

PuzzleJAX: A Benchmark for Reasoning and Learning

How Clued up are LLMs? Evaluating Multi-Step Deductive Reasoning in a Text-Based Game Environment