Fast and Space-Efficient Fixed-Length Path Optimization

First, I agree with the reviewer's rating, and I believe the paper falls below the acceptance threshold. Second, I want to address several disagreements.

• The paper should be evaluated based on the main content. Supplementary can assist us to improve understanding but shouldn't be a factor of strengths.
• Regarding weakness, I disagree with the reviewer's opinion. I don't think the authors need a formal discussion of runtime and space bounds. First, considering the context, these are fairly trivial, don't warrant a theorem or proposition. Second, the authors briefly discuss complexity in the main paper, which, I believe, is already sufficient. Additionally, the paper includes experiments demonstrating practical improvements in runtime and space, so theoretical analysis is less relevant given they didn't claim contributions on this aspect. The authors care more about the algorithmic design and practical improvements.
• I also disagree with the reviewer on the dataset critique. In the main paper, they did give discussions on real data, please refer to p.9-p.10.

The authors frequently emphasize the uniqueness of the work is from a novel combination of strategies (bfs, dfs, d&c ...), and provide experiments showing the due improvement. My concerns are: 1) Why is the combination important? Perhaps no one has done the similar before, but the combination doesn't appear particularly technical. 2) What do the reported improvements signify? Are the baselines the latest exact solvers for the two problems? Because, it seems the authors use most of the efforts to make the comparison under their framework with minor variations. (standard MINT, MINT Bound, Bidirectional MINT...)

To be honest, I can only evaluate the technical aspect, specifically, I am confident at the algorithm design aspect and the complexity aspect. I understand their approach. But it doesn't mean I am confident in their application aspect, or if their algorithm design is genuinely significant for fixed-length path optimization problems. I am not familiar with the state-of-the-art exact solvers for Viterbi Decoding or histogram construction. So maybe we should suggest ACs to re-evaluate the experimental results.

Please note that all my comments are intended to improve the review quality. I would be happy to raise my rate if I am proven wrong.

Thank you for your elaborate review.

The paper does not contain a good formal discussion of the running time and space bounds Can you state clearly the running time and space complexity of each of your variants of the algorithm?

For a discussion of the running time and space bounds, see Lines 167-184.

nor theoretical explanation for the good performance on realistic instances. What kind of theoretical analysis do you think can help explain the claimed good practical performace on realistic instances?

The good performance arises due to the nature of real-world problems, as discussed in Lines 469-472, 485-486, 527-529, and 536-538. In real data paths costs follow a skewed distribution, hence the best-first search explores promising paths in higher priority and quickly terminates to the optimal solution.

The main experimental results are for synthetic random graphs

We do offer more space to results on real graphs (Figures 3 and 4) than on synthetic graphs (Figure 2).

only compare the new algorithms to vanilla Viterbi, and not, say, to SIEVE variants (Ciaperoni et al.).

We do compare to SIEVE in Figure 4. We omitted a runtime comparison to SIEVE in Figures 2 and 3, given that SIEVE has higher runtime than Vanilla Viterbi, as Figure 4 shows.

Dear Reviewer HujK,

We would like to express our sympathy with you over being attacked by another reviewer over the content of your review.

As you may read in the same forum, we have engaged in a long discussion with the reviewer who attacked you, which revealed a lack of awareness of basic mathematical facts on behalf of this reviewer, such as how an exponential function appears on a logarithmic plot. In the course of this discussion, this reviewer repeatedly claimed that our work to lack technical meaningfulness and important references. When asked to clarify their claims with arguments and references on both accounts, they simply refrained from doing so and shifted the focus of the discussion to another trolling attempt.

Overall, we are quite astonished by the lack of professionalism, frivolous attitude, and mathematical incompetence exhibited by this reviewer, which we have not encountered previously in the process of reviewing. We would therefore like to simply express our sympathy with you over being attacked over the content of your review.

Sincerely, The authors

Thank you for the time invested for your thorough review.

(l.345) ... and produce all its derivatives on demand via a DFS traversal ... : What is "derivative"? And, what "on demand" means?

The derivatives of a token are the tokens generated from it in subsequence time steps. On demad means that we generate those tokens upon request, before their turn to be generated by the regular best-first search procedure arrives.

(l.348) ... The paths DFS explores identify and pass on middle pairs as usual ... : What is "middle pairs"? Is it the same with "middle frame"?

Yes, a middle pair is a pair of nodes connected by a middle edge at the middle frame of the solution path.

(l.349) By virtue of this DFS operation, ... : What is the "virtue" of DFS?

"By virtue of" is an English expression that means because or as a result of.

describe either a step-by-step explanation or pseudocodes for these procedures.

Depth-first search (DFS) works as usual; at a node $v$, it visits (i.e., produces a token for) a child node of $v$ and, recursively, its descendants; after it has processed this branch, it moves on to the next child of $v$. Each branch terminates when it either reaches the last frame or injects a token into the token set of a state $s_{j'}$ with the same time step as a pre-existing (i.e., already discovered) token in that set, as Lines 346-348 describe. As the operation of DFS is classic textbook material, we refrained from offering a pseudocode. A classic pseudocode is as follows:

DFS($G$, $v$) for each child $w$ of $v$: if $w$ not discovered DFS(G, $w$)

the details of the algorithm are ... not given for the Isabella framework

Please note that the details of the algorithm are given for the Isabella framework in Lines 167-184.

"Standard MINT", "Bidirectional MINT", "MINT Bound", and "MINT-LS" are derived, afterwards "Standard TECH" are derived, and then TECH variants are derived by analogy to MINT variants. Thus, I suspect that we cannot derive these variants for the other problems sharing the components (items 1--7).

We can indeed derive such variants for other problems sharing the components, exactly by analogy to MINT variants. We present specific variants to show the particulars of an application problem.

I recommend that, if possible, the step-by-step explanations based on the Isabella framework is given first, and then the algorithms for specific algorithm are derived by substituting the components (items 1--7).

This is exactly the presentation order the paper follows. First, it gives the step-by-step explanation based on the Isabella framework, in Lines 167-184, and then derives the algorithms for specific problems by substituting the components in Sections 3.2 and 3.4.

what are the triangle marks associated with a fraction in the second and fourth plots.

The triangle marks define the markers in the plot; as the text defines in Lines 523-524, the fractions are values of $\lambda = \frac Bn$, i.e., ratios of the number of buckets to sequece length.

The above comment is based on my understanding that the common procedure can be described on the Isabella framework like, e.g., "Standard Isabella", "Bidirectional Isabella", "Isabella Bound", and "Isabella-LS". Is this true?

Yes, your understanding is correct.

What is the filled area in the right part of Figure 4?

As the caption of Figure 4 defines, the shaded regions indicate the range of memory consumed over recursive calls.

the depth-first-search strategy performs more than just performing DFS.

DFS indeed performs DFS as usual in the space of tokens. We have updated the paper and included in a pseudocode for the divide-and-conquer and DFS procedures in Algorithms 4 and 5, Appendix E, discussed in Lines 351-360 in Section 3.3.

descriptions for other variants, namely "Isabella Bound", "Bidirectional Isabella", and "Isabella-LS", are not generally shown.

"Bidirectional Isabella" and "Isabella-LS" are indeed described upon their first apperance in the context of MINT, yet there is nothing specific to MINT in that description. The same description applies to other cases; we will include them in the general framework. On the other hand, the description of "Isabella Bound" depends on the particular problem examined, as bounds are problem-aware. We offer specific derivations of bounds for the two problems we study.

Thank you for the time invested in this thorough review.

for the BestFS, the authors replace the BreathFS component from the work Young et al., the bidirectional idea can be traced back to Pohl, the divide-and-conquer application in Viterbi decoding is originated from Ciaperoni et al.

Yes, these fragments of ideas have existed previously, yet none of the above has applied depth-first search to keep the size of the priority queue in check, and none of them has used these ideas in combination.

why is the combination important to the field, unique and innovative?

This combination is important to the field because it succeeds to fruitfully apply best-first search to this classic type of problem and retain the memory consumption of the priority queue in check, reaping benefits in time- and space-efficiency; it is unique because such a combination has not been tried in previous work; it is innovative because it is not obvious a priori.

Is there any particular reason to bring up Semirings and Dioids?

Yes, we bring up semirings and dioids to properly define the type of problems we study in all generality; without these concepts, we would have to write continuous reminders that "multiplication could be used in place of addition" in many equations, and the generality of the framework would have been blurred.

For standard MINT, is there any "major" difference with Dijkstra? Except 1) the cost function for path, 2) fixed length.

Yes, there is a major difference from Dijkstra. As we explain in the introduction, a direct application of Dijkstra to find an optimal-cost path of a predetermined length would raise additional space requirements for (i) tabulating the optimal cost per state and step to enable backtracking of the optimal sequence and (ii) maintaining a correspondingly larger priority queue. Standard MINT ameliorates these requirements with (i) a depth-first search strategy that prevents the priority queue from overextending and (ii) a divide-and-conquer provision that omits tabulating all subproblem solutions.

MINT -- Is this an abbrev. that has been formally defined?

The name stands for Time Efficient Viterbi; we apologize for the omission.

avoid mixing math expressions with normal text?

Thank you for pointing that out. We will eliminate italics from pseudocodes.

in Alg. 3, the if conditions should use some line breaks to trim the extra lengths.

The if statements use less length than the page provided by the single-column ICLR template, without any extra length.

Fig.2: y-axis is not showing the full range.

The axis shows the full range of values indeed.

Fig.2: the last semicolon, what does it mean by "axes in log scale"? Does it mean that both x and y axes are log scaled? How do the authors apply the log-scale to the axes?

Yes, the phrase "axes in log scale" means that both axes are in logarithmic scale. We bring the axes to such scale using the appropriate commands in a plot-drawing package.

In the definition of "MINT Bound" (the end of p.5), what does "til" mean? I guess it's the abbrev. of "till", right?

Yes, "til" is an English preposition, variant of "till" in the dictionary.

Sec. 3.4: "V-optimal (V for variance)" should be explained at the first appearance.

The explanation is in the parenthesis: these histograms are called "V-optimal" because they optimize variance; the letter 'V' stands for 'variance'.

Thank you for your engagement in discussion and thoughtful response.

it is not novel in the use of "DFS to prevent the PQ from being overly extended". Similar ideas have been widely utilized in all aspects of the algorithmic design, especially branch & bond algorithms, and have been widely applied to various problems, including path optimization problems.

Please kindly provide the references to those other works using DFS to prevent the PQ from being overly extended in path optimization problems.

It reminds me the iterative deepening depth-first search Korf, Richard (1985) as well. I feel the proposed method is somewhat similar to this one. (generally speaking, not similar in all details)

In fact, the proposed method does not perform depth-first iterative deepening (DFID) [Korf 1985], and its orientation is quite the opposite: DFID performs depth-first search to depth $i$ in iterations, discarding previously generated nodes and increasing $i$ in each iteration. By contrast, our solution performs selective DFS on demand without a depth constraint. To our knowledge, this type of solution has not appeared in previous work.

To explain the idea of the proposed framework, especially just the DP component, using well-established, plain DP terminology is more than sufficient to realize the presentation goal. Just like Ciaperoni et al. (2022).

Yes, that is definitely sufficient when introducing a solution to a single problem, as in [Ciaperoni et al. 2022]. As our paper introduces a solution applicable to several problems, we found the terminology of semirings and diodes necessary for the sake of generality.

list out few more state-of-the-art work in this specific direction. If all have been cited in the paper, please let me know as well.

Yes, all works we know of in this specific direction have been cited in the paper.

Thank you for the detailed response.

I don't think the authors answer my question directly on "the majority of the space reduction is contributed by D&C or by the claimed novelty -- DFS for PQ?".

This question stems from the false assumptions that (i) DFS for PQ adds to the space reduction achieved by D&C and (ii) the two can be treated independently. As we replied, the DFS for PQ serves to transfer, i.e., enable, the space reduction achieved in [Ciaperoni et al. 2002] on the optimization method we introduce.

I think the reason the algorithm is practically fast stems from the use of BestFS (prune many states), and D&C (reduce tabulations) contributes much as well.

No, D&C does not contribute to time-efficiency. On the contrary, it incurs a small time overhead as it recursively repeats work that was already done, for the sake of space-efficiency.

But the "DFS for PQ" part would contribute very less. Do we agree on this?

We can neither agree nor disagree, since the premise that DFS contributes in an additive manner to space reduction is false.

the proposed method has complexity $O(nL (n + \log{L}))$ on Viterbi decoding, right? But this isn't better than the vanilla DP in the worst case, right?

It is the same as Vanilla DP in any realistic worst-case scenario, where $L << 2^n$, and better than Vanilla DP in practice.

In Fig.2, the authors show 100x improvements in runtime for path length less than 5, the improvement quickly reduces to 0 when path length is around 12.

It reduces to 0 when the path length is around 30 on these synthetic data.

In Fig.4 ... the improvements are about from 1s(100s) to around 0.01s(1s) with a reducing leading margin. ... Based on Fig.3 (Right), the leading margin reduces as the path length reaches 100.

The leading margin is increasing; please note the y-axes are logarithmic in both cases.

using the SIEVE datasets for benchmarking, is not very sounding, since the time efficiency is the priority of SIEVE.

These datasets are standard speech recognition benchmarks that have nothing to do with the aims of SIEVE.

SIEVE and its variants exhibit no clear improvements in runtime when compared to the baseline "Vanilla Viterbi". ... Why did the authors exclude SIEVE as one of the baselines in the Fig.2 and 3 experiments?

The first question provides the answer to the second: we did so because SIEVE has higher runtime than Vanilla Viterbi, hence does not serve as a proper baseline for time efficiency.

is it safe to say that the baseline used in the authors' paper is somewhat weak?

No, that is not safe to say, because we do not use SIEVE as a baseline for time efficiency.

should we also consider comparing with MILP solution to Viterbi Decoding?

We are not aware of any work applying Mixed-Integer Linear Programming for Viterbi decoding; that would be an overkill, as the problem is solved well by dynamic programming and thus does not call for a more complicated solution.

they should compare with works designed exclusively for time-efficient improvements.

Please specify which works you refer to; we are not aware of any work advancing the time efficiency of Viterbi decoding.

What results might emerge if the path length extends to 760 for "standard decoding" dataset?

The advantage remains, as in Figure 4; we expand the path length in Figure 4 to present a more exhaustive comparison in this figure that includes both runtime and memory.

Line 751-752, does the worst-case imply that $T$ is close to $K$? Or the probability of the paths are uniformly distribution?

The examined parameter $\alpha$ determines, eventually, the distribution of transition and emission probabilities, as explained in Lines 702-707.

To me, if $T$ gets large enough, the likelihoods of all paths converge to a similar level, right?

Not necessarily. Path likelihoods may differ arbitrarily even with very large $T$.

Please enlighten me what's the worst-case to Viterbi decoding?

The worst case for Viterbi decoding is that all edges have the same transition probability and all {state, observation} pairs the same emission probability; then all paths are equally likely, so there is nothing to choose between them.

The authors state they use snowball sampling for real data. So, do they input the sampled HMM graphs to the Viterbi baseline? Or do they input the original graphs to Viterbi baseline?

As explained in Lines 735-736, we use snowball sampling to sample subsets of the original HMM graph, hence vary the number of states $K$.

snowball sampling is the one in graph sampling, right?

Yes.

To me, a hard case for Viterbi decoding might arise when T gets close to K.

A $T$ close to $K$ is unrealistic in real-world decoding tasks, while a path of such length may not even exist in a directed HMM graph.

In general, T/K is around 1/100 or 1/1000. Does this ratio matter to the practical performance as well?

This ratio does not affect performance; it only makes the setting realistic.

Thank you for providing a live example of shifting the target, which we pointed out previously. While the discussion was about whether a gap is being reduced in a figure, as soon as we established that the gap is not reduced in the figure, the target shifts to an argument about slopes. However, the mathematical assumptions underpinning this new argument are false.

In Fig.3 (Left, runtime), VV is linearly increasing in the log-scaled graph, meaning it is exponentially increasing.

No, a linear growth in log-scaled axes does not imply an exponential growth in real values; it only implies a polynomial growth in real values. A polynomial function $y = x^n$ appears as a linear function $\log_b{y} = \log_b{x^n} = n \log_b{x}$ on logarithmic axes and vice versa, as in the present case. On the other hand, an exponential function $y = α^x$ appears also as an exponential function $\log_b{y} = \log_b{α^x} = \log_b{α} \cdot b^{\log_b{x}}$ on logarithmic axes.

Anyway, we understand that the core concern is that the runtime of our solution may reach the runtime of Viterbi at very large path lengths. However, at such great path lengths, our solution has a remarkable and continuously growing advantage of space efficiency vis-à-vis Viterbi, therefore it is again preferable. Figure 4 illustrates this space efficiency advantage. The title of this work is "Fast and Space-Efficient Fixed-Length Path Optimization" exactly because it combines time-efficiency and space-efficiency as no previous work has done.

On Fig.3

Regarding the interpretation for Fig.3 (Right), my point is clear. The quoted sentence might lack precision, but it's not central to my argument. Yes, the actual growth can be polynomial; the curve appears "exponential", likely because the diagram only shows the initial phase of the complete curves. To put it simply: the trends of $x^n$ and $n^x$ can appear similar, especially when $x$ is small. And that's why I'd like to see $PL>100$.

$**My core argument is: MINT(s) runtime could surpass that of VV**$ when $PL>100$. I believe my previous math assumptions are sound. At this point, on this particular problem, I think things are clear enough. I defend my judgement. And we can wait for the ACs' assessment.

On the comparison in experiment sectiob

In the previous exchange, the authors mentioned: "...we claim and demonstrate an improvement on time efficiency over...". In the latest response, the authors mentioned: "...our solution has a remarkable and continuously growing advantage of space efficiency vis-à-vis Viterbi...".

In my opinion, the comparison in experiment section still has much space to improve. Without the rebuttal, it would be hard to discern when the authors prioritize "time advantages" and when they focus on "space advantages."

"...Figure 4 illustrates this space efficiency advantage..."

I have no issues with the space part in Fig.4. My concerns are on Fig.2 and Fig.3. These are completely different experiments, and I have expressed very different concerns.

Conclusion

Thanks for the authors invested time and efforts during the rebuttal.

Regarding the accusation of "shifting target", I firmly believe my questions are coherent, concise and clear. And I fully refuse the accusation. The rebuttal is to raise, discuss and address the concerns of the paper. Any discussion unrelated to the paper's content is a waste of time, including this paragraph in this response.

Although I hold my opinions about the accusations, including "shifting target" and etc, I have refrained from including those irrelevant arguments in my rebuttal. I suggest the authors set aside judgements about the manner of how I rebuttal, as such remarks do not contribute to the evaluations on this paper.

If the authors believe my review lacks professionalism, they are welcome to escalate this matter to the PCs, ACs and SACs. I am eager to hear ACs' evaluations of this paper, and see if they approve the "shifting target" blame. I have no further questions for now, and stand by my initial assessment. And I will respect ACs' decision.

Thank you for sharing your belief that a straight line can have a similar trend as an exponential curve.

I provide another closer example to the authors to better deliver what I mean. They are not use to fully replicate Fig.3, but can be used to express the overall concerns.

https://www.desmos.com/calculator/qwdki60vve

(Redacted by PCs)

Also, I would like to take this chance and have a professional discussion with the reviewer regarding the stated review opinions.

My first question is: what do you see as the novelty of the proposed method, given that you rated both Soundness and Contribution as 3?

Thank you for the concise review. The novelty of this work lies in fruitfully applying best-first search (BestFS) to a classic type of problem and devising additional algorithmic contributions to retain low space consumption while maintaining a BestFS heap. The components we use are in themselves classic, yet their combination to achieve the results we present is novel.