Jump Like A Squirrel: Optimized Execution Step Order for Anytime Random Forest Inference

This paper proposes optimizing anytime random forest inference on resource-constrained systems by reordering execution at the granularity of individual tree steps, introducing heuristics like the Backward Squirrel Order that achieve near-optimal accuracy with polynomial runtime.

The Gist

Imagine you are trying to guess the flavor of a mystery smoothie. You have a team of 100 expert tasters (a Random Forest). Usually, to get the final answer, you force every single taster to take a sip, chew, swallow, and write down their full opinion before you combine their votes.

But what if you only have 5 seconds before the smoothie melts? Or what if the power goes out mid-sip?

In the old way, if you stopped halfway, you'd have zero information because no one finished their "sip." You'd have to guess blindly.

This paper introduces a new way to run these teams of tasters, called "Jump Like A Squirrel." Here is the simple breakdown:

1. The Problem: The "All or Nothing" Trap

Traditionally, decision trees (the logic behind these tasters) work like a game of "20 Questions." You ask a question, get an answer, and move to the next question. You only know the final answer when you reach the very last question (the "leaf" of the tree).

If you are in a rush (like on a battery-powered device or a self-driving car), you might not have time to ask all 20 questions. The old method says, "If you stop at question 10, throw away the whole thing and guess randomly." That's a waste of the 10 questions you did ask!

2. The Solution: The "Squirrel" Strategy

The authors realized that even after just a few questions, you already have a pretty good idea of the answer.

• The Old Way: Finish one whole tree (ask all 20 questions), then move to the next taster.
• The New Way: Ask question #1 of Taster A, then question #1 of Taster B, then question #2 of Taster A. You can jump between tasters at any moment.

If the power cuts out after 15 jumps, you take the current "best guess" from all the partial answers you have so far. You never lose the progress you made.

3. The Big Challenge: Which Jump Comes Next?

Now that you can jump between trees, you have a massive choice: Which tree should you jump to next?

• Do you jump to the tree that is easiest to solve?
• Do you jump to the tree that is most likely to be right?
• Do you jump to the tree that gives you the most new information right now?

If you jump randomly, you might waste time on a tree that doesn't help much. If you jump smartly, you get the most accurate answer possible in the shortest time.

4. The Three "Jump Plans"

The paper proposes three ways to decide the order of jumps:

• The "Perfect Planner" (Optimal Order): This is like a super-computer that simulates every single possible path you could take to see which one gives the best average result.

  • Pros: It's perfect.
  • Cons: It takes forever to calculate the plan. If you have a big forest, it would take longer to plan the jumps than to actually drink the smoothie.

• The "Forward Squirrel" (Forward Squirrel Order): This is a greedy approach. It looks at the current moment and asks, "Which single jump right now gives me the biggest boost in accuracy?" It jumps there, then asks the same question again.

  • Analogy: It's like a squirrel running forward, always picking the nut that looks biggest right now.

• The "Backward Squirrel" (Backward Squirrel Order): This is the paper's star player. Instead of starting at the beginning and guessing forward, it starts at the end (where all trees are finished) and works backward. It asks, "If I had to stop one step early, which step should I have skipped to keep the accuracy highest?"

  • Analogy: Imagine a squirrel looking at the whole pile of nuts and working backward to figure out the most efficient path to gather them.
  • Result: This method is incredibly fast to calculate and performs almost as well as the "Perfect Planner" (94% as good) but beats all other random or intuitive methods by a huge margin (99% better).

5. Why This Matters

This isn't just about smoothies. This is about resource-constrained systems:

• Self-driving cars: They need to make decisions in milliseconds. If the computer is busy, it can stop the calculation early and still have a safe, high-confidence answer.
• Medical devices: A heart monitor might need to classify a heartbeat instantly. If the battery is low, it can stop early and still give a reliable diagnosis.
• Smartphones: Apps can run complex AI without draining your battery, because they can stop the "thinking" process the moment they are confident enough.

The Bottom Line

The paper teaches us how to turn a rigid, "finish the whole job or nothing" AI into a flexible, "give me the best answer you can in the time I have" AI. By using the Backward Squirrel method, we can organize the thinking process so that every single second of computing time counts, ensuring we get the most accurate result possible, even if we are interrupted.

Technical Summary

1. Problem Statement

Decision trees and Random Forests (RF) are widely used for classification on resource-constrained systems due to their efficiency and small size. However, in real-time or embedded environments, the available execution time for inference may be insufficient to complete the full traversal of all trees in a forest.

Existing "anytime" approaches for Random Forests operate on the granularity of whole trees. They execute trees sequentially and stop after a certain number of trees are completed. This approach has two major limitations:

1. Information Loss: If execution is halted while a tree is being traversed, all information gathered within that partially executed tree is discarded.
2. Suboptimal Accuracy: Since prediction confidence in decision trees increases with every step (node evaluation), stopping mid-tree wastes potential accuracy gains.

The paper addresses the need for an anytime algorithm that operates on the granularity of single steps (node evaluations) within trees. The goal is to determine an optimal step order (the sequence in which nodes across different trees are evaluated) that maximizes the mean accuracy across all possible stopping points, assuming a uniform probability of execution abortion at any step.

2. Methodology

A. Anytime Execution at the Node Level

The authors extend standard Random Forest implementations to retain prediction vectors at inner nodes, not just leaf nodes.

• Mechanism: During training (using CART), every node is associated with a sub-dataset. The empirical probability vector of classes in this sub-dataset is stored at the node.
• Inference: At any point during execution, the system can aggregate the probability vectors of the currently visited nodes across all trees to generate a valid prediction. This allows the algorithm to be aborted at any step without losing accumulated information.

B. Step Order Optimization

The core challenge is finding the sequence of steps through the forest that maximizes the average accuracy.

• Search Space: The number of distinct step orders is combinatorially large ($\frac{(d \cdot t)!}{d!^t}$, where $d$ is max depth and $t$ is the number of trees).
• Graph Formulation: The problem is modeled as a weighted Directed Acyclic Graph (DAG).
  • Vertices: Represent the state of the forest (number of steps taken in each tree).
  • Edges: Represent taking one additional step in a specific tree.
  • Weights: The inaccuracy (1 - accuracy) of the resulting state, calculated on an "ordering set" ($S_o$).
• Objective: Find the path from the initial state (0 steps) to the final state (all steps) that minimizes the sum of inaccuracies (maximizing mean accuracy).

C. Proposed Algorithms

The paper proposes three methods to generate step orders:

1. Optimal Order:

   • Uses Dijkstra's algorithm on the constructed DAG to find the path with the minimum cumulative inaccuracy.
   • Complexity: Guarantees the maximal mean accuracy but has exponential complexity relative to forest size, making it infeasible for large forests.

2. Forward Squirrel Order (Heuristic):

   • A greedy approach starting from the initial state (0 steps).
   • At each step, it evaluates all possible next states (taking one step in any tree) and selects the one that yields the highest immediate accuracy.
   • Complexity: Polynomial time $O(d \cdot t^2)$.

3. Backward Squirrel Order (Heuristic):

   • A greedy approach starting from the final state (all steps completed) and working backward to the initial state.
   • At each step, it determines which step to "remove" (i.e., which step was the last one taken) such that the remaining state has the highest accuracy.
   • Complexity: Polynomial time $O(d \cdot t^2)$.

D. Implementation

The authors implemented this using native tree representations (arrays with index tracking) rather than if-else code structures.

• State Management: An index array tracks the current node in each tree.
• Execution Loop: The inference engine iterates through the pre-computed step order, advancing one tree per step.
• Abort Handling: Upon interruption, the system uses the index array to fetch the stored probability vectors of the current nodes and computes the final prediction immediately.

3. Key Contributions

1. Granularity Shift: Successfully adapted Random Forests to operate as anytime algorithms on the granularity of single steps rather than whole trees, preserving intermediate prediction confidence.
2. Optimization Framework: Defined the problem of finding an optimal step order to maximize mean accuracy and provided a graph-theoretic solution (Optimal Order).
3. Heuristic Algorithms: Introduced the Squirrel Order (Forward and Backward variants), which provides near-optimal accuracy with polynomial runtime, making it practical for large-scale forests.
4. Implementation & Evaluation: Demonstrated a feasible technical implementation and validated the approach across 9 diverse datasets (UCI repository) on both high-performance (AMD EPYC) and embedded (ESP32) hardware.

4. Results

The evaluation was conducted on 9 datasets (e.g., Adult, Covertype, MNIST) with varying numbers of trees and depths.

• Accuracy vs. Steps: Random Forests exhibit a strong correlation between the number of steps taken and prediction accuracy. Accuracy increases monotonically with steps, validating the anytime approach.
• Performance of Squirrel Orders:
  • The Backward Squirrel Order performed exceptionally well, achieving ~94% of the Normalized Mean Accuracy (NMA) of the Optimal Order.
  • It outperformed all other intuitive strategies (Depth Order, Breadth Order, Prune Order, QWYC) and the Forward Squirrel Order.
  • In experiments excluding the Optimal Order (due to size constraints), the Backward Squirrel Order achieved ~99% of the best possible NMA.
• Runtime Efficiency:
  • The Optimal Order became computationally infeasible (exponential time/memory) with more than 8 trees.
  • The Backward Squirrel Order maintained polynomial runtime, capable of generating orders for forests with 20+ trees and deep depths in seconds.
• Dataset Characteristics:
  • Binary classification datasets showed smaller performance gaps between different step orders.
  • Multi-class classification datasets benefited significantly more from Depth Order variants (and the Squirrel Orders) compared to Breadth Order, as deeper traversal is required to distinguish between multiple classes.

5. Significance

This paper fundamentally changes how Random Forests can be deployed in time-constrained environments:

• Resource Efficiency: It eliminates the "all-or-nothing" nature of tree execution, allowing systems to return high-confidence predictions even when time is cut short mid-traversal.
• Practicality: By proving that a polynomial-time heuristic (Backward Squirrel Order) can approximate the theoretical optimum, the authors make anytime Random Forests viable for real-world embedded systems and edge computing.
• Design Space: It opens a new design space for optimizing inference not just by pruning trees, but by optimizing the execution path through the forest, ensuring that every millisecond of computation yields the maximum possible predictive value.