Range as first-class is the right priority. Pattern that works: keep ranges as single AST nodes (one dep edge per range, not N), then use interval trees on the reverse side so a cell change at C5 becomes "find intervals covering (C, 5)" instead of scanning all formulas. Pairs well with column-oriented storage if you go there

On the AST caching point, worth caching by structural hash of the parsed expression, not the source string. Copy paste with relative references produces different strings but identical AST shape, which hits a lot in financial-model-style workbooks where parallel columns share structure

Also worth a look: the "сalculation chain" docs in Microsot's OOXML SpreadsheetML spec describe how they serialize the dep order in xlsx files. Different problem (persistence vs runtime) but the data model is informative for what level of granularity ends up being practical