Training Turn-by-Turn Verifiers for Dialogue Tutoring Agents: The Curious Case of LLMs as Your Coding Tutors¶

🕒 Published (v1): 2025-02-18 22:13 UTC · Source: Arxiv · Venue: ACL 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

TRAVER (Trace-and-Verify) is an LLM agent workflow for coding tutoring that combines knowledge tracing to model student belief states with a trained turn-by-turn verifier that re-ranks candidate tutor utterances via best-of-$N$ sampling. The authors also introduce DICT, an automatic evaluation protocol using simulated students and code-execution tests as a scalable proxy for human evaluation.

Problem¶

LLM tutoring agents lack two forms of grounding necessary for goal-driven task tutoring: epistemic grounding (estimating what a student already knows) and communicative grounding (adapting utterances to close knowledge gaps and advance task completion). Prior work focused on knowledge delivery (math, language), not complex, open-ended tasks like repository-level coding where progress is hard to measure and tutoring must remain personalized.

Method¶

Knowledge Tracing (KT). Task-specific knowledge $K$ is decomposed into knowledge components $\{\text{KC}_1, \ldots, \text{KC}_K\}$ (reference dependencies + solution steps). At each turn $t$, the tutor LLM explicitly estimates a belief vector $B_t$ over KCs from the dialogue context $C_t$ and prior belief $B_{t-1}$, then generates utterances focused on unmastered KCs.

Turn-by-Turn Verifier. A Mistral-7B model with an additional linear layer is trained to predict a scalar reward $v_t \in [0,1]$ for each candidate utterance. The reward is defined recursively: $$v_t = \max(v_{t-1} + wr_t,\ 0), \quad v_0 = 0$$ where the weighted reward uses a guiding distance $d_t = T - t$: $$wr_t = \frac{1 - v_{t-1}}{d_t + 1}(2o_{s_t} - 1)$$ and $o_{s_t} \in \{0,1\}$ is a binary outcome label (whether turn $t$'s utterance contributed to eventual task success). The verifier is trained with MSE loss over synthesized dialogue data. At inference, $N$ candidate utterances are sampled in parallel and the highest-scoring one is selected.

DICT Evaluation Protocol. Three simulated student levels (low/medium/high prior knowledge) are constructed using Mixtral-8x7B-Instruct (trained only on data up to 2023-09, preventing contamination with post-2023-10 EvoCodeBench tasks). A "God's perspective" LLM dialogue manager decides tutoring termination. Student learning is assessed by a post-test: the student generates code (with cognitive load clipping at $M=60$ words per tutor utterance retained), evaluated by Recall@$k$ and Pass@$k$ on unit tests.

Key Contributions¶

TRAVER workflow: explicit KT-driven utterance generation + trained turn-by-turn verifier as a plug-and-play re-ranker
Guiding-distance-weighted, bounded turn-based reward formulation for training the verifier on dialogue data
DICT: fully automatic, reproducible evaluation harness for tutoring agents using simulated students + code execution
Empirical demonstration of inference-time scaling ($R^2 = 0.983$ linear fit between candidate utterances sampled and pass rate)
Ablation isolating contributions of KT and verifier components independently

Results¶

TRAVER (GPT-4o): Recall $68.8\%$ / Pass $43.7\%$, $\Delta\%_P = 106.5\%$ vs. pre-test baseline
TRAVER (Llama-3.1-70B): Pass $39.3\%$, $\Delta\%_P = 85.7\%$; outperforms vanilla GPT-4o ($38.7\%$ Pass)
vs. TreeInstruct (GPT-4o): TRAVER GPT-4o at $\Delta\%_P = 106.5\%$ vs. $88.1\%$; vs. Self-Refine $91.7\%$
Ablation: removing verifier drops GPT-4o Pass from $43.7\%$ to $39.8\%$ ($\Delta\%_P$ from $106.5\%$ to $88.2\%$); removing KT drops to $41.7\%$ ($97.1\%$)
Inference scaling: pass rate grows linearly with sampled candidates ($y = 0.21x + 35.10$, $R^2 = 0.983$) and log-linearly with inference tokens ($y = 8.42\log_{10}(x) + 2.85$, $R^2 = 0.964$)
Oracle ceiling: $51.9\%$ Pass; TRAVER GPT-4o reaches $43.7\%$

Limitations¶

Verifier trained on synthesized dialogues from vanilla LLMs; distribution shift when deployed with stronger backbone models may reduce reward accuracy
Cognitive load threshold $M = 60$ words is a fixed heuristic with no theoretical grounding
Evaluated solely on repository-level Python tasks (EvoCodeBench); cross-domain generalization is asserted but not tested
DICT relies on LLM-simulated students; correlation with real human learners is unverified beyond the pre-test validation
Significant gap remains between TRAVER and Oracle tutor across all student levels

Relevance to Harnesses / Meta-Harnesses¶

TRAVER is a multi-stage agent harness in the classical sense: it sequences KT (state estimation), utterance generation (LLM call), and verification (trained re-ranker) as discrete, composable pipeline stages, with the verifier functioning as a plug-and-play scoring module. DICT constitutes a meta-harness for evaluation: it orchestrates a student simulator, a dialogue manager, and a code-execution judge into a reproducible automated pipeline—exactly the pattern of wrapping an agent system with an outer control loop for scalable assessment. The inference-time scaling result (best-of-$N$ reranking) directly generalizes the process-reward-model harness pattern from math reasoning to interactive dialogue, making this paper relevant to anyone designing harnesses that interleave generation, scoring, and selection across sequential decision points.