{"id":"55daa609-ad38-4a8a-bbbe-db01bda94bc2","arxiv_id":"2507.19338","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A branch-and-bound algorithm with multiple bound types computes the most probable marginal path in triplet Markov models much faster than exhaustive search, with m-Viterbi giving the best lower bounds.","lead":"This paper finds the most likely hidden sequence in triplet Markov models, where the usual Viterbi shortcut no longer works because the hidden sequence alone is not Markov. The authors use branch-and-bound with several cheap upper and lower bounds to skip large parts of the search, and test the approach on randomly generated small models.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Equation (15) states an invalid Samuelson upper bound: the square-root argument S2 - p^2 is non-positive for nonnegative continuation probabilities, so the printed bound is unusable as written.","rationale":"The reader's weakest assumption identifies exactly the same load-bearing concern: Equation (15) as printed is not a valid upper bound, because the square-root argument S2 - p^2 is non-positive for nonnegative continuation probabilities. I agree with this assessment after independently re-deriving the expression from the standard Samuelson inequality stated in Equation (14). This is the most load-bearing issue because the branch-and-bound correctness proof is entirely conditional on the validity of the bounds used for pruning; an invalid upper bound can eliminate the optimal path, breaking the exactness claim. The likely explanation is a missing factor of N in the printed formula, and the presence of the correct lower-bound discussion nearby supports that reading, but the paper's missing code URL prevents verification of the actual implementation. The concern does not by itself overturn the central algorithmic idea, since the framework is standard B&B and the other bounds (simple, power-sum, m-SMS, m-Viterbi) appear valid as stated. The experimental results in Table 3 are averages without error bars and the Table 4 evaluation is partially self-referential, but those are secondary to the correctness of the printed Samuelson bound. Therefore the appropriate verdict remains conditional: the central claim is credible provided the authors correct Eq. (15), release the code so the correction can be confirmed, and clarify the evaluation details. My recommendation is UNCHANGED relative to the reader's conditional verdict, with the same primary condition.","tokens_in":24879,"tokens_out":5612,"duration_ms":56263,"concrete_test":"Take any branch with two continuations of probability 0.25 each (N=2, p=0.5, S2=0.125). The printed Eq. (15) requires sqrt((2-1)*(0.125-0.25)) = sqrt(-0.125), which is not real; the corrected standard formula gives sqrt((2-1)*(2*0.125-0.25)) = 0, yielding upper bound 0.25, which is exactly p*(x1:k). The decisive check is to inspect the released implementation of the Samuelson bound and confirm whether the square-root argument is N*S2 - p^2 or S2 - p^2. If the implementation uses the corrected N*S2 - p^2 form, then Eq. (15) is a typo and the algorithm's soundness is unaffected; if it uses the printed S2 - p^2 form, the Samuelson bound is invalid and all Samuelson-related experimental results are unsound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The branch-and-bound algorithm's soundness depends on every stated upper bound being a true upper bound on p*(x1:k). Equation (15) is the Samuelson upper bound, with N = |X|^(n-k), s1 = p(x1:k), and s2 = S2(x1:k). The standard Samuelson inequality (14) gives a1 <= (s1 + sqrt((N-1)(N*s2 - s1^2)))/N. The printed Eq. (15) instead has sqrt((N-1)(S2(x1:k) - p(x1:k)^2)) in the numerator, omitting the factor N multiplying S2. Because each continuation probability is nonnegative, S2(x1:k) <= p(x1:k)^2 (with equality only when the entire mass is on a single continuation), so S2 - p^2 <= 0. For any non-degenerate branch the expression under the square root is negative, giving an imaginary 'upper bound'; if the printed formula were actually used in the implementation, the Samuelson pruning strategy would be meaningless and the corresponding rows of Table 3 and Figure 5 would not rest on a valid bound. The most plausible reading is a typographical omission of N in the square-root term, since the standard inequality appears just above and the lower-bound discussion uses the correct N s2 - s1^2 structure. However, the paper does not provide the code URL (Section 4 says only 'The code is available at .'), so the reader cannot verify whether the implementation follows the printed formula or the corrected standard formula. This is a genuine correctness risk in the written method, even though it is likely fixable by a one-character correction.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the maximal marginal problem: for a finite-state non-homogeneous Markov chain (X,U), find argmax_x P(X=x), i.e. the Viterbi path of the marginal process X, motivated by MAP segmentation in triplet Markov models. It proposes a branch-and-bound algorithm with five families of bounds (simple, power-sum, Samuelson, swapped max-sum, and m-Viterbi), derives recursions for computing them, gives complexity tables, and reports experiments on randomly generated binary TMMs showing large reductions in the number of visited nodes relative to exhaustive search. Appendices contain derivations and counterexamples showing that m-Viterbi approximations can fail in non-monotone ways.","tokens_in":25165,"tokens_out":10182,"duration_ms":95746,"significance":"If the issues below are corrected, the paper makes a useful algorithmic contribution: an exact-or-bounded method for MAP decoding in TMMs, with explicitly derived recursions for the power-sum and swapped max-sum bounds and a careful empirical study of the m-Viterbi lower bound. The counterexamples in Appendix D are valuable and honestly presented. The main strengths are the explicit derivations of the bounds, the transparent complexity tables, and the clear statement of NP-hardness with the resulting modest expectations for worst-case performance.","major_comments":[{"comment":"The printed Samuelson upper bound is not a valid upper bound as written. With N=|X|^{n-k}, s1=p(x1:k), and s2=S2(x1:k), the standard inequality (14) gives (s1 + sqrt((N-1)(N s2 - s1^2)))/N, whereas Eq. (15) has sqrt((N-1)(S2(x1:k) - p(x1:k)^2)) in the numerator, omitting the factor N multiplying S2. Since every continuation probability is nonnegative, S2(x1:k) <= p(x1:k)^2, so the radicand is non-positive whenever the continuation mass is split among more than one path. This bound is used in the Samuelson strategy whose results appear in Table 3 and Figure 5, so the soundness of that strategy is not established as printed. The likely fix is a one-character correction inside the square root, but the code URL in Section 4 is empty, so the implementation cannot be checked against the printed formula.","section":"Section 3.3, Eq. (15)"},{"comment":"The 'distance from lower bound' column does not measure closeness to the optimal value because the early-stopped B&B lower bound includes the 5-Viterbi approximation. For m=4 and m=5 the zero entries show only that the m-Viterbi path attains the same value as the 5-Viterbi heuristic, not that it is the true Viterbi path; the same issue partly affects the m=2 and m=3 rows. The upper-bound distances remain sizable (about 5.3 nats for n=500 and 10.9 nats for n=1000 for m>=2), so the conclusion in Section 5 that B&B 'does not significantly improve' on m-Viterbi for m>=2 is not supported by the table as presented. Please compare against an independent lower bound, or restrict the claim to the upper-bound comparison.","section":"Section 4.2, Table 4"}],"minor_comments":[{"comment":"The sentence 'The code is available at .' has an empty URL; without the code the experimental results and the resolution of the Eq. (15) question cannot be verified.","section":"Section 4"},{"comment":"The text says 'only the case m >= k is considered', but Appendix C assumes k >= m; the intended condition is almost certainly k >= m, and the text should be corrected.","section":"Section 3.3, m-Viterbi paragraph"},{"comment":"The proof that s2/s1 bounds the maximum contains an incorrect intermediate inequality: a1^2 + (1-a1)^2 <= a1 is not true for a1 < 0.5. The conclusion s2/s1 <= max_i a_i is still true, but the given argument should be replaced by the simpler argument s2 <= a1 * s1.","section":"Section 3.3, Samuelson lower bound derivation"},{"comment":"The sentence defining the composite upper bound says 'the upper bound as minimum of all applied lower bounds'; it should say 'minimum of all applied upper bounds'.","section":"Section 4.1"},{"comment":"The text says 'Each model was then used to generate a sequence y1:25' even though the experiment uses n=100, 500, 1000; this should be y1:n.","section":"Section 4.2"},{"comment":"The formulas 'ln(lower bound) - p(x1:n)' and 'ln(upper bound) - p(x1:n)' appear to have missing logarithms on the second term; the table is presumably reporting log-probability differences.","section":"Section 4.2, Table 4 description"},{"comment":"The recursion for delta contains index typos (for example 'delta_{n-(j-1)n}'), and the complexity expression in the text uses k where m is meant; these should be cleaned up.","section":"Appendix B"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is likely sound after a small fix to Eq. (15) and a careful rewriting of the Section 4.2 claims. The missing code URL is a reproducibility problem that should be fixed before publication. The self-referential lower-bound comparison in Table 4 is the main substantive concern for the empirical conclusions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline: the branch-and-bound approach is real and the pruning experiments are striking, but the printed Samuelson bound is invalid as written and the code link is empty, so the paper needs a revision before the results can be trusted as-is.\n\nWhat is actually new: applying power-sum, Samuelson, and swapped max-sum bounds to the maximal marginal problem in TMMs is a legitimate extension of known machinery, and the m-Viterbi approximation as a lower bound--plus the counterexamples in Appendix D, showing non-monotonicity in m and zero-probability approximations--is genuinely useful. The derivations in the appendices are careful; the power-sum recursions and the SMS bound are worked out in enough detail for someone to reimplement. The experiments show B&B visiting orders of magnitude fewer nodes than exhaustive search, which is the right kind of evidence for this type of paper.\n\nSoft spots: Equation (15) as printed has sqrt((|X|^{n-k}-1)(S2(x1:k)-p(x1:k)^2)) in the numerator. With nonnegative continuation probabilities, S2 <= p^2, so the argument is negative for any non-degenerate branch. The standard Samuelson inequality printed just above has N*S2 - s1^2 inside the root, so this is almost certainly an omitted factor of |X|^{n-k} multiplying S2. That is a one-character fix, but as printed it is not a bound, and the Samuelson rows in Table 3 and Figure 5 rest on it. The code is announced as 'available at .' with no URL, which blocks independent verification. Table 4's \"distance from lower bound\" is partly self-referential because the B&B lower bound includes the 5-Viterbi bound being evaluated; that makes the near-zero distances for m>=2 less informative than they look. Averages without error bars are a minor issue, not a serious one. There is also a small typo in Section 4.2 (y1:25 should be y1:n) and a duplicated phrase in the introduction.\n\nThe central claim still holds up: the power-sum and SMS bounds are standard inequalities applied carefully, and the m-Viterbi lower bound is plainly valid. I'd send this to a referee; the appendices deserve scrutiny and the counterexamples are worth checking. It is not a desk reject.\n\nIf the authors correct the formula and post the code, I'd cite this as a reference for exact MAP decoding in TMMs.","headline":"Solid branch-and-bound framework for exact MAP decoding in TMMs, but the printed Samuelson bound is invalid as written and the code link is empty; revision needed before the results are fully trustworthy.","tokens_in":25751,"tokens_out":2523,"would_cite":true,"duration_ms":21441,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Branch-and-bound can solve the maximal marginal problem in triplet Markov models, with simulated searches visiting orders of magnitude fewer paths than exhaustive enumeration.","keywords":["Pairwise Markov models","Hidden Markov models","Maximum a posteriori estimation","maximal marginal problem","branch and bound","Viterbi path","triplet Markov models","m-Viterbi approximation"],"falsifier":"Evaluate the printed Samuelson upper bound (15) at any prefix with $0 < S_2(x_{1:k}) < p(x_{1:k})^2$, which occurs whenever the continuation is nondeterministic; the square root is then imaginary, so the formula is not a real upper bound. Alternatively, rerun the Section 4 experiments with the Samuelson bound literally implemented as printed and compare the number of visited nodes, which should collapse or produce errors if the formula is used.","tokens_in":24611,"feed_emoji":"🌳","tokens_out":7311,"duration_ms":66141,"temperature":0.7,"pith_summary":"The paper tackles the maximal marginal problem: find the single most probable realization of a hidden process X in a model where only the joint process (X,U) is Markov, so X by itself is not and the classical Viterbi algorithm cannot be applied. Its proposed solution is a branch-and-bound search over path prefixes, with upper and lower bounds on the probability of the best continuation. The bounds are computed from the joint Markov structure, which keeps their per-node cost low. In random binary triplet Markov models of length 25, the method visits on average about $2^{6}$ nodes instead of the $2^{26}$ an exhaustive search would need, and for longer chains it can stop early while still returning rigorous bounds on the optimum. The paper's claim is that exact or tightly bounded maximum a posteriori decoding in triplet Markov models is computationally practical.","feed_headline":"Pruning shrinks MAP decoding from 2^26 to about 2^6 nodes","feed_subtitle":"Branch-and-bound with m-Viterbi lower bounds makes exact Viterbi paths practical in triplet Markov models.","key_machinery":"The central object is the branch probability $p^*(x_{1:k}) = \\max_{x_{k+1:n}} p(x_{1:n})$, evaluated for every prefix of the path, and the search tree over all prefixes. The identity that carries the argument is that the joint process $(X,U)$ is Markov: summations over the nuisance process $U$ can be moved through transition kernels, and maximizations over continuations can be separated into blocks, so each bound family becomes a dynamic programming recursion. Branch-and-bound prunes any prefix whose upper bound falls below a global lower bound, so the method's efficiency is determined by how tight the bounds are relative to their per-node computation cost.","core_discovery":"The central claim is that the maximal marginal probability $\\max_x p(x)=\\max_x \\sum_u p(x,u)$ can, in practice, be computed or tightly bracketed by a branch-and-bound algorithm whose bounds exploit the joint Markov property of $(X,U)$. The paper introduces five bound families: simple, power-sum ($r$-PS), Samuelson-type, swapped max-sum ($m$-SMS), and $m$-Viterbi approximations, with recursions that price each prefix $x_{1:k}$ in polynomial time. In 1000 randomly generated binary TMMs of length 25, the combination of 10-PS bounds with a 2-Viterbi lower bound reduces the average number of visited nodes from $2^{26}$ to about $2^{6.3}$, and the experiments indicate that $m$-Viterbi approximations with $m\\ge 2$ provide the strongest lower bounds, often essentially matching the optimum. The paper also shows, by constructed examples, that larger $m$ need not improve the $m$-Viterbi approximation and that such approximations can even have zero probability, so the lower bound should be combined with a simple bound as a safeguard.","pith_inferences":["We infer, beyond the paper's own caution, that the printed Samuelson formula is a typographical slip rather than a conceptual one: with the standard Samuelson inequality used in the actual code, the Table 3 result of about $2^{14.1}$ visited nodes is plausible. This is testable by checking the released code.","An implication the authors leave implicit is that the same bounding machinery should apply to continuous-observation PMMs and TMMs, because conditioning on the observations produces a finite non-homogeneous Markov chain; the experiments only cover binary states, so the relative performance of bounds in larger alphabets remains open.","One possible extension is to use the $m$-SMS and $m$-Viterbi bounds together with an adaptive choice of $m$ per layer, exploiting the layer-by-layer plots in Figure 5; the paper compares fixed strategies only.","Given the NP-hardness results cited in the paper, the exponential worst case cannot be removed in general; we infer that the practical gains will depend on bound tightness for the particular model, so the method is best viewed as an exact solver with a rigorous early-stopping certificate rather than a polynomial-time algorithm."],"forward_implications":["For triplet Markov models with moderate state spaces and sequence lengths, exact MAP decoding becomes feasible in practice rather than requiring exhaustive enumeration over $|\\mathcal{X}|^n$ paths.","The $m$-Viterbi lower bound with $m\\ge 2$ can serve as a fast near-exact decoder on its own; the branch-and-bound search then supplies a certificate of how far the approximation is from optimal.","The same bound machinery transfers to non-homogeneous Markov chains obtained by conditioning on observations, so it applies to segmentation tasks in TMMs and to hybrid-path decoding.","Because no upper bound dominates in the simulations, an implementation can combine several upper bounds and take their minimum, at a cost that the paper's complexity tables make explicit."],"supporting_citations":[{"why":"Supplies the extension of Samuelson's inequality that the Samuelson-type upper and lower bounds are built from.","marker":"[37]"},{"why":"Introduces the systematic search and swapped max-sum idea for exact MAP solving that the m-SMS bounds generalize.","marker":"[30]"},{"why":"Establishes NP-hardness of the consensus-string (maximal marginal) problem in HMMs, motivating branch-and-bound over exhaustive search.","marker":"[28]"},{"why":"Previous study suggesting the m-th order Markov approximation of X whose Viterbi path defines the m-Viterbi lower bound.","marker":"[38]"},{"why":"Establishes the conditional Markov property of pairwise Markov chains that underlies all the dynamic programming recursions in the bounds.","marker":"[5]"},{"why":"Cited for NP-hardness of exact probabilistic inference in Bayesian networks, placing the maximal marginal problem in a broader hardness class.","marker":"[31]"},{"why":"Used with the maximum-clique reduction to show no polynomial O(n^{1/2-epsilon}) approximation of the maximal marginal problem exists unless P=NP.","marker":"[33]"}],"fun_headline_variants":["Branch-and-bound makes exact Viterbi path practical in TMMs","From 2^26 to 2^6 nodes: pruning speeds TMM decoding","m-Viterbi bounds power branch-and-bound for TMM decoding","Exact MAP decoding in TMMs via branch-and-bound pruning","New bounds shrink Viterbi search in triplet Markov models"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the printed formulas for the bounds are valid; in particular, the Samuelson upper bound in Equation (15), as printed, takes a square root of a negative quantity whenever the continuation probabilities are nonnegative and not degenerate, so the algorithm only works if its implementation uses the standard Samuelson inequality form.","fun_headline_variants_meta":{"raw":{"variants":["Branch-and-bound makes exact Viterbi path practical in TMMs","From 2^26 to 2^6 nodes: pruning speeds TMM decoding","m-Viterbi bounds power branch-and-bound for TMM decoding","Exact MAP decoding in TMMs via branch-and-bound pruning","New bounds shrink Viterbi search in triplet Markov models"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000244,"raw_usage":{"total_tokens":1620,"prompt_tokens":1121,"completion_tokens":499,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":737,"completion_tokens_details":{"reasoning_tokens":405}},"tokens_in":737,"tokens_out":499,"duration_ms":4835,"temperature":1.0,"reasoning_tokens":405,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T17:54:55.444946+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Evaluate the printed Samuelson upper bound (15) at any prefix with $0 < S_2(x_{1:k}) < p(x_{1:k})^2$, which occurs whenever the continuation is nondeterministic; the square root is then imaginary, so the formula is not a real upper bound. Alternatively, rerun the Section 4 experiments with the Samuelson bound literally implemented as printed and compare the number of visited nodes, which should collapse or produce errors if the formula is used.","supporting_citations":[{"cited_title":"Solving MAP Exactly using Systematic Search","cited_arxiv_id":"1212.2497","evidence_quote":"Introduces the systematic search and swapped max-sum idea for exact MAP solving that the m-SMS bounds generalize."},{"cited_title":"Journal of Computer and System Sciences 65(3), 545–569 (2002) https://doi.org/10.1016/S0022-0000(02)00009-0","cited_arxiv_id":null,"evidence_quote":"Establishes NP-hardness of the consensus-string (maximal marginal) problem in HMMs, motivating branch-and-bound over exhaustive search."},{"cited_title":"Mas- ter’s thesis, University of Tartu (2023)","cited_arxiv_id":null,"evidence_quote":"Previous study suggesting the m-th order Markov approximation of X whose Viterbi path defines the m-Viterbi lower bound."},{"cited_title":"Pedestrian Models for Autonomous Driving Part II: High-Level Models of Human Behavior","cited_arxiv_id":"2003.11959","evidence_quote":"Establishes the conditional Markov property of pairwise Markov chains that underlies all the dynamic programming recursions in the bounds."}],"review_version":2}