Efficient Optimization of Fixed-Length Paths

1 Introduction

Several problems call for finding a sequence of given length L over a space of n states and m connections that optimizes a cost; they are conventionally solved by A∗ search or dynamic programming (DP). Examples include Viterbi decoding, i.e., finding a most likely sequence of hidden states-a Viterbi path-in a Hidden Markov Model (HMM) to explain an observed sequence of length L [Viterbi, 1967], used in speech recognition [Pratap et al., 2024]; finding L-1 boundariesa V-optimal histogram ('V' for variance)-over a numeric sequence that minimize the error of constant approximation within each partition [Jagadish et al., 1998]; and identifying the most probable syntactic structure-a Viterbi parse treethat generates a length-L input sequence of tokens under a probabilistic context-free grammar (PCFG) [Klein and Manning, 2003; Huang et al., 2012].

Such algorithms iteratively derive solutions to a subproblem of length k+1 from solutions to subproblems of length k in O(mL) time. A∗ -based algorithms maintain a priority queue to prioritize subproblems that aid the solution in a best-first manner with an O(nL log nL) complexity overhead, while DP prioritizes them in a breadth-first manner by length.

Both memoize partial solutions; after determining the optimal cost, they backtrack over those memoized solutions to retrieve the path having that cost. In the shortest-path problem, path length is arbitrary [Russell and Norvig, 2010]; thus, a lower-cost arrival at node i in step ℓ dominates a highercost arrival in a different step ℓ′ . In effect, it suffices to track, for each node, the minimum arrival cost and the incoming neighbor from which it is reached, in O(n) space. Still, when path length is fixed [Klein and Manning, 2003; Huang et al., 2012] as L, arrivals at node i in different steps face continuations of different costs. We should thus memoize the lowest cost Opt(i, ℓ) of arriving at node i in each step ℓ in O(nL+m) space, leading to memory constraints in GPU-based speech recognition [Pratap et al., 2024]. If we discard partial solutions to work in-place in O(n +m) space, we need to recurse the algorithm L-1 times to build the optimal path after finding its cost in O(n2L2 ) time. A reformulation of the DP solution [Ciaperoni et al., 2022; Ciaperoni et al., 2024] constrains space to O(n + m) and time to O(n2L log L), yet does not directly apply when prioritizing subproblems by best-first search with a priority queue.

In this paper, we introduce COMPACTBFS, a framework for the efficient optimization of fixed-length paths that regulates the priority queue and avoids memoization, using O(n + m) space (m for the in-memory model). We vet COMPACTBFS on Viterbi decoding and V-optimal segmentation with real and synthetic data, gaining in memory use and runtime vs. prior work, especially under skewed cost distributions.

2 Background and RelatedWork

Dynamic programming (DP) [Bellman, 1966] explores the problem space exploiting an optimal substructure property, by which a globally optimal solution can be assembled from locally optimal solutions, to solve a problem by recursively expanding partial solutions in a breadth-first manner. Best-first-search algorithms [Pearl, 1984] may also exploit optimal substructures, as dynamic programming does [Sniedovich, 2006], to find a minimum-cost path from a start to an end node by repetitively expanding, i.e., visiting the neighbors of, the most promising unexpanded visited node. The A∗ algorithm [Russell and Norvig, 2010; Foead et al., 2021], an instance of best-first-search, finds a path of arbitrary length (i.e., number of steps) that minimizes a cost function, prioritizing paths by a cost estimation heuristic that is admissible (i.e., never overestimates a path's cost) and consistent (i.e., never estimates the cost via an intermediary node as lower) [Russell and Norvig, 2010]; the search may proceed from both start and end by bidirectional search [Pohl, 1969]. A∗ generalizes Dijkstra's algorithm [Dijkstra, 1959], by which the heuristic cost estimate of any unexplored path is 0. Dijkstra retains only the cheapest arrival at each node i and returns the cheapest path upon reaching a certain goal state, length L, or cost [Bemten et al., 2019]; it is based on the assumption that any continuation from node i adds the same cost to all paths. However, when seeking a minimum-cost path of exactly L steps, arrivals at the same node i at different steps ℓ and ℓ′ face different feasible continuations, whose cost depends on the exact steps remaining. In effect, a lower-cost arrival at i does not dominate a higher-cost arrival at a different step. An algorithm retaining only the cheapest arrival at each node i may thus miss the globally optimal length-L path; instead, we must track the lowest cost Opt(i, ℓ) of arriving at node i at each step ℓ.

Hidden Markov Models (HMMs) explain observation sequences. An HMM comprises a set of K hidden states, each with probabilities to be an initial state, transition to other states, and emit an observation. Decoding seeks a sequence of states most likely to generate a sequence of observations:

Problem 1 (Decoding). Given an HMM and a sequence of T observations Y = {y1, y2, . . . , yT }, find the sequence of hidden states Q = {s∗1 , s∗2 , . . . , s∗T } that maximizes the likelihood P (Q, Y ).

The Viterbi algorithm [Viterbi, 1967; Viterbi, 2006] solves Problem 1 by DP; it finds application from telecommunications [Viterbi, 2006] to speech recognition [Gales and Young, 2007; Braun et al., 2020; Pratap et al., 2024], where it finds the most probable transcription for an acoustic signal, and, in forced alignment, aligning transcriptions to audio recordings, running on a composition of HMMs in which states represent words and their phonemes. However, it raises high memory and runtime requirements. Recently, [Jo et al., 2019] proposed a heuristic for word recognition without proving its correctness. [Ciaperoni et al., 2022; Ciaperoni et al., 2024] enhanced decoding space efficiency at the cost of a runtime overhead via divide-and-conquer. A similar strategy has been applied to arbitrary-length sequence alignment [Hirschberg, 1975; Hirschberg, 1977; Korf, 1999; Korf and Zhang, 2000; Spouge, 1989; Spouge, 1991], but not to fixed-length path optimization, as in selecting and aligning L characters from each of two input strings. Other works reduce the state space representation for HMM classes [Siddiqi and Moore, 2005; Felzenszwalb et al., 2003]. Improving on time complexity is a tough undertaking, due to lower bounds [Backurs and Tzamos, 2017]. [Klein and Manning, 2003] and [Huang et al., 2012] apply A∗ -like policies to enhance Viterbi's time efficiency for PCFG parsing, yet neglect space efficiency. In contrast, we offer a time-efficient and parsimonious formulation.

Histogram construction splits a data series into a number of representative buckets that minimize an error function:

Problem 2 (Histogram Construction). Given I = {x1, . . . xn}, xi ∈ R, and B ∈ Z+, find a segmentation (or histogram) HB of I into B non-overlapping subsequences

(or buckets) Ib with associated bucket representatives ˆxb, b ∈ {1, . . . , B}, that minimizes error function EI (HB).

We focus on V-optimal histograms [Jagadish et al., 1998], i.e., EI (HB) = ∑Bb=1 Eb, where Eb = ∑xi∈Ib (xi - ˆxb)2 , and ˆxb is the mean of values in bucket Ib. This problem is solved by a DP algorithm [Jagadish et al., 1998; Guha et al., 2006; Halim et al., 2009] quadratic in n. COMPACTBFS offers gains extensible to any monotonic and distributive error measure [Karras and Mamoulis, 2008].

Semirings and Dioids [Gondran and Minoux, 2008] A semiring is a 5-tuple (D, ⊕, ⊗, ¯0, ¯1), where D is a non-empty set, ⊕ is a binary, associative, and commutative operator, ⊗ is a binary and associative operator, ¯0 is a neutral element for ⊕ (i.e., x ⊕ ¯0 = x, for all x ∈ D), ¯1 is a neutral element for ⊗ (i.e., x ⊗ ¯1 = ¯1 ⊗ x = x, for all x ∈ D), the operator ⊗ distributes over ⊕ and ¯0 is absorbing for ⊗ (i.e., x ⊗ ¯0 = ¯0 ⊗ x = ¯0, for all x ∈ D). A selective dioid is a semiring in which ⊕ is also selective (i.e., (x ⊕ y = x) ∨ (x ⊕ y = y), for all x, y ∈ D). Selective dioids provide an abstract expressive framework for shortest-path and DP problems [Mohri, 2002; Huang, 2008; Tziavelis et al., 2025].

3 The COMPACTBFS Framework

We define COMPACTBFS, which finds a fixed-length sequence that optimizes a cost measure, and apply it to Viterbi decoding (§ 3.1) and histogram construction (§ 3.2). Unlike dynamic programming, which visits subproblems in a fixed order even if some do not contribute to the solution, COMPACTBFS solves subproblems in a best-first fashion, as Figure 1 illustrates.

COMPACTBFS starts out with the following components:

1. A data space X of n elements;
2. A neighbor function N :X →2X that generates a set X of length-L eligible sequences (xiℓ), xiℓ∈X , ℓ∈{1, . . ., L}, with xiℓ-1 ∈N(xiℓ ) for ℓ∈{2, . . ., L}.
3. A gap function G(j, i, ℓ) associating a value with the transition from item xj ∈ X to item xi ∈ X at step ℓ.
4. A selective dioid D = (D,⊕,⊗, ¯0, ¯1) expressing the value of a sequence: f(x) = ⊗ℓ=L ℓ=2 G(xiℓ-1 , xiℓ , ℓ), whereby extending a sequence never improves its value.
5. A problem that seeks an eligible length-L sequence x∗ ∈ X of optimal f(x∗ ), compared via the ⊕ operator.
6. A recursive function Opt(i, ℓ) that stores the optimal value for an eligible length-ℓ sequence ending at xi ∈ X .
7. A solution to the problem in Item 5 by DP over sequences of increasing length fromX.

The solution in Item 7 finds an eligible sequence of L data items x∗ = {x∗1 , x∗2 , . . . , x∗L} that optimizes Opt(·,L); the selective dioid properties, in particular distributivity, guarantee correctness. The DP computation takes the form:

The recursion of Equation (1) requires Θ(n2L) time and Θ(nL) space, iterating over items i and lengths ℓ and storing, for each (i, ℓ) pair, a predecessor needed to backtrack the optimal sequence. The entailed solution may be implemented by either DP or token passing [Young et al., 1989]; both calculate all solutions of length ℓ, Opt(·, ℓ), before those of length ℓ + 1, Opt(·, ℓ + 1), by breadth-first search. While DP draws from solutions of length ℓ to build each solution of length ℓ+1, token passing broadcasts a token for each solution of length ℓ to its continuations of length ℓ + 1. In both cases, solutions solidify at length ℓ before moving to length ℓ + 1.

COMPACTBFS drops this breadth-first orientation for a best-first one; it organizes sub-problem solutions (represented by tokens) in a priority queue Q in which it initially inserts all tokens (·, 1). Thereafter, in each step, it selects the most promising token (h, ℓ) from Q and updates the priority in Q of each eligible successor (i, ℓ+1) not already extracted fromQ to Opt(h, ℓ) ⊗ G(h, i, ℓ + 1), when beneficial relative to the existing value. COMPACTBFS resembles Dijkstra's shortestpath algorithm [Dijkstra, 1959]; however, whereas Dijkstra minimizes a cost objective regardless of length (i.e., number of steps), COMPACTBFS optimizes the objective under a fixedlength constraint. It derives tokens (corresponding to DP table cells) selectively, without considering all options in order and without producing every token, resulting in significant savings. In problem-tailored variants, we prioritize tokens by anticipating the cost a sequence may obtain as it expands. We also derive bidirectional-search variants that craft both prefixes and suffixes of sequences until they reach the target length.

Nevertheless, the priority queue Q may reach size Θ(nL), holding one token for each state-length pair. Additionally, we need to memoize the subproblem solution each token represents even after we pop it fromQ, to enable backtracking the solution sequence. To ensure O(n) space complexity, which is highly desirable [Pratap et al., 2024], we employ the following measures, which still calculate the same exact objective.

Controlling the priority queue size. First, to keep the size of Q in O(n), when the best-first-search queue Q exceeds a predefined size threshold θ (or memory budget) upon inserting a token (sj, t), we invoke a containment mechanism, which is either a tailored depth-first-search (DFS) mechanism, or a mechanism that we propose, earliest-first search (EFS).

DFS. By the DFS mechanism, we pick the lowest-cost token (sj, t∗ ) from the set of tokens for sj, S j = {(sj, ·)}, and generate all its derivative tokens via a DFS traversal of the HMM graph G starting at sj. Each DFS branch terminates upon reaching the last frame (i.e., step) or upon injecting into the token set of a state sj ′ a token that either displaces or yields to a pre-existing one, without increasing memory usage. This DFS mechanism ensures queue size O(n) by constraining the size of Qwithin θ; it incurs O(n2L2 ) time in the worst case, as it may perform a DFS over all O(nL) tokens for each token; in practice we do not encounter a large overhead.

EFS. Small θ values in the DFS mechanism may cause excessive DFS calls, reprocessing the same tokens multiple times and slowing runtime, even compared to that of regular dynamic programming which processes all nL tokens. To address this predicament, we propose an alternative search mechanism that processes each token at most once, Earliest-First Search (EFS). EFS processes tokens in increasing time frame order, starting form the earliest frame represented in the priority queue, until the gap between the earliest and latest time frames in the queue falls below a user-specified constant ∆Q. In effect, the queue size is bounded by ∆Qn and best-first search resumes. While the EFS mechanism generates and must store additional tokens, at most 2n - 1 additional tokens will co-exist in the queue, occupying the earliest time frame and its successor. In effect, EFS ensures queue size O(n) and retains the compact O(nL(n + log L)) time including the queue overhead.

Reconstructing the optimal path. Second, instead of memoizing subproblem solutions for backtracking the final solution path, we construct that path by a divide-and-conquer strategy as in [Binder et al., 1997; Ciaperoni et al., 2022; Ciaperoni et al., 2024]. Upon reaching the middle frame of a solution path, we record, with each subsequent token, the edge at that middle frame (or middle pair). After establishing the last-frame optimal cost, we recursively rerun the algorithm on the L/2-hop predecessors and successors of that token's middle pair to construct the entire path, retrieving middle pairs as in an in-order tree traversal [Ciaperoni et al., 2022]. The main DP operation takes O(n2L) time; maintaining the priority queue incurs an O(nL log nL) overhead and the divide-andconquer iteration brings an log L factor, hence the dominant terms are O(n2L log L + nL log2 L), with O(n) space.

3.1 The MINT algorithm

The Viterbi algorithm selects a sequence of T states Q = {s∗1 , s∗2 , . . . , s∗T } from a universe of K HMM states S = {s1, s2, . . . , sK} connected via a set of edges E, most likely to have generated a sequence of T observations Y = {y1, y2, . . . , yT}. Q is called Viterbi path. By the Markov property, the likelihood to be in a state depends only on the previous state. The algorithm thus uses the DP recursion:

where T[si, t] stores the probability of the most likely path ending at state si in t steps, or time frames, Nin(si) is the set of in-neighbors of si, πi is the initial probability of si, Ash,si is the probability of transiting from state sh to state si on a directed graph G capturing eligible transitions in the HMM, and Bsi,yt is the probability of observing yt at state si. This setting suits COMPACTBFS as follows:

1. The data space X is the HMM of K hidden states S = {s1, s2, . . . , sK}.
2. The neighbor function Nin : X →2X generates a set X of eligible sequences (xit ), xit ∈X, t ∈ {1, . . . , T} as length-T paths of consecutive states in the HMM.
3. The gap function G(j, i, t) is Asj,si Bsi,yt , or, in logprobabilities, as logAsj,si + logBsi,yt .

1. The selective dioid is ([0, 1],max, ·, 0, 1), or, in the domain of log-probabilities, ([-∞, 0], max, +, -∞, 0). Thus, the value function f assigns probabilities to paths, given the sequence of observations Y = {y1, y2, . . . , yT}; the probability that Y is generated by a sequence of hidden states Q = {s1, s2, . . . , sT} is P(Q, Y ) = πs1 · Bs1y1 ∏Tt=2 Ast-1st · Bstyt , where π(s1), Ast-1st , and Bstyt are defined as above.
2. The problem seeks an eligible sequence of states Q of length T that best explains the given sequence of observations Y , i.e., maximizes probability (⊕ := max).
3. The recursive function Opt(i, ℓ) that stores the optimal value for an eligible sequence of length ℓ that ends at data item xi ∈ X is the function T[si, t = ℓ].
4. The solution by DP over sequences of increasing length from X is given by Equation (2).

The recursion of Equation (2) requires O(K2T) time and O(KT) space, as it iterates over states si and time frames t. For the sake of efficiency and accuracy, we replace products of likelihoods by sums of log-likelihoods. In case the structure of G is known, we iterate only over states sh that link to state si, hence visit each HMM graph edge only once; then time complexity becomes O((K + |E|)T ).

The Viterbi algorithm and its token passing variant [Young et al., 1989] operate by breadth-first search. MINT (Time Efficient Viterbi) replaces this strategy with best-first search. It organizes partial solutions in a priority queue Q and expands the most promising one in each step, as in [Klein and Manning, 2003]. Like Viterbi, it derives T[si, t + 1] entries from T[sh, t] entries. Still, while Viterbi calculates all T[·, t] entries before T[·, t + 1] entries, MINT first inserts all tokens (sh, 1) in Q and then iteratively pops the most promising token (sh, t) from Q and, for each outgoing neighbor si ∈ Nout(sh) such that (si, t + 1) has not been extracted from Q, it computes T[sh, t] · Ash,si · Bsi,yt+1 as a provisional T[si, t + 1] value and updates the priority of (si, t + 1) accordingly. Thanks to the monotonicity of T[·, ·] along a path, T[si, t] satisfies Equation (2) when (si, t) is popped from Q. In the worst case, MINT visits each HMM edge once per time frame, hence takes O((K logKT + |E|)T) time, where logKT expresses the priority queue overhead [Fredman and Tarjan, 1987]. In practice, it never considers some HMM edges. Next, we illustrate four MINT variants.

Standard MINT. In more detail, to achieve the maxsi T[si, T ] objective, we minimize the positive path log-likelihood, - log P (Q, Y ) ≥ 0, defined as cost of a path. For a given path Q ending at state i at frame t, we define its priority as p(si, t) = - log P (Q, Y ), with Q = {s1 , s2 , . . . , st }, such that st = si and Y = {y1, y2, . . . , yt}. The pseudocode of the plain MINT variant is shown in the full version [Ciaperoni et al., 2026]. First we insert in Q a token for each state in the first frame with priority -logπsi - logBsi,y1 . If a start state s is given, we only enqueue a token for s at t = 0. The main loop iterates until reaching the last frame. In each iteration, we dequeue fromQ the top token (sh, t), add it to a set V of visited tokens, compute the cost of reaching (si, t+1) via (sh, t) for each out-neighbor si of sh that has no such token in V, and insert or update (si, t + 1) in Q to the lowest known cost. When a pair (s, T) is dequeued, no path spanning T frames at lower cost exists, hence we return its cost as the Viterbi path log-likelihood maxsi T[si, T ].

Proposition 1. Standard MINT is correct.

To return the optimal path, MINT by default appends a path to each token and, when updating the priority of (si, t + 1), also updates the corresponding path to si. An alternative implementation, MINT-Backtracking, stores only the predecessor of each token, retains all explored tokens, and at the end constructs the optimal path by backtracking. Next, we present three extensions to MINT.

MINT Bound. We propose a variant of MINT that orders tokens by lower-bounding the path cost from each token (sh, t) until the final frame T using a lower bound ˆ c1 on the cost for moving from one frame to another for the remaining T - t frames. We call the ensuing algorithm MINT Bound.

We first insert all states (or the source state, if given) in Q with p (s, 1) = (T - 1) · ˆ c1. As the search proceeds, we replace lower bounds with exact costs. The priority of (sh, t) is p (sh, t) = - log P (Q, Y )+(T -t) · ˆ c1, Q being the current optimal path ending at sh in t frames; we compute the priority of a neighbour si for insertion or update in Q as p (sh, t) -ˆ c1-logAsh,si -logBsi,yt+1 . Upon reaching the last frame, all lower bounds capture exact costs. Setting ˆ c1 as the lowest value of - logAsh,si - logBsi,yt+1 over all edges (sh, si) at any t, found by pre-processing, ensures correctness.

Proposition 2. MINT Bound is correct.

MINT Bound encases information from unexamined time frames in the BestFS criterion and further explores already well-explored paths without compromising correctness.

Bidirectional MINT gains efficiency by bidirectional search [Pohl, 1969], exploring solutions from both the start and the end time frame. We denote the graph in which all edges are reversed as Grev. In each direction, the search proceeds as in Standard MINT, yet with two priority queues, Qf (forward search) and Qb (backward search). If an initial state is given and a final state is not given, we find, in pre-processing, all states S(T) reachable from the initial state in T frames, and initiate Qb with those. In each iteration, we expand both 1 searches, handling queues as in Standard MINT. Upon extracting (sfh , tf ) fromQf and (sbh , tb ) fromQb, we update the associated visited-token sets, Vf and Vb, and store associated costs in arrays df and db. We then consider tokens (sfi , tf +1) for all neighbors sfi of sfh in G and tokens (sbi , tb - 1) for all neighbors sbi of sbh in the graph Grev. We omit the details, which are the same as those in Standard MINT. When the two sides meet generating a path of length T , we update the hitherto best path cost µ, if the newly found path improves on it. Such a path is provably optimal, hence the algorithm terminates, when the sum of costs of tokens dequeued from Qf and Qb exceeds µ. To avoid double-counting emission probabilities, we add the emission probability of the last vertex visited while building a path only in the priority of Qf , thus the cost of any path through (w, t) is df [(w, t)] + db[(w, t)].

Proposition 3. Bidirectional MINT is correct.

1 A more refined strategy would choose which side to expand.

Bidirectional MINT Bound combines Bidirectional MINT and MINT Bound in one algorithm that searches in both directions and lower-bounds the total T-frames-long path costs used as priority values in both queues. The search in both directions follows the order determined by the cost of arriving to a state in a given number of steps (frames) plus a lower bound on the cost of arriving from there to the the end of the path. The single-frame lower bound for the forward search is as in MINT Bound. For backward search, it is the lowest cost of moving from a frame to the next one in the reverse HMM graph Grev, i.e., the lowest value of -logAsi,sh - logBsi,yt over all edges (si, sh) in Grev. We obtain both bounds by pre-processing with a single graph traversal. The correctness of Bidirectional MINT Bound follows from the correctness of MINT Bound and Bidirectional MINT.

Linear-space MINT (MINT-LS) Here, we propose a COMPACTBFS space-efficient variant, MINT-LS, which guarantees O(K) space by keeping the size of Q in O(K) by a containment strategy and reconstructs the solution by a divideand-conquer strategy. AlgorithmMINT-LS, shown in the full version [Ciaperoni et al., 2026], avoids storing tokens when the queue size reaches a threshold θ. Instead, it invokes the DFS subroutine, which only stores tokens either as replacements of others or at the last frame; with each such token (sh, t), it stores its predecessor state and the running middle pair for its path. These details help identify the subproblems to be solved recursively. Upon reaching the final frame (and the final state, if specified), it extracts the middle pair associated with the solution path and reruns recursively among Np-hop predecessors of the middle pair in as many preceding frames and among Ns-hop successors in as many following frames, identified through breadth-first search. MINT-LS+ applies our EFS strategy that visits each token at most once prioritizing tokens by time frame with an auxiliary queue Qt; it keeps track of the earliest and latest time frame in Qt and toggles between BestFS and EFS as required. As results in Section 4.1 show, these strategies ensure low space consumption. With large θ, DFS is preferable; otherwise, EFS is preferred. MINT-LS naturally combines with bidirectional search.

3.2 The TECH algorithm

We apply COMPACTBFS to V-Optimal histogram construction [Jagadish et al., 1998], outlined in Section 2. A V-Optimal histogram uses the mean value ˆx = 1 i-j+1 ∑ik=j xk as a representative to minimize the Euclidean error in a bucket Ib extending from the j th to the ith value in the sequence, E(j, i) = ∑ik=j (xk - ˆx)2 . The total error is aggregated over all buckets. V-Optimal algorithms use incremental sums S and sums of squares SS to obtain any E(j, i) as:

The algorithm finds, for each combination of a value index i and number of buckets b, the cost of the optimal b-bucket histogram covering the first i values in the sequence, as:

E∗ (i, b)=0 for i ≤ b and E∗ (i, 1)=E(1, i). After finding the optimal cost E∗ (n,B) for a length-n sequence and B buckets, we backtrack the histogram. The problem maps to COMPACTBFS as follows:

1. The data space X is the data series I = {x1, . . . xn}.
2. The neighbor function N(xi) = {xj|1 ≤ j < i} generates a set X of eligible sequences (xit ), xit ∈ X, t∈{1, . . . , B+1} as ordered boundaries from x1 to xn.
3. The gap function G(j, i, b) is the bucket error E(j +1, i) irrespective of b.
4. The selective dioid is (R ∪ {+∞},min,+,+∞, 0). Thus, the value function f : X → R assigns an approximation error ∑Bb=1 Eb to a histogram.
5. The problem seeks an error-minimizing eligible histogram of B + 1 boundaries (⊕ := min).
6. The recursive function Opt(i, ℓ) that stores the optimal value for an eligible sequence of length ℓ ending at item xi ∈ X is the function E∗ (i, b = ℓ).
7. The solution by DP over sequences of increasing length from X is given by Equation (4).

V-OPT histogram construction by DP [Jagadish et al., 1998] requires O(n2B) time and O(nB) space. We discuss COMPACTBFS variants, TECH (Time-Efficient Histogram), aligned to the variants of MINT.

Standard TECH. Standard TECH, like MINT, employs a priority queue Q to prune computations, where the priority of entry (h, b) is the cost of the b-bucket histogram for the first h values, p(h, b) = E∗ (h, b). After computing the S and SS arrays, used to compute the error measure by Equation (3), in each iteration, TECH dequeues the pair (h, b) of lowest error, adds it to a set V of visited tokens, and, provided b < B, computes via (h, b) the error for each pair (i, b + 1) with i > h that is not in V and inserts or updates (i, b + 1) in Q accordingly; thereby, it explores possible next buckets. We do not iterate over (i, b + 1) pairs for all i > h, but stop at i = n-B+b+1 since there must be at least B-b-1 values after i to make B buckets in total. The algorithm terminates after it dequeues (n,B). Correctness follows as in Proposition 1: after (n, B) is dequeued, there can be no lower-cost histogram of the same series and B. For further pruning, we use an upper bound UB[h, b] on the cost of a (B - b)-bucket histogram for the series {h + 1, . . . n}, derived in Proposition 4 below. If, after visiting (h, b), we find i∗ > h such that E(h + 1, i∗ ) ≥ UB[h, b], we eschew computing E(h + 1, i) for i > i∗ , as we have already exceeded the upper bound on the error therefrom.

TECH Bound. This variant uses bounds on the cost of a Bbucket histogram instead of the cost of a partial histogram with b ≤ B buckets. Given (h, b), we partition the series {h+1, . . . n} in B-b equal-width buckets. The minimum error among such buckets is a lower bound to the V-optimal histogram cost, while the sum of those errors is an upper bound, which we may use for pruning.

Proposition 4. The minimum error minb Eb among b buckets of an equal-width partitioning a sequence I is a lower bound to the V-optimal histogram cost and ∑b Eb is an upper bound.

TECH Bound adds the lower bound LB[h, b] to the priority of each pair (h, b). Upon arrival at the end of the series, it outputs the same cost as Standard TECH. We find these bounds by building equal-width histograms in a pre-processing step. Correctness follows as in the case of MINT Bound.

Other TECH variants work by analogy to MINT variants. Bidirectional TECH applies forward and backward search. When we pop a pair (h, b) from Qf , we consider entries (i, b + 1) with i > h, and, if the backward search has already visited (i,B - b - 1), we check whether the cost df [(h, b)] + E(h, i) + db[(i, B - b - 1)] improves upon the current best cost µ, and likewise in backward search. The search terminates when the sum of the costs of pairs from both queues exceeds the current best cost µ. Bidirectional TECH Bound combines Bidirectional TECH with TECH Bound, with reversed lower bounds to consider sequences of the form {1, . . . h} rather than {h + 1, . . . n}. TECH-LS variants limit space needs; in place of a middle pair of states, they detect a middle bucket that splits the data series in halves. [Guha, 2005] applied such a space-saving solution on DP.

4 Experiments

We experimented 2 on a 128GB, 2×12 core Xeon E5 2680 v3 machine @2.5GHz. For Viterbi decoding, we use as baselines the edge-aware Viterbi algorithm (§3.1), its recomputationbased space-efficient variant [Ciaperoni et al., 2022], checkpoint Viterbi [Tarnas and Hughey, 1998], which segments a sequence into √T parts, and SIEVE variants [Ciaperoni et al., 2022], including SIEVE-Middlepath, Standard SIEVE (partitioning the state space), and SIEVE-Hyperloglog (using approximate counts) [Flajolet et al., 2007]. For histogram construction, the baseline is the DP algorithm of [Jagadish et al., 1998] (§ 3.2). The full version [Ciaperoni et al., 2026] details data, measures, parameters, and further experiments.

4.1 Results on Viterbi decoding

Real data, runtime vs. T and K. Figure 2 plots results on forced-alignment and standard decoding with real data. MINT achieves savings of up to three orders of magnitude over Viterbi by focusing on promising paths. Enlarging the state space via snowball samples of the HMM does not affect MINT, but heavily impacts Viterbi. MINT-LS variants also gain lower runtime than Viterbi even while controlling memory.

Real data, runtime and memory vs. T . Figure 3 plots runtime and memory usage, including SIEVE variants. As the memory footprint of MINT-LS and SIEVE variants is dynamic, we report its median across recursion levels. The memory needs of MINT-LS (using DFS) are the lowest, while those of MINT-LS+ (using EFS) remain below those of the most memory-intensive SIEVE variants. In the full version we report the corresponding maximum memory usage. Overall, MINT-LS variants require memory comparable to SIEVE variants. We show results vs. T , as subsampling the state space on real data barely affects MINT-LS, as established in Figure 2.

2 Code and data at https://github.com/maciap/CompactBestFirst.

Effect of θ on linear-space algorithms. Figure 4 presents runtimes vs. the queue size threshold θ on ranges of θ where MINT-LS may process tokens more than once (Section 3.1). MINT-LS+ never processes the same token twice. SIEVE [Ciaperoni et al., 2022], a DP-based algorithm, also ensures O(K) space, yet incurs a practical runtime overhead (not time-complexity overhead) compared to Viterbi; we compare runtime to the latter as a baseline. MINT-LS consistently performs the fastest on synthetic data with skewed path likelihood distribution, where it explores only a few paths, yet becomes inefficient for small θ with uniform path likelihood distribution, where it explores more paths. On real data with forced alignment, the runtime of MINT-LS grows modestly as θ falls; with larger decoding data, runtime grows beyond that of Viterbi. Overall, MINT-LS is preferable for large enough θ, while MINT-LS+ maintains runtime within the same order of magnitude as, and typically lower than, that of Viterbi.

Effect of T on linear-space algorithms. Figure 5 plots runtimes vs. path length T for fixed values of the queue size threshold θ small enough to challenge MINT-LS, reconfirming that it becomes inefficient as more paths are explored.

As in Figure 4, this effect is evident in synthetic data with Erd˝os-Rényi transitions and uniform path likelihood distribution and in the real decoding data. MINT-LS+ emerges as the algorithm of choice, achieving competitive runtime even while maintaining memory usage under a small θ threshold.

4.2 Results on histogram construction

Figure 6 shows the histogram construction runtime on synthetic data vs. B for input sequence length n = 1010, and that of Standard TECH and the standard V-OPT algorithm vs. n for different values of λ = Bn . Standard TECH often suffices, as its variants do not bring significant gains. Linear-space TECH incurs a manageable runtime overhead for the sake of space efficiency. All COMPACTBFS variants gain in time efficiency as B grows, delimiting the search space for each bucket. Contrariwise, standard DP cannot contain the search space, hence its runtime surges for large B. Figure 6 also shows results on real data. The gains of TECH solutions are more emphatic here, as TECH exploits data patterns that facilitate summarization, whereas standard DP lacks such capacity.

5 Conclusion

We introduced COMPACTBFS, a framework that efficiently solves fixed-length path optimization problems by best-first search, while delimiting space complexity. We crafted COMPACTBFS-based algorithms for Viterbi decoding and histogram construction. Our experiments evince COMPACTBFS to gain up to four orders of magnitude in time and space efficiency, most pronouncedly on real data with nonuniform cost distributions. In the future, we aim to apply space-saving strategies to other applications of best-first search, such as nearest-neighbor search [Papadopoulos et al., 2011]. In the full version [Ciaperoni et al., 2026], we apply COMPACTBFS to temporal-graph community search.