Adaptive lookup tables for non-linear operators
An error-driven segmentation algorithm for fixed-point lookup tables. It refines segments only where the real fixed-point error is high, guaranteeing a 2 LSB worst-case error with 12–30 tables per operator instead of a uniform 126.
On this page
The problem
On automotive NPUs, non-linear operators such as rsqrt, reciprocal, the exp inside Softmax and sigmoid run as fixed-point lookup tables, not floating-point math. A bad table can break a model that looks fine everywhere else. In one production model, the root cause of an accuracy gap was a single table's segment boundary in an rsqrt inside a normalization layer (see Layered numerical consistency).
The hardware's segmented lookup table is not a global nearest-neighbor lookup:
- Dividing points pick a segment for the input.
- Inside a segment, a fixed-point table is read and interpolated.
- Outside the valid range, linear fits on the left and right take over.
So the error comes from four things: the valid input domain, where the dividing points sit, how densely each segment is sampled, and how the left and right linear regions are handled.
Measuring error the way the chip sees it
The reference is the IR's fake-quant output: the quantized value the model was trained and validated against. The candidate is the converter's real fixed-point lookup-table output code. For every valid integer input code xi:
e(x_i) = | q_LUT(x_i) − q_FQ( f(x_i) ) | error in output LSB
E_mean = Σ_i e(x_i) / N weighted by sample count
E_max = max_i e(x_i) over all operators and codes
- Mean LSB is weighted over every valid input code of every table, not a simple average of per-operator averages.
- Max LSB exposes rare but potentially fatal local distortions, the kind that slip through aggregate metrics.
- Valid domains come from calibration:
rsqrtandreciprocaluse the IR's calibrated range; the Softmaxexpinput is never positive after the max-subtraction, so it defaults to [−12, 0] when no range is recorded.
Three strategies compared
| Strategy | Dividing points | Left/right linear regions | Tables per op | Guarantee |
|---|---|---|---|---|
| A. Original 6-table | Native per op: mostly curvature-based, some evenly spaced | Original linear fits | 6 | Baseline only; no max-error target |
| B. Uniform 126-table | Valid range split into 126 equal-width segments | Not optimized | 126 | Table count only |
| C. Adaptive (this work) | Keep the 6-table boundaries, then recursively bisect | Upgraded only when the measured gain justifies it | 12–30, chosen per op | Boundaries kept, never worse than baseline, max 2 LSB |
Curvature-based placement (A) puts more boundaries where the function bends, which beats equal spacing, but six tables are too few for near-singular functions. Uniform 126 tables (B) is simple and lowers the mean, but it ignores curvature, output scale and the real fixed-point error. On rsqrt it wastes tables on flat regions and still leaves huge errors near extreme input codes.
The adaptive algorithm
The original 6-table layout is the floor: the algorithm only adds boundaries, never moves or removes them. The feedback signal is the real fixed-point output error, not a floating-point approximation.
for each LUT operator f with valid domain D:
S ← segments from the original 6-table layout # never removed
loop:
E ← real fixed-point error of f over every code in D, per segment
if max(E) ≤ 2 LSB: break
s* ← segment with the largest error
split s* at its midpoint # nested refinement
if a left/right linear region dominates the error:
upgrade that region only if the measured gain justifies it
if table budget exhausted and max(E) > 2 LSB:
fail hard and report the operator # never ship silently
round the table count up to a multiple of 6 # export constraint
Because new boundaries are midpoints of existing segments, the refinement is nested. Every original boundary survives, so the result can never be worse than the baseline on any segment. Most operators settle at 12, 18, 24 or 30 tables.
Try it in your browser
- Tables
- –
- Max error
- –
- Mean error
- –
- Verdict
- –
This is a simplified simulation running in your browser (12-bit output, linear interpolation per segment, 1,024 input codes). It only illustrates the mechanism: the same table budget does more where the error is than spread evenly. The numbers differ from the production converter; production results are in the table below.
Results
Evaluated on four production graphs of a temporal tracking model, each with 150 lookup-table modules (600 in total):
| Strategy | Weighted mean error | Worst-case error | Tables per operator |
|---|---|---|---|
| Uniform 126-table | 0.270 LSB | 11,381 LSB | 126 |
| Adaptive | 0.217 LSB | 2 LSB | 12–30 (avg 18.6) |
Lessons
- Measure what the hardware computes. Floating-point approximations of a table hide exactly the errors that matter.
- Bound the worst case, not just the mean. One bad input code can decide a corner case on the road.
- Refine where the error is. A budget spent by curvature and measured error beats a bigger uniform budget.
- Fail loudly. An operator that cannot meet the bound should stop the export, not ship.