Incremental Sequence Classification with Temporal Consistency
Authors: Lucas Maystre
Gabriel Barello
Tudor Berariu
Aleix Cambray
Rares Dolga
Alvaro Ortega Gonzalez
Andrei Cristian Nica
David Barber
Venue: NeurIPS 2025 spotlight ()
Keywords: sequence classification
temporal-difference learning
Primary area: deep_learning
TL;DR: Inspired by temporal-difference learning, we develop a new loss function that improves accuracy and data efficiency in incremental sequence classification.

Abstract: We address the problem of incremental sequence classification, where predictions are updated as new elements in the sequence are revealed. Drawing on temporal-difference learning from reinforcement learning, we identify a temporal-consistency condition that successive predictions should satisfy. We leverage this condition to develop a novel loss function for training incremental sequence classifiers. Through a concrete example, we demonstrate that optimizing this loss can offer substantial gains in data efficiency. We apply our method to text classification tasks and show that it improves predictive accuracy over competing approaches on several benchmark datasets. We further evaluate our approach on the task of verifying large language model generations for correctness in grade-school math problems. Our results show that models trained with our method are better able to distinguish promising generations from unpromising ones after observing only a few tokens.

Incremental Sequence Classification with Temporal Consistency
Lucas Maystre"
Gabriel Barello UiPath Bellevue, WA, USA
Tudor Berariu UiPath London, UK
Aleix Cambray UiPath London, UK
UiPath London, UK
Rares Dolga
Alvaro Ortega Gonzalez
Andrei Nica UiPath London, UK
David Barber
UiPath & UCL London, UK
UiPath London, UK
UiPath & UCL London, UK
Abstract
We address the problem of incremental sequence classification, where predictions are updated as new elements in the sequence are revealed. Drawing on temporal- difference learning from reinforcement learning, we identify temporaal-cnsiisenncy condition that successive predictions should satisfy. We leverage this condition to develop novel loss function for training incremental sequence classifiers. Through a concrete example, we demonstrate that optimizing this loss can offer substantial gains data efficiency. We apply our method text classification tasks and show that it improves predictive accuracy over competing approaches on several benchmark datasets. We further evaluate our approach on the task verifying large language model generations for correctness in grade-school math problems. Our results show that models trained with our method are better able to distinguish promising generations from unpromising ones after observing only few tokens.
Introduction
Learning to classify a sequence x (I11... .,, .T) into one of K classes is fundamental problem in machine learning 44 16]. this work, we focus on an incremental variant which the sequence revealed element by element, and predictive model must provide predictions at every timestep. As concrete example, consider a movic review, represented as a sequence of tokens.
A touching movie 271
It is full of emotions and wonderful acting 25
IL 24
22
JP
Z8
Z8
29g
210
2111
#12
213
We ask the question: Can we predict the sentiment of this review using only the first two or three tokens? More generally, can we learn predictive model that accurately classifies any prefix a consisting of the first < I" elements of sequence? This problem naturally arises in domains where there is cost associated waiting for the full sequence; healthcare or finance, for example, the cost might be time or opportunity 45 34 Recently, sequence classifiers have also been deployed as verifiers to improve applications of large language models (LLMs), where generating full sequences incurs a non-trivial computational cost g 31.
key property of the incremental classification problem is that any calibrated predictive model should That is, the predictive class distribution given a prefix &g should equal the
be cemporally-onsiistrr expected class distribution given the extended prefix æ<(+1,, where the expectation taken over # We take ad advantage of this temporal-consistengg property to develop novel loss function for training
Corresponding author, e-mail; Tucas@maystre.com
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

incremental classifiers (Section 2)
Our approach shares many parallels with lemporal-differnnce (TD)
learning [77,, an important class of methods in reinforcement learning (RL) [3 Exploiting these parallels, we study a simple sequence model and demonstrate that optimizing our loss function can lead to substantial data-efficiency gains over the standard meximum--lkellhood approach (Section 3
We apply our method to text classification using decoder-only transformers (Section 4). We first evaluate four benchmark datasets and find that models trained with our achieve higher predictive accuracy-both on prefixes and on full sequences. When fine-tuning models of the OPT family [4),, the improvement in predictive performance is comparable increasing the size of the base model by a factor 10. We then explore the emerging application of verifying LLM generations. On GSM8K math word problems [8]. our method yields verifiers that accurately distinguish correct from incorrect generations after observing only few tokens. We illustrate how this enables a more favorable trade-off between answer accuracy and computational cost.
loss
Our approach is inspired by celebrated methods in RI. and is rigorously grounded in theory. It is simple implement, adds negligible computational overhead during training and inference, and improves predictive performance across all the datasets we evaluated. As such, we believe it will be valuable machine-learning practitioners.
1.1 Related work
Early sequence classification [44 45 27 addresses a problem that is distinct but complementary to ours: determining when enough information has been observed to make a reliable prediction. In contrast, focus exclusively what to predict each prefix. Our goal is maximize classifi- cation accuracy across all timesteps, without addressing the decision-makiin aspect. We note that incremental classifiers trained with our method could serve as components in early classification architectures [34] 4
TD learning
leverages temporal-consisterr condition, closely related to ours, to learn value functions in RL. Classical TD learning is concerned with modeling the reward-to-go. a sealar quantity. Our work can be understood extending the core idea underpinning TD learning to the multiclass classification setting. Distributional RL [29 2 shares some algorithmic features, but does not address classification. Cheikhi and Russo 7 recently analyzed the data-efficiency benefits of TD learning, and we build on their results in Section
37
38
3 Beyond scalar values, ideas from TD
learning have also been applied to survival analysis 26
and early event prediction 48
Incremental classifiers have recently been applied verify LLM generations, either during post- training [39 21 or at inference time [8] 47 33. where they are referred to as token-level verifiers [ or suicome-supervised reward models [3 21 Verification is typically framed as a binary classifica- tion problem, with verifiers trained using a cross-entropy loss against the final observed outcome, baseline we refer to as direct cross-entropy (DCE). Some prior work use soft targets, as we do, but these targets are still derived solely from observed outcomes [4 20). A notable exception is Mudgal et al. [3I], who frame verification as a regression problem and learn a token-level value function using TD learning. However, they rely squared loss, which is ill-suited to binary outcomes [18]. Our work bridges this gap by developing a TD-style approach tailored to classification.
2 Direct and lemporally-consistent estimators
In order to introduce our approach to learning incremental sequence classifiers, we shift our perspec- tive slightly. Instead of sequence arbitrary elements, which we have denoted by x = (II,.... "01....,2y) .T) in the introduction, we now consider a sequence of Markov states 8 (81, ST). That is, we assume that the ground-truth distribution p(8,)) y) of states and class label satisfies
p(s St....,, 81) = p(5 8x),
ply St. , 81) p(y 8t),
for any t < T. and for any t < T and any y, respectively. This is not restrictive assumption: By slight abuse of notation, one can write 8; = &ec. and p(8e+1 8t) = p(x++1 ær and trivially satisfy these two Markov properties. The Markov-chain perspective will be useful to relate our developments to temporal-difference learning, and to provide intuition into the statistical benefits of method in Section B

---

Notation and problem setup Let [M] denote the set of consecutive integers 1, I...,.M. M. We are given a dataset of N labelled sequences D = ={s", . y²) n E [N]] where y" E [K], and where different sequences might be of different lengths. We seek to learn probabilistic classifier po st). parametrized by 0, that approximates the ground-truth distribution p(y 8e). We denote by Po 8t)
the K Kidimensional probability vector [Po 8t)
Po(K K 8c and by dy the K K-dimensional
one-hot vector with a in position y..
Direct cross-entropy A natural approach for learning po(y (.)) is to maximize the likelihood of the observed samples from p(y 8e) in the dataset D, or equivalently, to minimize the cross-entropy relative to these samples. Given labeled sequence (s. v), we define the following loss function, which penalizes deviations from the label simultancously across all t T.
(DCE(O; s,y) = -
t=1 Po st) = = H (6 po(- sx)]
(2)
where H[pl[q] = - - Ph: log qu is the cross-entropy function. Given the full dataset D, we find Ofee - arg ming Σn &DCE O; 8n, Mo)
We call this approach direct cross-entropy (DCE), because the target distribution is the observed one-hot class label 6,. In LLM verification applications, this the predominant approach to training
token-level verifiers 88 39 21 41 20].
2.1 A family of lemporally-consisten estimators
Intuitively, a drawback of the direct approach is that, for early states 8, (with < T), the training signal provided by observed label y is noisy. Indeed, the prediction po s;) needs to account for two sources of uncertainty, a) the uncertainty about how the remainder the sequence 8.+1..... 8T will unfold, and b) the uncertainty about the label y given the last state 8T. We make progress by observing that
ply 82)) Ep(ecsslee) le.) (P(y 8(41)),
(4)
for all y and all t < T, an identity that follows from 11 This identity captures a notion of temporal consistency: It states that the class distribution at step equal the class distribution at step + 1 on average. Driven by this observation, we propose the following loss function, which for f. < T penalizes the temporal inconsistency relative to a reference model parametrized by 0':
érc 8, = H(,,) I po sT)] + Σ H [pa 8(+1) p st]]-
(5)
Comparing (2) and (5) carefully, we can think of this cemporal-consistenge (TC) loss as replacing the hard targets 8, by soft targets (- 86+1) capturing the predictive distribution at the next state. Given the full dataset D, we start with random parameters (()), and iteratively solve
((+1)) arg ming Σn (f; ((1) Sn, Vn))
(6)
In Section 3 we study a tractable setting and show that this iteration converges to a fixed point Oic- and that the estimator is consistent, i.e., that (v s.)) + p(y st) as the dataset size N + Dc.
We can extend the identity 44) to multiple steps, capturing the temporal consistency of class dis- tributions across longer time spans (c.f. Appendix A.T) We use this formulate generalized temporal-consisenncy loss
(
v) = ΣT H E po( 1 st)],
2: = 7 -8 (1 ET= xt11 po ((+*),
where À E [o, 1] is a hyperparameter. In this loss function, the target 2; providing the training signal is weighted average of the predictive distributions & steps ahead, with exponentially decreasing weights. The larger À is, the larger the influence of distant states is l In fact, TC-À generalizes both TC (5) and DCE (2) Setting
0 recovers TC, while X = 1 yields DCE. Throughout the paper, refer to any model trained with the TC-À loss with À < 1 as temporally consistent.
We can think of the mean of the geometric distribution a/(1 X) as the effective lookahead, i.e., as "how far" the target looks ahead on average.
3

---

2.2
Connections to temporal-differenee learning
Our approach is inspired by semporal-differens (TD) learning, a key idea in reinforcement learning 28
Quoting [Sutton]s seminal paper, "whereas conventional prediction-leamingg methods assign credit by means of the difference between predicted and actual outcomes, the new methods assign credit by means of the difference between temporally successive predictions." Recasting our developments into the language of reinforcement learning, we can think of the probabilistic classifier we learn state-value function, capturing the eventual final outcome of a trajectory at any given intermediate state. The the value function across successive states. Similarly TD learning, our approach uses the temporal inconsistency of predictions across successive states as the learning signal. Our generalized loss function inspired by the TD(A) family of algorithms.
37
38
condition (4) is form of Bellman equation, relating
key difference is that we consider categorical outcomes and a cross-entropy loss, as opposed to the scalar outcomes and squared loss usually employed in TD learning algorithms. In Section 4 we compare our approach to classical value-estimation methods from RI., by treating our K-waa classification problem as K separate value estimation problems.
3 Convergence, consistency and data efficiency
In this section, analyze the DCE and TC estimators in problems with finite number of states. We consider tabular models, where a separate probability is learned for each state-class pair. This tractable setting enables theoretical comparison of the properties of DCE and TC. Specifically, show that a) the TC optimization procedure in (6) converges and b) yields a consistent estimator of the true class probabilities, and that c) the TC estimator is more data-efficient than DCE. Complete proofs of all propositions are provided in Appendix A.2 Our perspective in this section is partly inspired by dynamic programming and its application stochastic shortest path problems, as presented in Bertsekas and Tsitsiklis [3 Sec. 2.2].
In the sinite-state case, formalize the problem of multiclass sequence classification that of finding the absorption probabilities of Markov chain on M transient states and K absorbing states 32 The transient states correspond to M distinct values each element of the sequence
take,
and the absorbing states correspond to classes. The Markov chain is fully characterized by the pair (Q, R). where the M M matrix Q describes the transition probabilities between every pair of transient states, and the M x K matrix R describes the transition probabilities from transient to absorbing states. We assume that is possible reach terminal state from any transient state within a finite number of steps. That is, for any transient state m, there is a 2 0 such that [Q' R) > 0 for some k. Our goal is to estimate the absorption probabilities PT p(y organized into the M x K matrix P*
st = m) from data,
Before addressing the estimation problem, note that if the ground-truth transition matrices Q and R are known, P can be computed by starting from an initial guess Po and refining it iteratively as
P QP, + R.
(8)
Proposition 1. For any M x K row-stochastic Po. the fixed-point iteration converges to P
Now consider the setting where, instead of access to Q and R, we are given a dataset D ((s", y²) [N] of trajectories sampled from the Markov chain. Each trajectory is composed of transient sequence s" and terminates in an absorbing state y". We explore two approaches to estimating the absorption probabilities.
Direct estimation We can estimate the absorption probabilities directly, as the empirical fraction of sequences passing through ending in k. Denoting by T(s) the length of sequence and letting D' = UED Uist(e) {(t,,)) y)} be the union all pairs of transient state and eventual absorbing state in D, we have
Puli = ( (y=k) | == |=m],
where (5. D' denotes uniform sampling on D'. We collect these estimates into the matrix pdir

---

10a2
10-3
theory
10
DCE
TC
10 10
10
Figure 1: Left: Markov chain with T layers of W states each, and two absorbing states. Right: Mean- squared error of the direct (DCE) and indirect (TC) estimates for a state in the first layer state as function of W. We set N 20W and report the mean and 95% confidence intervals over 100 runs.
Indirect estimation Alternatively, we can first estimate the matrices Q and R by using the empirical one-hop transition counts. Letting A D Uc<T(s) {ss, st+1)) }} and B (() e (ST(a) ( y))
be the union of all transitions between successive transient states and between transient and absorbing states, respectively, and
AU B, we write
Arm'' E(s,s'>~Ti (~'mm)) = m],
Pink = (1
m...
(9)
We can then plug the estimates Q and Rt into the fixed-point iteration (8). and iterate until convergence. We denote the resulting estimate by pind By Proposition 1 this fixed point corresponds to the exact
absorption probability matrix of the empirical Markov chain (Q, R2), but it is only approximation of the ground-truth the absorption probabilities.
The following proposition relates the TC loss (5) and its iterative optimization procedure (6. intro- duced in Section 2. to the indirect estimator pind we have just derived.
Proposition 2. Let poly = k s. m) = m Then, the TC iterative optimization procedure is equivalent to the fixed-point iteration 8 the empirical Markov chain (Q, R) defined by (
It follows that, in the tabular case, the TC estimator (6) is guaranteed to converge. Furthermore, under mild assumptions the gane-eeng distribution the TC estimator consistent, i.c..
pind P as N Co.
Similarly, can relate the optimization of the DCE loss the direct estimator pdir (see Proposition in Appendix
3.1 Statistical benefits
In general, DCE and TC will not result in the same estimate, i.e., pind j pdir raising the question: Which estimator is better? related work, Cheikhi and Russo (7) study direct and indirect estimators for the state-value function of Markov reward process. They find that, depending on the structure of the Markov reward process, the indirect estimator can be significantly more Bata-efficient than (and is always at least as efficient as) the direct estimator.
revisit of their examples and adapt absorbing Markov chain with T layers of W distinct states each. For any t < T, the probability of transitioning from state at layer to any other state layer t 1 is 1/W. From any state layer T, we transition to one of two absorbing states, 0 and 1, with probability 1/2 each. Given this, it is easy verify that pi,.- 1/2 for any transient state m and any absorbing state k 10. We collect N trajectories of length 7 + 1, sampling the first state uniformly at random, and subsequent states as described previously. The next proposition shows that, for any state in the first layer, the expected squared error of the indirect estimator is W times smaller than that of the direct estimator.
In Figure T
classification setting. We consider
2 Assuming that the initial state distribution and the transition probabilities are such that, for every transient state, there is non-zero probability of it being sampled in the sequence.
5

---

Proposition 3 (Adapted from [7). For any T 2 1 and any state m. in the first layer,
E
Pink) )
[P Pink) N N0 1/W.
We validate this result empirically in Figure (rightt, where we report on numerical simulations using N 20W. In this Markov chain, the indirect estimator is increasingly more data-efficient W increases. Intuitively, the indirect approach acts as a form of regularization, by requiring the solution to satisfy the cemporal-consistene property (4). which arises from the problem's 's Markov structure. The indirect approach benefits from a form of data pooling: By minimizing the inconsistency across successive states instead of regressing the target outcome directly, take advantage of information from other trajectories that originated from different states and crossed paths.
Beyond the tabular setting In the remainder of this paper, move beyond the tabular setting studied above and fine-tune parametric large language models on very large state spaces. The theoretical results developed in this section no longer strictly apply, yet we believe that the underlying intuition remains valuable for interpreting our method's performance on complex, real-world tasks. In text classification, for example, many distinct word sequences result in similar semantic state predictive of the target label. Optimizing for consistency across successive states can therefore improve data efficiency, similarly to the tabular toy example. With temporal consistency, the model implicitly exploits information from sequences that begin differently but reach similar intermediate semantic states, the same data-pooling phenomenon underpinning the gains of the indirect method in Figure
4 Empirical evaluation
In this section, we apply our methodology to text classification with decoder-only transformers. First, in Section 4.1 we evaluate multiple different approaches to training incremental classifiers. We compare the predictive performance of models on four well-known text classification benchmarks. Then, in Section 4.2, we consider a concrete application to verifying LLM generations. We show that an accurate token-level correctness classifier enables solving grade-school math problems computationally more efficiently.
Model architecture & training Decoder-only (i.e., causal) transformers 23 are particularly well-suited to incremental sequence classification. As the tth output of a decoder on an input sequence depends only on the prefix æ<t. we can compute predictions every prefix efficiently, with single forward inference pass. Throughout this section, we model class probabilities as
(- mgge) softmax( (Ah, b);
(10)
where h2 E RRP is the hidden vector at the last layer of transformer at position t, and A E RxD and b R are the parameters of a classification head. We start with a pre-trained language model, and jointly optimize (A, b) well all the parameters of the transformer, which collectively refer to as 0. We make two minor practical adjustments with respect to the optimization procedure outlined in Section [] First, we update the parameters using stochastic gradient updates. Second, average the loss over all prefixes of each sequence, instead of summing them. This means that every sequence contributes the loss equally, irrespective of its length. Appendix B describes the precise training procedure and documents how we select hyperparameters.
4.1 Text classification datasets
We consider four text classification datasets, spanning tasks such movie review sentiment pre- diction (IMDB (25)) and topic classification (OHSUMED [30], NEWSGROUPS [19], AG-NEWS [00). The number of classes K ranges from 2 to 23. We provide summary statisties for all datasets in Appendix B.2 including the number of training and test samples and the distribution of document length. In addition the standard setting, where the goal is to predict the class label given the full sequence x, we are interested in evaluating the performance of classifiers in the incremental setting, where we need make a prediction after observing only prefix æggr consisting of the first tokens.
We fine-tune pre-trained language models from the OPT family [49]. Unless otherwise noted, we report results on the 125 M-parameter version of the family, with hidden size D 768. Our primary

---

Table 1: Predictive performance of incremental text classifiers on four datasets, We report the classification accuracy on 4-token and 16-token prefixes, and on full sequences (all tokens). We highlight the best and second-best performing models.
OHSUMED
NEWSGROUPS
IMDB
AG-NEW3
4
16
all
4
16
all
16
all
16
all
Most frequent
16.0
16.0
16.0
5.3
5.3
5.3
50.0
50.0
50.0
25.0
25.0
25.0
GPT 4o
31.5
54.0
57.5
7.5
11.0
80.4
58.0
67.0
94.3
77.4
87.4
88.3
Filtering
22.1
46.9
46.2
10.4
19.8
72.0
64.1
73.4
92.1
77.9
86.6
87.2
Last token
16.7
45.0
80.6
6.5
9.4
87.9
56.6
68.4
94.7
54.4
78.3
94.8
Specialist
24.5
59.8
80.6
23.6
47.3
87.9
59.8
73.3
94.7
77.8
91.8
94.8
Direct & loss
30.3
65.0
80.4
19.7
29.9
88.3
63.6
74.7
94.3
80.0
92.6
94.7
LSTD(A)
32.7
64.9
78.0
26.2
36.7
87.8
64.6
75,4
94.7
81.1
92.8
94.9
DCE
30.5
65.5
81.1
27.7
40.1
89.0
63.5
74.7
94.4
80.0
92.6
94.8
TC-À (ours)
33.7
68.3
81.8
33.4
44.7
88.5
64.7
75.7
94.9
81.4
93.0
95.0
focus is comparing models trained by using the DCE (2 and TC-X 7 loss functions. Both of these approaches train a single model to classify prefixes of any length (including the full sequence). In addition, we also consider the following baselines and competing methods.
Most frequent A naive baseline that always predicts the most frequent class in the training split.
GPT-4o We design a simple prompt asking GPT-4o (version 2024-08-06 to classify a text, by giving the list of classes, one example for each class, and the text itself. We access GPT-4o through OpenAl's commercial API. Details are provided in Appendix [.22
Filtering We fine-tune a class-conditional language model po y) on the training data, by using a standard next-token prediction task. At test time, we use Bayes' rule to reverse the conditional probability p(y xx) Z -o (æ y)p(y), where p(y) is a prior distribution and = -,, Po(x u)p(v)
Last token Similarly to the DCE loss (2), we minimize the cross-entropy relative to the observed label. But unlike the DCE loss, we include only single cross-entropy term per sequence, corresponding to the prediction based on the hidden vector hy at the last token (i.e., capturing the full sequence). To the best our knowledge, this is the most widespread approach to text classification with decoder-only transformers 43 12 [7].
Specialist This approach is similar to the last token method, but improves upon it by training distinct, specialized model for each prefix length. Instead of full sequences, each model is trained exclusively prefixes of the corresponding length.
Direct & loss This approach is similar DCE but removes the softmax and replaces the cross- entropy loss with a squared loss. This analogous to standard offline Monte Carlo methods for value function estimation in RL (38 Chap. 5].
LSTD(A) The offinn femporal-differenee value estimation method of Bradtke and Barto (5) recently applied to language modelling in Mudgal et al. [31]. This approach is similar to TC-Á, without the softmax and with a squared loss instead of the cross-entropy loss.
For TC-X and LSTD(A), we treat À as hyperparameter. Values for this and for all other hyper- parameters are presented in Appendix B.2 The time it takes to train a TC-À model is virtually indistinguishable (within 1 1%) from that used to train DCE model, confirming that the overhead required to compute the soft targets (z,) in 7 is negligible compared to the cost of LLM forward and backward passes.
In Table [] we report the predictive accuracy of classifiers on hold-out sequences, given prefixes of 4 tokens, 16 tokens, and full sequences. For DCE and TC-À and the corresponding squared-loss methods, we report additional metrics and more prefix lengths the appendix. As expected, the accuracy of every classifier increases as more tokens are available. However, even with only 4 or 16 tokens (often representing a small fraction of the full sequence), some approaches reach non-trivial accuracy.

---

4 tokens
8 tokens
16 tokens
Full sequence
1.0
obsumed: ROC AUC
DCE
0.9
TC-A
0.8
0.7
0.5
125M
350M
1.3B
125M
350M
1.3B
125M
350M
1.3B
125M
350M
1.3B
Predictive performance of OPT models with 125 M, 350 M, and 1.3 B parameters, respec- tively, on the OHIUMMD dataset. report the area under the ROC curve (mean and 95% confidence interval over 10 runs; higher is better).
Figure 2:
We observe that TC-À outperforms DCE and other approaches in all but two cases, where it ranks second. This supports the insights from Section 3.1 incorporating cempora--conssteene function improves predictive performance, even real-world sequences and with large parametric models. Gains are more substantial for short prefixes, but but-buuttt-eeeee perhaps surprisingly surprsingly-optimizzng for temporal-consistency also improves full-sequence classification accuracy. Relatedly, training incremental classifiers is beneficial even when the goal is only to classify full sequences. Indeed, both DCE and TC-À outperform the last-token approach in this setting. This noticed by Cobbe et al. [8] who suggest that including prefixes in the loss provides useful auxiliary signal. Our findings reinforce this observation. Finally, we that the filtering method generally underperforms approaches using classification head, consistent with conventional wisdom that, for classification problems, discriminative models can be more effective than generative models
into the loss
observe that
Cross-entropy vs. squared loss When comparing DCE and TC-À, which use a cross-entropy loss, their squared-loss counterparts (direct loss and LSTD(A), respectively), following. Temporal consistency tends to improves performance regardless of the loss function, especially partial sequences. Models trained with cross-entropy loss perform significantly better than those trained with a squared loss on datasets with many classes (OHSUMED and NEWSGROUPS). For binary three-way classification tasks (IMDB and AG-NEWS), both loss functions yield similar accuracy. However, Figure in in the appendix shows that methods optimizing a squared loss produce noticeably less well-calibrated predictive probabilities.
observe the
Increasing model size Focusing on the OHSUMED dataset and the DCE and TC-À methods, we train OPT models with 125 M, 350 M, and 1.3 B parameters. Figure shows the area under the ROC curve (ROC AUC) for predictions after 4, 8, and 16 tokens, as well as for full sequences. These results offer the following perspective the benefits of temporal consistency: DCE requires model that is approximately 10x larger to match the performance TC-X.
parameter In Figure (left) we show the accuracy of TC-A models trained on OIISUMED with different values X. The setting À = corresponsing to DCE, never optimal, but the best setting depends on the prefix length. When optimizing for full-sequence accuracy, we observe empirically (across four datasets) that performance maximized with an effective lookahead of 5-50 tokens, corresponding values of X between 0.8 and 0.98.
Varying the temporal-consister
Beyond predictive performance We examine the effects optimizing for temporal consistency more closely. Given predictive distributions p, and p:+1 produced after seeing t and t + 1 tokens, respectively. we compute the divergence KL[P(+1] p:]. Figure 3 (right) shows this divergence, averaged of all successive prefixes of all sequences in the test set. This is the quantity that TC-> explicitly optimizes] and unsurprisingly DCE models are significantly less consistent. While we view temporal consistency primarily as means to improve predictive performance, stable and consistent predictions might be valuable their own right, for example in decision-makinn systems [34].
KLLpp+1 [p:]
H pppipllll [ppe] + est, where the constant is independent of pt.

---

Ohsumed: accuracy A
Inconsistency of successive predictions
0.8
0.02
tokens
Accuracy
8 tokons
0.5
16 tokens
0.4
Full seg.
DCE
TC-4
0.3
0.00
0.0
0.5
0.95 0.98
obsumed
newegroups
imdb
ag-news
A
Figure 3: Left: Accuracy of OPT-125M classifiers OHSUMED as function of (mean and 95% CI over 5 runs). Right: Average Kl--divergence between successive predictive distributions (mean and 95% CI 10 runs). Lower values correspond predictive distributions that are more similar across successive time steps.
Evan
mill
meeds
The
1.0
Po Poly xgr)
0.5
0.0
Evan
neoded
10 buy
the watch
He
already hnd
now
moeds
The mnswor
Figure 4: Predicted probability of correctness for two generations of Qwen2.5-0.5B for the prompt David found $12 on the street. He then gave it to his friend Evan who has $1 and needed to buy watch worth $20. How much does Evan still need?
4.2 Language model verification on GSM8K
Next, we consider the problem of using an LLM to solve math word problems. In seminal work, Cobbe al. 8 propose a simple two-step procedure, consisting of sampling N generations from the LLM, and b) scoring them with a verifier model, ultimately selecting the generation with the largest score. This best-of-N approach was shown to significantly increase performance over single generation, at the expense of a larger computational cost (due to sampling N generations). In this setting, incremental verifiers bring substantial benefits: the verifier is able to accurately distinguish between correct and incorrect generations early on, we can focus computational resources on extending only the most promising generations. This idea has recently received significant attention 41
3 20). In this section, we demonstrate that our TC-À approach holds promise for learning better incremental LLM verifiers.
47 39 21
We study GSMSK, dataset of grade-school math problems and their solutions g For our experi- ments, use Qwen2.5-0.5B, pre-trained language model with 0.5 B parameters that known to perform well on GSM8K for its size [46]. We proceed as follows. For each of the 7473 problems in the training set, we sample 32 generations with temperature 0.7. We label each generation based on whether or not the answer extracted from the generation matches the ground-truth solution. For each problem, we keep exactly one correct and one incorrect generation (sampled uniformly at random), resulting in balanced dataset. We then train incremental verifiers by fine-tuning Qwen2.5-0.5B with a classification head, as in (10), using DCE and TC-À (details provided Appendix B.3). Figure illustrates our setup: Given problem, our model predicts the probability, token after token, that generation will eventually produce the correct answer.
Predictive performance For this binary classification task, the ROC AUC metric is particularly relevant, as reflects the probability that model correctly ranks a randomly-selected correct generation higher than an incorrect one [15] Figure 5 (leff) shows the performance of DCE and TC-A

---

Classifier performance
Test-time scaling
X10
0.9
E loss
Greedy
Best of
Best N Boosted
TC-A
0.8
.
Coverage
Boosted
Average #of tokens
ROC AUC
0.8
DCE
Accuracy
+ Majority
2
0.6
0.7
8 16 32
128.56
10a Average of generated tokens
0.45
0.5
0.55
Number of generated tokens
Accuracy
Figure 5: Incremental verification for Qwen2.5-0.5B on GSM8K. Left: The TC-À verifier is better at distinguishing between correct and incorrect generations early Center & right: A better trade-off between accuracy and compute can be obtained by stopping unpromising generations early on.
function of the number of generated tokens. We observe that TC-À significantly outperforms DCE when the number of tokens small. With only tokens, TC-À is almost 70% accurate in distinguishing correct from incorrect generations. Consistent with findings the text classification experiments, on this binary classification task, models trained with a squared loss perform almost identically to those trained with a cross-entropy loss in terms of ROC AUC. However, as shown in Figure in the appendix, they produce significantly worse predictive probabilities.
Application to test-time scaling We illustrate the benefit of accurate early correctness predictions in basic test-time scaling scenario, where trade off answer accuracy against computational cost, measured by the total number of generated tokens. We propose simple modification to the best- of-N method, which we call boosted best-of-N and which is simplistic version of the speculative rejection method recently proposed by Sun et al. [36]. Sample 10 tokens for each of 2/N independent generations, rank them using the TC-À incremental verifier, and continue sampling the remaining tokens for the top-N generations until completion. Finally, apply the verifier again to the N completed generations and select the best one. Figure [ (center & right) shows that our approach compares favorably to vanilla best-of-N and to majority voting 42 For given level of accuracy, the boosted approach requires 23%-339 -3% fewer tokens.
5 Limitations & future work
We have introduced TC-A, a loss function for training incremental sequence classifiers that draws insights from TD learning improve predictive performance. Our empirical results focus text classification with transformers, but our approach is architecture-agnssti any sequence classification problem. Future work could explore its effectiveness multimodal applications, such as predicting task success from video frames in robotics [11] and games [3].
and applicable to
Given limited compute budget, we have prioritized small-scale experiments. This has enabled us to run comprehensive hyperparameter sweeps and to report performance averaged over multiple random seeds, increasing our confidence in the results. Our experiments suggest that TC-À could benefit models at all scales (Figure D However, the effectiveness of temporally-conisstee models larger than 1.3 B parameters has not yet been systematically evaluated. Likewise, while experiments on LLM verification and test-time scaling show promise, further evaluation is needed, particularly in combination with otate-of-the-art approaches such as speculative rejection [36]
methods with
Finally, promising direction future work is applying TC-À to multi-token prediction [35] which
has been shown to improve LLM pre-training [14 22 and accelerate inference (6] Importantly,
calibrated multi-token predictive distributions should satisfy temporal-conssisency condition that
similar to 4) making this natural fit for our approach.
10

---

References
[1] D. Barber. Bayesian Reasoning and Machine Learning. Cambridge University Press, 2012.
[2] M. Bellemare, W. Dabney, and Munos. A distributional perspective on reinforcement learning. In Proceedings of ICML 2017, Sydney, Australia, Aug. 2017.
[3] D. P. Bertsekas and J. N. Tsitsiklis, Neuro-Dynamic Programming. Athena Scientific, 1996.
[4] J. M. Bilski and A. Jastrzebska. CALIMERA: A new early time series classification method. Information Processing & Management, 60(5), 2023.
[5] S. J. Bradtke and A. G. Barto. Linear least-squares algorithms for temporal difference learning. Machine Learning, 22:33-57, 1996.
[6] т. Cai, Y. Li, Z. Geng, H. Peng, J. D. Lee, D. Chen, and T. Dao. Medusa: Simple LLM inference acceleration framework with multiple decoding heads. In Proceedings of ICML 2024, Vienna, Austria, July 2024.
[7] D. Cheikhi and D. Russo. On the statistical benefits of temporal difference learning. In Proceedings of ICMI. 2023, Honolulu, HI, USA, July 2023.
[8] K. Cobbe, V. Kosaraju, et al. Training verifiers to solve math word problems. Preprint, arXiv:2110. 14168 [cs. CL], Oct. 2021.
[9] W. Dabney, M. Rowland, M. Bellemare, and R. Munos. Distributional reinforcement learning with quantile regression. In Proceedings of AAAI 2018, New Orleans, LA, USA, Feb. 2018.
[10] G. M. Del Corso, A. Gulli, and F. Romani. Ranking a stream of news. In Proceedings of WWW 2005, Chiba, Japan, May 2005.
[11] Y. Du, K. Konyushkova, M. Denil, A. Raju, J. Landon, F. Hill, N. de Freitas, and S. Cabi. Lasion-language models as success detectors. In Proceedings of CoLLAs 2023, Montreal, QC, Canada, Aug. 2023.
[12] D. Dukić and J. Snajder. Looking right is sometimes right: Investigating the capabilities of decoder-only LLMs for sequence labeling. In Findings of the Association for Computational Linguistics: ACL 2024, Bangkok, Thailand, Aug. 2024.
[13] I. Fan, G. Wang, Y. Jiang, Mandlekar, Yang, H. Zhu, A. Tang, D.-A. Huang, Zhu, and A. Anandkumar. MineDojo: Building open-ended embodied agents with internet-scale knowledge. In Advances Neural Information Processing Systems 35, New Orleans, LA, USA, Dec. 2022.
[14] F. Gloeckle, B. Y. Idrissi, B. Rozière, D. Lopez-Paz, and G. Synnaeve. Better & faster large language models via multi-token prediction. In Proceedings of ICMI. 2024, Vienna, Austria, July 2024.
[15] J. A. Hanley and B. J. McNeil. The meaning and use of the area under a receiver operating characteristic (ROC) curve. Radiology, 143(1):29-366 1982.
[16] H. Ismail Fawaz, G. Forestier, J. Weber, Idoumghar, and P.-A. Muller. Deep learning for time series classification: a review. Data Mining and Knowledge Discovery, 33(4):917-963, 2019.
[17] S. Kadavath, T. Conerly, et al. Language models (mostly) know what they know. Preprint, arXiv:2200 05221 [C).CL] July 2022.
[18] D. M. Kline and V. L. Berardi. Revisiting squared-error and cross-entropy functions for training neural network classifiers. Neural Computing & Applications, 14:310-318, 2005.
[19] K. Lang. News Weede:::::: Learning to filter netnews. In Proceedings of ICML 1995, Tahoe City, CA, USA, July 1995.
[20] J. H. Lee, J. Y. Yang, B. Heo, D. Han, and K. M. Yoo. Token-supervised value models for enhancing mathematical reasoning capabilities of large language models. Proceedings of ICLR 2025, Singapore, Apr. 2025.
11

---

[21] H. Lightman, V. Kosaraju, Y. Burda, H. Edwards, B. Baker, T. Lee, J. Leike, J. Schulman, I. Sutskever, and K. Cobbe. Let's verify step by step. In Proceedings of ICLR 2024, Vienna, Austria, May 2024.
[22] A. Liu, B. Feng, et al. DeepSeek-V3 technical report. Preprint, arXiv: 19437 [cs.CL), Dec. 2024.
[23] P. J. Liu, M. Salch, E. Pot, B. Goodrich, R. Sepassi, L. Kaiser, and N. Shazeer. Generating Wikipedia by summarizing long sequences. In Proceedings of ICLR 2018, Vancouver, BC, Canada, Apr. 2018.
[24] I. Loshchilov and F. Hutter. Decoupled weight decay regularization. In Proceedings of ICLR 2019, New Orleans, LA, USA, May 2019.
[25] A. L. Maas, R. E. Daly, P. T. Pham, D. Huang, A. Y. Ng, and C. Potts. Learning word vectors for sentiment analysis. In Proceedings of ACI-HLIT 20/1, Portland, Oregon, USA, June 2011.
[26] L. Maystre and D. Russo. femporally-consister survival analysis. In Advances in Neural Information Processing Systems 35, New Orleans, LA, USA, Dec. 2022.
[27] Y. Meier, J. Xu, O. Atan, and M. Van der Schaar. Predicting grades. IEEE Transactions on Signal Processing, 64(4):959-972, 2015.
[28] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller. Playing Atari with deep reinforcement learning. Preprint, arXiv: 1312. 5602 CG], Dec. 2013.
[29] T. Morimura, M. Sugiyama, H. Kashima, H. Hachiya, and T. Tanaka. Parametric return density estimation for reinforcement learning. In Proceedings of UAI 2010, Catalina Island, CA, USA, July 2010.
[30] A. Moschitti and R. Basili. Complex linguistic features for text classification: A comprehensive study. Proceedings of ECIR 2004, Sunderland, UK, Apr. 2004.
[31] Mudgal, J. Lee, et al. Controlled decoding from language models. Proceedings of ICML 2024, Vienna, Austria, July 2024.
[32] J. R. Norris. Markov Chains. Cambridge University Press, 1997.
[33] A. Radford, J. Wu, D. Luan, D. Amodei, and I. Sutskever. Language models are unsupervised multitask learners. Technical report, OpenAI, 2019.
[34] Schäfer and U. Leser. TEASER: Early and accurate time series classification. Data Mining and Knowledge Discovery, 14355:1336-1 1362, 2020.
[35] M. Stern, N. Shazeer, and J. Uszkoreit. Blockwise parallel decoding for deep autoregressive models. In Advances in Neural Information Processing Systems 31, Montreal, QC, Canada, Dec. 2018.
[36] H. Sun, M. Haider, R. Zhang, H. Yang, J. Qiu, M. Yin, M. Wang, P. Bartlett, and A. Zanette. Fast best-of-N decoding via speculative rejection. In Advances in Neural Information Processing Systems 36, Vancouver, BC, Canada, Dec. 2024.
[37] R. S. Sutton. Learning to predict by the methods of temporal differences. Machine Learning, 9 44, 1988.
[38] R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, second edition, 2018
[39] Uesato, N. Kushman, R. Kumar, F. Song, N. Siegel, L. Wang, A. Creswell, G. Irving, and I. Higgins. Solving math word problems with process- and silcome-based feedback. Preprint, arXiv: 2211. 14275 [Cs. Nov. 2022.
[40] M. Vargas Vieyra and P. Frossard. Deep end-to-end survival analysis with temporal consistency. Preprint, arXiv: 2410. 06786 [Cs.LG], Oct. 2024.
2410.06786
12

---

[41] P. Wang, L. Li. Z. Shao, R. Xu, D. Dai, Li, D. Chen, Y. Wu, and Z. Sui. Math-shepherd: Verify and reinforce LLMs step-by-step without human annotations. Preprint, arXiv: 08935 [cs.AI], Dec. 2023.
[42] X. Wang, J. Wei, D. Schuurmans, Q. Le, E. Chi, S. Narang, A. Chowdhery, and D. Zhou. Self-consistency improves chain of thought reasoning in language models. In Proceedings of ICLR 2023, Kigali, Rwanda, July 2023.
[43] Wolf, L. Debut, al. HuggingFace's transformers: State-of-the-art natural language process- ing. In Proceedings of EMNLP 2020: System Demonstrations, virtual event, Oct. 2020.
[44] Z. Xing, J. Pei, and E. Keogh. A brief survey sequence classification. ACM SIGKDD Explorations Newsletter, 1201))40-48, 2010.
[45] Z. Xing, J. Pei, and P. S. Yu. Early classification on time series. Knowledge and Information Systems, 31:105-127, 2012.
[46] A. Yang. B. Yang, et al. Qwen2.5 technical report. Preprint, arXiv: [cs.CL], Dec. 2024.
[47] K. Yang and D. Klein. FUDGE: Controlled text generation with future discriminators. In Proceedings of NAACI. 2021, virtual event, June 2021.
[48] H. Yèche, A. Pace, G. Rätsch, and R. Kuznetsova. Temporal label smoothing for early event prediction. In Proceedings of ICML 2023, Honolulu, HI, USA, July 2023.
[49] S. Zhang, S. Roller, N. Goyal, M. Artetxe, M. Chen, S. Chen, C. Dewan, M. Diab. X. Li, X. V. Lin, al. OPT: Open pre-trained transformer language models. Preprint, arXiv: 2205. 01068 [cs.CL] CL], May 2022.
NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims made in the abstract and in the introduction are supported by the remainder of the paper, and they respect the guidelines outlined below.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Section 3 when developing a theory for our approach, we call out specific assumptions that are likely not satisfied in real-world applications. However, the insights appear to be robust, as supported by the empirical results presented Section Section discusses additional limitations of our work.
Guidelines:
13

---

The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specffication, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Ye]]
Justification: Complete proofs for each of the three propositions presented in Section 3 are provided Appendix[A... [4.2 For space reasons, we were unable to provide proof sketches in the main body, but we made an effort to introduce the theoretical results gradually. in such way that the reader should have an intuitive understanding of why each result holds.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have attempted to document our experiments thoroughly, providing in the appendix many additional details that we deemed out of scope for the main text, such as specific dataset versions, hyperparameter configurations, the model selection procedure, and more. We intend to complement this information with comprehensive code release upon publication.
14

---

Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-sonnee open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All datasets used in our experiments are publicly available, are the pretrained language models we build upon (OPT [49] and Qwen2.5 [46).. We intend to release code with instructions support the reproduction our main experiments upon publication.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /nips.cccpubllcc// wwwpc//gguussseeee http///ooeeeuiiiieeee ssinnoliccy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
15

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All these details are provided in Appendix B
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All plots in the paper include error bars reflecting 95% confidence intervals across multiple random initializations, computed as 1.96 x standard error. Table [ omits error measures for clarity, but the results corresponding the DCE and TC-À rows also shown with error bars in Figure
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: We provide this information in Appendix B
16

---

Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We have reviewed the NeurlPS code of ethics, and we believe our work conforms with it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: Our paper proposes general purpose training method for improving incre- mental sequence classification, without targeting any specific application domain. While we acknowledge that downstream applications of such models may carry societal implications, we do not identify any impacts (positive or negative) that are specific to the contributions of this work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployyen of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
17

---

11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This work does not involve the release of models datasets that present high risk of misuse. As such, no specific safeguards have been put in place.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We use publicly available pretrained models and benchmark datasets in our experiments. We have cited the original sources the paper and have made a reasonable effort to ensure that all assets are used in accordance with their licenses and terms of use.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasete has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does introduce any new assets directly. We plan release code to support reproducibility and will ensure it is adequately documented.
Guidelines:
The answer NA means that the paper does not release new assets.
18

---

Researchers should communicate the details of the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
19

---

A Additional methodological details & proofs
In this appendix, we provide additional details relating the material presented in Sections and
A.1 Generalized lemsoral-consisenney condition
The temporal-consisenng condition abusing notation and setting ST+1
can be extended to k-step transitions as follows. Slightly
8T4 y. and p(y 8t) 1 (u=s.} for / > T, we have
p(u 8e) Ee(e441e 8r++)];
for any y, any and any k. This follows from the Markov properties (I)
A.2 Theoretical results
This sections provides proofs for Propositions 1 and 3 It also introduces an additional result,
Proposition 4 that is the analogue of Proposition 2 for DCE.
For N N-dimensional vector æ, denote the L1 norm || En [2a)- Similarly, for an N M matrix X, we denote the induced co-norm |X||> nth row of X.
max Zn full1. where 2n is the
Proof of Proposition Denote by a the math row of the matrix Q' R. By assumption, we know that there is a N and a 6 > 0 such that ||a || 2 for all m. Let F : R R + M be the linear operator defined by F(P) QP R. We will show that +1+1 is contraction mapping in the induced co-norm, that is.
(P) - FT+1 (P')llo 5 (1-E) P'I
for any two M K stw-stochastic matrices P, P.. By the Banach sked-point theorem, it follows that F admits unique fixed point p p== =limm ((PP)) for any initial Po-
By construction, the matrix U = [ R is row-stochastic, and thus | |ox 1 and || S 1. It follows that QU [Q++1 Q R] such that ||Q -
& |U|oo S Since every row of
Q" has Ln-norm at least e, must be that ||Q++1 1l S
follows that
[ - FT+ lox) = || P') S | b0 |P P'
S (1 c) P P' P'llcc.
Proof of Proposition 2 Consider one step of the TC optimization problem 66. where denote the
tabular model by using the M x K matrix = [0m]] Letting Cm = "(eeetET 1 [s=m] we have
θ (i+1) arg min e
Σ Lre(O, O Snn yrn
arg min
Σ H[,
+
Σ
H s' [0..
(8
(K,6")EA
arg min
Σ Cm
18x
+ Σ
ammm H m
[m
m
k
m
arg min
Σ
Cm (rm + q (0) (:0))
where P. = [mm]] E R and Qm = [@mme] E R.M. and where the last equality uses the linearity of the cross-entropy with respect the target distribution. It follows that the cross-entropy is minimized e (+) + R, which corresponds exactly to (
The Markov chain of Figure has exactly two absorbing states, and the absorption probabilities sum up to 1. As such, we can focus on the variance of the estimator for p We will construct a Markov reward process whose state-value function V(m) is equivalent to the
Proof of Proposition 3
20

---

absorption probability 1 To this end, we collapse the two absorbing states 0 and 1 into a single terminal state denoted by We instantiate the reward distribution as follows. For any transition between two transient states, the reward is always O. For any transition between state at layer T and the absorbing state 2, the reward is with probability 1/2 and zero otherwise.
We can now recast our problem by using the terminology of Cheikhi and Russo transient state m have
7 Sec. 7J. For every
(m) Pm.1
VMC(m) (m)
dir
V TD (m) pmi
We focus on states the first and second layer. Given the sampling process we have defined in the main text, any given state in the second layer will appear in N/W trajectories in expectation, and the transition between any pair of first and second layer states will appear in N N/W² trajectories in expectation. It follows that, for any state m in the first layer and any state m' in the second layer, the coupling coefficient and the inverse trajectory pooling coefficient are given by
C(m, m') = 1/W,
((m) = 1/W;
respectively. We can then apply Theorem 7.2 in Cheikhi and Russo 7 to obtain the desired result.
The next proposition relates the DCE loss 2 and the optimization problem Section to the direct estimator pdir presented in Section
3
introduced in
Proposition 4. Let py le Se m) 6mkk Then, pdir is solution of the DCE optimization problem
Proof. Denote the tabular model by using the M K matrix @ [m]] Letting Cm ((sd))D {s=m}, we have
OCE arg min Σ PIE ④ sn Vn.
arg min θ
H6
(+.9)ED
arg min
Σ Cm Σ Pull H [8 [m
m
arg min
Cy H P [m),
where pdr = [ein E R.K and where the last equality uses the linearity of the cross-entropy with respect to the target distribution. It follows that the cross-entropy is minimized if t piiir
B Additional details on experimental evaluation
This section provides additional details on the experiments presented in the main paper. In Section B.1 describe the precise procedure employ to train and select models. In Section B.2 we provide more details on the text classificiation experiments of Section 4.1 In Section B.3 we provide more details the verification experiments of Section 4.2
B.1 Training, model selection & metrics
Algorithm presents one step of the training loop for the TC-À and DCE approaches. Note that DCE is obtained simply by setting À 1, as explained in Section 2. With respect to the iterative optimization procedure (6). we make two minor practical adjustments. First, we update the parameters using stochastic gradient updates. Second, average the loss over all prefixes of each sequence, instead summing them. This means that every sequence contributes to the loss equally, irrespective of its length.
We run our experiments on an a3-highgpu--gr instance on Google Cloud, with 208 vCPUs, 1872 GB of memory, and 8 NVIDIA H100 GPUs. We ensure that every experiment runs single
21

---

Algorithm TC-À incremental classifier: single training step
Require: minibatch B, parameters 0, temporall-onsiisencyy parameter X, learning rate 7
1: {(0) f
b Initialize the loss function. Iterate over the minibatch.
2: for (z. y) do
3: T f length(@:)
4: ZT t dy
5:
for 1= 1....,1 do
6:
21 t A21+1 + +(1 A)po( xz(+1)
7:
((0) < (() + + H [topgradd (2)) pp( æg))]
8:
return [8] Vol(o)
Update the parameters.
GPU. For every dataset, we set the batch size to maximize GPU utilization. We use the AdamW optimizer (24] with dynamic learning rate. The learning rate starts zero, increases linearly over warmup period, then decreases linearly to zero at the end of the optimization process. We vary the following hyperparameters:
the number of training epochs,
the maximum learning rate,
the warmup period (as ratio of the total number training steps),
the weight decay, and
the temporal-consistency parameter (for TC-X only).
run experiments on grid of hyperparameter configurations, and we select the configuration that maximizes the full-sequence predictive accuracy small dataset of held-out sequences. Finally, throughout section 4 we report the mean and standard deviation the performance of the winning hyperparameter configuration the full test set, across 10 training runs with different random seeds.
We consider three metrics to measure the quality of a model pD x)) on held-out data. The average accuracy is the fraction of examples where arg max, Po (y x:) matches the ground-truth label y* (higher better). The average negative log- likeelkoo (NI..) the empirical average of log pe (y" æ)) (lower is better). The area under the ROC curve (ROC AUC) captures the model's ability to discriminate between a random positive and negative example; In the multiclass setting, we use the one-vs-rest macro-average version. A higher ROC AUC is better.
B.2 Text classification datasets
We evaluate models on the following four well-known text classification benchmarks. Summary statistics and licensing terms for each dataset are provided in Table 2
OHSUMED The dataset contains abstracts of publications in medical journals (30). The task is
to categorize each abstract into one of 23 themes, corresponding to sub-categories of cardiovascular diseases. We use the archive sesumed-all-doo tar. gz available https::/diss //tps///iii...mm/ unitn. wtt.tt..t//oscaitttt/coopopppp htm
NEWSGROUPS The dataset contains newsgroup documents from 20 different newsgroups [19
The task is to identify which newsgroup the document comes from. We the version of the dataset hosted htttps:/huginnfaace.. http:/faaa....aaaaaeeeeeee co/dattets/
google- datasets/neesgroon
IMDB The dataset contains movie reviews from the IMDb website 25
The task consists of identi- fying the sentiment of the review (positive negative). We use the version of the dataset hosted httt:s///haggnngg......oaaaaatte
AG-NEWS
The dataset contains short news articles [10 The task is to identify the topic of each article. use the version of the dataset hosted at https:tpp.... httpp://:////gggaaaeeeeee co/ co/datasets/
fancyzhx/ aewws
22

---

Table 2: Summary statistics for the text classification datasets. Statistics on the sequence length assume that the text is tokenized with the GPT-2 tokenizer [33]
Seq. length percentiles
Dataset
License
Nuain
Neett
K
50th
90th
99th
OHISUMED
CC BY-NC 4.0
11.500
6782
23
270
430
604
NEWSGROUPS
unknown
11.34
7532
20
373
935
4226
IMDB
unknown
25.000
250000
2
221
584
1159
AG-NEWS
unknown
120.000
7600
4
51
70
122
The NEWSGROUPS, IMDB and AG-NEWS datasets are provided with separate train and test splits, which reuse as-is. For OHSUMED, create our train and test splits, by partitioning the data uniformly at random.
We fine-tune pre-trained models from the OPT family 49), which are made publicly available under the OPT-175B license" Table 3 provides the hyperparameter configurations for the fine-tuned OPT- 125M models whose performance we report in Table iin the main text. These hyperparameters are found using the process outlined in Section B.1
T detailed results for DCE, TC-X, and the corresponding squared-loss variants, Direct &g loss and LSTD(A), for prefixes of length 2 i ...... 9, across three metrics. We report the mean and the 95% confidence interval of 10 independent seeds, but the standard error is too small to be visible the plot. On all datasets, the TC-À models outperform the DCE models on almost all metrics at almost all prefix lengths.
Compute resources Each experiment, consisting of training an evaluating a model, takes 5-90 minutes on a single GPU, depending on the dataset, the size of the model, and the number of epochs. We estimate that the total compute used for all the experiments performed in the paper, including the hyperparameter sweeps, amounts to approximately 2000 GPU hours.
B.2.1 GPT-4o baseline
We present the templates used for prompting GPT-4o Figure 7 We use the structured outputs API to ensure that the model always returns exactly one valid class label. For cost reasons, we sample of subset 200 examples uniformly at random from the test set for each dataset and each prefix length (4, 16, and all tokens), and restrict our evaluation to this subset. Approximately 0.7% of requests trigger the ChatGPT filters (mostly the IMDB and NEWSGROUPS datasets). We simply omit the corresponding examples from the evaluation.
'See: LICENSE. md
23

---

Table 3: Hyperparameters used to fine-tune the OPT-125M models reported in the paper.
Dataset
Model
Batch size
Epochs
Max.
Warmup
Weight decay
ohsumed
Filtering
32
2 10
0.03
x 10
Specialist, Specialist, 16
64
5 10
0.10
I x 10 I x 10
64
5 10
0.10
Last token
64
1x10
0.10
I 10
DCE
128
2x
0.10
I 10
TC-À
128
1x 1x
0.10
I 10
0.95
l loss, direct
128
1x
0.10
Ix 10
8 loss, TD-A
128
1x
0.10
I 10
0.95
newsgroups
Filtering Specialist.
4
1x
64
2
2x
0.10
1 10 10
Specialist, Last token
5x
64
4
5x10
0.10
X 10 10
DCE
1x
TC-X
64
1x
0.10
I X 10
0.98
& loss, direct
1x
X 10
& loss, TD-A
64
1x
0.10
X 10T3
0.98
imdb
Filtering
8
50
0.03
I X 10Th
Specialist, Specialist, 16 Last token
8
50
0.10
I X 10
8
2x 10
0.10
X 10
8
2x
0.10
X 10
DCE
8
2x
0.10
X 10
TC-A & loss, direct 8g loss, TD-A
8
1x
0.10
I X 10
0.80
8
2x 10
0.10
X 10
8
10
0.10
I x 10
0.80
ag- news
Filtering
64
2
5 1
0.03
Specialist, Specialist, 16
1 10
0.10
I 10
64
1x
0.10
1 10
token
1x
10
DCE
128
2
1x
0.03
1 10T3
TC-A
1x10
10
0.90
l2 loss, direct
128
2
1x10
0.03
1x 10
6 Joss, TD-A
128
1x
1x
0.90
24

---

Accuracy
AUC
Average NLL
0.8
0.9
obsumed
0.6
0.8
6 loss
0.7
TC-A
DCE
0.6
0.2
1.0
0.8
newsgroups
0.8
2
0.2
0.6
1.0
0.9
0.6
0.8
imdb
0.8
0.7
0.7
0.6
0.6
1.00
1.25
0.9
0.95
1.00
ng:new
0.90
0.75
0.7
0.50
0.85
0.6
0.25
0.80
4
16
64
256
16
64
256
16
64
256
Length of sequence prefix
Length sequence prefix
Length sequence prefix
Figure 6: Detailed results for 0PT-125M models trained with DCE, TC-À. and the corresponding squared-loss variants on the text classification datasets, Accuracy and ROC AUC: higher is better. Average NLL.: lower is better. We report means and 95% confidence intervals over 10 runs (too small to be visible).
25

---

Listing System prompt
Listing 2: Single example
Listing 3: User prompt
You are helpful AI assistant specializing in classifying text. The possible class labels are:
### BEGIN TEXT ### (text)
What is the label of the following text?
### END TEXT label: {label}
### BEGIN TEXT #2# (text)
### END TEXT ###
(class_names)
Here are some examples of text with their corresponding
class labels:
(examples)
Figure 7: Templates used for prompting GPT-4o.
26

---

Table 4: Hyperparameters used to fine-tune the Qwen2.5-0.5B models reported in the paper.
Dataset
Model
Batch size
Epochs
Max. LR
Warmup
Weight decay
GSM8K
DCE
48
2
5 10
0.03
I x 10
TC-À
48
5 10
0.10
x 10
0.95
Direct & loss
48
2
5 10
0.03
1 10
LSTD(A)
48
5 10
0.10
1 10
0.95
Classifier performance
0.8
Average NLL
0.7
0.6
TC-I
0.5
+
DCE
32
64
128
256
Number of generated tokens
Figure 8: Predictive negative log-likelihood of incremental Qwen2.5-0.5B verifiers GSM8K (mean and 95% CI over 10 runs).
B.3 Language model verification on GSM8K
For the language model verification experiments, we use the Qwen2.5-0.5B pre-trained language model [46]. which is publicly available under the Apache 2.0 license. The GSM8K dataset [8] is publicly available under the MIT license. Hyperparameter selection follows the procedure outlined for the text classification experiments in Section B.] with one small change: instead of selecting the best hyperparameter configuration based on the full-sequence accuracy, we select it based on the full-sequence ROC AUC. Table 3 provides the hyperparameter configurations for the fine-tuned the main text.
Qwen2.5-0.51 models whose performance we report Figure 5
In these experiments, there is one important conceptual difference with respect to the text classification experiments of Section The sequence we seek classify consists of the generated tokens only, but the verifier also needs to access the prompt (i.e., the problem statement). We implement this by concatenating the generated response the prompt. However, when computing the loss, we mask out the terms that correspond to tokens in the prompt.
Predictive NLL Figure 5 (left) the main text shows that models trained with squared loss achieve essentially the same ROC AUC as those trained with cross-entropy. Figure & further shows that models trained with cross-entropy loss achieve substantially lower (i.e., better) negative log- likelihood. Thus, when accurate & calibrated predictive uncertainties are important, optimizing the cross-entropy objective performs better in practice.
27


Reviews:
[{"review_id": "hncts3MpcR", "reviewer": "Reviewer_mRRN", "summary": "This paper propose a new loss function, TC-\\lambda, for training incremental sequence classifiers. The authors is inspired by TD learning and propose a method that enforces consistency between prediction distribution between different timestamps. The paper provides some theoretical analysis as well as empirical results on text classification and large language model (LLM) verification tasks.", "questions": "- Is there attempt to anneal the \\lambda throughout the training process?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n- The method is well motivated. The connection between TC-lambda and TD learning is straightforward and easy to intuitive.\n- The authors provide comprehensive empirical evaluation on text classification and LLM verification.\n\nWeaknesses:\n- Given that the model can do verification task, it should be able to serve as a good value function. It would be great if the authors actually use the value function to finetune a LLM.\n- My understanding is the authors originally want to learn an incremental value function for training LLM using RL. So how is TC-lambda different from simply train a value function using TD learning? One might simply use the original TD learning to train such an incremental sequence classification task, but there is no comparison on that in the paper.", "was_revised": true, "final_justification": "The authors well addressed my question on lambda annealing and difference compared to TD-lambda.\nI remain my original rating.", "rebuttal": "Thank you for your review!\n\n> how is TC-lambda different from simply train a value function using TD learning? One might simply use the original TD learning to train such an incremental sequence classification task\n\nThis is a helpful comment, also raised by reviewer `cjdV`. Although all the tasks we consider are naturally framed as classification problems with a binary or a categorical cross-entropy loss, they can indeed also be cast as regression problems with a squared loss. We address this question below in more details, including additional experiments comparing our approach to a standard TD-learning approach.\n\n> Is there attempt to anneal the \\lambda throughout the training process?\n\nWe have not directly experimented with continuous annealing schedules, but we have noticed that the following two-step process (which can be considered as a basic form of annealing) works well:\n\n1. Initialize the classification head by training a linear probe with $\\lambda = 1$.\n2. Unfreeze the language model parameters and fine-tune end-to-end with the desired value of $\\lambda$.\n\nWhile not strictly necessary to achieve good performance, we have noticed that this leads to very stable and robust training runs that converge quickly. This is the approach we have adopted for our experiments.\n\nContinuously annealing lambda during step 2 above is an interesting idea for future work.\n\n# Comparison to least squares methods\n\nIn our paper, we train classifiers with a softmax cross-entropy loss.\nAlternatively, we could frame the classification task as a regression problem (predicting a final scalar reward, which in our case is either $0$ or $1$; in the multiclass case, the $K$ classes can be modeled independently).\nThis regression-based framing naturally suggests using standard value-estimation algorithms from the RL literature, which use a squared loss.\n\nWith this in mind, we ran two additional baselines on the four text classification datasets:\n\n- **Direct squared loss**: regress the final reward directly. This the squared-loss variant of DCE.\n- **LSTD-$\\lambda$**: use temporal-difference learning, specifically the offline version of [1]. This is the squared-loss variant of TC-$\\lambda$.\n\n[1]: S. Bradtke, A. Barto. Linear Least-Squares Algorithms for Temporal Difference Learning. Machine Learning, 1996.\n\nWe compare the predictive performance of these regression baselines on the four text classification datasets of Section 4.1 below.\n\nKey:\n\n- **oh**: ohsumed\n- **ng**: newsgroups\n- **im**: imdb\n- **ag**: ag-news\n\nAccuracy (higher is better):\n\n|                     | oh-4 | oh-16 | oh-full | ng-4 | ng-16 | ng-full | im-4 | im-16 | im-full | ag-4 | ag-16 | ag-full |\n| ------------------- | ---- | ----- | ------- | ---- | ----- | ------- | ---- | ----- | ------- | ---- | ----- | ------- |\n| DCE                 | 30.5 |  65.5 |    81.1 | 27.7 |  40.1 |    **89.0** | 63.5 |  74.7 |    94.4 | 80.0 |  92.6 |    94.8 |\n| TC-$\\lambda$        | **33.7** | **68.3** | **81.8** | **33.4** | **44.7** | 88.5 | **64.7** | **75.7** | **94.9** | **81.4** | **93.0** | **95.0** |\n| Direct squared loss | 30.3 |  65.0 |    80.4 | 19.7 |  29.9 |    88.3 | 63.6 |  74.7 |    94.3 | 80.0 |  92.6 |    94.7 |\n| LSTD-$\\lambda$      | 32.7 |  64.9 |    78.0 | 26.2 |  36.7 |    87.8 | 64.6 |  75.4 |    94.7 | 81.1 |  92.8 |    94.9 |\n\nNegative log-likelihood (lower is better):\n\n|                     | oh-4 | oh-16 | oh-full | ng-4 | ng-16 | ng-full | im-4 | im-16 | im-full | ag-4 | ag-16 | ag-full |\n| ------------------- | ---- | ----- | ------- | ---- | ----- | ------- | ---- | ----- | ------- | ---- | ----- | ------- |\n| DCE                 | 2.428 | 1.241 |  0.663 | 2.783 | **2.538** |  0.616 | 0.626 | 0.497 |  0.155 | 0.545 | 0.226 |  0.158 |\n| TC-$\\lambda$        | **2.365** | **1.162** |  **0.646** | **2.777** | 2.635 |  **0.503** | **0.621** | **0.484** |  **0.138** | **0.510** | **0.209** |  **0.148** |\n| Direct squared loss | 2.964 | 2.636 |  2.485 | 2.845 | 2.741 |  2.209 | 0.632 | 0.545 |  0.369 | 0.958 | 0.829 |  0.804 |\n| LSTD-$\\lambda$      | 2.993 | 2.649 |  2.454 | 2.907 | 2.817 |  2.192 | 0.638 | 0.553 |  0.372 | 0.966 | 0.825 |  0.799 |\n\nTake-aways:\n\n- methods based on the softmax cross-entropy loss outperform methods based on squared-loss\n    - in terms of accuracy, the difference is relatively small\n    - the predictive log-likelihood, however, is very poor for regression models (as can be expected).\n- as could be expected, the difference is larger for problems with many classes (ohsumed, newsgroups)\n- temporally-consistent methods (TC-$\\lambda$, LSTD-$\\lambda$) tend outperform direct methods (DCE, direct squared loss), especially for short prefixes.\n\nIn a way, TC-$\\lambda$ provides the best of both worlds: it leverages the benefits of temporal-difference learning while optimizing a loss function that is arguably better suited for classification."}, {"review_id": "D8y69DUnzg", "reviewer": "Reviewer_C7UX", "summary": "The paper introduces a condition to express consistency between predictions in incremental sequence classification tasks and proposes a corresponding loss function to enforce this property during the training of a parametric model.", "questions": "1. Equation (5) resembles, to me, the typical form of a cost functional in optimal control problems, where the first term corresponds to a terminal cost and the second term resembles the integral of a running cost. However, in line 122, you remark that this equation can be seen as a form of the Bellman equation, suggesting a connection to value functions. Could you please elaborate on this?\n\n2. You mention that the computational overhead introduced by the proposed method is negligible, as training time is nearly indistinguishable from the baseline. However, it would be helpful to quantify this claim more precisely, perhaps by providing a theoretical estimate or reporting empirical runtime differences in a controlled setting.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The manuscript is extremely well written. The problems are clearly introduced and motivated, and all assumptions are adequately discussed.\n\nThe proposed method is analyzed both theoretically—demonstrating convergence and consistency—and experimentally, through evaluations on standard text classification benchmarks and a specific model verification task for LLMs. The experiments are well designed.\n\nIf I understand correctly, the theoretical analysis in Section 3 relies heavily on the assumption of working with tabular data, which does not hold for the experiments presented in Section 4. While one might hope that some desirable properties carry over to the parametric setting, the manuscript does not provide strong reasons or intuitions for why this should be the case.\n\nIn terms of novelty, the idea of enforcing temporal consistency across successive prefixes in a sequence classification task is a meaningful extension of related principles from reinforcement learning into a multiclass classification setting. This, to the best of my knowledge, is an original contribution.\n\nThis work advances the field from a theoretical point of view  by introducing a new temporal-consistency loss. The method is also proven consistent in a tabular setting and shown empirically to improve predictive performance.", "was_revised": true, "final_justification": "I have carefully read the authors’ rebuttal as well as the comments from the other reviewers and the AC. My questions were answered satisfactorily, and I did not find any additional major issues raised by the other reviewers. For these reasons, I maintain my positive score.", "rebuttal": "Thank you for your review!\n\n> If I understand correctly, the theoretical analysis in Section 3 relies heavily on the assumption of working with tabular data, which does not hold for the experiments presented in Section 4. While one might hope that some desirable properties carry over to the parametric setting, the manuscript does not provide strong reasons or intuitions for why this should be the case\n\nWe acknowledge that Section 3.1 does not provide much intuition about what makes our temporal-consistency loss particularly effective on the problem in Figure 1, and how this intuition might carry over in more realistic applications with parametric models. We hope to be able to improve this in the next version of the manuscript, given some additional space.\n\nInformally, temporally-consistent methods (such as TC-$\\lambda$) exploit information from the dynamics of the sequence. For example, in text classification, one could argue that there are many different ways of organizing words into sentences that capture a similar “semantic state” that is predictive of the class label. In this case, encouraging predictions to be consistent across successive states improves data-efficiency: the model is now implicitly leveraging information from sequences that might have started very differently but reached the same intermediate semantic state. (This data-pooling phenomenon is underpinning the improved statistical efficiency of TC-$\\lambda$ over DCE on the problem of Sec. 3.1)\n\n> Equation (5) resembles, to me, the typical form of a cost functional in optimal control problems, where the first term corresponds to a terminal cost and the second term resembles the integral of a running cost. However, in line 122, you remark that this equation can be seen as a form of the Bellman equation, suggesting a connection to value functions. Could you please elaborate on this?\n\nIn our setup, $p_\\theta(\\cdot \\mid s_t)$ plays the role of the value model. Consider the left-hand side (LHS) and right-hand side (RHS) of Equation (4). Equation (5) can be understood as penalizing the KL-divergence of the LHS relative to the RHS, under an empirical Markov model $p(s_{t+1} \\mid s_t)$ given by the data. (Proposition 2 in Sec. 3 makes this precise.)\n\nIt is perhaps helpful to make an analogy to a value model in a Markov reward process with discount factor $\\gamma$. In that case, the Bellman equation is\n\n$$\nV(s_t) = \\mathbb{E}  \\quad_{p(r_{t+1}, s_{t+1} \\mid s_t)} [ r_{t+1} + \\gamma V(s_{t+1})]\n$$\n\nAnd the analogue to our Equation (5) would penalize the squared Bellman error, i.e., the squared difference between the LHS and RHS as\n\n$$\n\\sum_{t=1}^T \\sum_{(s_t, r_{t+1}, s_{t+1})} [V_{\\theta}(s_t) - (r_{t+1} - \\gamma V_\\theta(s_{t+1}))]^2\n$$\n\n> You mention that the computational overhead introduced by the proposed method is negligible, as training time is nearly indistinguishable from the baseline. However, it would be helpful to quantify this claim more precisely, perhaps by providing a theoretical estimate or reporting empirical runtime differences in a controlled setting.\n\nTo answer your question, we have re-analyzed a sample of our training runs’ logs. Empirically, the time per training step of TC-$\\lambda$ appears to be within 1% of that of DCE. This is explained by the fact that the only overhead of TC-$\\lambda$ over DCE is the computation of the pseudo-targets $\\{z_t\\}$ in (7). This is several orders of magnitude faster than computing forward and backward passes of an LLM. We thank you for your question and will clarify this in the manuscript."}, {"review_id": "hTnJu3qtIN", "reviewer": "Reviewer_cjdV", "summary": "This paper studies the problem of sequence classification of partial sentences. The method is related to temporal difference learning in reinforcement learning. The paper proves the convergence, consistency and data efficiency of the proposed approach. Over a number of datasets, the authors show classification accuracy improvement over baselines such as DCE, Last Token only baseline etc.", "questions": "- See the weakness part\n\n- Why does the difference between the partial sentence classification accuracy (like 16 tokens) and all-token accuracy in Table 1 vary significantly across the datasets? Does the dataset affect the choices of hyperparameters like lambda?\n\n- In Line 331: \"scaling beyond than 1.3 B parameters remains an open question\", this sentence is a bit confusing to me. Do you expect the proposed approach to face scalability issues under larger models (which I don't think so), or do you just mean you did not perform larger scale experiments due to computational constraints? Please enhance the clarity of the sentence.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n- Significance: the research problem is timely and important for LLMs that incrementally generate sequences by nature.\n\n- Quality: The theoretical analysis of the consistency and data efficiency is solid. The analysis in Sec. 3.1 makes it convincing why the proposed TC outperforms DCE. The baselines are well-chosen, and the performance improvement is consistent over different model sizes and families.  The experiment section further shows consistent accuracy improvements under differently short partial sentences and the efficiency benefit of the approach. The two scenarios studied in the experiment section, text classification and LLM verification, are representative of the potential real-world application of the approach.\n\n- Clarity: The paper is well organized and the writing is clear.\n\n- Novelty: The novelty seems to lie on (1) applying the idea of TD learning to text classification over discrete label space (2) replacement of the squared loss to the cross entropy in the temporal consistency condition, which is a technically sound and natural choice. This novelty is acceptable for me.\n\n**Weakness**\n\n- Methodologically, the authors measures discrepancies with the cross entropy but conventional TD learning uses squared loss between the value function outputs. Adapting the TD learning idea to incremental sequence classification is non-trivial and interesting but I wonder whether the analysis like convergence of the approach is re-iteration (or minor adaptations) of known properties of TD learning. If so, citations are appreciated.\n\n- The cited Mudgal et al. paper exemplifies a setup where the value function for continuous rewards, which perform verification of the generated text in a setup similar to Sec 4.2 of the paper. What is the advantage of the proposed approach compared to Mudgal et al. for verification of LLM generation verification? Will using the cross entropy loss perform better than the squared loss for LLM generation verification, for example, on the GSM8k studied?\n\n- The experiment part can be strengthened - most of the points also mentioned in the limitations section by the author, like experiments in larger scale models (>1.3B parameters)", "was_revised": true, "final_justification": "Please update the writing as indicated in the response:\n- better involve discussions of existing literature in the theoretical analysis part\n- include more interpretations about the performance differences under different setups.\n\n\nI don't have any more concerns about the paper.", "rebuttal": "Thank you for your review!\n\n> I wonder whether the analysis like convergence of the approach is re-iteration (or minor adaptations) of known properties of TD learning. If so, citations are appreciated.\n\nIndeed, our analysis builds on analogous properties of TD learning. We agree with your suggestion and plan to relate our results more systematically to the corresponding results for TD-learning. These appear in many forms across multiple references, but their presentation in [1] is perhaps the easiest to relate to our developments.\n\n[1] D. Bertsekas, J. Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, 1996.\n\n> Will using the cross entropy loss perform better than the squared loss for LLM generation verification, for example, on the GSM8k studied?\n\nThis is a helpful comment, also raised by reviewer `mRRN`. Although the tasks we consider are naturally framed as classification problems with a binary or a categorical cross-entropy loss, they can indeed also be cast as regression problems with a squared loss. We have addressed this question in more details under `mRRN`'s review (see \"Comparison to least squares methods\"), including additional experiments comparing our approach to a standard TD-learning approach. We did not have time to run a comparison Qwen2.5 & GSM8K, but we hope that the experiments on the four text classification datasets of Section 4.1. provide some insight into this question.\n\n> Why does the difference between the partial sentence classification accuracy (like 16 tokens) and all-token accuracy in Table 1 vary significantly across the datasets?\n\nThe datasets in Table 1 span a wide range of characteristics: some have around 20 classes (ohsumed, newsgroups) while others have only 2-4 classes (imdb, ag-news). The informativeness of the first 4 or 16 tokens also seems to vary significantly across datasets, independently of how hard the full-sequence classification task is. In that sense, we are not particularly surprised to see different patterns of performance across datasets.\n\n> Does the dataset affect the choices of hyperparameters like lambda?\n\nYes, hyperparameters do change somewhat across datasets, including $\\lambda$. The optimal values are given in Tables 3 & 4 in the appendix. The quantity $1 / (1 - \\lambda)$ is the mean of the geometrically distributed weights in Eq. (7), assuming $T \\to \\infty$, and it has an intuitive interpretation as the _average lookahead_. In our experiments, the optimal average lookahead ranges between 5 and 50 tokens, depending on the dataset.\n\nUnderstanding what characteristics of the dataset correlate with optimal values $\\lambda$ is an interesting question for future research.\n\n> In Line 331: \"scaling beyond than 1.3 B parameters remains an open question\", this sentence is a bit confusing to me. Do you expect the proposed approach to face scalability issues under larger models (which I don't think so), or do you just mean you did not perform larger scale experiments due to computational constraints? Please enhance the clarity of the sentence.\n\nWe mean the latter (we did not perform larger-scale experiments due to computational constraints). Thank you for pointing this out, we will clarify this sentence in the next version of the manuscript."}, {"review_id": "aXUrgaczet", "reviewer": "Reviewer_qrJB", "summary": "The authors consider the problem of incremental sequence classification, where the goal is to classify partial sequences at every step that elements of the sequence are revealed. Drawing parallels to TD-learning, which considers a loss to the value at the next time step, as opposed to Monte-Carlo based methods that use full sequence reward, the authors introduce a cross-entropy-like method that minimizes incremental divergences. The authors theoretically analyze their work using a Markov-chain perspective, and empirically compare against standard cross entropy methods in several text classification tasks with decoder-only transformers, demonstrating improvement over the standard cross entropy baseline.", "questions": "How does your work compare to Nested Variational Inference https://arxiv.org/abs/2106.11302? Intuitively it feels to me like there's similarity in terms of minimizing divergences to the next-step distribution.\n\nWhat kinds of confidence intervals did you use?\n\nFigure 5 left - how come 1 token TC outperforms? How is it different from DCE if there's only 1 token? Shouldn't we expect consistency to make more of a difference with more generated tokens? I'm probably missing something here. Is it that you still generate the whole set of tokens, but only evaluate on a cut off set using labels from the whole set?\n\nI think my score is unlikely to change (more clarity would be nice, but I already gave a pretty high score, and I don't see this paper having \"groundbreaking impact\"). I suppose my score could decrease if discussion reveals weaknesses.", "limitations": "The authors acknowledge the limitations of their theoretical results in not being directly applicable to the language models they investigate. This honesty is good, but it does make me wonder how much value the theory provides. More discussion about how different they expect things to be, along with some further empirical investigation/comparison with the tabular setting or small-scale language modelling settings, might be useful.\n\nRegarding the potential negative societal impact, at least the authors are honest in saying that they don't address this, and they do at least acknowledge that \"downstream applications of such models may carry societal implications\". And while I do see the reasoning behind downstream application mattering more than the fundamental algorithm, I still think more could have been done (at least in the Appendix and/or checklist) to discuss possible negative impacts (even if unlikely), as fundamental algorithm advancements also enable more downstream applications.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nOverall, I think this paper is strong, which is why this review is relatively short.\n\nOverall idea makes sense and is definitely worth exploring (I was actually surprised that this hadn't been done before; I searched online for about 30 minutes and couldn't find it; doesn't mean it hasn't been done before, but I trust that the authors did a much more comprehensive search than I did). Theory makes sense, provides insights, and seems correct to me (though I only carefully checked a few things).\n\nEvaluations are very strong. Comprehensive baselines and ablations are considered, including things I thought of and more. Confidence intervals are included (although unfortunately not on all results). A range of datasets and models are tested. Results appear strong and convincing, supporting the value of the proposed method.\n\nPaper is well written overall and reasonably clear. I would have liked more explanation in many areas, but I understand that space is limited so sometimes there's no getting around the issue of having to write in a terse way.\n\nWeaknesses:\n\nLine 18 has a typo - x8 appears twice.\n\nLine 169 - what are these mild assumptions? Should be stated somewhere (or a reference given).\n\nAs the authors acknowledge, applicability of the theory to practical settings may be limited.\n\nWould have liked to see confidence intervals on all results (including e.g., Figure 3 left and Figure 5 left). \n\nFor originality, I'm only giving a \"fair\" rating because I think the main idea is slightly marginal. That said, lots of published conference works are quite marginal, so I don't think this should prevent this paper from being accepted; I definitely think this paper meets the standards for publication.", "was_revised": true, "final_justification": "I am keeping my score of accept. Discussion with authors was helpful but did not really change my evaluation.", "rebuttal": "Thank you for your review!\n\n> Line 169 - what are these mild assumptions? Should be stated somewhere (or a reference given)\n\nWe assume that the initial state distribution and the transition probabilities are such that, for every transient state, there is a non-zero probability of it being sampled in the sequence. We agree with your suggestion and will clarify this in the next version of the manuscript.\n\n> Would have liked to see confidence intervals on all results (including e.g., Figure 3 left and Figure 5 left).\n\nFigure 3 (left) and Figure 5 (left) do actually include confidence intervals (95% confidence intervals based on the standard error of the mean computed over 5 and 10 random seeds, respectively), but they are so small that they are barely visible. As far as we are aware, Table 1 is the only float where we present experimental results without confidence intervals (although the corresponding confidence intervals can be read off of Figure 6 in the appendix)\n\nWe acknowledge that it is not at all easy to see that confidence intervals are present in the figures you mentioned, and we will experiment with alternative presentation styles (we also welcome your suggestions in that regard).\n\n> How does your work compare to Nested Variational Inference https://arxiv.org/abs/2106.11302?\n\nThank you for bringing this paper to our attention. There are indeed some apparent similarities: their Eq. 7 resembles our Eq. 5. Both involve minimizing divergences across a sequence of distributions.\nThere are also some differences; most importantly, they are concerned with learning a generative model, whereas we learn a discriminative model. Also, it seems to us that the concept of \"next step\" captures something quite different in both problems.\n\nWe are not well-versed enough in the nested importance sampling literature to be able to relate our work to theirs, beyond noticing that the optimization objective appears superficially similar. It seems to us that the two papers solve fundamentally different problems, but we do not exclude the possibility that there are deeper links between these two lines of research.\n\n> What kinds of confidence intervals did you use?\n\nWe use 95% confidence intervals based on the standard error of the mean (`+- 1.96 * stderr`).\n\n> Figure 5 left - how come 1 token TC outperforms? How is it different from DCE if there's only 1 token? Shouldn't we expect consistency to make more of a difference with more generated tokens? I'm probably missing something here. Is it that you still generate the whole set of tokens, but only evaluate on a cut off set using labels from the whole set?\n\nYour last point is correct: we evaluate the model’s ability to discriminate between correct and incorrect generations given only the first $t$ tokens, but the labels come from the _full_ generation.\n\nYour questions raise two points.\n\n1. _When should we expect TC-$\\lambda$ to outperform DCE, with few tokens (i.e., short prefixes), or with a full completion?_ We expect short prefixes to benefit most from temporal-consistency, because that is when the soft targets in Eqs 5 & 7 are most dissimilar from the hard targets used in DCE. In fact, the loss term associated with full sequences is identical for TC-$\\lambda$ and DCE (this can be seen by comparing Eq. 2 and the first term in Eq. 5). We were somewhat (pleasantly!) surprised to observe that TC-$\\lambda$ models can also outperform DCE models on _full_ sequences.\n2. _Setting aside differences between TC-$\\lambda$ and DCE, how is it possible to achieve a non-trivial ROC AUC with only a single token?_ This is because, while the model can only see a single token from the generation, it can see the full problem statement. Even though the models are trained on a balanced dataset (every problem has one correct and one incorrect generation in the training data), the models seem to be able to recognize difficult problems statements at test time (and TC-$\\lambda$ more so than DCE)."}]

Author rebuttal:

Meta-review: The paper proposes an algorithm for incremental sequential classification, where predictions are progressively updated as new elements in the sequence are revealed, guided by a temporal-consistency condition. 

Based on reviewers’ comments, the paper demonstrates the following strengths:
* The problem is well-motivated, and the paper is clearly written.
*  Enforcing temporal consistency in sequential classification is novel, and the proposed temporal-consistency loss represents a new contribution.
* The empirical evaluation is well-designed and comprehensive, with competitive baselines and consistent performance improvements.

Reviewers raised questions regarding comparisons with original TD learning, analysis of computational overhead, and comparison with Nested Variational Inference etc.. Most of these concerns were addressed in the rebuttal. The authors are encouraged to incorporate the additional results and suggestions from reviewers into the final version to further strengthen the work.
Decision: Accept (spotlight)