What am I doing wrong using FindIntegerNullVector?

A solution is give the built-in the right amout of toleranz with a constant in another dimension:

FindIntegerNullVector[{a b, c d, 10^-14}, 10]

{1, -1, -3}

A particular solution

This seems to work on the case at hand:

FindIntegerNullVector[SetPrecision[{a b, c d}, 15] 10]

(*  {1, -1}  *)

But why the precision 15? The problem is to find, for real numbers $A$ and $B$, integers $x$ and $y$ such that $$Ax+By=0 ,.tag{1}$$ Suppose $A^*,,B^*$ are floating-point approximations of $A,B$ resp. Then the problem is to find an integer point $(x^*,y^*)$ such that the line in the real $xy$-plane given by equation (1) passes "close enough" to $(x^*,y^*)$, where close enough depends on the error of the approximations $A^*,,B^*$. FindIntegerNullVector does this with some notion of "close enough" depending on the precision of the input.

A general approach

Below is an adaptation fINS of an example in the documentation for LatticeReduce to solve the FindIntegerNullVector problem that diminishes the precision until we get a solution with a relatively small error (rough 1 ulp at the current precision). In the couple of tests in which there is an integer null relation, it tends to overestimate the reduction in precision needed (pick a precision that is lower than necessary). In the one totally random example, it did the reverse. Consequently, fINS only approximates the precision needed for FindIntegerNullVector to reproduce the result of LatticeReduce/fINS.

fINS[z_?VectorQ] := Module[{a, b, err},
  a = IdentityMatrix[Length[z]];
  b = {{2, 2, 2}}; (* dummy values: fails While test *)
  err = 1;
  While[Abs[b[[1, -1]]] > 1, 
   b = PadRight[a, {Automatic, Length@z + 1}, 
     List /@ Round[-10^Precision[z]/err*z]]; (* scale the FP vec z and round *)
                                             (* which simulates FP round-off *)
                                             (* in integers *)
   b = LatticeReduce[b];
   If[b[[1, -1]] != 0, err *= b[[1, -1]]];
   ];
  {b[[1, ;; -2]], 10.^-Precision[z] * err}
  ];

OP's example.

Note fINS returns the null sequence and the estimate of the error tolerance needed.

{sol, tol} = fINS[{a b, c d}]

(*  {{-1, 1}, 2.84217*10^-14}  *)

Map the tolerance to Precision:

reltol = Abs@tol/Max@Abs@{a b, c d};
prec = -Log10[reltol]

(*  15.2066  *)

FindIntegerNullVector[SetPrecision[{a b, c d}, prec], 10]

(*  {1, -1}  *)

We can increase the precision a little; too much, and FindIntegerNullVector fails:

prec = -Log10[reltol/2];
FindIntegerNullVector[SetPrecision[{a b, c d}, prec], 10]
prec = -Log10[reltol/5];
FindIntegerNullVector[SetPrecision[{a b, c d}, prec], 10]

(*  {1, -1}  *)

FindIntegerNullVector::norel: There is no integer null vector for {45.73414164516444,45.73414164516441} with norm less than or equal to 10.

(*  FindIntegerNullVector[{45.73414164516444, 45.73414164516441}, 10]  *)

Second example, the LatticeReduce example perturbed by noise.

First, the exact problem:

FindIntegerNullVector[{Cos[4], Cos[1]^4, Cos[1]^2, 1}]

(*  {1, -8, 8, -1}  *)

The perturbed problem: a tolerance of around 10^-14 or precision of around 14 should be needed.

SeedRandom[1];
coeffs = N@{Cos[4], Cos[1]^4, Cos[1]^2, 1} + RandomReal[10^-14, 4];
{sol, tol} = fINS[coeffs]
reltol = Abs@tol/Max@Abs@coeffs;
prec = -Log10[reltol];

(*  {{-1, 8, -8, 1}, 6.15064*10^-13}  *)

FindIntegerNullVector[SetPrecision[coeffs, prec]]
FindIntegerNullVector[coeffs]

(*
  {1, -8, 8, -1}
  {78257927, -626063069, 626063140, -78257876}
*)

In this case the precision can be raised more:

prec = -Log10[reltol/10];
FindIntegerNullVector[SetPrecision[coeffs, prec]]
prec = -Log10[reltol/50];
FindIntegerNullVector[SetPrecision[coeffs, prec]]

(*
  {1, -8, 8, -1}
  {-36655, -42915, 67969, -40144}
*)

Third example, a random vector.

No relationship is expected but FindIntegerNullVector finds one with large norm. The precision in this particular case needs to be lowered to get FindIntegerNullVector to return the same result as fINS

SeedRandom[0];
coeffs = RandomReal[1, 4];
{sol, tol} = fINS[coeffs]
reltol = Abs@tol/Max@Abs@coeffs;
prec = -Log10[reltol ];
FindIntegerNullVector[SetPrecision[coeffs, prec]]
FindIntegerNullVector[coeffs]

(*
  {{6, -6, -1, 1}, 0.0000326167}  <-- prec ~ 4.3
  {-12, 7, 0, 6}
  {-18811, -20158, 21650, 18102}
*)

To get the smaller norm solution, we need to lower the precision:

Norm /@ N@{{-6, 6, 1, -1}, {-12, 7, 0, 6}}

(*  {8.60233, 15.1327}  *)

FindIntegerNullVector[SetPrecision[coeffs, prec], 12]
FindIntegerNullVector[SetPrecision[coeffs, prec - 0.3], 12]

FindIntegerNullVector::rnf: FindIntegerNullVector has not found an integer null vector for {0.6525,0.6331,0.6828,0.5664} with norm less than or equal to 12.

(*  FindIntegerNullVector[{0.6525, 0.6331, 0.6828, 0.5664}, 12]  *)

(*  {-6, 6, 1, -1}  *)